6.4 常用文本聚类工具

6.4.1 使用 scikit-learn 进行文本聚类

scikit-learn 库提供了丰富的聚类算法,本部分选取几个常用聚类方法进行说明。

6.4.1.1 k-means 聚类

sklearn 库 cluster 包中的 kmeans 模块下定义了实现 k-means 聚类的类 KMeans 及相关方法,KMeans 类实例化方式为:实例=KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')

参数说明:

n_clusters:聚类数,也是需要初始化的类中心的个数,默认取值为 8

max_iter:一次聚类算法所执行的最大迭代次数,默认取值为 300

n_init:使用不同的初始化类中心进行聚类的次数,最终输出结果为几次聚类中效果最好的,以组内距离衡量

init:初始化方法,有以下几种取值方式:
(1)‘k-means++’:使用 k-means++ 算法选取初始聚类中心以加速收敛过程
(2)‘random’:随机选取样本点最为初始聚类中心
(3)由使用者自行制定初始聚类中心,形如 (n_clusters, n_features) 的对象
默认取值为‘k-means++’

algorithm:选择聚类算法,有以下几种取值方式:
(1)“auto”:根据数据类型自动选择合适的算法,稀疏数据选择“full”算法,否则选择“elkan”算法
(2)“full”:经典的 EM 算法
(3)“elkan”:使用三角不等式进行 “elkan” 变换,该算法目前不支持稀疏数据
默认取值为“auto”

precompute_distances:是否进行距离的预先计算,有以下几种取值方式:
(1)‘auto’:若样本总数乘以聚类数 n_samples * n_clusters 大于 1200 万,就不进行预计算
(2)True:进行预计算
(3)False:不进行预计算
默认取值为‘auto’

tol:当两次迭代的组内距离之差小于该值时,停止迭代

n_jobs:设置并行计算的处理器个数。取值为“-1”时,使用所有的处理器;取值为“1”时,不进行并行计算;小于“-1”时,使用(n_cpus + 1 + n_jobs)个处理器进行计算

random_state:随机初始化聚类中心的随机规则。取值为整数时,随机规则固定,默认使用 numpy 随机数生成器

相关方法及属性见下表:

@todo 补充方法、属性列表

例 1


In [1]:from sklearn.cluster import KMeans
       import numpy as np
       X = np.array([[1, 2, 3], [1, 3, 4], [1, 2, 0],
                     [4, 5, 2], [4, 4, 6], [4, 5, 0]])
       kmeans = KMeans(n_clusters=2)
       kmeans.fit(X)
Out[1]:KMeans(copy_x=True, init='k-means++', max_iter=300, n_clusters=2, n_init=10,n_jobs=1, precompute_distances='auto', random_state=None, tol=0.0001,verbose=0)
In [2]:kmeans.fit_predict(X)
Out[2]:array([0, 0, 0, 1, 1, 1], dtype=int32)
In [3]:kmeans.cluster_centers_
Out[3]:array([[ 1.        ,  2.33333333,  2.33333333],
              [ 4.        ,  4.66666667,  2.66666667]])
In [4]:kmeans.inertia_ 
Out[4]:28.666666666666664

6.4.1.2 Birch 聚类

sklearn 库 cluster 包中的 birch 模块下定义了实现 Birch 聚类的类 Birch 及相关方法,Birch 类实例化方式为:实例=Birch(threshold=0.5, branching_factor=50, n_clusters=3, compute_labels=True, copy=True)

参数说明:

threshold:叶节点簇直径阈值,如果新的样本点加入后,簇的直径大于该值,则需要新建簇,默认取值为 0.5

branching_factor:每个节点所能包含的最大聚类特征(CF)数,如果超过该值,则需要分割当前节点,默认取值是 50

n_clusters:用于设置最后的聚类数,有以下几种取值方式:
(1)整数:当原始聚类结果类别数不等于该值时,对聚类结果进行聚合 (2)None:不设置时直接返回原始聚类结果
(3)cluster 包的其他聚类模型:将叶节点的子类作为新样本继续按照指定聚类模型进行聚类
默认取值为 3

compute_labels:是否输出类别标签,默认取值为 True

copy:是否备份原始数据,默认取值为 True,取值为 False 时,原始数据会被覆盖

相关方法及属性见下表:

@todo 补充方法、属性列表

例 2


