机器学习K-mans.doc

机器学习报告 非监督学习-----一些聚类算法 聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术 该图为Kmeans方法分为3类和4类得结果.可以发现该聚类中心并不是集合中本 身的点。 图为用Kmeans方法得到的3类和4类的结果 从图中可以看出，Kmedoid方法分类中，聚类中心点全是集合本身的点，且与Kmeans方法比较，聚类中心点近似的，且分类结果也差不多。 注：Kmeans方法和Kmedoid方法对初始值要求比较敏感，且要求各类的密度差不多。 （三)谱聚类 为了能在任意形状的样本空间上聚类，且收敛于全局最优解，现研究利用谱方法来聚类。谱方法聚类是由数据点间相似关系建立矩阵，获取该矩阵的前n个特征向量，并且用它们来聚类不同的数据点。谱聚类方法建立在图论中的谱图理论上。谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的，这样就得到一个基于相似度的无向G(V, E)，于是聚类问题就可以转化为图的划分问题。基于的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。 Shi和MalikEz提出了基于将图划分为两个子图的2-way目标函数Ncut： 其中cut(A，B)是子图A，B间的边，又叫“边切集”。其中为连点之间定义的权重。 我们可以看出改进后目标函数不仅满足类间样本间的相似度小，也满足类内样本间的相似度大。 现令P是A的划分指示向量： 其中为A中样本的个数，为B中样本的个数，为样本的总数。 那么：问题可转化为： 其中，且满足 求该问题中的是离散的，为了解决该问题，我们将问题进行放松为连续的情况，转化为： S.t 可得：由L=D-W的性质，该问题的解为矩阵对应的第二最小特征值，取对应的特征向量。 对应于第二最小特征值对应的特征向量X2则包含了图的划分信息。人们可以根据启发式规则在X2寻找划分点i，使得值大于等于X2i的划为A类，而小于X2i的划为B类。 注：L=D-W称为Laplacian矩阵： Laplacian矩阵是对称半正定矩阵，因此它的所有特征值是实数且是非负的：如果G是c个连接部件，那么L有c个等于0的特征向量。如果G是连通的，第二个最小特征值不为0，则它是G的连接代数值(Fiedter-value)。其对应的特征向量为Fiedler向量。 具体算法叙述如下： Stept1:通过样本集建立无向加权图G，根据G构造W和D； Stept2:计算L=D-W的第二最小特征值及对应的Fiedler向量； Stept3:根据启发式规则在寻找划分点i，使得值大于等于X2i的划为A类，而 小于X2i的划为B类; 注：对于大于2类的k情况，在第二步中取L的除了最小特征值外剩下的k个特征值和对应的特征向量。然后对特征向量空间的特征向量用k-means方法聚类。 （四）模糊C-means 方法 模糊聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算技术求最优代价函数，在基于概率算法的聚类方法中将使用概率密度函数，为此要假定合适的模型，模糊聚类算法的向量可以同时属于多个聚类。 K-均值算法在聚类过程中，每次得到的结果虽然不一定是期望的结果，但类别之间的边界是明确的，聚类中心根据各类当前具有的样本进行修改。模糊C-均值算法在聚类过程中，每次得到的类别边界任然是模糊的，每次聚类中心的修改都要用到所有的样本，此外，聚类准则也体现了模糊行。 现先虑属度解释，隶属度函数是表示一个对象隶属于集合A的程度的函数，通常记做，其自变量范围是所有可能属于集合A的对象（即集合A所在空间中的所有点），取值范围是[0,1]，即。表示完全隶属于集合A，相当于传统集合概念上的。一个定义在空间上的隶属度函数就定义了一个模糊集合A，或者叫定义在论域上的模糊子集。对于有限个对象模糊集合可以表示为： (6.1) 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。 对于模糊C均值聚类算法的步骤还是比较简单的，模糊C均值聚类（FCM），即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬C均值聚类（HCM）方法的一种改进。 FCM把n个向量分为c个模糊组，并求每组的聚类中心，使得非相似性指