来源：蜘蛛抓取(WebSpider)
时间：2017-10-14 10:40
标签：
k means聚类算法
基于K- means 算法和FCM算法的聚类研究_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
基于K- means 算法和FCM算法的聚类研究
&&基于K- means 算法和算法的聚类研究
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢安全检查中...
请打开浏览器的javascript，然后刷新浏览器
< 浏览器安全检查中...
还剩 5 秒&转自：http://blog.csdn.net/zouxy09/article/details/9982495
Deep Learning论文笔记之（一）K-means特征学习
&&&&&&&&&自己平时看了一些论文，但老感觉看完过后就会慢慢的淡忘，某一天重新拾起来的时候又好像没有看过一样。所以想习惯地把一些感觉有用的论文中的知识点总结整理一下，一方面在整理过程中，自己的理解也会更深，另一方面也方便未来自己的勘察。更好的还可以放到博客上面与大家交流。因为基础有限，所以对论文的一些理解可能不太正确，还望大家不吝指正交流，谢谢。
&&&&&&& 本文的论文来自：
, Adam Coates and Andrew Y. Ng. In Neural Networks: Tricks of the Trade, Reloaded, Springer LNCS, 2012
&&&&&&&&&下面是自己对其中的一些知识点的理解：
《Learning Feature Representations with K-means》
&&&&&&&&&自从Deep Learning之风盛起之时到现在，江湖上诞生了很多都可以从无标签数据中学习到深度的分级的特征的算法。大部分情况，这些算法都涉及到一个多层网络，而训练和调整这个网络需要很多tricks。最近，我们发现K-means聚类算法也可以被作为一个非常快的训练方法。它的优点是快！容易实现！当然了，K-means也不是万能神丹，它也存在自身的局限性。在本文中，我们就关注K-means的方方面面。总结了最近的K-means算法的效果和介绍使用k-means来有效地学习图像的特征的一些技巧。
&&&&&&&&&非监督学习的一般流程是：先从一组无标签数据中学习特征，然后用学习到的特征提取函数去提取有标签数据特征，然后再进行分类器的训练和分类。之前说到，一般的非监督学习算法都存在很多hyper-parameters需要调整。而，最近我们发现对于上面同样的非监督学习流程中，用K-means聚类算法来实现特征学习，也可以达到非常好的效果，有时候还能达到state-of-the-art的效果。亮瞎了凡人之俗眼。
&&&&&&&&&托“bag of features&”的福，K-means其实在特征学习领域也已经略有名气。今天我们就不要花时间迷失在其往日的光芒中了。在这里，我们只关注，如果要K-means算法在一个特征学习系统中发挥良好的性能需要考虑哪些因素。这里的特征学习系统和其他的Deep
Learning算法一样：直接从原始的输入（像素灰度值）中学习并构建多层的分级的特征。另外，我们还分析了K-means算法与江湖中其他知名的特征学习算法的千丝万缕的联系（天下武功出少林，哈哈）。
&&&&&&&&&经典的K-means聚类算法通过最小化数据点和最近邻中心的距离来寻找各个类中心。江湖中还有个别名，叫“矢量量化vector quantization”（）。我们可以把K-means当成是在构建一个字典D?Rnxk，通过最小化重构误差，一个数据样本x(i)?Rn可以通过这个字典映射为一个k维的码矢量。所以K-means实际上就是寻找D的一个过程：
&&&&&& 这里，s(i)就是一个与输入x(i)对应的码矢量。D(j)是字典D的第j列。K-means毕生的目标就是寻找满足上面这些条件的一个字典D和每个样本x(i)对应的码矢量s(i)。我们一起来分析下这些条件。首先，给定字典D和码矢量s(i)，我们需要能很好的重构原始的输入x(i)。数学的表达是最小化x(i)和它的重构D
s(i)。这个目标函数的优化需要满足两个约束。首先，|| s(i)||0&=1，意味着每个码矢量s(i)被约束为最多只有一个非零元素。所以我们寻找一个x(i)对应的新的表达，这个新的表达不仅需要更好的保留x(i)的信息，还需要尽可能的简单。第二个约束要求字典的每列都是单位长度，防止字典中的元素或者特征变得任意大或者任意小。否则，我们就可以随意的放缩D(j)和对应的码矢量，这样一点用都木有。
&&&&&&&&&这个算法从精神层面与其他学习有效编码的算法很相似，例如sparse coding：
&&&&&&&& Sparse coding也是优化同样类型的重构。但对于编码复杂度的约束是通过在代价函数中增加一个惩罚项λ|| s(i)||1，以限制s(i)是稀疏的。这个约束和K-means的差不多，但它允许多于一个非零值。在保证s(i)简单的基础上，可以更准确的描述x(i)。
&&&&&&&&&虽然Sparse coding比K-means性能要好，但是Sparse coding需要对每个s(i)重复的求解一个凸优化问题，当拓展到大规模数据的时候，这个优化问题是非常昂贵的。但对于K-means来说，对s(i)的优化求解就简单很多了：
&&&&&&&&&这个求解是很快的，而且给定s求解D也很容易，所以我们可以通过交互的优化D和s（）来快速的训练一个非常大的字典。另外，K-means还有一个让人青睐的地方是，它只有一个参数需要调整，也就是要聚类的中心的个数k。
二、数据、预处理和初始化
&&&&&&&&&这里我们采用的是包含很多小的图像patches的数据集，每个patch是16x16的灰度图，对每个patch样本我们将其拉成一个256维的列向量。这些patches可以在无标签图像中随机的裁剪得到。为了建立一个“完备complete”的字典（至少有256个类中心的字典），我们需要保证有足够的用以训练的patches，这样每个聚类才会包含一定合理数量的输入样本。对于16x16的灰度patch来说，样本数m=100,000个是足够的。实际上，训练一个k-means字典比其他的算法（例如sparse
coding）需要的训练样本个数要多，因为在k-means中，一个样本数据只会贡献于一个聚类的中心，换句话说一个样本只能属于一个类，与其他类就毫无瓜葛了，该样本的信息全部倾注给了它的归宿（对应类的中心）。
2.1、预处理&Pre-processing
&&&&&&&&&在训练之前，我们需要对所有的训练样本patches先进行亮度和对比度的归一化。具体做法是，对每个样本，我们减去灰度的均值和除以标准差。另外，在除以标准差的时候，为了避免分母为0和压制噪声，我们给标准差增加一个小的常数。对于[0,
255]范围的灰度图，给方差加10一般是ok的：
&&&&&&&&&对训练数据进行归一化后，我们就可以在上面运行k-means算法以获得相应的聚类中心了（字典D的每一列），可视化在图a中，可以看到，k-means趋向于学习到低频的类边缘的聚类中心。但不幸的是，这样的特征不会有比较好的识别效果，因为邻域像素的相关性（图像的低频变化）会很强。这样K-means就会产生很多高度相关的聚类中心。而不是分散开聚类中心以更均匀的展开训练数据。所以我们需要先用白化来去除数据的相关性，以驱使K-means在正交方向上分配更多的聚类中心。
&&&&&& 图a是由k-means从没有经过白化处理的自然图像中学习到的聚类中心。图b展示了没有和有白化的效果。左边是没有经过白化的，因为数据存在相关性，所以聚类中心会跑偏。右边是经过白化后的，可以看到聚类中心是更加正交的，这样学习到的特征才会不一样。图c展示的是从经过白化后的图像patches学习到的聚类中心。
&&&&&&&&&实现whitening白化一个比较简单的方法是ZCA白化（）。我们先对数据点x的协方差矩阵进行特征值分解cov(x)=VDVT。然后白化后的点可以表示为：
&&&&&&& ?zca是一个很小的常数。对于对比度归一化后的数据，对16x16的patch，可以设?zca=0.01，对8x8的patch，可以设?zca=0.1&。需要注意的一点是，这个常数不能太小，如果太小会加强数据的高频噪声，会使特征学习更加困难。另外，因为数据的旋转对K-means没有影响，所以可以使用其他的白化变换方法，例如PCA白化（与ZCA不同只在于其旋转了一个角度）。
&&&&&&&&&在白化后的数据中运行k-means可以得到清晰的边缘特征。这些特征和sparse coding啊，ICA啊等等方法学到的初级特征差不多。如图c所示。另外，对于新的数据，可能需要调整归一化的参数?和白化的参数?zca，以满足好的效果（例如，图像patches具有高对比度，低噪声和少低频波动）。
2.2、初始化&Initialization
&&&&&&&&&一般的K-means聚类算法存在一个比较常见的问题，就是会出现空的聚类。通俗的讲，就是它聚类后的一个类里面居然没有样本（接近于没有）。那么很明显，这个类就一点意义都没有，留着反而还会危害人间。这我们当然得做些努力来避免这种情况的发生了。那就得找原因了吧。其实这一定情况下可以认为是中心的初始化的不恰当导致的。常用的中心初始化方法就是随机地从样本中挑k个出来作为k个初始的聚类中心。但这不是个明智的选择。它有可能会导致图像趋于稠密聚集某些区域，因为如果随机选择的patches，也就是训练样本本身就在某个区域分布非常密，那么我们随机去选择聚类中心的时候，就会出现就在这个数据分布密集的地方被选出了很多的聚类中心（因为原数据分布密集，所以被选中的概率会大）。这是不好的，因为本身这个密集的区域，一个聚类中心才是好的，你硬搞出几个聚类中心，好好的队伍就会被强拆了，还搞得其他比较分散的数据点找不到归宿，因为聚类中心离它好遥远，大部分的聚类中心都让富二代给占有了，社会资源分配不当啊，哈哈。这样还会出现一种情况，就是如果样本分布密集的话，它们都几乎从属于一个聚类中心，那么其他聚类中心就几乎没有样本属于它。这样也不好。所以，一个比较好的初始化方式就是从一个正态分布中随机初始化聚类中心，然后归一化他们到单位长度。另外，因为经过了白化的阶段，我们期望我们的数据的主要成分已经在一定程度上被组织为球面spherical分布了，而在一个球面上随机地选取一些向量结果就显得温柔多了。
&&&&&&&&&另外，还存在一些启发性的方法去改善k-means的这个问题。例如启发性得重新初始化空的聚类中心。实践中证明，这种方法对图像数据的效果比较好。当空类出现的时候，我们再随机挑选样本来替代这个空类中心，一般都是足够有效的。但好像一般也没啥必要。事实上，对于一个足够规模的实现来说，我们会训练很多的聚类中心，如果一个聚类中心包含的数据点太少了，我们直接抛弃它就好了，不要这个聚类中心了，因为俺们的聚类中心够多，多你一个不多，少你一个不少的。
&&&&&&&&&还有一种改善的方法叫做聚类中心的抑制更新damped updates。它在每次的迭代中，都会根据以下方式更新聚类中心：
&&&&&&&&&需要注意的是，这种形式的抑制并不会对“大”的聚类有很大的影响（因为XST的第j列会比Dold的第j列要大得多），它只能防止小的聚类在一次的迭代过程中被拉得太远（就像滤波的方法一样，新的值不仅受当前值的影响，还受历史值的影响，这样就会防止这个值出现突变。例如a_old=1，新的值为5，那么a_new=0.5*5+0.5*a_old=3，也就是a_new会跳到3而不是一下子跳到5，当然还取决于前面的权值0.5，看我们更信任新值还是历史值。但如果新值很大，那就没有特别大的效果了。例如新值为99，那么a_new=50，它还是比a_old=1要大多了）。我们将这个k-means训练算法概括如下：
三、与稀疏特征学习的比较
&&&&&&&&&上面我们提到，K-means能像ICA，sparse coding一样学习到方向性的边缘特征。那我们会怀疑，这是偶然吗（因为边缘太常见了，所以一般的学习模型都可以发现它们）？！还是说这隐含着K-means本身就具有和ICA相似的稀疏分解的能力。因为每个s(i)只能包含一个非零元素（相应的聚类中心），所以k-means会尝试去学习一个可以很好的描述整个输入图像的聚类中心。因此，它也无法保证一定可以学到和ICA或者sparse
coding学到的滤波器一样。这些算法可以学习到真正的“分布式”描述，因为一张图像可以通过一个字典的几列来联合描述，而不是只通过一列。尽管如此，k-means在天时地利人和的时候依然能发现数据的稀疏投影，虽然作为一个聚类方法它好像没有明确的通过公式告诉我们它还能做这个。所以我们看到的结果也不是幻觉或者偶然。
&&&&&&&&&虽然k-means和ICA和sparse coding有着经验性的相似，但它有一个很大的缺点：它发现数据稀疏投影方向的能力很大程度上取决于输入数据的维数和数量。如果数据的维数增加，我们就需要增加大量的样本，才能得到好的结果。这点就比较难伺候了。例如，在实验中，对64x64的patch，我们用了500,000个样本来训练k-means，结果还是很烂。我们只学习到了很少的边缘。在这种情况下，就会存在很多的接近空数据点的聚类，所以就需要非常多的数据才能让k-means发挥光与热。所以，这就存在一个折衷了，是否要采用k-means，就要看我们的数据有多少维，我们能提供多少数据（一般要达到相同的结果，比sparse
coding要多很多）。对于适当的维度（例如100维），使用k-means的训练速度比其他算法快那么多，那么我情愿花点力气去提供更多的样本给它。但对于很高维的数据，采用其他算法例如sparse coding会比k-means性能要好，甚至速度也要更快。
4、在图像识别上的应用
&&&&&&&&&在这里没什么好说的，k-means就作为一种学习特征的方法，取代一般的非监督学习过程里面的特征学习那块就好了。可以参考UFLDL中的“”和“”。另外，文中也介绍了一些选择参数的方法，很多论文也可以看到，这里也不说了。这里比较有趣的一点是，文中说到，根据观测的结果，如果我们的识别系统设计有大量有效的有标签训练数据的话，那么选择一个简单的快速的前向编码器（特征映射函数）的话，效果都可以挺好。但如果我们的有标签训练数据不多，那么采用一个复杂的编码函数会更好。例如，在大规模情况下，采用软阈值非线性函数:
就可以工作的比较好。其中，ɑ是个可调的常数。相反，复杂的sigmoid非线性函数效果就没那么好了：
5、构建深度网络
&&&&&&&&&在上面一个章节中，我们是先从一些无标签数据中随机提取一些patches，然后用k-means来学习其中的特征，得到一个字典。然后对于一个大的图像，我们用这个字典（特征提取器）去卷积图像的每个局部感受野，从而提取整幅图像的特征。然后我们再通过一个pooling步骤去对提取到的特征进行绛维。当然了，如果我们可以通过上面这些提取到的特征去学习更高层的特征，那就更好了。最简单的方法就是，对无标签数据集X中，我们通过上面的方法得到pooling后的特征后，然后得到新的数据集Z，我们再在这个数据库Z中用同样的特征学习过程去学习新的特征。从而得到第二层的特征。但这有个问题，就是这个Z一般都是非常高维的，所以需要用非常大的特征字典来学习（例如k=10000甚至更多）。但这样，对k-means的要求也高了，我们需要提供更多的样本来训练。
&&&&&&&&&该文提出了一种pair-wise “dependency test&的方法来改善这个问题。我们通过一个“能量相关”来定义数据集Z中两个特征zj和zk的依赖性。我们需要在Z的特征表达之上学习更高级的特征。使用“dependency
test&，我们可以以一种相对简单的方式来选择合理的感受野：我们挑了一个特征z0，然后使用“dependency test&来寻找和z0具有很强依赖性的R特征。然后只用这R特征作为k-means算法的输入。如果我们选取的R足够小（例如100或者200），那么归一化和白化过后，再用k-means来训练一般都可以达到好的效果。因为输入的维数很小，所以我们只需要训练一百个左右的聚类中心，这样使用少量的训练样本就可以运行k-means了。
&&&&&&&&&详细的算法介绍和效果见原论文。
&&&&&&&&&本文中，我们讨论了用k-means来搭建特征学习系统的一些关键点，现在总结如下：
1、需要先对数据进行均值和对比度的归一化。
2、使用白化来消去数据的相关性。注意白化参数的选择。
3、通过高斯噪声和归一化来初始化k-means的聚类中心。
4、使用抑制更新来避免空聚类和增加稳定性。
5、注意数据的维数和稀疏的影响。K-means通过寻找数据分布的”heavy-tailed&方向来找到输入数据的稀疏投影。但如果数据没有经过适当的白化，或者数据维数太高了，或者存在无效的数据，那么效果往往是不好的。
6、对于高维数据，k-means需要增加大量的样本来能得到好的效果。
7、一些外在的参数（例如pooling，编码方法的选择等等）对于系统性能的影响比学习算法本身要大。所以最好先化时间和成本在通过更多的交叉检验的方法来挑选好的参数比花更多的成本在学习算法上要明智的多。
8、对于图像识别来说，更多的聚类中心往往是有帮助的。当然，前提是我们要有足够的训练样本。
9、当有标签数据多的时候，采用一个简单的编码器。如果标签数据有限（例如每类只有百来个训练样本），那么采用一个复杂的编码器会更好。
10、尽可能地使用局部感受野。K-means是否成功，其瓶颈在于输入数据的维数。越低越好。如果无法手动的选择好的局部感受野，那么尝试去通过一个自动的依赖性测试dependency test来帮助从数据中挑选出一组低维的数据。这对于深度网络来说是很有必要的。
本文已收录于以下专栏：
相关文章推荐
Deep Learning论文笔记之（一）K-means特征学习
http://blog.csdn.net/zouxy09
        
