We use cookies to improve your experience with our site.

文本数据流聚类

Clustering Text Data Streams

  • 摘要: 随着网络和信息技术的快速发展,现实生活中人们往往会接触到大量的文本流数据,如即时通讯工具ICQ等产生的大量聊天记录,连续到达的电子邮件以及定时更新的网络新闻等等。如何从这些大量的文本数据流中挖掘有用的知识?文本数据流聚类是有效的方法之一。文本数据流聚类是数据挖掘研究领域的一个重要课题,具有广泛的应用,如在线新闻组过滤、文本搜集、在线文本组织、主题跟踪和检测等。在这些应用中,文本数据以流的形式连续地出现,这给传统的文本聚类带来了巨大挑战,如(1)文本流中数据连续出现的特点使得不能一次将整个数据集读入到内存处理;(2)文本流聚类要求实时的响应时间,因此不能对数据集进行多趟扫描等等。已有的文本流聚类方法大都是一种基于相似策略的方法,并只用TF*IDF模式表示文本语义,往往导致较低的聚类精度。文本聚类质量低的一个重要原因是文本数据集包含过多的通用词(如停止词)以及过少的核心词(如文本的主题词),并且TF*IDF模式不能有效地减少通用词和加强核心词在文本聚类中的作用,因此往往导致较低的文本聚类精度。最近,研究者利用语义过滤模型进行静态文本的聚类,结果表明语义过滤模型能有效地提高文本聚类的质量,其精确度要明显优于基于TF*IDF模式的聚类精度。但是,已有的语义过滤模型主要适合处理静态文本数据,无法应用于动态的文本数据流环境。如何提高文本数据流的聚类精度?能否设计一种适合文本流的语义过滤模型呢?如果可以,语义过滤模型的计算将会给文本流的聚类带来额外的开销,那么又如何在提高聚类精度的同时保持较快的聚类响应时间(即平衡聚类精度和实时聚类之间的矛盾)?本文对这些问题进行了深入研究,利用扩展的语义过滤模型进行文本数据流的聚类,从而改善文本数据流的聚类质量。本文主要贡献是:(1)将现有的语义过滤模型扩展到了文本数据流上下文环境,提出了一种扩展的语义过滤模型。(2) 基于扩展的语义过滤模型,提出了两种在线的文本流聚类算法OCTS和OCTSM,其中OCTSM是OCTS的进一步改进。在聚类算法中,提出了一种新的聚类统计结构即聚类轮廓,该结构用于实时保存聚类的统计信息。聚类算法利用聚类轮廓来动态地捕获文本流语义、加速文本聚类过程、平衡聚类精度和实时聚类之间的矛盾。另外,通过聚类算法的有效实现来进一步加速聚类过程。(3)基于流行的文本数据集对算法性能进行了一系列的对比实验包括聚类精度,聚类时间和聚类代价开销等。实验结果表明了我们算法的有效性:聚类精度明显优于已有的基于TF*IDF模式的聚类方法,聚类时间接近已有较好的聚类算法,聚类的内存开销能够满足文本流实时聚类需求。

     

    Abstract: Clustering text data streams is an important issue indata mining community and has a number of applications such as newsgroup filtering, text crawling, document organization and topicdetection and tracing etc. However, most methods are similarity-basedapproaches and only use the TF*IDF scheme to represent the semantics oftext data and often lead to poor clustering quality. Recently,researchers argue that semantic smoothing model is more efficient thanthe existing TF*IDF scheme for improving text clustering quality.However, the existing semantic smoothing model is not suitable fordynamic text data context. In this paper, we extend the semanticsmoothing model into text data streams context firstly. Based on theextended model, we then present two online clustering algorithms OCTSand OCTSM for the clustering of massive text data streams. In bothalgorithms, we also present a new cluster statistics structure namedcluster profile which can capture the semantics of text data streamsdynamically and at the same time speed up the clustering process. Someefficient implementations for our algorithms are also given. Finally,we present a series of experimental results illustrating theeffectiveness of our technique.

     

/

返回文章
返回