维普资讯 http://www.cqvip.com ２００７年第６期 福建 电脑 １ 基于密度聚类方法在文本挖掘中的应用研究 茅剑’．吴顺祥 ｆ１．厦门大学自动化系福建厦门３６１００５ ２．厦门大学系统与控制研究中心福建厦门３６１００５） 【摘要】：文本聚类是文本挖掘的重要组成部分。本文详细分析了文本聚类的过程，并给出了一个文本聚类模型。分析 比较各类聚类算法之后．着重研究了一个基于密度的聚类算法，以及它在文本挖掘中的具体应用。 【关键词】：文本挖掘聚类密度ＤＢＳＣＡＮ １．概述 文本挖掘作为数据挖掘的一个分支．它把文本型信息源作 为分析的对象。利用定量计算和定性分析的方法，从中寻找信息 的结构、模型、模式等各种隐含的知识。文本挖掘又是一项综合 技术，涉及数据挖掘、计算机语言学、信息检索、自然语言管理、 知识管理等诸多领域 文本聚类是文本挖掘中的一项重要技术。它通过对文本内 容的分析。将原始文本集合分成若干个簇，要求簇内文本内容的 相似性尽可能大．而簇之间的 相似度尽可能小。文本聚类可 广泛应用于文本挖掘与信息检 等的。因此需要度量词在文本中的权重，只有大于一定权重阀值 的词才能作为表征文本内容的关键词。提取关键词的工作就称 为文本特征抽取。文本特征抽取的本质是高维数据的降维技术， 即将高维数据通过变换映射到低维空间。降维的主要问题在于。 从高维到低维的变换可能掩盖数据原有的信息。这样原先在高 维空间存在明显差异或特征的类别在低维空间内会混杂在一起 难以区分。因此。寻找合适的映射就成了文本特征抽取的关键。 在文本中的词的加权体系中用某一权重值取代表示该词是 否出现的ｆＯ。ｌｌ二进制布尔表示，通常具有更高的准确性。词在文 本中的权重计算方法主要运用ＴＦ—ＩＤＦ公式。目前存在多种 ｒＦＩ－ＩＤＦ公式．本文中采用的ＴＦ－ＩＤＦ公式： 索的不同方面。文本聚类在大 规模文本集的组织与浏览、文 本集层次归类的自动生成等方 面都具有重要的应用价值。本 文论述的文本聚类模型如图１ 所示： ２．文本预处理 图１ （ｆ， ）＝ 其中。 ）为词ｔ在文本 中的权重，而掀动为词ｔ在文 本 中的词频，Ⅳ为训练文本的总数，，ｌＩ为训练文本集中出现ｔ 的文本数．分母为归一化因子。 ３．文本聚类算法 通过文本预处理．现已得到了可供聚类算法直接处理的标 本文讨论汉语言文本的聚类问题。在进行聚类分析之前。需 要对文本集进行预处理．将文本格式转化成聚类算法能够处理 准数据集。接下来要考虑的是。如何对数据集进行有效的分析， 的数据格式。需要指出的是．文本预处理的应用不仅限于文本聚 得出所需的聚类结果。聚类算法的选择显得至关重要。 类。它同样是文本挖掘的第一个步骤，对文本挖掘效果的影响至 ３．１传统的聚类算法及其局限性 聚类分析作为数据挖掘中的一种分析方法．它可以作为一 关重要。 个单独的工具以发现数据库中数据分布的一些深入的信息．并 目前，在信息处理方向上的基本思想是以向量来表示文本， 且概括出每一类的特点．或者把注意力放在某一个特定的类上 那么选取什么作为特征项呢。一般可以选择字、词或词组，根据 以作进一步的分析：聚类分析也可以作为数据挖掘算法中其他 实验结果。普遍认为选取词作为特征项要优于字和词组。因此。 分析算法的一个预处理步骤。目前．已经提出的聚类算法有很 文本预处理的第一步工作就是文本分词．它是进行文本表示的 多。 （１１划分法：给定一个有Ｎ个对象的数据集，构造Ｋ个分 准备工作。为了将一篇文档切分为一个个的中文单词．本文 采用了一种逆向最大匹配算法。算法基本思想是：从文档的最后 组，每一个分组代表一个簇 ＜ 。对于给定的Ｋ，可以给出一个 字开始，逆向抽取最大长度的字符串．然后在词典中循环匹配 初始的划分方法．以后通过迭代重定位将每个对象归入合适的 可以成词的子字符串。逆向搜索文档直至无词可取。 簇中，从而完成聚类划分。如Ｋ—ＭＥＡＮＳ算法。划分法的缺陷在 分词中要注意的是。为了更好的体现出文本的语义内容。需 于需要事先确定聚类划分的个数Ｋ。而聚类算法的目的正是要 要在分词过程中去除停用词（不宜作为文本特征的词．如介词、 将未知数据集做出合适的划分。可见。这种要得到聚类结果必须 叹词等）和合并同义词（将意思相近的词用一个词替代。如”微 先确认聚簇个数的做法显然会影响到分析结果的客观性。 机”可用”计算机”替换）。停用词典和同义词典需要事先定义。对 （２１层次法：对给定的数据集进行层次的分解，直到某种条 于之后的文本表示来说．这实际上是一个特征值约减的降维过程。 件满足为止。层次法又分为自底向上的凝聚法和自顶向下的分 ２．２文本表示 裂法。其基本算法均是迭代分层至某个终止条件。层次法的缺陷 文本的表示主要采用向量空间模￣ＣＣＳＭ）。向量空间模型的 在于，一个步骤（合并或）完成，就不能被撤销。因此需要和 基本思想是以一个规范化的特征向量来表示文本：ｖ（ ）＝（ｔｌ。 其他算法结合来改进聚类结果。 ｆ３１基于网格的方法：将数据空间划分成有限个单元的网格 Ｗ１；…ｔｉ，Ｗｉ；…ｔｎ，Ｗｎ）。其中ｔｉ为第ｉ个特征项。Ｗｉ为第ｉ个 特征项的权重。在之前文本分词的基础上．把切分后的词作为向 结构．所有的处理都是以单个的单元为对象的。从而使得处理速 量的特征项ｔｉ．将统计过的词频计算后作为向量的权重Ｗｉ来表 度加快．因为它与目标数据库中记录的个数无关，只与数据空间 示文本。词频分为绝对词频和相对词频。绝对词频。即使用词在 的单元多少有关 （４１基于模型的方法：给每一个聚类假定一个模型，然后去 文本中出现的频率表示文本：相对词频为归一化的词频。 文本中词空间维度很高．不同的词对文本内容的贡献是不 寻找能够很好的满足这个模型的数据集。这样一个模型可能是 ２．１文本分词 一基金项目：由厦门大学９８５二期信息创新平台项目和福建省教委科技项目（ＪＡ０５２９０）资助 维普资讯 http://www.cqvip.com ２ 福建 电脑 ２００７年第６期 数据点在空间中的密度分布函数或者其它。它的一个潜在的假 对象加入聚类Ｃ中。 （３）对这些对象做同样的处理。重复（１）（２），直到没有新的 定就是：目标数据集是由一系列的概率分布所决定的。通常有两 种尝试方案：统计的方案和神经网络的方案。 对象可以加入聚类Ｃ。 给定数据集ＤａｔａＳｅｔ，聚类半径ｓ，最小对象数量ＭｉｎＰｔｓ，有 ３．２ ＤＢＳＣＡＮ算法描述及其实现 ＤＢＳＣＡＮ算法是一种基于密度的聚类算法。它利用类的密 ＤＢＳＣＡＮ算法代码实现： ＤＢＳＣＡＮ（ＤａｔａＳｅｔ，８，Ｍｉｎｐｍ） 度连通特性．可以快速发现任意形状的类。其优点在于，它可以 ｛Ｃｌｕｓｔｅｒｌｄ－－ｎｅｘｔｌｄ（ＮＯＩＳＥ）； 发现任意形状的聚类．并且不受”噪声”的干扰 ｆｏｒ（ｉｎｔ．－ｌ；ｉ＜ＤａｔａＳｅｔ．Ｓｉｚｅ；ｉ＋＋） 基于密度聚类的关键思想是．聚类中每个核心点在给定半 ｛Ｐｏｉｎｔ＝ＤａｍＳｅｔ．ｇｅｔ（ｉ）； ｉｆ（Ｐｏｉｎｔ．Ｃｌｉｄ＝＝－ＵＮＣＬＡＳＳＩＦＩＥＤ） 径（８）的圆内的相邻对象至少必须达到一个数量（ＭｉｎＰｔｓ），也就 ｉｆ（ＥｘｐａｎｄＣｌｕｓｔｅｒ（ＤａｔａＳｅｔ，Ｐｏｉｎｔ．Ｃｌｕｓｔｅｒｌｄ，８，Ｍｉｎｐｔｓ）） 是相邻对象的数量必须超过一个阀值。下面对一个聚类的定义 Ｃｌｕｓｔｅｒｌｄ＝ｎｅｘｔｌｄ（Ｃｌｕｓｔｅｒｌｄ）； 有简短的介绍 Ｊ 定义一：直接密度可达 Ｊ 在对象集Ｄ中．关于ｓ和ＭｉｎＰｔｓ，对象Ｐ直接密度可达至 ４．聚类实验及结果分析 本文从网上采集了３０００篇文档，作为初始文本集。文档表 对象ｑ必须满足以下条件： １）Ｐ Ｅ ｒ 是对象集合Ｄ包含在ｇ的一邻域内 现为：文档内容复杂，按照不同的网页主题，共采集了１Ｏ类文 档：文档大小差别悬殊。去噪后的文档字节数从８３Ｂｙｔｅ到３８ＫＢ 的子集 ２） ｌ，ｄ口 向ＪＪ ｎ ｒ Ｃａｒｄ（Ｎ）表示集合Ｎ内的对象数量Ｊ 不等。按照本文中所述的步骤进行实验。结果表明，如果各文档主 条件２１称为”核心对象条件”。如果一个对象Ｐ满足该条 实验效果很好。聚类结果和文 件．则称Ｐ为一个”核心对象”。其它对象只有相对于核心对象才 题之间区别明显且文档分布稠密．档的类别基本相符。且不受噪声干扰。但是如果各文档的主题接 能称为直接密度可达。 近或文档内容主题不鲜明．则有可能出现将几个聚类簇合并的 定义二：密度可达 文档的特征表示 在对象集Ｄ中．关于８和ＭｉｎＰｔｓ．对象Ｐ密度可达至对象 现象。本文分析认为。在整个文本聚类过程中， ｑ必须满足以下条件：存－＋Ｘ￣象链ｐｌ…．，ｐｎ，ｐｌ＝ｑ，ｐｎ＝ 对聚类结果的影响是举足轻重的。此外．本文还用了Ｋ—ＭＥＡＮＳ算ＴＯ Ｐ，其中ｐｉＥＤ且ｐ ＋Ｊ关于Ｅ和ＭｉｎＰｔｓ，直接密度可达至ｐｉ。 密度可达是直接密度可达的传递 密度可达的两个对象关 法进行了比对运算实验，实验结果如一： 系通常上是不对称的。也就是说，ｐ密度可达ｑ并不意味着ｑ密 图２所示。由此可见在大数据量的情善＊ 度可达Ｐ．只有核心对象之间才可以相互密度可达。 况下．ＤＢＳＣＡＮ算法时间复杂度低的 优势可以得到很好的体现。这说明 １０ 定义三：密度相连 在对象集Ｄ中。关于ｓ和ＭｉｎＰｔｓ，对象Ｐ与对象口密度相 ＤＢＳＣＡＮ算法不失为一个高效、快速 的聚类算法．它在文本聚类中可以得 连必须满足以下条件： 存在一个对象ｏ ＥＤ。Ｐ和ｑ关于ｓ和ＭｉｎＰｔｓ，均密度可达 到很好的应用。至０密度相连的对象是一个对称的关系。 ４．总结 文档羹（■） 图２ 文本聚类尤其是Ｗｅｂ文本聚类．在互联网飞速发展的今天 定义四：聚类和噪声 在对象集Ｄ中．一个关于ｓ和ＭｉｎＰｔｓ的聚类Ｃ是Ｄ的一个 有着广阔的应用前景。基于密度的聚类算法以其快速高效，抗干 扰性强的优点．可以很好地适应海量数据文本挖掘的要求。 非空子集。它满足以下条件： １）极大性：Ｖｐ，ｑ Ｅ 如果Ｐ Ｅ Ｃ且ｇ密度可达ｆｒｏｍ Ｐ关 于ｓ和Ｍｉｎｔ￣，而且口Ｅ Ｃ 参考文献： ２）连通性：Ｖｐ，ｑ ＥＣ：Ｐ密度可达ｔｏ ｑ关于Ｄ中的ｓ和 １．Ａｌｓａｂｄ Ｋ，Ｒａｎｋａ Ｓ，ｓｉＩ１曲Ｖ．Ａｎ Ｅｆ￣ｃｉｅｎｔ Ｋ—ｍｅ，ａｌａｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ＭｉｎＰｔｓ。 【ｃ】．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｒｓｔ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈｉ曲Ｐｅｒｆｏｒｍａｎｃｅ ＤａｔｅＭｉｎｉｎｇ， 不属于任何聚类的对象为噪声。 根据以上定义，使用ＤＢＳＣＡＮ算法发现的一个聚类．实际 相当于数据集中以一个核心对象为起点．密度可达的所有对象 ＩＰＰＳ－９８，Ｏｒｌａｎｄｏ，Ｆｌｏｒｉ出，ＵＳＡ，１９９８ ２．ＥＳＴＥＫ Ｍ。ＨＡＮＳ２ＰＥＴＥＲ．ＫＲ ＩＥＧＥＬ，ＳＡＮＤＥＫ Ｊ，ｅｔ ａ１．Ａ ｄｅｍｌ— ｔｙ２ｂａｓｅｄ ａｌｏｒｇｉｔｈｍ ｆｏｒ ｄｉｓｃｏｖｅｒｉｎｇ ｄｕｓｔｅｒｓ ｉｎ ｌａｒｇｅ ｓｐａｔｉｌ ｄａｔａａｂａｓｅｓｗｉｈ ｔ的集合。而密度可达对象的获取实际上是直接密度可达对象获 ｃｏｖｅｒｙ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ（ＫＤＤ）【Ｃ】．Ｐｏｒｔｌａｎｄ，１９９６．２２６—２３１． 取过程的重复。 ３．Ｈａｎ Ｊ，Ｋａｌｌｌｂｅｒ Ｍ．Ｄａｔａ Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ ａｎｄ Ｔｅｃｈｎｉｑｕｅｓ．ＳｉｍｏｎＦｒａｓｅｒ ＤＢＳＣＡＮ算法的处理步骤如下： Ｕｎｉｖｅｒｓｉｔｙ，２０００ （１）检查数据库中每个对象的一邻域，如果一个对象Ｐ的一 ４．Ｍｉｈａｄ Ａｎｋｅｒｓｔ，Ｍａｒｋｕｓ Ｍ．Ｂｒｅｕｎｉｇ，Ｈａｎｓ—Ｐｅｔｅｒ Ｋｒｉｅｇｅｌ，Ｊ？ｒｇ Ｓａｎｄｅｒ： ｎｏｉｓｅ［Ａ】．Ｐｒｃｅｅｄｉｏｎｇ ｔｈｅ ２ｎｄ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎＫｎｏｗｔｅｄｇｅ 邻域 ｒｐｊ内包含的对象数目大于Ｍｉｎｔ￣，就创建一个包含 ｒｐｊ中所有对象的新聚类ｃ。 （２）检查Ｃ中还未处理过的对象ｑ，如果ｑ的一邻域＾ 向Ｊ ＯＰＴＩＣＳ：Ｏｒｄｅｒｉｎｇ Ｐｏｉｎｔｓ Ｔｏ Ｉｄｅｎｔｉｆｙ ｔｈｅ Ｃｌｕｓｔｅｒｉｎｇ Ｓｔｒｕｃｔｕｒｅ Ｐｒｏｃ． ＡＣＭ ＳＩＧＭＯＤ ９９ Ｉｎｔ．Ｃｏｎ￣ｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ，Ｐｈｉｌａｄｅｌｐｈｉａ Ｐ １９９９． 科学技术文献出版社．２００３ 内包含的对象数目大于Ｍｉｎｔ￣，就把脂向ｊ中未包含于聚类ｃ的 ５．苏新宁等著、数据挖掘理论与技术．北京：—＋—＋・—●—＋・ （上接第１４页） Ｉｍａｇｅ Ｉｎｐａｉｎｄｎｇ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｊｊ 翻 参考文献： １・Ｍ、Ｂｅｒｔｌｍｉａｏ，Ｇ．ＳａｐｉｒｏＶ．Ｃａｓｅｌｌｅｓ，ａｎｄ Ｃ、Ｂａｌｌｅｓｔｅｒ，Ｉｍａｇｅ Ｉｎｐａｉｎｆｉｎｇ，。 ｄｏｎ，Ｉｍ，￣ｉｎｇ ｎｄ Ｉａｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ ｆｖ１ＩＰ ２００１），ＰＰ．２６１—２６６。２００１． ５．丁雯。一美非线性扩散问题夏其在图像修复中的应用。上海交通大学 学报。２００４．３８（１）：１５３－１５６． 刘政凯．宋壁．一种基于Ｔｖ模型的自适应图像修复方法。电路 ２、Ｃｈａｒｔ，Ｔ．，Ｓｈｅｎ，Ｊ．Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌｓ ｆｏｒ Ｌｏｃａｌ Ｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｉｎｐａｉｎｔ－ ６、邵肖伟。ｉｎｇｓ、ＵＣＬＡＣＡＭＴＲ０ｏ一１１。Ｍａ￣ｃｈ ２０００与系统学报。９（２）：１１３－１１７。２００４ ＳＩＧＧＩＬＡＰＨ ２０００，ＰＰ．４１７—４２４． ． 王进．王章野．彭群生。基于径向基函数的图像修复技术。 ３．Ｃｈａｎ，Ｔ．，Ｓｈｅｎ，Ｊ．Ｎｏｎ－Ｔｅｘｔｕｒｅ ｌ￣ｐａｉｎｔｉｎｇ ｂｙ Ｃｕｒｖａｔｕｒｅ－Ｄｒｉｖｅｎ Ｄ／ｆ－ ７．周延方。汤锋．中国图象图形学报，９（１ｏ１：１１９０—１１９６。２００４． ｆｕｓｉｏｍ（ＣＣＤ）．ＵＣＬＡ ＣＡＭ ＴｔＬ ００－３５，Ｓｅｐｔ．２０００． ４．Ｍ．Ｍ、Ｏｌｉｖｅｒｉ￣Ｂ．Ｂｏｗｅｎ，ＩＬ．Ｍｃｋｅｎｎａ，ａｎｄ Ｃｈａｎｇ，Ｆａｓｔ Ｄｉｇｉｔａｌ