In [5]:from sklearn.cluster import Birch
       X =  np.array([[0, 0, 1], [0.5, 0.3, 1], [-0.2, -1, 1], [0, -0.4, -1], [0.3, 0.2, -1]])
       birch = Birch(n_clusters=None)
       birch.fit(X)
Out[5]:Birch(branching_factor=50, compute_labels=True, copy=True, n_clusters=None,threshold=0.5)
In [6]:birch.predict(X)
Out[6]:array([0, 0, 1, 2, 2])

6.4.2 使用 NLTK 进行文本聚类

NLTK 工具库中的 cluster 包中有几种基本的聚类算法,包括 k-means 聚类、E-M 聚类、GAAC 聚类,这些聚类方法对于多维空间向量聚类均有较好的效果。

6.4.2.1 k-means 聚类

kmeans 模块下定义了 KMeansClusterer 类及相关方法实现 k-means 聚类,KMeansClusterer 类实例化方式为:实例=KMeansClusterer(num_means, distance, repeats=1, conv_test=1e-06, initial_means=None, normalise=False, svd_dimensions=None, rng=None, avoid_empty_clusters=False)

参数说明:

num_means:初始聚类中心的个数

distance:距离定义函数,用于衡量向量之间的距离,可以自行定义,也可以直接调用 util 模块下定义的距离函数,包括:
(1)cosine_distance:夹角余弦距离
(2)euclidean_distance:欧氏距离

repeats:随机初始化聚类次数

conv_test:如果类中心变动小于该参数,则停止迭代

initial_means:用于指定初始聚类中心向量

normalise:是否对聚类向量进行标准化处理

svd_dimensions:使用 SVD 进行降维的维度

rng:随机数生成器

avoid_empty_clusters:在下一次迭代计算过程中考虑当前的聚类中心,以免出现类别为空的情况

相关方法及属性见下表:

@todo 补充方法、属性列表

例 3


In [7]:from nltk.cluster import KMeansClusterer
       X =  np.array([[0, 0, 1], [0.5, 0.3, 1], [-0.2, -1, 1], [0, -0.4, -1], [0.3, 0.2, -1]])
       km=KMeansClusterer(num_means=3,distance=nltk.cluster.util.cosine_distance)
       km.cluster(X)
       for i in X:
           print i,km.classify(i)
Out[7]:[ 0.  0.  1.] 1
       [ 0.5  0.3  1. ] 1
       [-0.2 -1.   1. ] 0
       [ 0.  -0.4 -1. ] 2
       [ 0.3  0.2 -1. ] 2
In [8]:km.means()
Out[8]:[array([-0.2, -1. ,  1. ]),
        array([ 0.25,  0.15,  1.  ]),
        array([ 0.15, -0.1 , -1.  ])]
In [9]:km.num_clusters()
Out[9]:3

6.4.2.2 GMM

em 模块下定义了 EMClusterer 类及相关方法实现混合高斯聚类,采用 EM 算法求解,EMClusterer 类实例化方式为:实例=EMClusterer(initial_means, priors=None, covariance_matrices=None, conv_threshold=1e-06, bias=0.1, normalise=False, svd_dimensions=None)

参数说明:

initial_means:每一类的初始化聚类中心

priors:每一类的先验概率

covariance_matrices:每一类的协方差矩阵

conv_threshold:当似然函数值变动小于该值时,停止迭代

bias:确保非奇异协方差矩阵的偏差

normalise:是否对向量进行标准化处理

svd_dimensions:使用 SVD 进行降维的维度

相关方法及属性见下表:

@todo 补充方法、属性列表

例 4


In [10]:from nltk.cluster import EMClusterer
        X =  np.array([[0, 0, 1], [0.5, 0.3, 1], [-0.2, -1, 1], [0, -0.4, -1], [0.3, 0.2, -1]])
        means=[[-0.2, -1,  1 ],[ 0.25,  0.15,  1 ],[ 0.15, -0.1 , -1  ]]
        em=EMClusterer(initial_means=means)
        em.cluster(X)
Out[10]:[ 0.2  1.   0. ] [[ 1.  0.  0.]
         [ 0.  1.  0.]
         [ 0.  0.  1.]]
         ……
         [  1.50000000e-01   3.00000000e-01  -4.64910288e-09] [[  8.94117646e+00  -2.11764706e+00  -3.73064999e-10]
          [ -2.11764706e+00   5.76470588e+00  -2.69806806e-08]
          [ -3.73064999e-10  -2.69806806e-08   9.99999907e+00]]
