K-Means的K值确定

一、elbow method

x轴为聚类的数量,y轴为WSS(within cluster sum of squares)也就是各个点到cluster中心的距离的平方的和。

Elbow method就是“肘”方法,对于n个点的数据集,迭代计算k from 1 to n,每次聚类完成后计算每个点到其所属的簇中心的距离的平方和,可以想象到这个平方和是会逐渐变小的,直到k==n时平方和为0,因为每个点都是它所在的簇中心本身。但是在这个平方和变化过程中,会出现一个拐点也即“肘”点,盗了张图可以看到下降率突然变缓时即认为是最佳的k值。

def elbow_method(data2vec):
    distortions = []
    K = range(1, 31)
    for k in tqdm(K):
        clf = KMeans(n_clusters=k,
                     n_init=20,
                     init='k-means++', n_jobs=multiprocessing.cpu_count() - 1)  # n_init选择质心的次数,返回最好的结果
        km = clf.fit(data2vec)
        print('Fit over, begin to compute cdist.')
        distortions.append(sum(np.min(cdist(data2vec, km.cluster_centers_, 'euclidean'), axis=1)) / data2vec.shape[0])
    print(K)
    print(distortions)
    with open('result_elbow.txt', 'w') as f:
        for k in K:
            f.write(str(k) + ' ')
        f.write('\n')
        for dis in distortions:
            f.write(str(dis) + ' ')
        f.write('\n')

    # Plot the elbow
    plt.plot(k, distortions, 'bx-')
    plt.xlabel('k')
    plt.ylabel('Distortion')
    plt.title('The Elbow Method showing the optimal k')
    plt.show()

 

二、轮廓系数(Silhouette Coefficient)

在实际应用中,由于Kmean一般作为数据预处理,或者用于辅助分聚类贴标签。所以k一般不会设置很大。可以通过枚举,令k从2到一个固定值如10,在每个k值上重复运行数次kmeans(避免局部最优解),并计算当前k的平均轮廓系数,最后选取轮廓系数最大的值对应的k作为最终的集群数目。
轮廓系数取值范围为[-1,1],取值越接近1则说明聚类性能越好,相反,取值越接近-1则说明聚类性能越差。
    • a:某个样本与其所在簇内其他样本的平均距离
    • b:某个样本与其他簇样本的平均距离

def silhouette_score_method(data2vec):
    scores = []
    K = range(2, 31)
    best_k = None
    best_score = -1
    for k in tqdm(K):
        clf = KMeans(n_clusters=k,
                     n_init=20,
                     init='k-means++', n_jobs=multiprocessing.cpu_count() - 1)  # n_init选择质心的次数,返回最好的结果
        km = clf.fit(data2vec)
        print('Fit over, begin to compute silhouette_score.')
        labels = km.labels_
        score = metrics.silhouette_score(data2vec, labels, metric='cosine')
        scores.append(score)
        if score > best_score:
            best_k = k
            best_score = score
    print('Best k:', str(best_k), 'Best score:', str(best_score))
    with open('result_silhouette_score.txt', 'w') as f:
        for k in K:
            f.write(str(k) + ' ')
        f.write('\n')
        for score in scores:
            f.write(str(score) + ' ')
        f.write('\n')
        f.write('Best k: ' + str(best_k) + ' Best score: ' + str(best_score) + '\n')

三、Reference

文本聚类

一. 划分法(基于划分的聚类算法)

k-means(k的选取,大规模文本计算距离复杂度高)

大样本采取Mini Batch K-Means算法

二. 层次法(基于层次的聚类算法)

  • 自底向上(合并聚类)
    • 将语料库中的任一数据都当作一个新的簇,计算所有簇相互之间的相似度,然后将相似度最大的两个簇进行合并,重复这个步骤直到达到某个终止条件,因此合并聚类方法也被称为由下而上的方法。
  • 自顶向下(分裂聚类)
    • 先将数据集中所有的对象都归为同一簇,并将不断地对原来的簇进行划分从而得到更小的簇,直到满足最初设定的某个终止条件。
  • 优缺点
    • 优点
      1. 适用于发现任意形状的簇;
      2. 适用于任意形式的相似度或距离表示形式;
      3. 聚类粒度的灵活性。
    •  缺点
      1. 算法终止的条件很模糊,难以精确表达并控制算法的停止;
      2. 一旦聚类结果形成,一般不再重新构建层次结构来提高聚类的性能;
      3. 难以处理大规模数据,也不能适应动态数据集的处理。

三. DBSCAN(密度聚类)

  • 由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇
  • 先从数据集w中找到任意一个对象q,并查找w中关于R和最小下限数MinPts的从q密度到达的所有对象。如果q是核心对象,也就是说,q半径为R的领域中包含的对象数不少于MinPts,则根据算法可以找到一个关于参数R和MinPts的类。如果q是一个边界点,即q半径为R的领域包含的对象数小于MinPts,则没有对象从q密度到达,q被暂时标注为噪声点。然后,DBSCAN处理数据集W中的下一个对象。

四. Single-pass(增量聚类)

其顺序处理文本,以第一篇文档为种子,建立一个新主题。之后再进行新进入文档与已有主题的相似度,将该文档加入到与它相似度最大的且大于一定阈值的主题中。如果与所有已有话题相似度都小于阈值,则以该文档为聚类种子,建立新的主题类别。适合大规模文本聚类

五.BIRCH聚类算法原理

适合于数据量大,类别数K也比较多的情况

  • 1) 将所有的样本依次读入,在内存中建立一颗CF Tree, 建立的方法略。
  • 2)(可选)将第一步建立的CF Tree进行筛选,去除一些异常CF节点,这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并
  • 3)(可选)利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类,得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构,以及一些由于节点CF个数限制导致的树结构分裂。
  • 4)(可选)利用第三步生成的CF Tree的所有CF节点的质心,作为初始质心点,对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。

HMM VS CRF

一、区别

  1. HMM是生成模型(由数据学习联合概率分布P(X,Y), 然后由P(Y|X)=P(X,Y)/P(X)求出概率分布P(Y|X)作为预测的模型),CRF是判别模型(由数据直接学习决策函数Y=f(X)或条件概率分布P(Y|X)作为预测模型)
  2. HMM是概率有向图CRF是概率无向图
  3. CRF由于得分进行全局softmax归一化,所以得到的是全局最优值;并且解决了最大熵马尔可夫模型(MEMM)中的标注偏置问题(MEMM只去除了观测独立性假设,没有去除齐次马尔科夫链假设 Thus, states with a single outgoing transition effectively ignore their observations. More generally, states with low-entropy next state distributions will take little notice of observations)。
      局部归一化,局部最优。
  • CRF打破了HMM的两种假设:
    • 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态;
    • 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态
  • CRF可以定义数量更多,种类更丰富的特征函数,并且加权求和(score)
  • CRF在特征函数中还包含了整条观测序列的信息,都可以被利用
  • 任意的HMM都可以由CRF表达出来

二、HMM

隐马尔可夫模型 HMM

三、CRF

CRF条件随机场

四、Refs

生成模型和判别模型