在针对微博博文的话题发现上，传统的文本聚类技术有很多不足之处。本次报告就使用传统的文本表示及聚类技术，对微博的话题发现进行初探。在话题聚类中，主要使用了K-means和Single-pass聚类算法。从实验结果来看，Single-pass比传统的类K-means的聚类算法，更适合微博博文的话题聚类。

文档表示和话题聚类技术

1 文档的表示方法

文档常常采用向量空间模型（Vector Space Model,VSM）来表示。特征向量权值wi计算方法采用基于统计的词频—逆文档频率（TF-IDF）方法。 2常见的相似度计算

两篇文档di和dj之间的相似度sim(di,dj)一般使用夹角余弦公式来衡量，夹角θ越小，说明相似度越大，反之则越小。

同时，基于Jaccard coefficient相似度计算

3聚类技术

聚类就是将属于同一类别的事物聚成一个簇。聚类分析，通过数据相似度将数据进行分组，并给每组赋予不同的标签。聚类在分类上的主要优势，在于其对变化适用性强，同时可以有助于挑选出对于分类有效的特征。

常见的聚类方法分类：基于划分(partitioning)的方法、基于层次(hierachical)的方法、基于密度(density)的方法、基于网格(grid)的方法、基于模型(model)的方法、基于约束(constraint)的方法。

3.1 Single-pass聚类算法

Single-pass聚类算法，能以增量的方式进行聚类，它以信息文本出现的顺序依次进行处理，根据相度值进行匹配以确定信息文本所属话题类别。如果是第一篇文档，则以该文档为种子，建立一个新的话题类别，以后出现的每篇都跟已有的话题类别进行匹配，将该文档归并到与它的相似度最大且大于给定阈值的话题类别中。若与已有话题类别的相似度都小于某一阈值，则以该文档为种子，建立新的话题类别，对于不同的阈值设置将会形成不同粒度的话题类别。其算法流程如下：

（1）接收一篇向量化的文本文档d；

（2）将d与已有的所有话题均做相似度计算，取最大值作为该话题的相似度；

（3）在所有话题中找出与d有最大相似度的话题；

（4）若相似度值大于阈值TC，则把文本d分配到有最大相似度的话题中，跳转至（6）；

（5）若相似度值小于阈值TC， 即文本d不属于任一已有话题， 需创建新的话题类别，同时将当前文本归属到新创建的话题类别中；

（6）聚类结束，等待下一篇文档d’。

3.2 K-means聚类算法 k-means算法是最常用的聚类方法之一。传统的k-means算法产生局部最优解，而不是全局最优解。从不同的初始聚类中心出发会得到不同的聚类结果且准确率也不一样。通常k-means算法是从n个数据对象中随机选择k个对象作为初始聚类中心，这样就使得产生的聚类结果具有很大不确定性，

如何选择初始聚类中心点成了影响最后聚类结果的重要因素。k-means算法的过程如下：

输入：聚类个数k以及包含n个数据对象的样本集。

输出：满足一定条件的k个聚类。

处理流程：

（1）从n个数据对象中任意选择k个对象作为初始聚类中心；

（2）循环下述流程（3）到（4）直到每个聚类不再发生变化为止；

（3）根据每个聚类中所有对象的均值（中心对象），计算样本集中每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；

（4）重新计算每个（有变化）聚类的均值（中心对象）。

代码中，使用微博语料进行话题聚类实现。

cluster_for_weibo_data.py是主程序

stopwords.txt是分词时使用的停用词

*.csv 是微博语料，可以下载使用