常用聚类算法比较分析[转贴]

frogfish

1 BIRCH算法　　BIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类特征3元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有两个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数，而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类，非叶子结点为它的子女的最大关键字，可以根据这些关键字进行插人索引，它总结了其子女的信息。　　聚类特征树可以动态构造，因此不要求所有数据读人内存，而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T，则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小，控制其占内存容量。　　BIRCH算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于大数据量。对于给定的M兆内存空间，其空间复杂度为O(M)，时间间复杂度为O(dNBlnB(M/P)).其中d为维数,N为节点数,P为内存页的大小，B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法只适用于类的分布呈凸形及球形的情况，并且由于BIRCH算法需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行。
　　2 CURE算法　　CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行了改进，回避了用所有点或用中心和半径来表示一个类，而是从每一个类中抽取固定数量、分布较好的点作为描述此类的代表点，并将这些点乘以一个适当的收缩因子，使它们更靠近类的中心点。将一个类用代表点表示，使得类的外延可以向非球形的形状扩展，从而可调整类的形状以表达那些非球形的类。另外，收缩因子的使用减小了嗓音对聚类的影响。CURE算法采用随机抽样与分割相结合的办法来提高算法的空间和时间效率，并且在算法中用了堆和K-d树结构来提高算法效率。
　　3 DBSCAN算法　　DBSCAN算法即基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。在DBSCAN算法中，发现一个类的过程是基于这样的事实：一个类能够被其中的任意一个核心对象所确定。为了发现一个类，DBSCAN先从对象集D中找到任意一对象P，并查找D中关于关径Eps和最小对象数Minpts的从P密度可达的所有对象。如果P是核心对象，即半径为Eps的P的邻域中包含的对象不少于Minpts,则根据算法，可以找到一个关于参数Eps和Minpts的类。如果P是一个边界点，则半径为Eps的P邻域包含的对象少于Minpts，P被暂时标注为噪声点。然后，DBSCAN处理D中的下一个对象。　　密度可达对象的获取是通过不断执行区域查询来实现的。一个区域查询返回指定区域中的所有对象。为了有效地执行区域查询，DBSCAN算法使用了空间查询R-树结构。在进行聚类前，必须建立针对所有数据的R*-树。另外，DBSCAN要求用户指定一个全局参数Eps(为了减少计算量，预先确定参数Minpts)。为了确定取值，DBSCAN计算任意对象与它的第k个最临近的对象之间的距离。然后，根据求得的距离由小到大排序，并绘出排序后的图，称做k-dist图。k-dist图中的横坐标表示数据对象与它的第k个最近的对象间的距离；纵坐标为对应于某一k-dist距离值的数据对象的个数。R*-树的建立和k-dist图的绘制非常消耗时间。此外，为了得到较好的聚类结果，用户必须根据k-dist图，通过试探选定一个比较合适的Eps值。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大内存量支持，I/O消耗也非常大。其时间复杂度为O(nlogn)(n为数据量)，聚类过程的大部分时间用在区域查询操作上。DBSCAN算法对参数Eps及Minpts非常敏感，且这两个参数很难确定。
　　4 K-pototypes算法　　K-pototypes算法结合了K-means方法和根据K-means方法改进的能够处理符号属性的K-modes方法，同K-means方法相比，K-pototypes 算法能够处理符号属性。
　　5 CLARANS算法　　CLARANS算法即随机搜索聚类算法，是一种分割聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxneighbor个的一些邻接点，假如找到一个比它更好的邻接点，则把它移人该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调人内存，并且需多次扫描数据集，这对大数据量而言，无论时间复杂度还是空间复杂度都相当大。虽通过引人R-树结构对其性能进行改善，使之能够处理基于磁盘的大型数据库，但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据物人顺序异常敏感，且只能处理凸形或球形边界聚类。
　　6 CLIQUE算法　　CLIQUE 9法即自动子空间聚类算法。该算法利用自顶向上方法求出各个子空间的聚类单元。CUQUE算法主要用于找出在高维数据空间中存在的低维聚类。为了求出d维空间聚类，必须组合给出所有d-1维子空间的聚类，导致其算法的空间和时间效率都较低，而且要求用户输入两个参数：数据取值空间等间隔距离和密度阔值。这2个参数与样木数据紧密相关，用户一般难以确定。CLIQUE算法对数据输人顺序不敏感。

转自：http://www.penna.cn/key/article.asp?id=120

[ 本帖最后由 frogfish 于 2007-7-7 07:40 编辑 ]