自己平时看了一...
Deep Learning论文笔记之（一）K-means特征学习
http://blog.csdn.net/zouxy09
         ...
Deep Learning论文笔记之（一）K-means特征学习
 转载出处：点击打开链接
      本文的论文来自：
Learning Feature Representatio...
Deep Learning论文笔记之（一）K-means特征学习
转自：http://blog.csdn.net/zouxy09
         自己平时看了一些论文，但老感觉...
聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术，聚类分析是指事先不了解一批样品中的每个样品的类别或者其他的先验知识，而唯一的分类依据是样品的特征，利用某种相似性度量的方法，把特征相同的或相近...
深度网络高层特征可视化
http://blog.csdn.net/zouxy09
  
        本文的论文来自：
Dumitru Erhan, Aaron Courvill...
Deep Learning论文笔记之（七）深度网络高层特征可视化
转自：http://blog.csdn.net/zouxy09
         自己平时看了一些论文，但老感觉...
Deep Learning论文笔记之（七）深度网络高层特征可视化
http://blog.csdn.net/zouxy09
        
自己平时看了一...
Deep Learning论文笔记之（三）单层非监督学习网络分析
http://blog.csdn.net/zouxy09
         ...
Deep Learning论文笔记之（三）单层非监督学习网络分析
转自：http://blog.csdn.net/zouxy09
         自己平时看了一些论文，但老感觉...
