图像处理—聚类算法原理

1、聚类分析（Clusteranalysis）Clustering（聚类）和Classfcation（分类）Clustering中文翻译作“聚类”，简单地说就是把相似的东西分到一组，同Classification分类）不同，对于一个classifier,通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个classifier会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做supervisedlearning（监督学习），而在聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需

2、要知道如何计算相似度就可以开始工作了，因此clustering通常并不需要使用训练数据进行学习，这在MachineLearning中被称作unsupervisedlearning（无监督学习）。举一个简单的例子：现在有一群小学生，你要把他们分成几组，让组内的成员之间尽量相似一些，而组之间则差别大一些。最后分出怎样的结果，就取决于你对于“相似”的定义了咽此，在分类前，一定要知道，每一类的特征到底是什么），比如，你决定男生和男生是相似的，女生和女生也是相似的，而男生和女生之间则差别很大，这样，你实际上是用一个可能取两个值“男”和“女”的离散变量来代表了原来的一个小学生，我们通常把这样的变量叫做特征

3、”。实际上，在这种情况下，所有的小学生都被映射到了两个点的其中一个上，已经很自然地形成了两个组，不需要专门再做聚类了。另一种可能是使用“身高”这个特征。我在读小学候，每周五在操场开会训话的时候会按照大家住的地方的地域和距离远近来列队，这样结束之后就可以结队回家了。除了让事物映射到一个单独的特征之外，一种常见的做法是同时提取N种特征，将它们放在一起组成一个N维向量（特征向量），从而得到一个从原始数据集合到N维向量空间的映射你总是需要显式地或者隐式地完成这样一个过程，因为许多机器学习的算法都需要工作在一个向量空间中。聚类分析聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程

4、。聚类分析的目标就是在相似的基础上收集数据来分类。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。Clusteranalysisorclusteringisthetaskofassigningasetofobjectsintogroups（calledclusters）sothattheobjectsinthesameclusteraremoresimilar（insomesenseoranother）toeachotherthantothoseinotherclusters.1Clusteranalysisits

5、elfisnotonespecificalgorithm,butthegeneraltasktobesolved.Itcanbeachievedbyvariousalgorithmsthatdiffersignificantlyintheirnotionofwhatconstitutesaclusterandhowtoefficientlyfindthem.Popularnotionsofclustersincludegroupswithlowdistancesamongtheclustermembers,denseareasofthedataspace,intervalsorparticul

6、arstatisticaldistributions.Clusteringcanthereforebeformulatedasamulti-objectiveoptimizationproblem.Theappropriateclusteringalgorithmandparametersettings（includingvaluessuchasthedistancefunctiontouse,adensitythresholdorthenumberofexpectedclusters）dependontheindividualdatasetandintendeduseoftheresults

7、.Clusteranalysisassuchisnotanautomatictask,butaniterativeprocessofknowledgediscoveryorinteractivemulti-objectiveoptimizationthatinvolvestrialandfailure.Itwilloftenbenecessarytomodifypreprocessingandparametersuntiltheresultachievesthedesiredproperties.K-means（K-均值聚类法）K-均值算法表示以空间中k个点为中心进行聚类，对最靠近他们的对象归

8、类。该算法的最大优势在于简洁和快速。劣势在于对于一些结果并不能够满足需要，因为结果往往需要随机点的选择非常巧合。算法归纳为（J.MacQueen,1967）:（1）初始化：选择（或人为指定）某些记录作为凝聚点循环：2.1按就近原则将其余记录向凝聚点凝集2.2计算出各个初始分类的中心位置（均值）2.3用计算出的中心位置重新进行聚类如此反复循环，直到凝聚点位置收敛为止方法特点通常要求已知类别数节省运算时间样本量大于100时有必要考虑只能使用连续性变量k-means对于需要进行聚类的数据有一个基本假设：对于每一个cluster，我们可以选出一个中心点(center)，使得该cluster中的所有的点

9、到该中心点的距离小于到其他cluster的中心的距离。虽然实际情况中得到的数据并不能保证总是满足这样的约束，但这通常已经是我们所能达到的最好的结果，而那些误差通常是固有存在的或者问题本身的不可分性造成的。例如下图所示的两个高斯分布，从两个分布中随机地抽取一些数据点出来，混杂到一起，现在要让你将这些混杂在一起的数据点按照它们被生成的那个分布分开来：0.沁由于这两个分布本身有很大一部分重叠在一起了，例如，对于数据点2.5来说，它由两个分布产生的概率都是相等的，你所做的只能是一个猜测；稍微好一点的情况是2，通常我们会将它归类为左边的那个分布，因为概率大一些，然而此时它由右边的分布生成的概率仍然是比较

10、大的，我们仍然有不小的几率会猜错。而整个阴影部分是我们所能达到的最小的猜错的概率，这来自于问题本身的不可分性，无法避免。因此，我们将:-means所依赖的这个假设看作是合理的。基于这样一个假设，我们再来导出k-means所要优化的目标函数：设我们一共有N个数据点需要分为K个cluster，k-means要做的就是最小化YKJ=工工-阳F,-i=Lk=I这个函数，其中，在数据点n被归类到clusterk的时候为1，否则为0。直接寻找和:来最小化、并不容易，不过我们可以采取迭代的办法：先固定，选择最优的，很容易看出，只要将数据点归类到离他最近的那个中心就能保证最小。下一步则固定，再求最优的:将对:

11、求导并令导数等于零，很容易得到、最小的时候：应该满足：=mean(xn),其中xn为属于clusterk的点的坐标亦即丿从的值应当是所有clusterk中的数据点的平均值。由于每一次迭代都是取到的最小值，因此只会不断地减小(或者不变)，而不会增加，这保证了k-means最终会到达一个极小值。虽然k-means并不能保证总是能得到全局最优解，但是对于这样的问题，像k-means这种复杂度的算法，这样的结果已经是很不错的了。下面我们来总结一下k-means算法的具体步骤：选定K个中心丿的初值。这个过程通常是针对具体的问题有一些启发式的选取方法，或者大多数情况下采用随机选取的办法。因为前面说过k-means并不能保证全局最优，而是否能收敛到全局最优解其实和初值的选取有很大的关系，所以有时候我们会多次选取初值跑k-means，并取其中最好的一