一、层次聚类
1、层次聚类的原理及分类
1)层次法(Hierarchical methods)先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算类与类之间的距离,将距离最近的类合并为一个大类。不停的合并,直到合成了一个类。其中类与类的距离的计算方法有:最短距离法,最长距离法,中间距离法,类平均法等。比如最短距离法,将类与类的距离定义为类与类之间样本的最短距离。
层次聚类算法根据层次分解的顺序分为:自下底向上与自上向下,即凝聚的层次聚类算法与分裂的层次聚类算法(agglomerative与divisive),也可以理解为自下而上法(bottom-up)与自上而下法(top-down)。自下而上法就就是一开始每个个体(object)都就是一个类,然后根据linkage寻找同类,最后形成一个“类”。自上而下法就就是反过来,一开始所有个体都属于一个“类”,然后根据linkage排除异己,最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分,只就是在实际应用的时候要根据数据特点以及您想要的“类”的个数,来考虑就是自上而下更快还就是自下而上更快。至于根据Linkage判断“类”的方法就就是最短距离法、最长距离法、中间距离法、类平均法等等(其中类平均法往往被认为就是最常用也最好用的方法,一方面因为其良好的单调性,另一方面因为其空间扩张/浓缩的程度适中)。为弥补分解与合并的不足,层次合并经常要与其它聚类方法相结合,如循环定位。
2)Hierarchical methods中比较新的算法有BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约与聚类)主要就是在数据量很大的时候使用,而且数据类型就是numerical。首先利用树的结构对对象集进行划分,然后再利用其它聚类方法对这些聚类进行优化;ROCK(A Hierarchical Clustering Algorithm for Categorical Attributes)主要用在categorical的数据类型上;Chameleon(A Hierarchical Clustering Algorithm Using Dynamic Modeling)里用到的linkage就是kNN(k-nearest-neighbor)算法,并以此构建一个graph,Chameleon的聚类效果被认为非常强大,比BIRCH好用,但运算复杂度很高,O(n^2)。
2、层次聚类的流程
凝聚型层次聚类的策略就是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇中,或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类,它们只就是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程:
(1) 将每个对象瞧作一类,计算两两之间的最小距离;
(2) 将距离最小的两个类合并成一个新类;
(3) 重新计算新类与所有类之间的距离;
(4) 重复(2)、(3),直到所有类最后合并成一类。
聚类的效果如下图,黑色就是噪音点:
另外我们可以瞧出凝聚的层次聚类并没有类似基本K均值的全局目标函数,没有局部极小问题或就是很难选择初始点的问题。合并的操作往往就是最终的,一旦合并两个簇之后就不会撤销。当然其计算存储的代价就是昂贵的。
3、层次聚类的优缺点
优点:1,距离与规则的相似度容易定义,限制少;2,不需要预先制定聚类数;3,可以发现类的层次关系;4,可以聚类成其它形状
缺点:1,计算复杂度太高;2,奇异值也能产生很大影响;3,算法很可能聚类成链状
r语言中使用hclust(d, method = "complete", members=NULL):进行层次聚类。d为距离矩阵;method表示类的合并方法,single最短距离法,complete最长距离法,median中间距离法,mcquitty 相似法,average 类平均法,centroid重心法,ward离差平方与法;members为NULL或d长度的矢量。
二、划分聚类法k-means
基于划分的方法(Partition-based methods):其原理简单来说就就是,想象您有一堆散点需要聚类,想要的聚类效果就就是“类内的点都足够近,类间的点都足够远”。首先您要确定这堆散点最后聚成几类,然后挑选几个点作为初始中心点,再然后依据预先定好的启发式算法(heuristic algorithms)给数据点做迭代重置(iterative relocation),直到最后到达“类内的点都足够近,类间的点都足够远”的目标效果。
Partition-based methods聚类多适用于中等体量的数据集,但我们也不知道“中等”到底有多“中”,所以不妨理解成,数据集越大,越有可能陷入局部最小。
1、Kmeans算法的原理
k-means算法以k为参数,把n个对象分成k个簇,使簇内具有较高的相似度,而簇间的相似度较低。k-means算法的处理过程如下:首先,随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心,即选择K个初始质心;对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛,直到质心不发生明显的变化。通常,采用平方误差准则,误差的平方与SSE作为全局的目标函
数,即最小化每个点到最近质心的欧几里得距离的平方与。此时,簇的质心就就是该簇内所有数据点的平均值。
选择K个点作为初始质心
repeat
将每个点指派到最近的质心,形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数
时间复杂度:O(tKmn),其中,t为迭代次数,K为簇的数目,m为记录数,n为维数
空间复杂度:O((m+K)n),其中,K为簇的数目,m为记录数,n为维数
K-Means 算法的详细过程
从上图中,我们可以瞧到,A, B, C, D, E 就是五个在图中点。而灰色的点就是我们的种子点,也就就是我们用来找点群的点。有两个种子点,所以K=2。
然后,K-Means的算法如下:
①随机在图中取K(这里K=2)个种子点。
②然后对图中的所有点求到这K个种子点的距离,假如点Pi离种子点Si最近,那么Pi属于Si 点群。(我们可以瞧到A,B属于上面的种子点,C,D,E属于下面中部的种子点)
③接下来,我们要移动种子点到属于她的“点群”的中心。(见图上的第三步)
④然后重复第2)与第3)步,直到,种子点没有移动(我们可以瞧到图中的第四步上面的种子点聚合了A,B,C,下面的种子点聚合了D,E)。
聚类的效果如下图,折线就是历次循环时3个簇的质心的更新轨迹,黑点就是初始质心:
我们查瞧基本K均值算法实现步骤及上面的聚类效果可以发现,该聚类算法将所有数据点都进行了指派,不识别噪音点。另外选择适当的初试质心就是基本K均值过程的关键。
2、k均值的优缺点及分类
优点:1,简单,易于理解与实现;2,时间复杂度低
缺点:
