基于密度概念的初始中心选取方法
传统的K-Means算法存在不少问题，为了得到更好的聚类结果，也为了得到更高效的聚类过程，所以对算法进行改进。改进的算法就希望在选取初始的聚类中心的时候就尽可能做到这一点，而不是随机的选取k个对象来作为初始的聚类中心。而且聚类受噪声和孤立点等影响很大，改进的算法将改进这个方面。
假设已经知道数据集的分布情况。认为一个优良的初始聚类中心集应该满足以下条件:
(l)选择的初始中心各属于不同的类，即任意两个初始中心不能属于同一类。
(2)选择的初始聚类中心应该能作为该类代表，即应该尽量靠近类中心。
基于以上考虑，本文采用了一种的基于密度概念的初始中心选取方法。
K-Means算法聚类效果受到初始时聚类中心的影响很大，如果它们选择较为合理，聚类结果就会更合理，而且聚类的速度也会更快一些。为了使初始类中心选取得较为分散，不过于集中，可以给定一个距离。同时，为了尽量消除孤立点对聚类结果得影响，即通过算法将孤立点放在最后考虑，或者将其另外作为一类。为此，需要用到密度的概念[6]:本文来自优-文~论^文.网原文请找腾讯3249^114
以某个对象为中心，以正数r为半径作超文球，落在该球内的对象数就称为该对象的密度。把对象按照密度排序，尽量选中密度较大的对象作为初始类中心，对于密度过小的对象，可将其视为孤立点。
首先，给定两个正数r和d，:用于计算密度的半径，d是初始类中心的距离，一般要求r<d。然后，以r为半径计算每个对象的密度，将对象按密度大小排序。选择密度最大的对象为第一个类中心。再取密度次大的对象，计算它与第1个类中心的距离，如果小于d，则取消该点，否则选择它作为第2个类中心;接着取下一个对象，计算其与前两个类中心的距离，如果小于d，则取消，否则作为第3个类中心。按此标准确定其余的类中心。经过如此选择的初始类中心距离相隔较远，不至于分布集中，影响聚类效果。除此之外，经过排序后，打乱了对象的最初的输入顺序，使其总是按密度大小顺序输入，从而使算法对输入顺序不敏感，获得较好的聚类效果。
但是在实际操作过程中会出现一个问题，由于r和d都是经验值，对于一个给定的样本集，一般无法预知:和d的大小，对于d可以设置它为r的一定的倍数即可，为了不让两个范围中有重复，本文选取的是d=2r;但是对于r，很难找到一个最佳的值。r取值太大或太小都失去了对象点密度的意义，从而找不出合理的初始中心点，而且r的取值很敏感，它和样本集中的数据密切相关，样本集中对象的个数，每个对象数据值的大小，每个对象文数的大小，聚类的簇数k，对象的分布情况等因素都会对合适的r值起到重要影响，可以说，对于一个给定的样本集，就要确定一个相对于它的合适的r值。
论文网http://www.youerw.com/
为此，本文提出一种自适应选择最佳密度半径的方法。一般期望最大的点密度应该与一个聚类簇中样本的个数相当或小于之。因此考虑用样本数n除以k，得到大致期望的平均的一个聚类中对象的个数，再用其乘以一定的系数(比如90%和75%)，想法把最大密度锁定在95%n/k和75%n/k之间。具体方法如下:
先设定一个初始的r值，如果所有点的最大密度大于95%n/k，则r减去一个步长(比如本文中采用的是0.01)，重新计算最大密度;如果点的最大密度小于75%n/k，则:加上一个步长，重新计算最大密度，这样就找到最大密度在95%n/k和75%n/k之间的值，从而进一步确定最佳的聚类中心点。算法的流程图如图 3-1:
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9]
基于K-means的文本聚类算法研究 第9页下载如图片无法显示或论文不完整，请联系qq752018766
