基于向量空间模型的中文文本聚类方法的研究

上海交通大学

硕士学位论文

基于向量空间模型的中文文本聚类方法的研究

姓名：姚清耘

申请学位级别：硕士

专业：通信与信息系统

指导教师：李翔;刘功申

20080101

基于向量空间模型的中文文本聚类方法的研究

摘要

文本聚类是聚类分析领域的一个重要研究分支，是聚类方法在文本处理领域的应用。

本文对基于空间向量模型的中文文本聚类算法做了较深入的讨论。利用开源语料库，实现并讨论了现有比较流行的多种算法的优劣，并基于语料库的实际聚类效果，就维度确定、特征选择、文本表示等方面提出优化方案。

本文首先回顾了中文文本聚类领域的已有成果，列举了文本聚类领域在文本表示、文本相似度衡量、文本信息特征集缩减等方面的基础研究工作。另外，本文回顾了现有的中文文本聚类算法，以及常用的文本聚类效果评价指标。

在回顾了已有成果的基础上，本文针对向量空间表示模型，基于搜狐研发中心搜狗实验室的开源语料，设计并实现了几种比较流行的聚类算法，并根据实验结果，对这几种算法在多个层面上做了比对。实验表明，层次法的聚类效果较好，但时间消耗较大；而划分法在聚类效果的表现上不够稳定，但时间消耗相对较小。

在对实验结果进行分析后，本文还针对现有算法存在的一些问题，在维度确定、特征选择、文本表示等多方面提出了改进，改变了

传统的空间向量模型单纯依靠词条进行统计的缺点，考虑了词条本身所蕴含的含义以及词与词之间的关系，这些改进在基于语料库的文本聚类实验中有效地提高了聚类的效果。在两种流行的聚类有效性评价指标PP与PR的表现上，分别最多提高了11.4%与20.5%。这表明，基于词条更多隐藏信息的文本聚类可以得到较好的聚类结果。

关键词：向量空间模型，文本聚类，语料库

RESEARCH OF VSM-BASED

CHINESE TEXT CLUSTERING ALGORITHMS

ABSTRACT

Text Clustering, one of the most important research braches of clustering, is the application of clustering algorithm in Text Processing.

This paper makes relatively deep discussion in the field of VSM(Vector Space Model)-Based Chinese Text Clustering algorithms. By using Open Source Corpuses, it discusses with the strengths and weaknesses of VSM-Based algorithms and presents optimizations of Text Clustering algorithms, including dimension determining, feature selection etc.

Firstly, this paper turns back to the achievement in the field of Chinese Text Clustering; it lists the basic research in the areas of feature selection and dimension determining. Moreover, it also discusses with the Chinese Text algorithms and introduces basic knowledge of Clustering Validity.

On the basis of these works, by doing research with the Open Source Corpus of Sogou Laboratory, this paper implements several Clustering algorithms. According to the effects of clustering of the corpus, it

discusses with the strengths and weakness of these algorithms. The results indicate that the Hierarchical Method can obtain a better result than the Partitioning Method, but its time consumption is longer.

Finally, to improve the clustering effect, this paper presents some optimizations of clustering algorithms, including dimension determining, feature selection etc. These optimizations not only take into consideration the feature words themselves, but also the information involved and the relationship between the words. It is proved that these optimizations can effectively improve the effects of text clustering on the corpus. Based on PP and PR, two common indexes of Clustering Validity, the veracity of text clustering has been improved by 11.4% and 20.5% at most.

KEY WORDS: VSM, Text Clustering, Corpus

上海交通大学

学位论文原创性声明

本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明的引用内容外，本论文不包含其他个人或集体已经发表或撰写过的作品成果。对文人的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。

学位论文作者签名：姚清耘

日期：2008年 1 月16 日

上海交通大学

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文贝查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。

保密□，在年解密后适用本授权书。本学位论文属于

不保密□√

（请在以上方框内打“√”）

学位论文作者签名：姚清耘指导教师签名：李翔日期：2008年 1 月16 日日期：2008年 1 月16 日

第1章绪论

1.1. 引言

随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，Internet已经发展为当今世界上最大的信息库和全球范围内传播信息的最主要渠道。无论是商业企业、科研机构或是政府部门，在过去若干年的时间里都积累了海量的，以不同形式存储的数据资料。由于这些资料十分复杂，仅仅依靠数据库的查询检索机制和统计学方法已经远远不能满足显示需要了，它迫切要求自动、智能地将数据转化为有用的信息和知识，从而达到为决策服务的目的。数据挖掘[1]正是为迎合这种需要而产生并迅速发展起来的用于开发信息资源的一种新的数据处理技术。

数据挖掘（Data Mining），就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，简单地说，数据挖掘就是从大量数据中提取或“挖掘”知识。

数据挖掘的研究范围涉及关联规则挖掘、分类规则挖掘、聚类规则挖掘、趋势分析、孤立点分析、演变分析等方面。数据挖掘所获取的信息和知识已广泛地用于各种应用，包括商务管理、生产控制、市场分析、工程设计和科学探索等方面。

聚类分析是数据挖掘的研究内容之一，它是在无类别标记信息的情况下，根据事物的不同特征，将事物划分为不同的分组，使得同属于一个分组的个体之间的距离尽可能的小，不同分组的个体间的聚类尽可能的大。

随着Internet的大规模普及和企业信息化程度的提高，各种资源呈爆炸式增长。在中国互联网络信息中心（China Internet Network Information Center，CNNIC）2007年7月最新公布的中国互联网络发展状况统计报告中显示，70.2%的网络信息均以文本形式体现[2]。如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。文本挖掘已经成为数据挖掘中一个日益流行而重要的研究领域。

图1-1数据挖掘系统结构图

Figure 1-1 Structure of Data Mining System

1.2. 文本挖掘技术简介

据数据挖掘著名网站Kdnuggets（https://www.sodocs.net/doc/6f10978696.html,）2007年11月公布的最新调查结果表明， 83%左右的人曾利用软件工具进行文本挖掘。如图1-2所示。

图1-2文本挖掘使用状况[3]

Figure 1-2 Current Using Status of Text Mining

与一般数据挖掘以关系、事务和数据仓库中的结构数据为研究目标所不同的是，文本挖掘（Text Mining）所研究的文本数据库，由来自各种数据源的大量文档组成，包括新闻文章、研究论文、书籍、期刊、报告、专利说明书、会议文献、技术档案、政府出版物、数字图书馆、技术标准、产品样本、电子邮件消息、Web页面等。这些文档可能包含标题、作者、出版日期等结构化数据,也可能包含摘要、内容等非结构化的文本成分。

文本挖掘（Text Mining），就是从这种半结构或无结构化的文本数据中发现潜在的概念以及概念间的相互关系。

图1-3文本挖掘过程[4]

Figure 1-3 Procedures of Text Mining

文本挖掘主要分为三个阶段：预处理阶段、挖掘分析阶段、结果展示阶段。预处理技术主要包括Stemming(英文) /分词(中文) 、噪音词处理、特征表示和特征提取。常用的文本挖掘分析技术有:文本结构分析、文本摘要、文本分类、文本聚类、文本关联分析、分布分析和趋势预测等。数据可视化(Data Visualization)技术是指运用计算机图形学和图像处理技术,将数据转换为图形或图像在屏幕上显示出来,并进行交互处理的理论、方法和技术。

