【最优化方法】K

  手写数字图像数据分类问题：文件train_images.mat包含大小为28*28的手写数字图像，共60000张；文件train_labels.mat是其对应的数字标签。文件数据的具体读写和数据格式，请参考附件DataRead.m文件。实验要求对手写数字图像进行聚类，并讨论其性能：(MNIST DATABASE下载) (1) 对train_images.mat的前100张手写数字图像进行聚类，共10类；

(2) 对train_images.mat的前1000张手写数字图像进行聚类，共10类； (3) 根据实际情况，讨论k-Means能对多少张手写图像进行聚类，性能如何？

  本次实验实现过程的思维逻辑如图1所示：

  由于所给的手写体文件是以mat格式来存储的，在Python中需要使用相关的工具库进行导入，这里笔者使用scipy.io中的函数loadmat()来读取mat文件。最终得到的images数据是一个(28,28,60000)的三维数组，labels数据是一个（1，60000）的二维数据。图2展示了导入成功后，其中一张手写体及其标签的灰度像素图片。

  经典 K-means 算法的基本工作流程：首先随机选取 K 个数据作为的聚类的聚类中心，计算各个数据对象到所选出来的各个中心的距离，将数据对象指派到最近的类中；然后计算每个类的均值，循环往复执行，直到满足聚类的收敛条件为止。具体的执行步骤如表1所示：

  利用存储图片对应数字的数组和上一步求得的聚类中心数字可以得到利用K-means算法识别的数字结果，再将其与train_labels（每张图片真正的label）对照并计算识别正确率。(精确度 =正确数/总数)

  为了对聚类的效果进行映射到二维平面的可视化，以直观显示出聚类效果的散点图，所以需要将维度为 28×28=784 的手写体图片降到2维。   主成分分析（PCA）是最常用的一种降维方法，通常用于高维数据集的探索与可视化，还可以用作数据压缩和预处理等。PCA可以把具有相关性的高维变量合成为线性无关的低维变量，称为主成分，主成分能够尽可能保留原始数据的信息。原理就是其协方差矩阵对应的特征向量，按照对应的特征值大小进行排序，最大的特征值就是第一主成分，其次是第二主成分，依次类推。 PCA算法流程如表2所示：

  这里，笔者使用Python的sklearn库，调用decomposition.PAC加载PCA进行降维，使用参数n_components指定主成分的个数为2，即降维后数据的纬度为2。封装成display()函数，然后分别对聚类前后的样本进行可视化。

  MacOS Big Sur + Intel I5 + 16G内存 + Pycharm

  k个聚类中心,m个数据,计算两数据之间二范数的复杂度为O(d),则聚类一次的时间复杂度为O(kmd)。对于dim"*" dim像素的灰度图像,两数据间的欧氏距离的复杂度为3*dim*dim。所以时间复杂度可以写为O(3*dim*dim*km)。重新确定聚类中心所需的时间复杂度为O(dim* dim * m),少于第一步。k-Meams的时间复杂度则为O(dim*dim*km)。

  a. 当m=100时   首先设置参数，m=100，k=10，times=100，将前100张手写数字图像聚成10类，并且重复运行100次，得到如图3所示的可视化图表。可以看到，100次聚类测试中，聚类的平均正确率为59.50%，最高达到70%，最低为46%，方差为0.002，每次聚类的平均时间为0.051s。

  如表3所示，笔者选取其中5次运行结果进行详细展示：

  接下来，笔者将探究：在 10 个聚类中心的前提下，随着聚类的样本数的增加，K-means算法的匹配正确率是否会有显著差异。   b．当m=1000时   设置参数，m=1000，k=10，times=100，将前1000张手写数字图像聚成10类，并且重复运行100次，得到如图4所示的可视化图表。可以看到，100次聚类测试中，聚类的平均正确率为54.45%，最高达到62.70%，最低为45.10%，方差为0.001，每次聚类的平均时间为1.392s。

  c. 对m=100，1000，3000，5000，7000，9000，11000的情况进行对比分析   由于篇幅所限，笔者就不在这里详细画出其他情况的正确率折线图。这里随着样本数目不断增多，算法运行时间不断增加，受制于硬件性能，当样本增加到9000时，100次的运行次数已经较难完成了，所以当m≥9000时，本实验的测试次数减少为10次，但10次取平均得到的正确率也可以较好地说明问题了。结果总结如表4所示，可以看到，在10个聚类中心的前提下，随着聚类的样本数的增加，K-means算法的平均正确率都集中在55%-60%，样本量的增加没有带来正确率的显著差异，但是平均运行时间却显著不断增加。   d. K-Means能对多少张手写图像进行聚类，性能如何？   为了探究本次设计的K-Means能对多少张手写图像进行聚类，在k=10的情况，我选取数据集中全部60000张图片进行聚类，如图5所示，可以看到聚类的正确率为58.97%，仍处于55%-60%的区间，运行时间为249.778s。所以本K-Means算法能完成对全部60000张手写图像进行聚类，性能正确率可以达到58.97%。

  接下来，笔者还将探究：在聚类样本数m=100的前提下，随着聚类中心k的增加，K-means算法的匹配正确率是否会有显著差异。   设置参数，m=100，k=15，times=100，将前100张手写数字图像聚成15类，并且重复运行100次，得到如图6所示的可视化图表。可以看到，100次聚类测试中，聚类的平均正确率为67.21%，最高达到79.00%，最低为58.00%，方差为0.002，每次聚类的平均时间为0.067s。可以看到随着聚类中心的增加（从10到15），聚类的平均正确率显著提升，但聚类的平均时间也有所增加。（如前面图2所示，当k=10时，聚类的平均正确率为59.50%，最高达到70%，最低为46%，方差为0.002，每次聚类的平均时间为0.051s。）

  如表5所示，笔者选取其中5次运行结果进行详细展示，可以看到跟k=10的情形进行相对，聚类迭代的次数也明显下降（从6.6下降为4）

  当m=100，k=10时，运行程序，正确率为57%，得到如图7的聚类可视化结果：

  当m=1000，k=10时，运行程序，正确率为55.80%，得到如图8的聚类可视化结果：

  在经过PCA算法的可视化后，可以轻易看出数据集使用K-Means进行聚类并不能有很好的效果。虽然有一部分是因为K-means 是根据28*28来度量距离的，取前两维之后可视化的效果不会特别好。但是其实作为一种无监督的基于距离的聚类算法，K-Means算法虽然易于理解并被广泛运用，但算法并没有完美一说，K-Means时间复杂度较高并且在实际问题中聚类中心的数量和选取在一开始难以精准确认，这都使得K-Means算法的聚类结果并没有表现的很好，仍存在着一些问题。