In [11]:em.cluster_names()
Out[11]:[0, 1, 2]
In [12]:for i in X:
            print i,em.classify(i)
Out[12]:[ 0.  0.  1.] …… 1
        [ 0.5  0.3  1. ] …… 1
        [-0.2 -1.   1. ] …… 1
        [ 0.  -0.4 -1. ] …… 2
        [ 0.3  0.2 -1. ] …… 2

6.4.2.3 GAAC 聚类

gaac 模块下定义了 GAAClusterer 类及相关方法实现聚合分层聚类,采用夹角余弦度量向量相似度,GAAClusterer 类实例化方式为:实例=GAAClusterer(num_clusters=1, normalise=True, svd_dimensions=None)

参数说明:

num_clusters:聚类数

normalise:是否对向量进行标准化处理

svd_dimensions:使用 SVD 进行降维的维度

相关方法及属性见下表:

@todo 补充方法、属性列表

例 5


In [13]:from nltk.cluster.gaac import GAAClusterer
        X =  np.array([[0, 0, 1], [0.5, 0.3, 1], [-0.2, -1, 1], [0, -0.4, -1], [0.3, 0.2, -1]])
        gaac=GAAClusterer(num_clusters=3)
        gaac.cluster(X)
        gaac.dendrogram().show()
Out[13]:        +---------------------------------+----------------+                         
                |                                 |                |                         
                |                                 |                +----------------+        
                |                                 |                |                |        
                +----------------+                |                |                |        
                |                |                |                |                |        
          [ 0.  0.  1.]   [ 0.5  0.3  1. ] [-0.2 -1.   1. ] [ 0.  -0.4 -1. ] [ 0.3  0.2 -1. ]
In [14]:for i in X:
            print i,gaac.classify(i)
Out[14]:[ 0.  0.  1.] 1
        [ 0.5  0.3  1. ] 1
        [-0.2 -1.   1. ] 0
        [ 0.  -0.4 -1. ] 2
        [ 0.3  0.2 -1. ] 2

6.4.3 使用 Pattern 进行文本聚类

Pattern 工具库中 vector 包内定义了 Model 类及相关的方法可以实现文本聚类,支持 k-means 聚类和分层聚类,Model 类实例化方式为:实例=Model(documents=[], weight='tf-idf')

参数说明:

documents:需要聚类的文本列表,其元素类型为 Document。

weight:计算文本相似性的依据,包括:TF、TFIDF (默认取值)、IG、BINARY、 None(使用初始文本权重)

对 Model 类实例调用 cluster 方法即可实现聚类,调用方式为:实例.cluster(method, k, iterations, distance)

参数说明:

method:聚类方法,支持 KMEANS 和 HIERARCHICAL 两种聚类算法

k:聚类数

iterations:迭代次数

distance:距离度量方式,默认取值为 COSINE ,即夹角余弦,此外还支持 EUCLIDEAN、MANHATTAN 和 HAMMING

例 7


In [16]:from pattern.vector import HIERARCHICAL,KMEANS
        from pattern.vector import Model
        text=['Cats are independent pets.','Dogs are trustworthy pets.','Boxes are made of cardboard.']
        document=[Document(i) for i in text]
        document
Out[16]:[Document(id='Q6TVPey-14'),
         Document(id='Q6TVPey-15'),
         Document(id='Q6TVPey-16')]
In [17]:model=Model(document)
        model.cluster(method=KMEANS, k=2)
Out[17]:[[Document(id='Q6TVPey-14'), Document(id='Q6TVPey-16')],
         [Document(id='Q6TVPey-15')]]

6.4.4 聚类效果评价指标

sklearn 库 metrics 模块下的 cluster 包给出了多种聚类效果评价指标,按照聚类对象是否有真实类别标记,可分为两类,即有监督和无监督,使用者可以根据实际数据情况考量各个指标的优缺点自行选择适合的评价指标,本部分对部分指标的计算原理及调用方式做简要说明:

6.4.4.1 有监督

(1)调整兰德指数(Adjusted Rand index)

如果已知聚类对象的实际类别标签,结合预测的分类结果,就可以计算调整兰德指数对比二者的相似度,对于一个样本量为 n 的样本空间 S ,我们将空间中原本的样本标签划分与我们要评价聚类结果划分分别用 X={X1,X2,...,Xn} 与 Y={Y1,Y2,...Yn} 表示,此时调整兰得指数 R 可以由如下公式表示:

其中,上式中的指标 a,b,c,d 含义如下:

  • a:在样本空间 S 中,在 X 划分中属于同一类且在 Y 划分中属于同一类的样本对数
  • b:在样本空间 S 中,在 X 划分中属于不同类且在 Y 划分中属于不同类的样本对数
  • c:在样本空间 S 中,在 X 划分中属于同一类且在 Y 划分中属于不同类的样本对数
  • d:在样本空间 S 中,在 X 划分中属于不同类且在 Y 划分中属于同一类的样本对数

可以看到,上式中的指标 a+b 的值越大,反映了划分 X 与 Y 之间的一致程度越强;而指标 c+d 的值越大,则反映了划分 X 与 Y 之间的差异程度越高。调整兰德指数正是以这样一种直观的比值形式来反映聚类结果与样本标签的相似程度。Scikit-Learn 中的 cluster 包提供了调整兰德指数计算函数 adjusted_rand_score,调用方式如下:

sklearn.metrics.adjusted_rand_score(labels_true, labels_pred)

参数说明:

labels_true:样本真实类别标签列表

labels_pred:预测的类别标签列表

该函数直接返回取值范围在-1到1之间的聚类结果相似度得分,如果结果位于0-1之间表明聚类效果较好。

例 8


In [18]:from sklearn import metrics
        labels_true = [0, 0, 1, 1, 1]
        labels_pred = [0, 0, 1, 1, 2]
        metrics.adjusted_rand_score(labels_true, labels_pred)
Out[18]:0.5454545454545454
In [19]:labels_pred = [0, 0, 1, 1, 1]
        metrics.adjusted_rand_score(labels_true, labels_pred)
Out[19]:1.0
In [20]:labels_pred = [1, 1, 0, 0, 0]
        metrics.adjusted_rand_score(labels_true, labels_pred)
Out[20]:1.0

(2)互信息(Mutual Information)

作为信息论里一种常用的信息度量,互信息也是对两组分类集合相似度的衡量。互信息 I 的定义如下式所示:

I(X;Y)=H(X)-H(X|Y)=H(X,Y)-H(X|Y)-H(Y|X)

其中 H(X,Y) 为联合熵, $H(X,Y)=\Sigma p(x,y) log p(x,y)$ ;H(X|Y) 为条件熵, $H(X|Y)=\Sigma_x \Sigma_y p(xy) log_2 p(x|y)$

为了消除聚类中心和样本数对聚类效果评价产生的影响,有时我们也采用 AMI(Adjusted Mutual Information) 对聚类结果的互信息水平进行评价,其定义如下:

AMI(U, V) = [MI(U, V) - E(MI(U, V))] / [max(H(U), H(V)) - E(MI(U, V))]

cluster 包提供了互信息计算函数 normalized_mutual_info_score 和 adjusted_mutual_info_score 分别计算 Normalized Mutual Information(NMI) 和 Adjusted Mutual Information(AMI) 两种互信息,调用方式为:sklearn.metrics.normalized_mutual_info_score/adjusted_mutual_info_score(labels_true, labels_pred)

例 9


In [21]:labels_true = [0, 0, 1, 1, 1]
        labels_pred = [0, 0, 1, 1, 2]
        metrics.normalized_mutual_info_score(labels_true, labels_pred)
Out[21]:0.79873276276445015
In [22]:metrics.adjusted_mutual_info_score(labels_true, labels_pred)
Out[22]:0.46557755827004066
In [23]:labels_pred = [1, 1, 0, 0, 0]
        metrics.adjusted_mutual_info_score(labels_true, labels_pred)
Out[23]:1.0

(3)同质性(Homogeneity)和完备性(completeness)

同质性(Homogenelty)用于衡量聚类结果中类内样本之间的平均相似度,相似度越高,代表该聚类结果中的簇越“纯”;而完备性(Completeness)则用于反映属于相同类别的样本对象是否都被聚类入同一个簇。

对于含有 n 个样本的样本空间 S ,划分 $X={x1,x_2,...,x_n}$ 为原本的样本标记,而划分 $Y={y_1,y_2,...,y_n}$ 则为我们的聚类结果,我们以 $ a {ij} $ 来表示属于类别 $x_i$ 且属于聚类簇 $y_j$ 的样本序号。此时,聚类结果的同质性 $h$ 以及完备性 $c$ 可由下式表示:

$h=\begin{cases} 1 & \text{if H(X,Y)=0} \ 1-\frac{H(X|Y)}{H(X)} & \text{else}\ \end{cases}$

$c=\begin{cases} 1 & \text{if H(Y,X)=0} \ 1-\frac{H(Y|X)}{H(Y)} & \text{else}\ \end{cases}$

其中,

$H(X|Y)=-\Sigmay \Sigma_x \frac{a{xy}}{n} log \frac{a{xy}}{\Sigma_x a{xy}}$

$H(X)=-\Sigmax \frac{\Sigma_y a{xy}}{n} log \frac{\Sigmay a{xy}}{n}$

不难看出,当一个聚类结果同时具有较高的同质性和完备性水平时,聚类的效果也较好,适合我们在分析中采用。

cluster 包提供了互信息计算函数 homogeneity_score 和 completeness_score 分别计算同质性和完备性,调用方式为:

sklearn.metrics.homogeneity_score/completeness_score(labels_true, labels_pred)

例 10


In [24]:labels_true = [0, 0, 1, 1, 1]
        labels_pred = [0, 0, 1, 1, 2]
        metrics.homogeneity_score(labels_true, labels_pred)
Out[24]:1.0
In [25]:metrics.completeness_score(labels_true, labels_pred)
Out[25]:0.63797402631333133

6.4.4.2 无监督

在实际聚类过程中,聚类对象的真实类别往往是未知的,此时只能借助聚类模型本身得到聚类效果评价指标,轮廓系数(Silhouette Coefficient)就是较为常用的一种。

轮廓系数是在没有基准可用的情况下考察聚类结果中粗的分离与紧凑情况的度量。对于样本量为 n 的样本数据集 D ,假设我们的聚类结果将其划分为 k 个簇 $C_1,C_2,...C_n$ 。而对于每个样本 $o∈C_i$ ,我们可以计算出它与所属簇中其他样本之间的平均距离 $a(o)$,以及它与其他簇之间的最小平均距离 $b(o)$ ,即

$a(o)=\frac{\Sigma dist(o,o_i')}{|C_i|-1}$ $b(o)=min { \frac{\Sigma dist(o,o_j')}{|C_j|} }$

此时,样本 o 的轮廓系数 s(o) 定义为:

$s(o)=\frac{b(o)-a(o)}{max{a(o),b(o)}}$

可以看到,轮廓系数的值在 -1 与 1 之间,当样本 o 的轮廓系数越接近于 1 时,表明聚类的效果越好;而当轮廓系数的值为负时,则说明我们的这次聚类相当失败,可以完全舍弃了。

cluster 包提供了轮廓系数计算函数 silhouette_score,计算所有样本轮廓系数的均值,调用方式如下:silhouette_score(X, labels, metric='euclidean', sample_size=None, random_state=None)

参数说明:

X:待聚类样本特征数组或者已经计算好的样本两两之间的距离数组

labels:聚类得到的每一个样本的类别标签数组

metric:计算轮廓系数所使用的距离度量方式,有以下两种取值方式:
(1)字符串:必须是函数 metrics.pairwise.pairwise_distances 定义下的距离,包括 ‘cityblock’、‘cosine’、‘euclidean’、‘l1’、‘l2’、‘manhattan’等,更加具体的信息可以参见 pairwise_distances 函数说明(http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.pairwise_distances.html#sklearn.metrics.pairwise.pairwise_distances)
(2)"precomputed":当 X 为已经计算好的样本两两之间的距离数组时,metric 只能取该值

sample_size:用于计算轮廓系数的样本个数,取值为整数或 None(不抽样)

random_state:当 sample_size 取值非 None 时,使用该参数设置用于生成指定样本数的随机数生成器

例 11


In [26]:import numpy as np
        X = np.array(([  5,  3,  1,  0],
                      [  4,  3,  1,  1],
                      [ -4,  3,  1,  0],
                      [ -4,  3,  1,  2],
                      [ -5,  3,  1,  2]))
        y = np.array((0,0,1,1,1))
        metrics.silhouette_score(X, y, metric='euclidean')
Out[26]:0.81845375003407805

results matching ""

    No results matching ""