他的最新文章
讲师：王哲涵
讲师：韦玮
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)1.基本Kmeans算法[1]
选择K个点作为初始质心
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数时间复杂度：O(tKmn)，其中，t为迭代次数，K为簇的数目，m为记录数，n为维数
空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数
2.注意问题
（1）K如何确定
& & & & kmenas算法首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。这样做的前提是我们已经知道数据集中包含多少个簇，但很多情况下，我们并不知道数据的分布情况，实际上聚类就是我们发现数据分布的一种手段，这就陷入了鸡和蛋的矛盾。如何有效的确定K值，这里大致提供几种方法，若各位有更好的方法，欢迎探讨。
1.与层次聚类结合[2]
& & & & &经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。
2.稳定性方法[3]
& & & & 稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有k个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明k个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个k，找到合适的k值。
3.系统演化方法[3]
& & & & &系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为K个聚类时称系统处于状态K。系统由初始状态K=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态Ki，其所对应的聚类结构决定了最优类数Ki。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。
4.使用canopy算法进行初始划分[4]
& & & & & 基于Canopy Method的聚类算法将聚类过程分为两个阶段
& & & & &Stage1、聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy ，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；
& & & & & Stage2、在各个Canopy 内使用传统的聚类方法(如K-means)，不属于同一Canopy 的对象之间不进行相似性计算。
从这个方法起码可以看出两点好处：首先，Canopy 不要太大且Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy 个数完全可以作为这个K值，一定程度上减少了选择K的盲目性。
& & & & &其他方法如贝叶斯信息准则方法（BIC）可参看文献[5]。
（2）初始质心的选取
& & & & & 选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始质心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE（误差的平方和）的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。
& & & & & 第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：（1）样本相对较小，例如数百到数千（层次聚类开销较大）；（2）K相对于样本大小较小
& & & & & &第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少（多了就不是离群点了），它们多半不会在随机样本中出现。计算量也大幅减少。
& & & & & 第四种方法就是上面提到的canopy算法。
（3）距离的度量
& & & & & 常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？
& & & & & 从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。[6]
（4）质心的计算
& & & & &对于距离度量不管是采用欧式距离还是采用余弦相似度，簇的质心都是其均值，即向量各维取平均即可。对于距离对量采用其它方式时，这个还没研究过。
（5）算法停止条件
& & & & &一般是目标函数达到最优或者达到最大的迭代次数即可终止。对于不同的距离度量，目标函数往往不同。当采用欧式距离时，目标函数一般为最小化对象到其簇质心的距离的平方和，如下：
& & & & &当采用余弦相似度时，目标函数一般为最大化对象到其簇质心的余弦相似度和，如下：
（6）空聚类的处理
& & & & & &如果所有的点在指派步骤都未分配到某个簇，就会得到空簇。如果这种情况发生，则需要某种策略来选择一个替补质心，否则的话，平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。另一种方法是从具有最大SSE的簇中选择一个替补的质心。这将分裂簇并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。另外，编程实现时，要注意空簇可能导致的程序bug。
3.适用范围及缺陷
& & & & & &Kmenas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tKmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
#include &iostream&
#include &sstream&
#include &fstream&
#include &vector&
#include &math.h&
#include &stdlib.h&
#define k 3//簇的数目
//存放元组的属性信息
typedef vector&double& T//存储每条数据记录
int dataN//数据集中数据记录数目
int dimN//每条记录的维数
//计算两个元组间的欧几里距离
double getDistXY(const Tuple& t1, const Tuple& t2)
double sum = 0;
for(int i=1; i&=dimN ++i)
sum += (t1[i]-t2[i]) * (t1[i]-t2[i]);
return sqrt(sum);
//根据质心，决定当前元组属于哪个簇
int clusterOfTuple(Tuple means[],const Tuple& tuple){
double dist=getDistXY(means[0],tuple);
int label=0;//标示属于哪一个簇
for(int i=1;i&k;i++){
tmp=getDistXY(means[i],tuple);
if(tmp&dist) {dist=label=i;}
//获得给定簇集的平方误差
double getVar(vector&Tuple& clusters[],Tuple means[]){
double var = 0;
for (int i = 0; i & i++)
vector&Tuple& t = clusters[i];
for (int j = 0; j& t.size(); j++)
var += getDistXY(t[j],means[i]);
//cout&&&sum:&&&sum&&
//获得当前簇的均值（质心）
Tuple getMeans(const vector&Tuple&& cluster){
int num = cluster.size();
Tuple t(dimNum+1, 0);
for (int i = 0; i & i++)
for(int j=1; j&=dimN ++j)
t[j] += cluster[i][j];
for(int j=1; j&=dimN ++j)
//cout&&&sum:&&&sum&&
void print(const vector&Tuple& clusters[])
for(int lable=0; lable&k; lable++)
cout&&&第&&&lable+1&&&个簇：&&&
vector&Tuple& t = clusters[lable];
for(int i=0; i&t.size(); i++)
cout&&i+1&&&.(&;
for(int j=0; j&=dimN ++j)
cout&&t[i][j]&&&, &;
cout&&&)\n&;
void KMeans(vector&Tuple&& tuples){
vector&Tuple& clusters[k];//k个簇
Tuple means[k];//k个中心点
//一开始随机选取k条记录的值作为k个簇的质心（均值）
srand((unsigned int)time(NULL));
for(i=0;i&k;){
int iToSelect = rand()%tuples.size();
if(means[iToSelect].size() == 0)
for(int j=0; j&=dimN ++j)
means[i].push_back(tuples[iToSelect][j]);
int lable=0;
//根据默认的质心给簇赋值
for(i=0;i!=tuples.size();++i){
lable=clusterOfTuple(means,tuples[i]);
clusters[lable].push_back(tuples[i]);
double oldVar=-1;
double newVar=getVar(clusters,means);
cout&&&初始的的整体误差平方和为：&&&newVar&&
int t = 0;
while(abs(newVar - oldVar) &= 1) //当新旧函数值相差不到1即准则函数值不发生明显变化时，算法终止
cout&&&第 &&&++t&&& 次迭代开始：&&&
for (i = 0; i & i++) //更新每个簇的中心点
means[i] = getMeans(clusters[i]);
oldVar = newV
newVar = getVar(clusters,means); //计算新的准则函数值
for (i = 0; i & i++) //清空每个簇
clusters[i].clear();
//根据新的质心获得新的簇
for(i=0; i!=tuples.size(); ++i){
lable=clusterOfTuple(means,tuples[i]);
clusters[lable].push_back(tuples[i]);
cout&&&此次迭代之后的整体误差平方和为：&&&newVar&&
cout&&&The result is:\n&;
print(clusters);
int main(){
char fname[256];
cout&&&请输入存放数据的文件名： &;
cout&&endl&&& 请依次输入: 维数 样本数目&&&
cout&&endl&&& 维数dimNum: &;
cout&&endl&&& 样本数目dataNum: &;
cin&&dataN
ifstream infile(fname);
if(!infile){
cout&&&不能打开输入的文件&&&fname&&
vector&Tuple&
//从文件流中读入数据
for(int i=0; i&dataNum && !infile.eof(); ++i)
getline(infile, str);
istringstream istr(str);
Tuple tuple(dimNum+1, 0);//第一个位置存放记录编号，第2到dimNum+1个位置存放实际元素
tuple[0] = i+1;
for(int j=1; j&=dimN ++j)
istr&&tuple[j];
tuples.push_back(tuple);
cout&&endl&&&开始聚类&&&
KMeans(tuples);
这里是随机选取的初始质心，以鸢尾花的数据集为例，原数据集中1-50为一个簇，51-100为第二个簇，101到150为第三个簇：
第一次运行结果 SSE=97.5905
第二次运行结果 SSE=98.1404
第五次运行结果 SSE=123.397
& & & & &由于初始质心是随机选取的，前两次还算正常，运行到第五次时，第一个簇基本包括了后51-150个记录，第二个簇和第三个簇包含了第1-50个记录，可能的原因就是随机选择初始点时，有两个初始点都选在了1-50个记录中。
[1]Pang-Ning Tan等著，《数据挖掘导论》，2011
[2]Jiawei Han等著，《数据挖掘概念与技术》，2008
[3]聚类分析中类数估计方法的实验比较
[4]/vivounicorn/archive//2186483.html
[5]一种基于贝叶斯信息准则的k均值聚类方法
[6]/question/?nr=1¬i_id=8736954
本文已收录于以下专栏：
相关文章推荐
一、聚类算法的简介
聚类分析是我们数据挖掘中常用的算法，常常用于没有分类，但又有相关相似性的样本研究当中，包括了K-Means、K-中心点和系统聚类三种算法，各自有各自的特点和适用环境。今天我们大圣众包根据网络资源详细介...
概述什么是聚类分析聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。不同的簇类型聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用...
K均值聚类是一种应用广泛的聚类技术，特别是它不依赖于任何对数据所做的假设，比如说，给定一个数据集合及对应的类数目，就可以运用K均值方法，通过最小化均方误差，来进行聚类分析。
因此，K均值实际上是一个...
图像基础知识：
常用的图像空间。
简述你熟悉的聚类算法并说明其优缺点。
请描述以下任一概念：SIFT/SURF  LDA/PCA
请说出使用过的分类器和实现原理。
索贝公司笔试题：图像处理算法工程师
一、填空：
1、常用的插值方法有：最近邻插值、双线性插值、立方卷积插值。
2、常用的边缘检测算子有：一阶: Roberts Cross算子, Prewitt算...
相关文章：
李航《统计学习方法》第二章——用Python实现感知器模型（MNIST数据集）
李航《统计学习方法》第三章——用Python实现KNN算法（MNIST数据集）
K-Means介绍
       K-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据他们的属性分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相...
他的最新文章
讲师：王哲涵
讲师：韦玮
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)
