Python实现并测试K-means聚类算法

实现并测试K-means聚类算法
目录
机器学习与数据挖掘第二次实验报告 1
实现并测试K-means聚类算法 1
一 、K-Means 简述 1
四 、实验结果分析 5
4.1 K-Means 迭代结果 5
4.2 比较不同初始化方法和距离选择的效果 12
4.3 不同聚类个数下目标函数 J 的曲线 14
五 、结论 16
一 、K-Means 简述
聚类（Clustering）是按照某个特定的标准将一个数据集划分成若干的簇，使得同一个簇内的样本相似 性尽可能大，不同簇之间的样本差异性尽可能大。聚类的目的在于划分数据，不关心簇对应的实际标 签，是一种常见的无监督学习方法。
常见的聚类算法包括划分式的聚类方法、基于密度的聚类方法和层次化的聚类方法，其中 K-Means
聚类是常见的划分式聚类方法。
KMeans 算法的算法效率高，聚类形状成球形，抗噪声性能较差，异常数据容易影响聚类的效果。
实验结果分析：
可以看到对于以下所有数据集， J 曲线都有一个陡峭的阶段和平缓下降的阶段，它们的转折点都与数据集原本的簇接近，本文转载自http://www.biyezuopin.vip/onews.asp?id=16713对于数据集 Iris、Seed、Wine都在 附近有一个曲线从陡到缓的一个转折，对于 Wine 数据集同样在 附近有一个转折。
J 曲线单调递减，最终都趋于收敛
五 、结论
在本次实验中，我们实现了 K-Means 聚类算法，并测试了三种簇中心初始化方法和两种距离衡量标准， 并使用 NMI 和 目标函数 J 进行评估，我们得到以下结论。
K-Means 聚类算法，能够较快达到收敛，但在样本和簇个数较多的情况下通常得到的聚簇结果不唯一，即有多种划分，容易陷入局部最优。
不同的初始化方法和距离计算标准在面对不同数据集时有不同的性能，没有一个通用的最佳策略。

from visual_utils import *
from data_utils import *
from kmeans import *
from sklearn.metrics.cluster import normalized_mutual_info_score
from sklearn.cluster import KMeans


if __name__ == "__main__":
    # 载入数据集
    data, label, col_name, classes = load_iris()
    name = "iris"

    # 对于样本太多的数据集，取一部分样本进行测试
    # data = data[:5000]
    # label = label[:5000]

    # 真实分类的数据降维可视化
    # show_t_sne(data, label, classes, name)
    # show_pca(data, label, classes, name)

    # 生成Kmean聚类过程中聚类的变化图，结果保存在 AnimImage 文件夹
    # 运行可能需要较长时间

    # 随机初始化
    # name1 = name
    # c, y, more = kmeans(data, len(classes), ite_max=50, centers_init=get_random_centers)
    # s = normalized_mutual_info_score(y, label)
    # print(name1, "NMI: ", s)
    # show_anim(data, more["labels"], more["centers"], name=name1)

    # 距离初始化
    # name2 = name + "_dis"
    # c, y, more = kmeans(data, len(classes), ite_max=50, centers_init=get_distance_based_centers)
    # s = normalized_mutual_info_score(y, label)
    # print(name2, "NMI: ", s)
    # show_anim(data, more["labels"], more["centers"], name=name2)

    # 随机距离初始化
    # name3 = name  + "_randis"
    # c, y, more = kmeans(data, len(classes), ite_max=50, centers_init=get_randis_centers)
    # s = normalized_mutual_info_score(y, label)
    # print(name3, "NMI: ", s)
    # show_anim(data, more["labels"], more["centers"], name=name3)


    # 【可选】：对数据先进行 PCA 降维
    # dim = 8
    # pca = PCA(n_components=dim)
    # data = pca.fit_transform(data)


    # 比较不同初始化方法和距离选择的效果
    # t = 20
    # k = {}
    # cen = [get_random_centers, get_distance_based_centers, get_randis_centers]
    # dis = [d_eculidean, d_manhattan]
    # idx = range(len(cen) * len(dis))
    # xtick = ["eculidean\nrandom_centers", "eculidean\ndistance_based_centers", "eculidean\nrandis_centers",
    #          "manhattan\nrandom_centers", "manhattan\ndistance_based_centers", "manhattan\nrandis_centers"]
    # err_limit = 0.0
    # for i in idx:
    #     k[i] = []
    #
    # for i in idx:
    #     for j in range(t):
    #         centers, y_kmeans, _ = kmeans(data, len(classes), ite_max=100, centers_init=cen[i % len(cen)] , distance=dis[i // len(cen)])
    #         res = normalized_mutual_info_score(y_kmeans, label)
    #         print(xtick[i], res)
    #         if res > err_limit:
    #             k[i].append(res)
    #
    # validition_visual(idx, k, ylabel="NMI", xtick=xtick, name=name)


    # sklearn kmean模型聚类，与我们的实现结果进行比较
    # kmean = KMeans(n_clusters=len(classes))
    # kmean.fit(data)
    # y_kmeans = kmean.predict(data)
    # s = normalized_mutual_info_score(y_kmeans, label)
    # print("SkLearn kmeans: ", s)

    # 对分类结果进行降维（t-sne 或 pca）可视化
    # show_t_sne(data, y_kmeans, classes)
    # show_pca(data, y_kmeans, classes)

    # 计算样本与聚类中心的距离和
    # x = range(1, 20)
    # y = []
    # l = 5
    # for k in x:
    #     j = 0
    #     for i in range(l):
    #         centers, data_class, _ = kmeans(data, k, ite_max=100, centers_init=get_distance_based_centers)
    #         j += get_total_distance(data, centers, data_class)
    #     y.append(j / l)
    # show_j(x, y, name=name)

    # 比较不同初始化方法和距离选择的 J 效果
    # t = 20
    # k = {}
    # cen = [get_random_centers, get_distance_based_centers, get_randis_centers]
    # dis = [d_eculidean, d_manhattan]
    # idx = range(len(cen) * len(dis))
    # label_list = ["eculidean + random", "eculidean + distance", "eculidean + randis",
    #          "manhattan + random", "manhattan + distance", "manhattan + randis"]
    #
    # y_6 = []
    # # x = range(1, 20)
    # x = range(1, 50, 4) # for Letter dataset
    # for i in idx:
    #     y = []
    #     # l = 5
    #     l = 3 # for Letter Dataset
    #     for k in x:
    #         j = 0
    #         for i in range(l):
    #             centers, y_kmeans, _ = kmeans(data, k, ite_max=100000, centers_init=cen[i % len(cen)] , distance=dis[i // len(cen)])
    #             j += get_total_distance(data, centers, y_kmeans)
    #         y.append(j / l)
    #     y_6.append(y)
    # show_j(x, y_6, label_list, name=name)


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