k-means 算法的 Python 实现

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

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

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

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

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

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

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 与其分类有着较强的相关关系，这一结果也通过决策树与神经网络模型得到了验证，有时间再整理代码放上来吧。

$ 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 问题（本文中采用了向量余弦距离，目标函数为 $max\sum\limits ^{k}_{i}\sum\limits _{x\in C_{i}} cosine( c_{i} ,x)$ ），因此难以确定其是否会收敛至全局最优解，并且聚类结果相当依赖初始聚类中心的选择，对数据中异常点也比较敏感，一般在使用 k-means 算法时会选取不同的初始聚类中心进行多次聚类，选择其中较为优秀的结果。