K-means算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
K-means算法
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩5页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢当前位置： >>
K-means算法
K-means 算法K-means 算法是硬聚类算法，是典型的基于原型的目标函数聚类 方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利 用函数求极值的方法得到迭代运算的调整规则。K-means 算法以欧 式距离作为相似度测度，它是求对应某一初始聚类中心向量 V 最优 分类，使得评价指标 J 最小。算法采用误差平方和准则函数作为聚类 准则函数。1.K-means 算法K-means 算法是很典型的基于距离的聚类算法，采用距离作为 相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。 该算法认为簇是由距离靠近的对象组成的， 因此把得到紧凑且独立的 簇作为最终目标。 k 个初始类聚类中心点的选取对聚类结果具有较大的影响，因 为在该算法第一步中是随机的选取任意 k 个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个 对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当 考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出 来。如果在一次迭代前后， J 的值没有发生变化， 说明算法已经收敛。2. 算法过程1）从 N 个文档随机选取 K 个文档作为质心 2）对剩余的每个文档测量其到每个质心的距离，并把它归到最 近的质心的类 3）重新计算已经得到的各个类的质心 4）迭代 2～3 步直至新的质心与原质心相等或小于指定阈值，算 法结束 具体如下： 输入：k, data[n]; （1）选择 k 个初始中心点， 例如 c[0]=data[0],…c[k-1]=data[k-1]； （2） 对于 data[0]….data[n]，分别与 c[0]…c[k-1]比较，假定与 c[i]差值最少，就标记为 i； （3）对于所有标记为 i 点， 重新计算 c[i]={ 所有标记为 i 的 data[j] 之和}/标记为 i 的个数； （4） 重复(2)(3)，直到所有 c[i]值的变化小于给定阈值。3. 工作原理与处理流程1）工作原理输入：聚类个数 k，以及包含 n 个数据对象的数据库。 输出：满足方差最小标准的 k 个聚类。2）处理流程（1） 从 n 个数据对象任意选择 k 个对象作为初始聚类中心； （2） 根据每个聚类对象的均值（中心对象），计算每个对象与 这些中心对象的距离；并根据最小距离重新对相应对象进行划分； （3） 重新计算每个（有变化）聚类的均值（中心对象） （4） 循环（2）到（3）直到每个聚类不再发生变化为止 k-means 算法接受输入量 k ；然后将 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高； 而不同聚类中的对象相似度较小。 聚类相似度是利用各聚类中对象的 均值所获得一个“中心对象”（引力中心）来进行计算的。 工作过程 k-means 算法的工作过程 说明如下：首先从 n 个数据对象任意选择 k 个对象作为初始聚 类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的） 聚类；然 后再计算每个所获新聚类的聚类中心（该聚类中所有对象 的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般 都采用均方差作为标准测度函数。k 个聚类具有以下特点：各聚类本 身尽可能的紧凑，而各聚类之间尽可能的分开。3. 算法存在的问题K 均值聚类 K-means 算法的特点――采用两阶段反复循环过程算法，结束 的条件是不再有数据元素被重新分配： 指定聚类 即指定数据到某一个聚类，使得它与这个聚类中心的距离比它到 其它聚类中心的距离要近。 修改聚类中心 优点： 本算法确定的 K 个划分到达平方误差最小。 当聚类是密集 的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个 算法是相对可伸缩和高效的，计算的复杂度为 O(NKt)，其中 N 是数 据对象的数目，t 是迭代的次数。一般来说，K&&N，t&&N 。4. 算法的优缺点 1）优点K-Means 聚类算法的优点主要集中在:（1） 算法快速、简单; （2） 对大数据集有较高的效率并且是可伸缩性的; （3） 时间复杂度近于线性，而且适合挖掘大规模数据集。 K-Means 聚类算法的时间复杂度是 O(nkt) ,其中 n 代表数据集中对象 的数量，t 代表着算法迭代的次数，k 代表着簇的数目。2）缺点k-means 算法缺点： ① 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是 非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多 少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是 通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。关于 K-means 算法中聚类数目 K 值的确定在文 献中，是根据方差分析理论，应用混合 F 统计量来确定最佳分类数， 并应用了模糊划分熵来验证最佳分类数的正确性。在文献中，使用了 一种结合全协方差矩阵的 RPCL 算法，并逐步删除那些只包含少量 训练数据的类。 而文献中使用的是一种称为次胜者受罚的竞争学习规 则，来自动决定类的适当数目。它的思想是：对每个输入而言，不仅 竞争获胜单元的权值被修正以适应输入值， 而且对次胜单元采用惩罚 的方法使之远离输入值。 ② 在 K-means 算法中，首先需要根据初始聚类中心来确定一 个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效 的聚类结果，这也成为 K-means 算法的一个主要问题。对于该问题 的解决，许多算法采用遗传算法（GA），例如文献 中采用遗传算法 （GA）进行初始化，以内部聚类准则作为评价指标。 ③ 从 K-means 算法框架可以看出，该算法需要不断地进行样 本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常 大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进 行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度 进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而 在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初 始点的选择还是一次迭代完成时对数据的调整， 都是建立在随机选取 的样本数据的基础之上，这样可以提高算法的收敛速度。6 参考文献[ 1 ] 赵力，语音信号处理[M]．第一版，北京：机械工业出版社，2003 [ 2 ] 王炳锡，屈丹，彭煊．实用语音识别基础[M].北京：国防工业出版社，2005 [ 3 ]易克初，田斌，付强等．语音信号处理[M].北京：国防工业出版社，2000 [ 4 ]高成华， 聋儿康复事业的历史、现状和展望[J]，中国听力语言康复科学杂志， 2003 [ 5 ] 杨行竣， 迟惠生等， 语音信号数字处理[M].第一版， 北京： 电子工业出版社， 1995 [6] 彭昭，吕冠中，梁洁，等. 基于 P2P 的流媒体点播技术研究与展望[J]. 计算机科学，2008. [ 7 ] 庄雷，常玉存，董西广. 一种 P2P 文件共享系统中的激励机制[J] . 计算机 应用研究，2009， (01) ：266-26 [ 8 ]孙卫琴. JAVA 面向对象编程[M ]. 北京:电子工业出版社, 2006, 8[ 9 ] 庄雷，常玉存，董西广. 一种 P2P 文件共享系统中的激励机制[J] . 计算机 应用研究，2009， (01) ：266-268. [10] 周辉，董正宏.数字信号处理基础及 MATLAB 实现[M].北京：北京希望电子 出版社，2006. [11] 邹理和.语音信号处理[M].北京：国防工业出版社，1985. [12] 梁晓辉, 周权.语音信号处理方法的可靠性研究[J].电声技术，2010 年 04 期. [13] 吴艳花.语言短时幅度和短时过零率分析与应用[J].电脑知识与技术.2009 年 33 期. [14] 胡航.语音信号处理[M].哈尔滨：哈尔滨工业大学出版社,2009.7. [15] 孙燕.语音频谱分析与应用[J].计算机与现代化，2010 年 04 期. [16] 孙卫琴. JAVA 面向对象编程[M]. 北京:电子工业出版社, ] 黄文梅，熊桂林，杨勇. 信号分析与处理[M]――MATLAB 语言及应用.长沙 ：国防科技大学出版社，2010 年 2 月. [18] 刘江华，程君实，陈佳品．支持向量机训练算法综述 [J]．信息与控制， ):45-49. [19]ZENG Qingning.Speech enhancement by array crosstalk resistant ANC and spectrumSubtraction. 声学学报：英文版，2008 年，27 卷 1 期. [20] GUAN Tian ， GONG Qin ， YE Datian.Effective use of the spectral information in speech processing of cochlear implant. 自然科学进展， 2007 年 17 卷 3 期. [21] 侯风雷，王炳锡．基于支持向量机的说话人辨认研究 [J]. 通信学报， ):61-67. [22]周志杰.MLP 语音信号非线性预测器[J].解放军理工大学学报（自然科学版 ）,):1-4. [23]RIZVI A.Residual vector quantization using a multiplayer competiting neural network[J].IEEE Trans .on SAC,):. [24]RABINER L R ,SCHAFER R W.Digital processing of SpeechSignals[M].Englewood Cliffs (New Jersey):Prentice-Hall Inc.,1978(祝雪龙等.语音信号数字处理[M].北京：科学出版社,1983).
更多搜索：
赞助商链接
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
标签：至少1个，最多5个
K-means， K均值聚类算法
假设每个 cluster 存在一个中心点，该 cluster 内的所有数据项到这个中心点的欧式距离（勾股定理的扩展：各维度差的平方求和再开方）都小于到其他 cluster 中心点的距离。算法的任务就是找出这些 cluster 的中心点。K-means 算法先随机选取 K （唯一的算法参数） 个点作为中心点，然后通过计算欧式距离来给所有数据项归类。归类之后使用平均值算法（mean）重新计算每个类的中心点，继续计算距离归类，直到中心点不再变化，此时视为收敛完成。
GMM，高斯混合聚类算法
假设每个聚类的数据都是符合高斯分布（又叫常态分布或者正态分布）的，当前数据呈现的分布就是各个聚类的分布叠加在一起。使用 EM 算法求解，具体没搞太明白。大概就是两个参数先随机指定一个，然后算另外一个，最后跟结果比较。
算法简单，容易理解。计算量不大，收敛快。可以很方便的进行分布式计算。默认所有属性对距离的影响是相同的，默认所有数据均匀分布在聚类中。如果数据是三维空间中的圆柱体，模型就失效了。
不容易理解，需要翻翻统计学的教材。假设各个特征的权重不同，假设各个聚类中的数据分布不均匀。理论上可以拟合任何连续函数。计算量较大。如果其中一个聚类的数据并不服从正态分布、偏态分布，聚类算法会出现偏差。
sk-learn 代码
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
#遍历可能的 cluster 个数，选择边界最清晰的
for i in [2, 3, 4, 5, 6, 7, 8]:
clusterer = KMeans(n_clusters=i, random_state=1024)
clusterer.fit(data)
#预测每一个点的簇
labels = clusterer.predict(data)
#边界系数，[-1, 1] 越大越清晰
silhouette_avg = silhouette_score(data, labels)
print("For clusters = ", i,
"The average silhouette_score is :", silhouette_avg)
if silhouette_avg & best_score:
best_clusterer = clusterer
best_score = silhouette_avg
best_cluster = i
print best_clusterer.centers_
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score
#遍历可能的 cluster 个数，选择边界最清晰的
for i in [2, 3, 4, 5, 6, 7, 8]:
clusterer = GaussianMixture(n_components=i, random_state=1024)
clusterer.fit(data)
#预测每一个点的簇
labels = clusterer.predict(data)
#边界系数，[-1, 1] 越大越清晰
silhouette_avg = silhouette_score(data, labels)
print("For clusters = ", i,
"The average silhouette_score is :", silhouette_avg)
if silhouette_avg & best_score:
best_clusterer = clusterer
best_score = silhouette_avg
best_cluster = i
print best_clusterer.means_
0 收藏&&|&&2
你可能感兴趣的文章
12 收藏，1.8k
29 收藏，6.5k
你好，我觉得你写得非常简介明了，但是我认为这个描述高斯混合模型的缺点是错误的:
"如果数据不服从正态分布、偏态分布，会出现偏差"
我想你的意思是，数据不符合混合的正态/偏态，会出现偏差吧．
当数据符合正态，偏态分布的时候，相当于数据是单峰的，无法聚类．
你好，我觉得你写得非常简介明了，但是我认为这个描述高斯混合模型的缺点是错误的:
_&如果数据不服从正态分布、偏态分布，会出现偏差&_
我想你的意思是，数据不符合**混合**的正态/偏态，会出现偏差吧．
当数据符合正态，偏态分布的时候，相当于数据是单峰的，无法聚类．
多谢指正！我这里表述有点不明确，其实我这里说的数据是指单个 cluster 的数据。我理解的是高斯混合默认当前数据是由多个符合正态或者偏态分布的单峰数据（潜在的 cluster）叠加组成，如果某个 cluster
同假设不符会对算法拟合造成影响，导致算法出现偏差。
多谢指正！我这里表述有点不明确，其实我这里说的数据是指单个 cluster 的数据。我理解的是高斯混合默认当前数据是由多个符合正态或者偏态分布的单峰数据（潜在的 cluster）叠加组成，如果某个 cluster
同假设不符会对算法拟合造成影响，导致算法出现偏差。
?赞，是这个意思的
?赞，是这个意思的
分享到微博？
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。k-means算法研究综述_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
k-means算法研究综述
&&k-means算法研究综述
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢K-Means聚类算法
KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。
K-Means聚类算法主要分为三个步骤：
(1)第一步是为待聚类的点寻找聚类中心
(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去
(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止
下图展示了对n个样本点进行K-means聚类的效果，这里k取2：
(a)未聚类的初始点集
(b)随机选取两个点作为聚类中心
(c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去
(d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
(e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去
(f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
Matlab实现：
执行结果：
6 iterations, total sum of distances = 204.821
10 iterations, total sum of distances = 205.886
16 iterations, total sum of distances = 204.821
9 iterations, total sum of distances = 205.886
9 iterations, total sum of distances = 205.886
8 iterations, total sum of distances = 204.821
8 iterations, total sum of distances = 204.821
14 iterations, total sum of distances = 205.886
14 iterations, total sum of distances = 205.886
6 iterations, total sum of distances = 204.821
1.0754&& -1.0632
-1.1442&& -1.1121
&& 64.2944
&& 63.5939
&& 76.9329
聚类效果：
Matlab R2012a Documentation：
stackoverflow：kmeans example in matlab does not run：
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}