|
聚类算法体系的划分可以基于不同的标准，比如凝聚还是分裂、增量还是非增量、确定还是随机、Hard还是Fuzzy等，因此聚类算法体系的划分在各文献中并不统一。灵玖文本聚类算法采用的的划分方法是把聚类算法分为层次聚类、划分聚类、基于网格的方法、基于密度的方法、基于模型的方法。 1 基于层次的聚类 层次聚类将文本对象组织成树，每个叶子节点是一个簇，该树称为一个聚类谱系图。根据树形成是自底向上还是自顶向下的，可以划分为凝聚式和分裂式层次聚类。层次聚类算法复杂度高，但被认为效果比较好，可根据需要获得不同粒度的类。目前在层次聚类研究中出现了一些结合其他聚类方法的多阶段聚类分析技术，比较有代表性的有BIRCH 、CURE、Chameleon等都是基于层次思想的组合算法。 2 基于划分的聚类 基于划分的聚类分析不需要建立起类之间的层次结构，只需要将数据集进行划分，形成一个平面的类结构。比较典型的方法有： (1) K-Means聚类 K-Means聚类分析算法是一种简单效率高的聚类分析算法。K-Means将聚类对象划分成为K个簇（K是事先必须确定的参数），K-Means中每个簇用一个中心表示，该中心定义为簇中对象的平均值。K-Means聚类的缺点是必须事先给出K、对数据输入顺序敏感、不适于发现大小很大的簇、对于噪声和孤立点敏感等。在文本聚类中如果不进行特征选择，特征维度过高的话容易扎堆成几个大类和众多小类。 (2) K-Medoids聚类 K-Medoids聚类是与K-Means类似的一种聚类分析方法，其主要区别在于K-Means使用所有点的均值来代表簇，而K-Medoids则采用类中某个数据对象来代表簇。PAM（Partitioning Around Medoid）是最早提出的K-Medoids算法之一。 (3) 最近邻聚类 最近邻聚类是一种简单的聚类分析。该算法认为，如果某个待处理的对象与现有的所有簇的最小距离小于给定阈值，那么将该对象归入该簇，否则将该对象作为一个新的簇。最近邻聚类不需要事先决定结果类数，适合于类内距离小，类间距离大的情况。结果与样本的输入顺序有关，也与阈值T有关。随着样本集的增大，产生的结果类数可能越来越多，处理的速度会越来越慢。 3. 基于密度的聚类 基于密度的聚类算法将簇看成是数据空间中被低密度区域分割开的高密度区域。密度定义为单位体积内的点数，簇的内部密度大。由于密度是一个局部概念，这类算法又称为局部聚类；基于密度的聚类算法通常只扫描一遍数据库，所以又称为单遍扫描聚类。 对于空间中的一个对象，如果在给定半径Eps的邻域中的对象个数大于给定的数值Minpts，该对象称为核心对象，否则称为边界对象。由一个核心对象可达的所有对象构成一个簇。DBSCAN在研究中得到比较多的关注，GDBSCAN，DBCLASD，FDC都是对DBSCAN的进一步扩展和优化。 4. 基于网格的聚类 基于网格的聚类首先把数据空间划分为一定数目的单元，以后所有的操作都针对这些单元，通过对单元的操作来产生结果簇。这种方法的优点是处理速度快，处理时间独立于数据对象的数目，仅仅依靠于网格空间的维度。 5. 基于模型的聚类 基于模型的方法为每一个簇假定了一个模型，寻找数据对给定模型的最佳拟合。基于模型的方法有统计学方法COBWEB和自组织映射（SOM）神经网络方法等。其中自组织特征映射方法首先对文档降维，把特征维度降低到足够小，然后进行SOM聚类。该算法的意图是把SOM算法扩展到处理高维数据对象的领域，适合于用户对文档内容所属领域不太了解的情况。 与普通的聚类场景相比，文本聚类属于高维空间上的聚类分析。高维空间的数据经常呈现奇怪的特征，例如噪声的比例增加、网格单元的个数指数级增加、数据空间的稀疏性大、聚类的密度低等，这在数据挖掘中称为“维数祸根”。许多聚类分析的算法，例如 DBSCAN、STING、WaveCluster，随着维数的增加，算法的空间和时间的复杂性往往增长得很快，所以很难实用化。对于传统的聚类算法来说，当应用在文本聚类的场景中时，除了要调整好参数以外，还要尽量避免高维特征所带来的影响。
| 
发表于 2016-10-31 17:19:31
