k-means 算法是一个常见的聚类算法,其基本思路如下:

  1. 选取样本中给定数量的 k 个样本作为初始簇中心,遍历样本分别对每个聚类中心计算距离,将样本分配至距离最近的簇中。

  2. 更新每个簇中心为簇中全部样本的均值。

  3. 使用新的簇中心重新分配全部样本。

  4. 重复 2、3 步,直至簇不再发生变化。

以下是在上一篇文章所述的 e-hentai 数据集上实现的 k-means 算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import time
import pickle
import random
import math
from collections import Counter

#计算两部作品 tag 向量间的夹角余弦值
def calc(book1, book2):
cos = 0
book1 = book1["tags"]
book2 = book2["tags"]
same_tag = set(book1) & set(book2)
if (math.sqrt(len(book1)) * math.sqrt(len(book2))) != 0:
dotproduct = 0
vector1 = 0
vector2 = 0
for tag in same_tag:
dotproduct += book1[tag] * book2[tag]
for tag in book1:
vector1 += math.pow(book1[tag],2)
for tag in book2:
vector2 += math.pow(book2[tag],2)
cos = dotproduct/math.sqrt(vector1*vector2)
else:
cos = 0
return cos

#kmeans 算法函数
def kMeans(dataset,k):
#随机选取 k 个样本作为聚类中心
axis = random.sample(dataset, k)
normal = {}
#--------统计样本总体中各个分类的出现频率----------
for book in dataset:
if book["category"] not in normal:
normal[book["category"]] = 1
else:
normal[book["category"]] += 1
for i in normal:
normal[i] /= len(dataset)
#---------------------------------------------
times = 0
#储存上一次聚类结果
clustered = []
while True:
cluster = []
for i in range(k):
cluster.append([])
for book in dataset:
max = [0,0]
for i in axis:
cos = calc(i, book)
if cos > max[0]: max = [cos,axis.index(i)]
cluster[max[1]].append(book)
times += 1

#若本次分配结果与上次相同,说明已收敛,退出迭代,输出结果
if clustered == cluster:
for i in cluster:
categories = []
for t in i:
categories.append(t["category"])
amount = len(categories)
categories = Counter(categories)
for category in categories:
categories[category] /= amount
for category in categories:
categories[category] = round((categories[category] - normal[category])/normal[category],4)

#输出每个簇中各分类的权重相比于样本总体的变化比
print(categories)

#输出样本总体各分类权重
print(normal)
print("Loop Times:{}".format(times))
break

#----------若不相同,更新聚类中心,进行下一次迭代---------
for l in cluster:
centre = {}
centre["tags"] = Counter()
for book in l:
centre["tags"] += Counter(book["tags"])
for tag in centre:
centre["tags"][tag] /= len(l)
axis[cluster.index(l)] = centre
clustered = cluster

#---------------------------------------------
return cluster

t1 = time.time()

#导入数据集
with open("dataset",'rb') as file:
dataset = pickle.load(file)

###数据处理###

#------------统计 tag 在全体样本中出现次数-------
tag_set = dict()
for i in dataset:
for tag in i["tags"]:
if tag not in tag_set:
tag_set[tag] = 1
else:
tag_set[tag] += 1
#---------------------------------------------
print("tag 总数:{}".format(len(tag_set)))

#去除在总体中出现 500 次以下的tag
for i in dataset:
i["tags"] = [tag for tag in i["tags"] if tag_set[tag]>500]

#去除数据集中 tag 数少于 10 条的样本
dataset = [i for i in dataset if len(i["tags"])>10]
print("处理后数据集总条数:{}".format(len(dataset)))

#随机选取部分样本
random_set = random.sample(dataset, 2000)

#转换样本 tag list 为Counter类:{tag1:出现次数,tag2:出现次数...} 便于更新聚类中心
for i in random_set:
i["tags"] = Counter(i["tags"])

#运行kmeans算法
kMeans(random_set,k = 10)
print("共计用时{:.3f}s".format(time.time()-t1))

以下是随机选取 1000 条样本 k = 10 时的聚类结果。可以看出基于 tag 向量相似度的聚类结果的每个簇中,相对样本均值分类占比增益最大的分类,与样本的天然分类标签能够基本对应起来。这说明k-means 算法工作正常,且样本的 tag 与其分类有着较强的相关关系,这一结果也通过决策树与神经网络模型得到了验证,有时间再整理代码放上来吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ python3 k-means.py
tag 总数:98247
处理后数据集总条数:79501
Counter({'Manga': 1.5836, 'Cosplay': 0.1236, 'Non-H': -0.0637, 'Image Sets': -0.4086, 'Western': -0.7446, 'Doujinshi': -0.7582, 'Game CG Sets': -0.7945, 'Artist CG Sets': -0.8395})
Counter({'Artist CG Sets': 1.1801, 'Image Sets': 0.9023, 'Doujinshi': 0.2506, 'Misc': -0.3976, 'Game CG Sets': -0.4123, 'Western': -0.4524, 'Manga': -0.5166})
Counter({'Doujinshi': 0.5371, 'Artist CG Sets': 0.2755, 'Manga': -0.2835, 'Western': -0.5942, 'Game CG Sets': -0.8911})
Counter({'Image Sets': 2.8377, 'Misc': 2.6458, 'Artist CG Sets': 1.6786, 'Game CG Sets': 0.7785, 'Manga': -0.3891, 'Doujinshi': -0.4198})
Counter({'Non-H': 1.6247, 'Doujinshi': 0.7343, 'Manga': -0.1737, 'Western': -0.2842})
Counter({'Western': 14.7343, 'Non-H': 11.8205, 'Misc': 0.9231, 'Doujinshi': -0.5131})
Counter({'Misc': 1.2222, 'Doujinshi': 0.594, 'Non-H': 0.2346, 'Manga': -0.2227, 'Western': -0.4949, 'Artist CG Sets': -0.5767})
Counter({'Image Sets': 1.193, 'Doujinshi': 0.2658, 'Manga': -0.0355, 'Western': -0.053, 'Artist CG Sets': -0.4048, 'Game CG Sets': -0.4919})
Counter({'Game CG Sets': 4.8414, 'Artist CG Sets': 0.6807, 'Misc': 0.6807, 'Cosplay': 0.6807, 'Image Sets': -0.5577, 'Doujinshi': -0.5958, 'Manga': -0.611, 'Western': -0.809})
Counter({'Cosplay': 6.8947, 'Western': 1.9904, 'Image Sets': 1.7701, 'Artist CG Sets': 0.3784, 'Doujinshi': -0.1006, 'Manga': -0.2284, 'Misc': -0.3421, 'Game CG Sets': -0.8395})
{'Manga': 0.324, 'Doujinshi': 0.395, 'Misc': 0.02, 'Image Sets': 0.019, 'Artist CG Sets': 0.105, 'Game CG Sets': 0.082, 'Western': 0.044, 'Cosplay': 0.005, 'Non-H': 0.006}
Loop Times:20
共计用时35.417s

需要注意的是,k-means 是一个启发式算法,其优化目标函数是一个 NP-hard 问题(本文中采用了向量余弦距离,目标函数为 ),因此难以确定其是否会收敛至全局最优解,并且聚类结果相当依赖初始聚类中心的选择,对数据中异常点也比较敏感,一般在使用 k-means 算法时会选取不同的初始聚类中心进行多次聚类,选择其中较为优秀的结果。