（转载）文本聚类算法分析

柔情只为你懂 2021-10-15 10:25 375阅读 0赞

## 出处：[http://blog.csdn.net/uestcfrog/article/details/6875984][http_blog.csdn.net_uestcfrog_article_details_6875984] ##

## 1. 传统的文本聚类算法 ##

传统的文本聚类算法分为以下几种

### 1.1 分割方法(partitioning methods) ###

#### 1.1.1 [K-MEANS算法][K-MEANS]： ####

工作原理：

首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

具体过程:

(1)选取k个对象作为初始的聚类种子;

(2)根据聚类种子的值,将每个对象重新赋给最相似的簇;

(3)重新计算每个簇中对象的平均值,用此平均值作为新的聚类种子;

(4)重复执行(2)、(3)步,直到各个簇不再发生变化。

#### 1.1.2  K-MEDOIDS算法： ####

与[K-MEANS算法][K-MEANS]不同的是在衡量收敛标准，K-MEDOIDS算法用聚类对象到中心点的距离和值而不是平局值。

K-MEDOIDS算法对小数据集合非常有效，减少了噪声的干扰，比K-MEANS算法更有健壮性，但执行代价比较高，且对于大的数据集没有良好的伸缩性。

#### 1.1.3  CLARANS算法：  ####

基础是K-MEDOIDS思想。给定含有N个数据对象的数据集X，发现 k 个中心点的过程被看作是搜索图G的过程。G的每一个定点表示一组k个中心点集合，图创建后从定点逐个搜索整个图，并且计算每个定点所对应的聚类结果的平局距离，求出全局最优的聚类结果。为避免计算量过大，此算法用随机重启局部搜索计算对图进行搜索。所以算法设置参数，限制局部搜索的重启次数 nunlocal 和限制当前搜索定点的最大搜索邻居数 maxneighbor 对算法的影响很大。

算法多用于大规模的数据处理。

我的问题在于，不是很明了这些算法中的距离对于文本文件来说要怎么去计算。

### 1.2. 层次方法(hierarchical methods) ###

#### 1.2.1  BIRCH算法： ####

（1）扫描数据库，建立动态的一棵存放在内存的CF Tree。如果内存不够，则增大阈值，在原树基础上构造一棵较小的树。

（2）对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。

#### 1.2.2.  CURE算法: ####

基本原理：

针对大型数据库的高效的聚类算法。基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较脆弱。CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。

算法实现：

CURE的算法在开始时，每个点都是一个簇，然后将距离最近的簇结合，一直到簇的个数为要求的K。它是一种分裂的层次聚类。算法分为以下6步：

1）从源数据对象中抽取一个随机样本S。

2）将样本S分割为一组划分。

3）对划分局部的聚类。

4）通过随机取样提出孤立点。如果一个簇增长得太慢，就去掉它。

5）对局部的簇进行聚类。

6）用相应的簇标签标记数据。

#### 1.3. 基于密度的方法(density-based methods) ####

算法的基本思想：

基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。这个方法的指导思想就是，只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去。

代表有.DBSCAN算法：OPTICS算法：.DENCLUE算法等；

### 1.4. 基于网格的方法(grid-based methods) ###

这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。

代表算法有：

#### 1.4.1  CLIQUE算法： ####

CLIQUE算法采用了基于网格和密度的方法。首先对每个属性进行等分，整个数据空间就被分成一个超长方体集合，对每个单元进行数据点计数，大于某个阈值的单元称这稠密单元，然后对稠密单元进行连接就构成类。不同于其它方法，它可以自动地识别嵌入在数据子空间中的类。

好处是能够在高维空间中，它能够有效地进行聚类，并且能够发现嵌套在高维空间中的聚类。

#### 1.4.2  WAVE-CLUSTER算法： ####

工作原理：

WaveCluster算法中把多维空间数据看作是多维信号，首先将数据空间网格化，然后用小波变换技术（Wavelet transform）把信号从空间域转换到频率域。在小波变换中，用一个合适的内核函数进行旋转，产生一个变形后的空间，使数据中的簇易于区分。然后在变换后的空间中通过寻找密集区域对应起来。

WaveCluster算法通过把d维数据对象看作是d维信号，信号的高频部分对应特征空间中对象分布有急剧变化的区域，也就是类簇边界；而低频中高振幅部分则对应于对象分布比较集中的区域，也就是簇的内部。通过信号处理中的小波变换技术把信号分解成不同的频率段，找出d维信号的高频部分和低频部分，也就找出了簇。其中的噪声可以自动地被消除。

算法的步骤：

步骤1） 对特征空间进行量化，把每个维度分成m段，这样，整个空间分成单元，然后把对象分机到相应的单元；

步骤2） 对量化后的特征空间进行离散小波变换；

步骤3） 在变化后的特征空间的子波段中找出相连的部分，就是簇；

步骤4） 为每个簇所包含的单元分配相应的标签；

步骤5） 建立查找表，用于把变换后特征空间中的单元映射到原特征空间中的单元；

步骤6） 把每个单元的标签分配给该单元内的所有对象。

WaveCluster算法不受噪声影响，对输入顺序不敏感，不需要事先知道簇的数目，并且能够快速处理大型数据集，能够发现任意复杂形状的聚类。

WaveCluster算法是一种基于网格和基于密度的算法。它符合好的聚类算法的许多要求：它能有效地处理大数据集，发现任意形状的簇，成功地处理离群点，对输入的顺序不敏感，不需要指定求诸如结果的数目和领域半径等输入参数。

这个方面的算法完全是搬照过来的，我最近在看，只是明了基础意思，对实际的运行原理不清楚。

总结，这些都是一些传统的聚类算法，但都包含了现在的思想，是其它算法的基础。目前的这些算法在网上可以找到源代码，但是它的发展并没有得到完全，而且由于用处和用法的不同，每种算法有不同的缺陷，所应用的领域也大有不同。大部分的人都是从中应用其思想根据自己的需求进行改进。

转载于:https://www.cnblogs.com/beyiwork/archive/2012/09/25/2702089.html

[http_blog.csdn.net_uestcfrog_article_details_6875984]: http://blog.csdn.net/uestcfrog/article/details/6875984
[K-MEANS]: http://baike.baidu.com/view/31854.htm