文本聚类技术是文本挖掘分析技术的一个重要的研究分支。

1.3. 文本聚类的研究意义

文本聚类针对大量的文本信息内容为分析以及深层次的“知识检索”提供了有效手段，在多项研究或系统中都有很好的应用。因此，文本聚类也作为文本挖掘的一个研究分支，被越来越多的研究人员所关注。

文本聚类的主要应用点包括：

1. 自然语言处理应用的预处理步骤

文本聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤，在对

大量文档进行聚类处理后，再针对同类别的文档集合进行自然语言处理的后续步骤。这方面应用中，比较典型的例子是哥伦比亚大学开发的多文档自动文摘系统Newsblaster[5](https://www.sodocs.net/doc/6f10978696.html,/nlp/newsblaster/)。该系统将新闻进行聚类处理,并对同主题文档进行冗余消除、信息融合、文本生成等处理,从而生成一篇简明扼要的摘要文档。

2. 对于检索结果的组织

这方面的应用主要体现在对于搜索引擎检索结果的组织上。使用者在输入一些关键词后，得到的一般都是成千上万条的检索结果，而且其中大部分都是不需要的无关资料。虽然有一些技巧试图给那些有较多关键词或者罕见关键词的页面赋予更大的权重，却仍然不能保证和用户意图最相关的页面一定被排在前列以方面用户查看。因此，我们迫切需要对搜索引擎返回的结果进行聚类，以使得用户迅速定位到所需要的信息。

这方面比较典型的系统有Infonetware Real Term Search (https://www.sodocs.net/doc/6f10978696.html,)。Infonetware具有强大的对搜索结果进行主题分类的功能。另外，由Carrot Search开发的基于Java的开源Carrot2搜索结果聚合聚类引擎2.0版[6]也是这方面的利用，Carrot2 可以自动把自然的搜索结果归类（聚合聚类）到相应的语义类别中，提供基于层级的、同义的、标签过滤的等功能。

3. 个性化信息推送

传统的获取信息的技术中用户是主动方，因此可以称之为“拉”，与之相反的另一种方式则称为“推”，由信息发布方主动地将信息推送给感兴趣的用户。要想快速完成信息分发步骤，可以通过文本聚类将用户分为对不同事物感兴趣的小团体，以向有相同兴趣方向的用户提供类似的信息。用户的兴趣可以使用用户自己提交的，或者用户访问过的文本集合来描述。

1.4. 文本聚类技术

文本聚类（Text Clustering）主要依据聚类假设[7]：同类的文档相似度较大，非同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有较高的灵活性和自动化处理能力，成为对文本信息进行有效组织、摘要和导航的重要手段。

文本聚类的具体过程如图1-4所示。

图1- 4文本聚类过程

Figure 1-4 Procedures of Text Clustering

文本聚类的首要问题是如何将文本内容这种半结构或无结构化的数据表示成为结构化数据，即建立文本特征，以一定的特征项（如词条或描述）来代表目标文本信息，使得数学上可以进行分析处理。在将文本内容表示成数学上可分析处理的形式后，接下来的工作就是在此数学形式的基础上，对文本进行聚类处理。具体的聚类分析算法将在后续的章节中予以介绍。

1.5. 本文的工作

目前文本聚类技术正在发展阶段，许多研究人员对文本聚类技术进行了大量的研究，但这些研究大部分是在英文环境下进行的，对中文的研究却很少。针对这一现状，本文主要做了以下几点工作：

1. 对中文文本聚类分析算法进行了探讨；

2. 设计和实现了多个中文文本聚类算法；

3. 基于语料库的实际聚类效果作了相关分析；

4. 就维度确定、特征选择、文本表示等方面提出优化方案。

本文的组织结构如下：

第1章绪论

介绍文本挖掘与文本聚类的研究意义与背景，介绍本文的主要研究内容和组织架构。

第2章中文文本聚类算法综述

本章主要介绍了文本聚类领域里的文本表示模型、文本与文本、文本簇之间相似度的衡量函数、用于文档信息特征集缩减的常用评价函数、现有较为流行的中文文本聚类算法及其主要代表方法。另外，本章还介绍了常用的文本聚类效果

评价指标。

第3章中文文本聚类算法的研究与分析

基于实际语料库资源，设计实现了中文文本聚类的多种算法，并根据实际的聚类结果，对各类中文文本聚类算法以及多种聚类效果的影响因素进行了分析和比对。

第4章中文文本聚类的相关改进

根据第4章的实验结果，在维度确定、特征数缩减、文本表示等方面提出改进。实验表明，这些改进可以有效地改善文本聚类的性能，从而为下一阶段的工作指明了方向。

第5章总结与展望

总结本文工作，并提出进一步需要研究的问题。

第2章 中文文本聚类算法综述

中文文本的聚类算法是本论文的重点，也是本论文要着重分析的部分。在本章中，我们将首先介绍文本聚类领域在文本表示、文本相似度衡量、文本信息特征集缩减等方面的知识，然后会介绍几种常见的文本聚类算法以及常用的文本聚类效果评价指标。

文本聚类的数学描述为：对文本集合12{,}n X x x x =L 进行划分，分成

{|,1,}1i i i C C C X i m C X i m

=?===L U L ，i C 称为一个簇。

2.1. 文本表示模型

文本表示模型也称为文本特征的表达。文本特征是指关于文本的元数据,分为描述性特征(如文本的名称、日期、大小、类型等)和语义性特征(如文本的作者、机构、标题、内容等) 。特征表示是指以一定特征项(如词条或描述)来代表文档,在文本挖掘时只需对这些特征项进行处理,从而实现对非结构化的文本进行处理，这是一个非结构化向结构化转换的处理步骤。

在实际的文本聚类分析研究中，将文本内容变成计算机内部表示结构的方法多种多样，可以用词、字、短语、n-Gram 、显著性短语[8]等形成向量、树等结构。文本表示是文本聚类的第一步，该步骤的变化很多，对最终聚类效果的影响也不尽相同。

本节接下来主要介绍信息检索和文本分析处理中经常用到的几个模型。

2.1.1. 布尔模型

布尔模型是基于集合论与布尔代数的一种简单模型[9]。在布尔模型中，文档j D 中索引特征i T 的权重,i j W 是二值的，即,{0,1}i j W ∈，即可以将单个文本表示称为特征空间上的一个向量，向量中的每个分量权重为0或者1，这种布尔模型称为布尔模型（Boolean Approach ）。由于权重的二值性，所以布尔模型只能用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似度。在经典布尔模型基础上，研究人员又提出了扩展布尔模型（Extended Boolean Approach ），使相关性可以成为[0,1]之间的数。

布尔模型是基于集合论与布尔代数之上的一种表示模型，其表示与计算可以转化为向量来等价实现，是一种类向量的模型。

2.1.2. 向量空间模型

1969年，Gerard Salton 提出的向量空间模型VSM （Vector Space Model ）是信息检索领域中经典的检索模型。该模型的主要思想是：将每一文档都映射为一组规范化正交词条矢量张成的向量空间中的一个点[10]。

在用向量表示文档时，需要对文档集进行切分、停用词处理等步骤。在经过这些步骤后，基本上就可以得到一系列词或词素，将这些词或词素作为文档的特征。此时，所有的这些词就构成了一个“空间”，每个词对应着空间中的一维。

表2-1 VSM 模型中文本与空间的映射表 文档视角

向量空间模型视角 文档

向量、空间中的点 词或词素

空间中的一个维度 文档集合

分布在空间中的一组点集 词的权重 空间中点的坐标值

对于每个文档j D ，都可以用文档中的词来表示，这些词及其对应的权重就构成了“空间”中的一个向量：

()1,j 2,j n,j ,,,W

W W L (2. 1) 其中，,i j W 为j D 中词条i 的权重。

权重的经典定义是： ,,*i j i j i W TF IDF = (2. 2)

TF 指Term Frequency ，表示词条i 在文档j D 中出现的次数，称为词频；IDF 指Inverse Document Frequency 。Salton 将IDF 定义为：

log()i i N IDF n = (2. 3)

在这个公式中，N 表示文档集合中所有的文档数目，i n 表示整个文档集合中出现过词条i 的文档的总数，称为特征的文档频率。

2.1.

3. 概率检索模型

概率检索模型[11][12]是信息检索领域另一比较成熟的模型，并在很多系统中应用取得不错的效果。概率模型是一系列模型的简称，它综合考虑了词频、文档频

率和文档长度等因素，把文档和用户兴趣（查询）按照一定的概率关系融合，并在概率测度空间上通过概率来衡量两个文本的语义相似度。在信息检索中，主要计算P（Relevance | Document, Query），并利用概率排序原则PRP（Probabilistic Ranking Principle）[13][14]来判断不同文档与同一个查询相关的程度。

P（Relevance | Document, Query）表示对于查询Query，文档Document与该查询相关的概率。根据不同的假设得到的求P（Relevance | Document, Query）的计算公式，可以衍生出不同的概率检索模型。概率检索模型包括BIR（Binary Independence Retrieval），INQUERY等。其中，应用最广的是OKAPI模型[15]，该模型在信息检索领域取得了成功，并在多届的TREC（Text Retrieval Conference）评测中都取得了很好的成绩。

2.1.4. 语言模型

语言模型[16]本质上也是一种基于概率和统计的模型。在语言模型中，每个文档、整个语料库、相关查询都被看作是语言模型，通过计算语言模型之间的距离来衡量查询与文档的相关性及文档与文档之间的相关性。

语言模型就其研究方向而言，一般分为两类。一类是基于语言学知识的规则文法，另一类是基于统计的语言模型。目前，以语料库为基础的统计语言建模方法成为潮流。这种方法通过对语料库进行深层加工、统计和学习，来获取大规模真实语料中的语言知识。统计语言模型认为语言就是字母表上的一种概率分布，通过概率分布计算任何一个字母序列成为该语言一个语言单元（句子、段落、文

D中形成一个分布，这个概率分布就称章等）的可能性。特征集合在某个文档

j

为一个语言模型。

在语言模型研究方面，卡内基梅隆大学（Carnegie Mellon University，CMU）的语言技术研究所（Language Technologies Institute）和马萨诸塞大学（University of Massachusetts，UMass）的智能信息检索中心（Center for Intelligent Information Retrieval）合作开发的LEMUR系统是实现语言模型的信息检索系统，在TREC 中取得过很好的成绩，该系统也是研习语言模型的有用工具。

2.2. 文本相似度衡量

在文本聚类中，除了对文本进行表示外，还必须对文本进行相似度度量。相似度度量是影响聚类效果的一个重要方面。

相似度是用来衡量两个对象之间相似程度的度量。同时，我们也可以使用距离的概念来衡量两个对象之间的不相似程度。相似度和距离是两个相对的概念，在聚类分析中这两个概念经常一起使用。

在文本聚类分析中，主要有三种相似度度量（距离同）：

1. 文档与文档之间的相似度度量；

2. 文档与文档集合之间的相似度度量；

3. 文档集合与文档集合之间的相似度度量。

2.2.1. 文档与文档之间的相似度度量

为了衡量以向量形式表示的文档X 与Y 之间的距离，最常用的方法就是采用明氏距离：

1(,)((-))q q i i i Sim X Y x y =∑

(2. 4)

其中，2q =时，就是著名的欧几里德距离。

除此之外，我们还可以采用文档表示向量之间的余弦夹角来衡量X 与Y 之间的相似度：

*(,)(,)i

i x y Sim X Y Cos X Y ==∑ (2. 5)

在语言模型中，文档之间的距离可以采用Kullback-Leiblerj 距离（简称KL 距离)来计算查询Q 的语言模型与文档D 的语言模型之间的相关性：

()(,)()log ()i Q i Q i w Q D i p w KL Q D p w p w ∈=∑ (2. 6)

2.2.2. 文档集合与文档集合之间的相似度度量

为了衡量文档集合之间的相似度，常见的方法有：最小距离、最大距离、平均距离、质心法、离差平方和、代表点[17]等。以下是各个相似度定义的数学描述， 其中，1C 与2C 分别表示两个文档集合。

1．最小距离（Single link ）：

1212(,)min{(,)|,}j D C C D X Y X C Y C =∈∈

(2. 7)

2．最大距离（Complete link ）： 1212(,)max{(,)|,}D C C D X Y X C Y C =∈∈

(2. 8)

3．平均距离（Average link ）：

1212121(,)*(,)||*||X C Y C D C C D X Y C C ∈∈=∑∑ (2. 9)

4．质心法：使用集合中所有文档向量的算术平均作为集合的中心向量，这之后，使用计算文档与文档相似度的方法来计算文档集合之间的相似度。

5．离差平方和（Ward ）：

121212(,)()()()D C C S C C S C S C =∪??

(2. 10)

其中， ()()()*T X C S C X X X X ∈=

??∑ (2. 11)

6．代表点：从集合中选择若干个最能代表该集合的点，利用这些点来计算集合与集合之间的相似度。

2.2.

3. 文档与文档集合之间的相似度度量

对于文档与文档集合之间相似度度量的问题，我们可以将文档看作是只含有一个文档的文档集合。我们可以套用上面介绍的文档集合与文档集合之间相似度度量的办法来衡量。

在能够度量文档之间的相似性之后，理论上我们就可以通过聚类算法对文档进行聚类分析了。

2.3. 文档信息特征集的缩减

在讨论文本聚类分析算法之前，本文需要再讨论一下文档信息特征集的缩减问题。这主要是因为：在实际的聚类分析过程中，如果采用向量表示模型，文档特征向量往往具有惊人的维数，如此高维的特征对即将进行聚类的分析过程未必全是重要有益的（按照经验，一般只选择2% ～5%的最佳特征就可以获得较好的聚类效果）。而且，高维的特征会大大增加聚类的处理负荷，影响聚类的时间效应，因此我们需要选择一个好的特征提取算法以选取最终用于聚类的文档信息特征。

为了提取特征信息，通常采取的方法是构造一个评价函数[18]，针对每个特征进行评估，然后按照特征词条的排序，选取预定数目的最佳特征作为结果的特征子集。在文本处理中,常用的评价函数主要有以下几种：

2.3.1. 信息增益

整个特征集T 的熵为：

1()log k k k i I T p p ==

?∑L (2. 12)

其中，i 为特征集的维数，k p 为当前特征词条的出现概率。

特征k T 的熵为：

()log k k k I T p p =? (2. 13)

针对特征k T 的信息增益( Information Gain)为：

(,)()(,)k k Gain T T I T I T T =?

(2. 14)

其中，()k P T 为特征k T 出现的概率， 1(,)()()k k k k i p I T T I T I T ==?∑L (2. 15)

2.3.2. 期望交叉熵

特征k T 的期望交叉熵( Expected Cross Entropy )为：

1(|)()()(|)log

()l k k k l k k i l P C T f T P T P C T P C ==∑L (2. 16)

其中，()k P T 为特征k T 出现的概率，(|)l k P C T 为类别l C 在特征k T 出现情况下的概率，()l P C 为类别l C 的出现概率。

2.3.3. 互信息量

在特征选择领域中，特征k T 和类别l C 的互信息体现了特征与类别的相关程度。特征k T 的互信息量(Mutual Information )为：

1()()*log((|)/())k l k l k k i MI T p C p T C p T ==

∑L (2. 17)

2.3.4. 文本证据权

文本证据权(the Weight of Evidence for Text, WET )比较了()l p C 与(|)l p C t 之间的差别，特征k T 的定义为：

1log((|)(1())()()*

()*())

()(1(|))l k l k k l l l k k i p C T p C WET T p T p C abs p C p C T =??=?∑L

(2. 18)

2.3.5. 词频

词频（Word Frequency ），即特征词条k T 出现的频率，按照词条频率的大小来

选取最佳特征作为结果的特征子集。

2.4. 中文文本聚类算法

常见的聚类分析的方法有五类[19]：划分方法（Partitioning Method ）、层次方法（Hierarchical Method ）、基于密度的方法（Density-Based Method ）、基于网格的方法（Grid-Based Method ）、基于模型的方法（Model-Based Method ），其代表性算法请参见图2-1。

2.4.1. 划分方法

划分方法（Partitioning Method ）的基本思想是：将数据集合D 中的n 个元素进行划分，形成一个平面的类结构，同时满足如下要求：

1．每个组至少包含一个对象；

2．每个对象必须属于且只属于一个组。（在某些模糊划分技术中第二个要求可以

放宽）；

3．指定一个相异函数F 来计算元素之间的差异，使得在同一个簇中的对象之间

尽可能的相近或相关，而不同簇中的对象之间尽可能远离或不同。

划分方法的典型算法代表有k ?均值算法（K-Means ）、k ?中心点算法（K-Medoids ）、最近邻聚类（Nearest Neighbor ）、最大距离聚类（Max-Distance Clustering ）等。

空间聚类的研究现状及其应用_戴晓燕

空间聚类的研究现状及其应用＊ 戴晓燕1　过仲阳1　李勤奋2　吴健平1 (1华东师范大学教育部地球信息科学实验室　上海　200062) (2上海市地质调查研究院　上海　200072) 摘　要　作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 关键词　空间聚类　K-均值法　散度 1　前言 随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。 空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。例如,土地利用、居住类型的空间分布、商业区位分布等。因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。 空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。 本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 2　划分法 设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。聚类过程中,通常用相似度函数来计算某个点的偏离。常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。 K-均值法[3]根据簇中数据对象的平均值来计算 ——————————————— ＊基金项目:国家自然科学基金资助。(资助号: 40371080) 收稿日期:2003-7-11 第一作者简介:戴晓燕,女,1979年生,华东师范大学 地理系硕士研究生,主要从事空间数 据挖掘的研究。 · 41 · 2003年第4期 上海地质 Shanghai Geology

K-means文本聚类算法

最大距离法选取初始簇中心的K-means文本聚类算法的研究 的评论 背景 随着计算机技术和网络技术的飞速发展，人们的生活方式产生了极大的改变。计算机从一个有几个房子大小的巨无霸，已经变成了小巧的笔记本。网络设备也已经从PC端走向移动端。越来越丰富的网络设备，让人们能在网络里畅游，网络对于人们来说触手可及，同时也产生了巨大的数据流量。人们如何从海量的数据中找到有用的信息，成为了现在计算机学科的研究热点。聚类是数据挖掘中重要的一支。由于聚类具有无需先验知识的优势，可以根据数据自然分部而获取知识。聚类成为数据挖掘领域一个非常活跃的领域，而且得到了广泛的应用。聚类就是把一个数据集合分成几个簇，在同一个簇里，数据相关性最高，但是在2个不同的簇里，数据相关性最低。K-means聚类算法主要针对处理大数据集时，处理快速简单，并且算法具有高效性和可伸缩性。但是，K-means聚类算法随机的选择初始簇中心会导致以下缺点：（1）得到的聚类结果中容易出现局部最优，而不是全局最优；（2）聚类结果不具有稳定性，很大程度上依赖于初始簇中心；（3）聚类过程中的迭代次数增加使聚类过程中的总耗时增加。 传统的k-means聚类算法 传统的聚类算法思想：首先从N个数据对象集合中随机选择k个对象，然后计算剩余的N-k个对象与k个对象的距离（相似度），与k个对象中哪个对象的距离最小，就把分给那个对象；然后在计算每个簇中的簇中心，即是每个簇中对象的均值；不断重复这一过程步骤，直到标准测度函数E开始收敛为止。 K-means算法描述如下： 输入：迭代终止条件ε，最大的迭代次数为max，簇的总数目是k，样本集有N个数据对象。 输出：满足迭代终止条件的k个簇和迭代次数s。 随机初始化k个簇中心： 对每个数据对象，分别计算该对象与k个簇中心均值的距离，并选择距离最小的簇将该对象加个到该簇里； 重新计算k个簇的中心，利用函数E计算出此时的函数值； 如果带到最大迭代次数或满足：

文本聚类

目录 1 概念及应用背景 (1) 1.1概念 (1) 1.2应用背景 (1) 2 系统设计框架 (2) 2.1总体框架 (2) 2.2文本聚类的具体过程 (3) 3应用程序具体实现及说明 (4) 3.1获取文档的输入 (4) 3.2提取文档的TF/IDF权重 (5) 3.3 k-means进行数据聚类 (6) 4 实验结果及分析 (7) 4.1实验结果 (7) 4.2结果分析 (10) 5结论 (10) 5.1实验结论 (10) 5.2个人感受 (11) 附录：项目框架和主程序代码 (12)

1 概念及应用背景 1.1概念 文本聚类（Text clustering）是在没有学习的条件下对文本集合进行组织或划分的过程，其主要依据著名的聚类假设：同类的文档相似度较大，而不同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来越多的研究人员所关注。（代码下载：https://www.sodocs.net/doc/6f10978696.html,/source/3277899） 1.2应用背景 文本聚类是搜索引擎和语义Web的基本技术，Internet 已经发展为当今世界上最大的信息库和全球范围内传播信息最主要的渠道。随着Internet 的大规模普及和企业信息化程度的提高，各种资源呈爆炸式增长。在中国互联网络信息中心(CNNIC)2011年1月最新公布的中国互联网络发展状况统计报告中显示，自2003年开始，中国的网页规模基本保持翻番增长，2010年网页数量达到600亿个，年增长率78.6%，其中仍有62.3% 的网络信息均以文本形式体现。对于这种半结构或无结构化数据，如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。近年来，文本挖掘、信息过滤和信息检索等方面的研究出现了前所未有的高潮。 作为一种无监督的机器学习方法，聚类技术可以将大量文本信息组成少数有意义的簇，并提供导航或浏览机制。 文本聚类的主要应用点包括： (1) 文本聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤。 (2) 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。 (3) 对用户感兴趣的文档（如用户浏览器cache中的网页）聚类，从而发现用户的兴趣模式并用于信息过滤和信息主动推荐等服务。 (4) 改善文本分类的结果。 (5) 数字图书馆服务。通过SOM神经网络等方法，可以将高维空间的文档拓扑保序地映射到二维空间，使得聚类结果可视化和便于理解。 (6) 文档集合的自动整理。如Scatter/Gather，它是一个基于聚类的文档浏览系统。

子空间聚类Sparse Subspace Clustering SSC

【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm Symbol definition： is n linear subspace of . is the dimentsion of . is N noise-free data points. is a rank- matrix, represent (>) points that lie in . is a unknown permutation matrix. SSC Algorithm: Step 1: Solve the sparse optimization program ①Uncorrupted data ②Corrupted data ps: E corresponds to a matrix of sparse outlying entries, and Z is a noise matrix. Step 2: Normalize the columns of C as . ps: max norm : .

Step 3: Form a similarity grahp with N nodes wegiths on the edges between the nodes by . ps: Step: Use spectral clustering to the similarity graph. Output: . Subspace-Sparse Recovery Theory Definition: ① ps: is said to be independent. ② ③Principle angle between and

文本聚类的现状研究

1 文本聚类研究现状 1 文本聚类研究现状 Internet 已经发展为当今世界上最大的信息库和全球范围内传播信息最主要的渠道。随着Internet 的大规模普及和企业信息化程度的提高，各种资源呈爆炸式增长。在中国互联网络信息中心(CNNIC)2007 年 1 月最新公布的中国互联网络发展状况统计报告中显示，70.2% 的网络信息均以文本形式体现。对于这种半结构或无结构化数据，如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。近年来，文本挖掘、信息过滤和信息检索等方面的研究出现了前所未有的高潮。 作为一种无监督的机器学习方法，聚类技术可以将大量文本信息组成少数有意义的簇，并提供导航或浏览机制。 文本聚类的主要应用点包括： (1) 文本聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤。其中比较典型的例子是哥伦比亚大学开发的多文档自动文摘系统Newsblaster[1] 。该系统将新闻进行 聚类处理，并对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档。 (2) 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。比较典型的系统有Infonetware Real Term Search 。Infonetware 具有强大的对搜索结果进行主题分类的功能。另外，由Carrot Search 开发的基于Java 的开源Carrot2 搜索结果聚合聚类引擎2.0 版也是这方面的利用，Carrot2 可以自动把自然的搜索结果归类( 聚合聚类) 到相应的语义类别中，提供基于层级的、同义的以及标签过滤的功能。 (3) 改善文本分类的结果，如俄亥俄州立大学的Y.C.Fang 等人的工作[2] 。 (4) 文档集合的自动整理。如Scatter/Gather[3] ，它是一个基于聚类的文档浏览系统。 2 文本聚类过程 文本聚类主要依据聚类假设：同类的文档相似度较大，非同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程、以及不需要预先对文档手工标注类别，因此具有较高的灵活性和自动化处理能力，成为对文本信息进行有效组织、摘要和导航的重要手段。文本聚类的具体过程如图 1 所示。 图 1 文本聚类过程 2.1 文本信息的预处理 文本聚类的首要问题是如何将文本内容表示成为数学上可分析处理的形式，即建立文本特

基于向量空间模型的文本聚类算法

基于向量空间模型的文本聚类算法 转自：https://www.sodocs.net/doc/6f10978696.html,/2009/0910/15270.php 1 文本聚类研究现状 Internet 已经发展为当今世界上最大的信息库和全球范围内传播信息最主要的渠道。随着Internet 的大规模普及和企业信息化程度的提高，各种资源呈爆炸式增长。在中国互联网络信息中心(CNNIC)2007 年1 月最新公布的中国互联网络发展状况统计报告中显示，70.2% 的网络信息均以文本形式体现。对于这种半结构或无结构化数据，如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。近年来，文本挖掘、信息过滤和信息检索等方面的研究出现了前所未有的高潮。 作为一种无监督的机器学习方法，聚类技术可以将大量文本信息组成少数有意义的簇，并提供导航或浏览机制。 文本聚类的主要应用点包括： (1) 文本聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤。其中比较典型的例子是哥伦比亚大学开发的多文档自动文摘系统Newsblaster[1] 。该系统将新闻进行 聚类处理，并对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档。 (2) 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。比较典型的系统有Infonetware Real Term Search 。Infonetware 具有强大的对搜索结果进行主题分类的功能。另外，由Carrot Search 开发的基于Java 的开源Carrot2 搜索结果聚合聚类引擎2.0 版也是这方面的利用，Carrot2 可以自动把自然的搜索结果归类( 聚合聚类) 到相应的语义类别中，提供基于层级的、同义的以及标签过滤的功能。 (3) 改善文本分类的结果，如俄亥俄州立大学的Y.C.Fang 等人的工作[2] 。 (4) 文档集合的自动整理。如Scatter/Gather[3] ，它是一个基于聚类的文档浏览系统。 2 文本聚类过程 文本聚类主要依据聚类假设：同类的文档相似度较大，非同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程、以及不需要预先对文档手工标注类别，因此具有较高的灵活性和自动化处理能力，成为对文本信息进行有效组织、摘要和导航的重要手段。文本聚类的具体过程如图 1 所示。 图 1 文本聚类过程

数据挖掘研究及发展现状

数据挖掘技术的研究现状及发展方向 摘要：数据挖掘技术是当前数据库和人工智能领域研究的热点。从数据挖掘的定义出发，介绍了数据挖掘的神经网络法、决策树法、遗传算法、粗糙集法、模糊集法和关联规则法等概念及其各自的优缺点；详细总结了国内外数据挖掘的研究现状及研究热点，指出了数据挖掘的发展方向。 关键词：数据挖掘；神经网络；决策树；粗糙集；模糊集；研究现状；发展方向 The present situation and future direction of the data mining technology research Abstract: Data mining technology is hot spot in the field of current database and artificial intelligence. From the definition of data mining, the paper introduced concepts and advantages and disadvantages of neural network algorithm, decision tree algorithm, genetic algorithm, rough set method, fuzzy set method and association rule method of data mining, summarized domestic and international research situation and focus of data mining in details, and pointed out the development trend of data mining. Key words: data mining, neural network, decision tree, rough set, fuzzy set, research situation, development direction 0 引言 随着信息技术的迅猛发展，许多行业如商业、企业、科研机构和政府部门等都积累了海量的、不同形式存储的数据资料[1]。这些海量数据中往往隐含着各种各样有用的信息，仅仅依靠数据库的查询检索机制和统计学方法很难获得这些信息，数据和信息之间的鸿沟要求系统地开发数据挖掘工具，将数据坟墓转换成知识金砖，从而达到为决策服务的目的。在这种情况下，一个新的技术——数据挖掘(Data Mining，DM)技术应运而生[2]。数据挖掘正是为了迎合这种需要而产生并迅速发展起来的、用于开发信息资源的、一种新的数据处理技术。 数据挖掘通常又称数据库中的知识发现（Knowledge Discovery in Databases），是一个多学科领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、信息检索等最新技术的研究成果，其应用非常广泛。只要是有分析价值的数据库，都可以利用数据挖掘工具来挖掘有用的信息。数据挖掘典型的应用领域包括市场、工业生产、金融、医学、科学研究、工程诊断等。本文主要介绍数据挖掘的主要算法及其各自的优缺点，并对国内外的研究现状及研究热点进行了详细的总结，最后指出其发展趋势及问题所在。 1 数据挖掘算法 数据挖掘就是从大量的、有噪声的、不完全的、模糊的、随机的实际应用数据中提取有效的、新颖的、潜在有用的知识的非平凡过程[3]。所得到的信息应具有先前未知、有效和实用三个特征。数据挖掘过程如图1所示。这些数据的类型可以是结构化的、半结构化的、甚至是异构型的。发现知识的方法可以是数学的、非数学的、也可以是归纳的。最终被发现了的知识可以用于信息管理、查询优化、决策支持及数据自身的维护等[4]。 数据选择：确定发现任务的操作对象,即目标对象； 预处理：包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等； 转换：消减数据维数或降维； 数据开采：确定开采的任务，如数据总结、分类、聚类、关联规则发现或序列模式发现等，并确定使用什么样的开采算法； 解释和评价：数据挖掘阶段发现的模式，经过用户和机器的评价，可能存在冗余或无关的模式，这时需要剔除，使用户更容易理解和应用。十大经典算法如图2： 目前，数据挖掘的算法主要包括神经网络法、决策树法、遗传算法、粗糙集法、模糊集法、关联规则法等。

基于文本的聚类算法研究本科毕设论文

摘要 聚类作为一种知识发现的重要方法，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源。文本聚类是聚类问题在文本挖掘中的有效应用，它根据文本数据的不同特征，按照文本间的相似性，将其分为不同的文本簇。其目的是要使同一类别的文本间的相似度尽可能大，而不同类别的文本间的相似度尽可能的小。整个聚类过程无需指导，事先对数据结构未知，是一种典型的无监督分类。 本文首先介绍了文本聚类的相关的技术，包括文本聚类的过程，文本表示模型，相似度计算及常见聚类算法。本文主要研究的聚类主要方法是k-均值和SOM 算法，介绍了两种算法的基本思想和实现步骤，并分析两种算法的聚类效果。同时介绍了两种算法的改进算法。 关键词：文本聚类聚类方法K-MEAN SOM

Abstract Clustering as an important knowledge discovery method, which extensively with Chinese information processing technology, used in network information processing to meet the users to quickly access from the Internet, the information resources they need. Text clustering is a clustering problem in the effective application of text mining, which according to the different characteristics of text data, according to the similarity between the text, the text will be divided into different clusters. The aim is to make the same class as large as possible the similarity between the text, and different types of text as small as possible the similarity between. The clustering process without guidance, prior to the data structure is unknown, is a typical unsupervised classification. This paper studies the effect of influencing factors that text clustering, text representation of the model such as the Boolean model, vector space model, probabilistic retrieval model and language model. Also studied the analysis of such text clustering algorithm: hierarchical clustering, agglomerative hierarchical clustering algorithm, hierarchical clustering algorithm to split and so on. Also studied the text clustering algorithm analysis and methods of improvement. Key words：Text clustering clustering method k-mean som

文本聚类研究知识图谱分析_奉国和

文本聚类研究知识图谱分析 奉国和1,黄家兴1,薛 云2 （1.华南师范大学经济与管理学院,广东广州510006; 2.华南师范大学物理与电信工程学院,广东广州510006） 摘要：利用词频分析、共词分析、聚类分析、多维尺度分析，绘制我国2005—2010年间文本聚类 研究的知识图谱，得出领域研究结构，结合关键词粘合力，归纳出该领域四个类团研究群：相似度研究、向量空间模型、搜索引擎、Web 文本挖掘。关键词：文本聚类；知识图谱；共词分析；多元统计分析中图分类号：G250.2 文献标识码：A 文章编号：1007-7634（2014）03-23-05 Study in the Knowledge Mapping of the Text Clustering FENG Guo-he 1,HUANG Jia-xing 1,XUE Yun 2 （1.School of Economics and Management,South China Normal University,Guangzhou 510006,China; 2.School of Physics and Telecommunication,South China Normal University, Guangzhou 510006,China ） Abstract:Word-frequency analysis,Co-word analysis,together with Cluster analysis and Multi-dimen ?sional analysis,are used in the paper to draw the mapping of knowledge of the Text clustering in China from the year of 2005to https://www.sodocs.net/doc/6f10978696.html,bining with key words adhesion method reveals the research structure of this field.The conclusion indicates that there are four groups in the research of text clustering,which is Similarity study,Vector Space Model,Search Engine,Web Text mining. Key words ：text clustering;knowledge mapping;co-word analysis;multivariate statistical analysis 1引言文本聚类（Text clustering ）是指利用聚类分析使得同类的文档相似度较大，而不同类的文档相似度较小，它是一种无监督的机器学习方法，已经成为文本信息有效地组织、信息过滤、信息推荐、摘要和导航的重要手段，为越来越多的研究人员所关注。本文基于共词分析对2005年至2010年间国内文本聚类研究文献进行聚类与知识图谱分析，探索出国内文本聚类领域的研究结构，为相关研究者提供参考。 2数据来源与研究方法 2.1材料来源及预处理 在CNKI 学术期刊数据库中，以“文本聚类”为检索词，检索时间跨度为2005年1月1日至2010年12月31日，进行题名或关键词检索，为提高研究的 准确性而去除中英文扩展检索，将文献记录导入NoteExpress ，剔除重复及无关键词的记录后得到有效文献382篇，提取出关键词1530个。对关键词进 行规范化处理，将关键词中的同义词和相似词进行 收稿日期：2012-01-21 基金项目：广州市科技计划项目（2011J4300046) 作者简介：奉国和（1971-），男，湖南永州人，副教授，博士，主要从事文本分类、信息检索、自然语言处理研究. 情报科学 第32卷第3期2014年3月 ·理论研究· - -23DOI:10.13833/https://www.sodocs.net/doc/6f10978696.html,ki.is.2014.03.012

【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm=

Sparse subspace clustering:Algorithm,theory,and Application 稀疏子空间聚类（SSC）的算法，理论和应用 参考文献： 1、E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm,theory,and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013 2、E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 2009 2013年的这篇论文写得比09年那篇容易懂一些，讨论和实验也更详细。2013年的这篇可以看成是09那篇会议的扩展版。 一、算法 数据没有损坏，求解模型（5）获得矩阵C：

数据有损坏（noise and sparse outlying entries)，求解模型（13）获得矩阵C： 仿射子空间模型： 二、理论 1、independent子空间 设rank(Yi)=di，Yi表示从第i个子空间Si抽取的Ni个样本构成的矩阵，di 表示Si的维数。论文的定理1表明，模型（5）的解C*是一个块对角矩阵，属于同一个子空间的数据间的cij可能非零，不属于同一个子空间的数据间的cij=0.

