基于改进流形距离Kmedoids算法

摘要：

针对空间分布复杂的数据以及空间分布未知的现实数据聚类问题，设计了一种改进流形距离作为不相似测度。该不相似测度可有效利用所有数据点之间的全局一致性，挖掘无类属数据集的空间分布信息。通过使用该不相似测度，提出了基于改进流形距离Kmedoids算法。将新算法与基于已有的流形距离和基于欧氏距离的Kmedoids算法进行性能比较，对八个人工数据集以及USPS手写体数字识别问题的实验结果表明：新算法针对不同结构的测试数据集，在聚类性能上均优于或接近于另外两种Kmedoids算法，并且对于各种分布的，无论简单或复杂，凸或者非凸的数据都可以进行聚类。

关键词：不相似测度；Kmedoids算法；聚类；流形距离；模式识别

中图分类号：TP181；TP391.4

文献标志码：A

0引言

聚类就是将物理或抽象的数据对象，按照对象间的相似性进行分组或分类的过程[1]。由聚类所生成的类或簇是一组数据对象的集合，且同类中的对象彼此相似，不同类中的对象彼此相异。聚类作为一种重要的数据分析方法已经被广泛应用于模式识别、数据挖掘、信息检索和图像处理等领域。

在现有的聚类算法中，基于划分的方法以数据点与类原型之间的距离为基础，通常将聚类结果的评判标准定义为一个目标函数。类原型、数据点与类原型间距离以及目标函数定义的不同就产生了多种多样的划分聚类算法。典型的划分聚类算法有Kmeans算法[2]、Kmedoids算法[3]。不相似测度对这类算法的性能有重要影响。最简单的不相似测度是欧氏距离，但以欧氏距离作为不相似测度存在一个缺点，即它只对空间分布为球形或超球体的数据具有较好的性能，而对空间分布复杂的数据性能很差[4]。

2基于改进流形距离的Kmedoids算法

Kmeans算法和Kmedoids算法是基于划分的聚类算法代表。Kmeans算法以类中所有数据点的均值点作为每个类别的类原型，当数据为球形或超球体分布时，算法可以取得较好性能，而当数据呈现复杂分布的流形结构时，均值点可能偏离类别，用均值点作为类别的类原型，对性能会有较大影响。Kmedoids算法从当前类中选取一个到类中的其他所有数据点的距离之和最小的数据点作为类原型，可以确保类原型不会偏离类别。当数据呈现复杂分布，尤其是不符合球形或超球体的分布时，Kmedoids算法比Kmeans算法更有优势。基于以上分析，本文将改进流形距离作为不相似测度用于Kmedoids算法，得到IMDKmedoids算法。

4结语

本文设计了一种改进流形距离不相似测度，应用于Kmedoids算法，提出IMDKmedoids算法具有较好的聚类性能。在不同数据集上，将IMDKmedoids算法和MDKmedoids算法、Kmedoids算法进行了对比测试，证明其对复杂分布数据聚类问题和真实世界模式识别问题的有效性。在人工数据集的测试中，IMDKmedoids对球形分布数据的聚类结果与最佳结果接近，而对于流形分布数据的聚类效果，其优势十分明显，在真实世界的USPS数据集模式识别问题中，准确率同样最高，明显优于其他两个算法。

参考文献：

[1]XU R， WUNSCH D. Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks， 2005，16（3）：645-678.

[2]HARTIGAN J A， WONG M A. A kmeans clustering algorithm[J]. Applied Statistics，1979， 28（1）：100-108.

[3]KAUFMAN L， ROUSSEUW P J. Finding groups in data： an introduction to cluster analysis[M]. New York： John Wiley & Sons， 1990：108-110.

[4]SU M C， CHOU C H. A modified version of the kmeans algorithm with a distance based on cluster symmetry [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（6）： 674-680.