流形上的非线性判别K均值聚类
开篇：润墨网以专业的文秘视角，为您筛选了一篇流形上的非线性判别K均值聚类范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
フ 要:为提高具有流形结构的高维数据的聚类性能，提出非线性判别K均值聚类算法(NDisKmeans)。该方
>> 基于粗糙K—均值用户兴趣的聚类算法 一种K―均值聚类的改进算法 基于Matlab环境下的K均值聚类算法 k均值聚类中的EM思想 基于k均值聚类的微博用户分类的研究 改进的K—均值聚类算法在Web日志挖掘技术中的应用 基于K-均值聚类的中国存货景气指数设计研究 基于K-均值聚类粒子群优化算法的组合测试数据生成 一种并行的加速k—均值聚类方法 基于K—means均值聚类的车牌定位算法研究 基于改进差分进化的K—均值聚类算法 采用k―均值聚类算法的资源搜索模型研究 基于K均值聚类的文字分割算法研究与实现 基于改进k―均值算法的轻型车尾气排放数据聚类方法 基于K均值聚类和HSV颜色模型的烟雾图像分割 基于改进人工蜂群算法的K均值聚类算法 基于蚁群粒子群混合算法的K均值聚类优化算法研究 基于改进K均值算法的X光片图像聚类研究 基于自适应遗传算法的K均值混合聚类算法 基于分裂式K均值聚类的图像分割方法 常见问题解答 当前所在位置：l)。这三种数据集分别代表了不同的图像分类任务。对于Yale人脸数据，每个人脸图像都被裁剪成32×32大小;而对于USPS手写数字数据集，我们选择数字“1”、“2”、“3”、“4”和数字“5”，并且每个数字随机选取300幅图像进行实验;Coil20数据集包含20个物体大小为32×32的共1B440幅图像，其中每个物体有72幅图像。
3)文本数据：分别在两个有代表性的文本数据上进行了实验：TDT2()和WebKB(www.cs.cmu.edu/~WebKB/)。对于TDT2数据集，选择类别20013、20070、20044和20076中包含的所有1B931个文档，这四个类别包含的文档数目在整个TDT2数据集中排在第4、5、6和第7的位置。同时删除在这1B931个文档中出现总次数少于5次的单词，最后每个文档采用TFIDF为一7B906维的向量。而对于WebKB网页数据，仅选择包含Cornell大学计算机系网页的子集，这个网页可以导致分为7个不同的主题。
表1总结了实验中所使用数据的细节。对每个数据集，进行10次实验以获取平均结果。
4.2 聚类性能评估方法
实验中采用两种标准的聚类评估方法来评估参与比较的所有聚类算法的性能。
1)聚类精度(Clustering Accuracy, ACC)。这种方法通过度量聚类结果与真实类标号的匹配程度来衡量算法的性能。具体定义如下：
ACC = 1n∑ni = 1δ(map (ci),li)(24)お
其中：li是样本xi的真实标号；ci则是聚类算法获取的xi的聚类标号;δ(x,y)为Delta函数，δ(x,y)=1当且仅当x=y，否则δ(x,y)=0；map (•)为最佳匹配映射函数，利用文献［21］中介绍的KuhnMunkres最佳匹配算法来寻找该映射map (•)。ACC值越大意味着聚类性能越好。オ
2)规范化互信息(Normalized Mutual Information, NMI)。对于给定的聚类结果，规范化互信息计算如下：
NMI=MI(Cr,Cv)max(H(Cr),H(Cv))(25)
其中:Cr为按照真实的类标号划分的聚类集合；Cv为聚类算法获取的聚类集合；MI(Cr,Cv)是集合Cr和Cv之间的互信息；H(Cr)和H(Cv)分别是集合Cr和Cv的信息熵。NMI值越大意味着聚类性能越好。オ
4.3 参数选择
在很多机器学习算法中都涉及参数的选取。在参与比较的算法中，都有一个或多个参数需要手动选取。为了比较的公平性，我们在不同的参数条件下执行所比较的算法，然后介绍最好的平均结果。
对所有涉及到的聚类算法，都令聚类数为数据集的类别数；而对所有基于图的学习算法，比如规范化割、谱嵌入聚类以及本文的NDisKmeans算法，采用式(5)高斯相似性构造相同的近邻矩阵S；同时相似性中的参数Е要О凑瘴南祝22］中自适应选择的方法自动确定。对于邻域大小k，Т蛹合{5, 10, 15, 20, 50, 100}中选择。
对于NDisKmeans方法，令m=min(D,15)，其中D为原始数据的维数；而待求的低维坐标的维数dг虼蛹合{3,5,10,15}中选择和调整，并且保证其不大于mе怠＊
对于SEC算法，存在两个折中参数Е毯挺锚需要调整。按照文献［20］中做法，固定Е=1，Ф在集合{10-7,10-5,10-3,10-1,1,102,103,105}中调整Е酞У娜≈怠＊
对于给定的近邻图和聚类数C，Ч娣痘割算法没有其他需要手动调整的参数；而对于判别KЬ值聚类(DisKmeans)，需要确定正则化参数Е锚取值，仍旧从集合{10-7,10-5,10-3,10-1,1,102,103, 105}中选取。
除KЬ值算法外，其他几种聚类算法获得连续的聚类赋值矩阵，最后都采用谱旋转［20］的方法来获取聚类结果。
4.4 聚类性能比较
表2和表3分别比较了所涉及几种算法在不同数据集上的所获得的聚类精度和规范化互信息。表中带下划线的值代表最好的性能。
从对这两个表的比较中，可以观察到：
1)在大多数数据集上，本文提出的NDisKmeans方法能取得较其他方法更好的聚类性能。这表明利用高维数据的流形结构，且取消降维时线性映射的限制，能提高对具有流形结构的高维数据的聚类性能。
2)在大多数情况下，SEC聚类性能略优于规范化割算法。但是SEC和规范化割相比K均值和判别K均值聚类，性能有较大提高。KЬ值聚类相比其他复杂的聚类方法，聚类效果最差。
5 结语
本文针对具有流形结构的高维数据的聚类问题，提出了一种基于谱正则化的非线性判别K均值聚类算法。考虑到判别K均值算法采用线性维数归约方法，没有有效利用高维数据的流形结构，因此限制了聚类性能的提高。本文提出的非线性判别K均值算法利用流形上的谱正则化技术，将数据的低维坐标表示成数据流形上平滑函数的线性组合，并通过最大化Fisher判别标准，实现在低维空间增强数据的聚类结构并对其进行聚类。NDisKmeans算法虽然采用迭代优化方式求解最优聚类赋值矩阵和组合系数矩阵，但是迭代过程具有收敛性。与其他聚类算法在不同数据集上的比较实验，结果显示NDisKmeans算法能获得较高的聚类性能，证实了本文所提NDisKmeans算法聚类高维数据的有效性。
げ慰嘉南:
[1] von LUXBURG U. A tutorial on spectral clustering［J］. Statistics and Computing，2007, 17(4): 395-416.
[2] TORRE F D L, KANADE T. Discriminative cluster analysis［C］// Proceedings of the 23rd International Conference on Machine Learning. New York: ACM, 2006: 241-248.
[3] LI T, DING C. A daptive dimension reduction using discriminant analysis and kmeans clustering［C］// Proceedings of the 23rd International Conference on Machine Learning. New York: ACM, 2007：521-528.
[4] JOLLIFFE I. Principal component analysis［M］. Heidelberg: Springer, 2002.
[5] TENENBAUM J, SILVA V, LANGFORD J. A global geometric framework for nonlinear dimensionality reduction［J］. Science, 2000, 290(5500): 2319-2323.
[6] ROWEIS S, SAUL L. Nonlinear dimensionality reduction by locally linear embedding［J］. Science, 2000, 290(5500): 2323-2326.
[7] BELKIN M, NIYOGI P, Laplacian eigenmaps for dimensionality reduction and data representation［J］. Neural Computation, 2003, 15(6): 1373-1396.
[8] ZHAN Y, YIN J. Cluster preserving embedding［C］// Proceedings of the 20th International Conference on Pattern Recognition. New York: IEEE, 2010: 621-624.
[9] YE J, ZHAN Z, WU M. Discriminative ┆kmeans for clustering［C］// Advances in Neural Information Processing Systems. Cambridge: MIT Press. 2008: 1649-1656.
[10] NIE F, XU D, TSANG I W, et al. Spectral embedded clustering［C］// Proceedings of the 21st International Jont Conference on Artifical Intelligence. San Francisco: Morgan Kaufmann Publishers,2009: 1181-1186.
[11] BOUTSIDIS C, MAHONEY M W, DRINEAS P. Unsupervised feature selection for the kmeans clustering problem［C］// Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2009:1-9.
[12] HAGEN L, KAHNG A B. New spectral methods for ratio cut partitioning and clustering［J］. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 1992, 11(9): 1074-1085.
[13] SHI J, MALIK J. Normalized cuts and image segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
[14] DUDA R, HARTA P, STORK D. Pattern classification ［M］. Chichester: John Wiley and Sons, 2001.
[15] LI ZHENGUO, LIU JIANZHUANG, TANG XIAOOU. Constrained clustering via spectral regularization［C］// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2009:421-428.
[16] BELKIN M, NIYOGI P. Semisupervised learning on Riemannian manifolds［J］. Machine Learning, 2004, 56(1): 209-239.
[17] WANG H, YAN S, XU D, et al. Trace ratio vs. ratio trace for dimensionality reduction［C］// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition 2007. New York：IEEE, 2007: 1-8.
[18] JIA Y, NIE F, ZHANG C. Trace ratio problem revisited［J］. IEEE Transactions on Neural Networks, 2009, 20(4): 729-730.
[19] NIE F, XIANG S, JIA Y,et al. Trace ratio criterion for feature selection［C］// Proceedings of the 23rd National Conference on Artificial Intelligence. Chicago: AAAI Press. 2008: 671-676.
[20] YU S X, SHI JIANBO. Multiclass spectral clustering［C］// Proceedings of the 9th IEEE International Conference on Computer Vision. New York: IEEE, 2003: 313-319.
[21] LOVASZ L, PLUMMER M D. Matching theory［M］. Amsterdam: Elsevier Science, 2009.
[22] ZELNIKMANOR L, PERONA P. Selftuning spectral clustering［C］// Advances in Neural Information Processing Systems. Cambridge: MIT Press,2005: 1601-1608.