2、disjoint子空间 对于disjoint子空间，除了满足条件rank(Yi)=di外，还需要满足公式（21）： 则可获得与independent子空间下类似的结论：

数据挖掘技术的研究现状及发展方向_陈娜

数据挖掘技术的研究现状及发展方向 陈娜1.2 （1.北京交通大学计算机学院，北京100044；2.石家庄铁路运输学校，河北石家庄050021） 第 !" 电脑与信息技术卷 （ ! ）可视化技术 ［ " ］ 通过直观的图形方式将 信息数据、关联关系以及发展趋势呈现给决策者， 使用最多的方法是直方图、数据立方体、散点图。 其中数据立方体可以通过 #$%& 操作将更多用户 关心的信息反映给用户。 （ ’ ）遗传算法 ［ ( ］ 是一种模拟生物进化过程 的算法，最早由 )*++,-. 于 /0 世纪 (0 年代提出。 它是基于群体的、具有随机和定向搜索特征的迭 代过程，包括 ! 种典型的算子：遗传、交叉、变异和 自然选择。遗传算法作用于一个由问题的多个潜

在解（个体）组成的群体上，并且群体中的每个个体都由一个编码表示，同时个体均需依据问题的 目标函数而被赋予一个适应值。另外，为了应用遗传算法，还需要把数据挖掘任务表达为一种搜索 的问题，以便发挥遗传算法的优势搜索能力。同时可以用遗传算法中的交叉、变异完成数据挖掘中 用于异常数据的处理。 （ "）统计学方法 ［ 1 ］ 在数据库字段项之间存 在着两种关系：函数关系（能用函数公式表示的确定性关系）和相关关系（不能用函数公式表示，但仍是相关确定关系）。对它们的分析采用如下方 法：回归分析、相关分析、主成分分析。主要用于数据挖据的聚类方法中。 （ (）模糊集（23445 678）方法利用模糊集理 论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化能力就越低，即模糊性就越强，这是 9,.7: 总结出的互克性原理。 / 数据挖掘的算法 （ ;）关联规则中的算法 %<=>*=>算法是一种最具有影响力的挖掘布 尔关联规则频繁项集的算法，该算法是一种称为 主层搜索的迭代方法，它分为两个步骤： ,?通过多趟扫描数据库求解出频繁;@项集的 集合 $ ; ； A?不断的寻找到/@项集$ / … -@项集$ - ，最后 利用频繁项集生成规则。 随后的许多算法都沿用

稀疏子空间聚类算法

稀疏子空间聚类算法与模型建立 稀疏子空间聚类是一种基于谱聚类的子空间聚类方法， 基本思想：假设高位空间中的数据本质上属于低维子空间，能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间, 有利于数据聚类. 基 本方法是, 对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数, 然后根据表示系数矩阵构造相似度矩阵, 最后利用谱聚类方法如规范化割(Normalized cut, Ncut)[22] 获得数据的聚类结果。 基本原理 稀疏子空间聚类[32] 的基本思想是: 将数据 αS x i ∈表示为所有其他数据的线性组合, j i j ij i x Z x ∑≠= （1） 并对表示系数施加一定的约束使得在一定条件下对所有的αS x j ?, 对应的0=ij Z 。将所有数据及其表示系数按一定方式排成矩阵 ，则式（1）等价于 XZ X = （2） 且系数矩阵N N R Z ?∈ 满足: 当i x 和j x 属于不同的子空间时, 有0=ij Z . 不同于用一组基或字典表示数据, 式（2）用数据集本身表示数据, 称为数据的自表示. 若已知数据的子空间结构, 并将数据按类别逐列排放, 则在一定条件下可使系数矩阵Z 具有块对角结构, 即 ????? ???????=k Z Z Z Z 00000021 （3） 这里),,1(k Z =αα 表示子空间αS 中数据的表示系数矩阵; 反之, 若Z 具有块对角结构, 这种结构揭示了数据的子空间结构. 稀疏子空间聚类就是通过对系数矩阵Z 采用不同的稀疏约束, 使其尽可能具有理想结构, 从而实现子空间聚类. Elhamifar 等[32] 基于一维稀疏性提出了稀疏子空间聚类(Sparse subspace clustering,SSC) 方法, 其子空间表示模型为 1min Z Z 0,..==ii Z XZ X t s （4）

聚类算法的研究综述

聚类算法的研究综述 华东交通大学理工学院 Institute of Technology. East China Jiaotong University 毕业论文 Graduation Thesis （2009―7>2013年） 题目聚类算法的研究综述 分院：电子与信息工程分院 专业：信息管理与信息系统 班级：信管2009-2 学号： 20090210450221 学生姓名：于继伟 指导教师：葛菁 起讫日期: 2012-12――2013-05 华东交通大学理工学院 毕业设计（论文）原创性申明 本人郑重申明：所呈交的毕业设计（论文）是本人在导师指导下独立进行的研究工作所取得的研究成果。设计（论文）中引用他人的文献、数据、图件、资

料，均已在设计（论文）中特别加以标注引用，除此之外，本设计（论文）不含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式表明。本人完全意识到本申明的法律后果由本人承担。 毕业设计（论文）作者签名：日期：年月日毕业设计（论文）版权使用授权书 本毕业设计（论文）作者完全了解学院有关保留、使用毕业设计（论文）的规定，同意学校保留并向国家有关部门或机构送交设计（论文）的复印件和电子版，允许设计（论文）被查阅和借阅。本人授权华东交通大学理工学院可以将本设计（论文）的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编毕业设计（论文）。 （保密的毕业设计（论文）在解密后适用本授权书） 毕业设计（论文）作者签名：指导教师签名： 签字日期：年月日签字日期：年月日 摘要 聚类算法的兴起，大大地改变了我们的生活和工作方式。这是计算机科学的发展和相关学科发展的必然结果。聚类算法作为数据挖掘中的一部分，我们不仅利用聚类算法进行我们的科研，而且我们的日常生活中聚类算法的应用也无处不在。可以说和我们的生活息息相关。目前这方面的专家也在致力于聚类算法的研究，在现有的聚类算法的基础上改进以及发掘出新的聚类算法。因为没有什么是一成不变的，聚类算法也有缺点，因此必须不断改进和创新。 例如我们的学校、政府单位、企业都需要用到聚类算法和聚类分析，

基于分布式低秩表示的子空间聚类算法

计算机研究与发展ＤＯＩ：１０．７５４４桙ｉｓｓｎ１０００‐１２３９．２０１６．２０１４８３６２ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ５３（７）：１６０５１６１１，２０１６　收稿日期：２０１４－１２－０９；修回日期：２０１５－０６－０９ 　基金项目：国家自然科学基金项目（６１３７３０５５）；江苏省自然科学基金项目（ＢＫ２０１４０４１９）；江苏省高校自然科学研究计划重大项目 （１４ＫＪＢ５２０００１） ＴｈｉｓｗｏｒｋｗａｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（６１３７３０５５），ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（ＢＫ２０１４０４１９），ａｎｄｔｈｅＭａｊｏｒＰｒｏｇｒａｍｏｆＲｅｓｅａｒｃｈＰｌａｎｏｆｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅｉｎＨｉｇｈｅｒＥｄｕｃａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（１４ＫＪＢ５２０００１）．　通信作者：吴小俊（ｗｕ＿ｘｉａｏｊｕｎ＠ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ）基于分布式低秩表示的子空间聚类算法 许　凯　吴小俊　尹贺峰 （江南大学物联网工程学院　江苏无锡　２１４１２２） （ｘｕｋａｉ３４７＠ｓｉｎａ．ｃｏｍ） ＤｉｓｔｒｉｂｕｔｅｄＬｏｗＲａｎｋＲｅｐｒｅｓｅｎｔａｔｉｏｎ‐ＢａｓｅｄＳｕｂｓｐａｃｅＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍＸｕＫａｉ，ＷｕＸｉａｏｊｕｎ，ａｎｄＹｉｎＨｅｆｅｎｇ（ＳｃｈｏｏｌｏｆＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ２１４１２２） Ａｂｓｔｒａｃｔ　Ｖｉｓｉｏｎｐｒｏｂｌｅｍｒａｎｇｉｎｇｆｒｏｍｉｍａｇｅｃｌｕｓｔｅｒｉｎｇｔｏｍｏｔｉｏｎｓｅｇｍｅｎｔａｔｉｏｎｃａｎｎａｔｕｒａｌｌｙｂｅｆｒａｍｅｄａｓｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎｐｒｏｂｌｅｍ，ｉｎｗｈｉｃｈｏｎｅａｉｍｓｔｏｒｅｃｏｖｅｒｍｕｌｔｉｐｌｅｌｏｗｄｉｍｅｎｓｉｏｎａｌｓｕｂｓｐａｃｅｓｆｒｏｍｎｏｉｓｙａｎｄｃｏｒｒｕｐｔｅｄｉｎｐｕｔｄａｔａ．Ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ（ＬＲＲ）ｆｏｒｍｕｌａｔｅｓｔｈｅｐｒｏｂｌｅｍａｓａｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎａｎｄａｃｈｉｅｖｅｓｉｍｐｒｅｓｓｉｖｅｒｅｓｕｌｔｓ．Ｈｏｗｅｖｅｒ，ｉｔｎｅｅｄｓｔｏｔａｋｅａｌｏｎｇｔｉｍｅｔｏｓｏｌｖｅｔｈｅｃｏｎｖｅｘｐｒｏｂｌｅｍ，ａｎｄｔｈｅｃｌｕｓｔｅｒｉｎｇａｃｃｕｒａｃｙｉｓｎｏｔｈｉｇｈｅｎｏｕｇｈ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＤＬＲＲＳ）．ＤＬＲＲＳａｄｏｐｔｓｔｈｅｄｉｓｔｒｉｂｕｔｅｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｔｏｇｅｔｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ｔｈｅｎｔａｋｅｔｈｅａｂｓｏｌｕｔｅｖａｌｕｅｏｆｅａｃｈｅｌｅｍｅｎｔｏｆｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ａｎｄｒｅｔａｉｎｔｈｅｋｌａｒｇｅｓｔｃｏｅｆｆｉｃｉｅｎｔｓｐｅｒｃｏｌｕｍｎａｎｄｓｅｔｔｈｅｏｔｈｅｒｅｌｅｍｅｎｔｓｔｏ０ｔｏｇｅｔａｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｆｉｎａｌｌｙ，ＤＬＲＲＳｐｅｒｆｏｒｍｓｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｏｖｅｒｔｈｅｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｂｕｔｉｔｄｏｅｓｎ摧ｔｈａｖｅｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇｆｕｎｃｔｉｏｎ，ｓｏｔｈｅｒｅｉｓａｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＳＤＬＲＲＳ）ｈｅｒｅ．Ｉｆｎｅｗｓａｍｐｌｅｓａｒｅｂｒｏｕｇｈｔｉｎ，ＳＤＬＲＲＳｃａｎｕｓｅｔｈｅｆｏｒｍｅｒｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｔｏｃｌａｓｓｉｆｙｔｈｅｎｅｗｓａｍｐｌｅｓｔｏｇｅｔｔｈｅｆｉｎａｌｒｅｓｕｌｔ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎＡＲａｎｄＥｘｔｅｎｄｅｄＹａｌｅＢｄａｔａｓｅｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｃａｎｎｏｔｏｎｌｙｏｂｖｉｏｕｓｌｙｒｅｄｕｃｅｔｈｅｒｕｎｎｉｎｇｔｉｍｅ，ｂｕｔａｌｓｏａｃｈｉｅｖｅｈｉｇｈｅｒａｃｃｕｒａｃｙ，ｗｈｉｃｈｖｅｒｉｆｉｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓａｒｅｅｆｆｉｃｉｅｎｔａｎｄｆｅａｓｉｂｌｅ．Ｋｅｙｗｏｒｄｓ　ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇ；ｃｏｅｆｆｉｃｉｅｎｔｓｒｅｃｏｎｓｔｒｕｃｔｉｏｎ 摘　要　针对基于低秩表示的子空间分割算法运算时间较长、 聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（ｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＤＬＲＲＳ），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前ｋ个绝对值最大系数，其他系数置为０，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果．但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（ｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＳＤＬＲＲＳ），如果有新增样本，可以利用前面的聚类结果对新增样本进行

聚类分析中几种算法的比较

聚类分析中几种算法的比较 2009-04-13 23:12 将数据库中的对象进行聚类是聚类分析的基本操作，其准则是使属于同一类的个体间距离尽可能小，而不同类个体间距离尽可能大，为了找到效率高、通用性强的聚类方法人们从不同角度提出了近百种聚类方法，典型的有K-means 方法、K-medoids方法、CLARANS方法,BIRCH方法等，这些算法适用于特定的问题及用户。本文综合提出了评价聚类算法好坏的5个标准，基于这5个标准，对数据挖掘中常用聚类方法作了比较分析，以便于人们更容易、更快捷地找到一种适用于特定问题及用户的聚类算法。 聚类算法研究及比较框架 聚类算法一般有五种方法，最主要的是划分方法和层次方法两种。划分聚类算法通过优化评价函数把数据集分割为K个部分，它需要K作为输人参数。典型的分割聚类算法有K-means算法, K-medoids算法、CLARANS算法。层次聚类由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系。它不需要输入参数，这是它优于分割聚类算法的一个明显的优点，其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。 对各聚类算法的比较研究基于以下5个标准： ①是否适用于大数据量，算法的效率是否满足大数据量高复杂性的要求; ②是否能应付不同的数据类型，能否处理符号属性; ③是否能发现不同类型的聚类; ④是否能应付脏数据或异常数据; ⑤是否对数据的输入顺序不敏感。 下面将在该框架下对各聚类算法作分析比较。 数据挖掘常用聚类算法比较分析 3.1 K-pototypes算法 K-pototypes算法结合了K-means方法和根据K-means方法改进的能够处理符号属性的K-modes方法，同K-means 方法相比，K-pototypes 算法能够处理符号属性。 3.2 CLARANS算法（划分方法） CLARANS算法即随机搜索聚类算法，是一种分割聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxneighbor个的一些邻接点，假如找到一个比它更好的邻接点，则把它移人该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调人内存，并且需多次扫描数据集，这对大数据量而言，无论时间复杂度还是空间复杂度都相当大。虽通过引人R-树结构对其性能进行改善，使之能够处理基于磁盘的大型数据库，但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据物人顺序异常敏感，且只能处理凸形或球形边界聚类。 3.3 BIRCH算法（层次方法） BIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类特征3元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有两个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数，而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类，非叶子结点为它的子女的最大关键字，可以根据这些关键字进行插人索引，它总结了其子女的信息。 聚类特征树可以动态构造，因此不要求所有数据读人内存，而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T，则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小，控制其占内存容量。 BIRCH算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于大数据量。对于给定的M兆内存空间，其空间复杂度为O(M)，时间间复杂度为O(dNBlnB(M/P)).其中d为维数,N为节点数,P为内存页的大小，B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法只适用于类的分布呈凸形及球形的情况，并且由于BIRCH算法需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行。 3.4 CURE算法（层次方法） CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行了改进，回避了用所有点或用中心和半径来表示一个类，而