相对杂讯过滤法

《相对杂讯过滤法》由会员分享，可在线阅读，更多相关《相对杂讯过滤法（6页珍藏版）》请在金锄头文库上搜索。

1、相对杂讯过滤法-以混合式技术改善文件聚类精确度 古佑嘉，真理大学信息管理系 王海霞，真理大学信息管理系 王台平，真理大学信息管理系 摘要本研究讨论的是利用混合式方式改善文件聚类的精确度。目的是以电脑自动化的方式 取代传统以人工分类方式以完成文件聚类，并运用 AHC 结合 K-means 的方式达到控制文 件聚类时的品质，以提高其精确度(Precision)及召回率(Recall)。 文件聚类之前，需针对文 件做前处理的动作。首先我们使用 CKIP 的中文分词系统将文件进行中文分词的处理，接 著计算 TF，每个关键词在各篇文章中出现的次数及 IDF，最后用杂讯过滤的方法，将权重 值中会影响文件聚

2、类精确度与召回率的关键词权重值加以过滤。实验信息在 95%的信赖度 之下，有效样本为 512 篇新闻信息。实验结果显示出，本研究所提出 AHC 结合 K-means 聚类演算法并加入杂讯过滤法相较於 AHC 结合 K-means 聚类演算法，获得较理想的聚类 结果。 关键字：文本挖掘，文件聚类，凝聚式阶层聚类法，杂讯过滤 1绪论 研究动机 数据挖掘(Data Mining)是信息科学中的一项新兴且重要的技术，美国麻省理工学院 (Massachusetts Institute of Technology， MIT)的 Technology Review 期刊更将之列入为改变 未来世界的十大创新科

3、技之一(曾新穆，李建亿，2003)。而文本挖掘(Text Mining)就是由数 据挖掘中延伸出来，其中最广泛被运用的是文件分类(Text Classification)。 分类，指的是事先以人工方式定义各个类别建立好模型。然而，聚类则不需事先建立 模型，而以当时文件中最相近的视为一群。以往在文件自动分类的研究，大多采用分类 (Classification)的方式做文件自动分类(谢儒诚，2002)。由於类别是事先定义好的，每当有 新的文件产生而要加入时，如果其未在事先定义的类别中则会导致不知道该分至何类别。 所以，使用文件聚类(Clustering)的方式就不会产生上述的问题。 在文件聚类上，

4、最为广泛被使用的两种聚类演算法： Agglomerative Hierarchical Clustering(AHC)、K-means。AHC 的品质控制比较好，能将信息以阶层式的树状图表达出 来，缺点是在处理较大量的信息时较不易判读及分析，而且其执行效率差。K-means 是最 简单又易实作的方法，能处理较大量的信息，执行的效率较高。缺点是从其信息中随机选 取初始中心点的 K 值该是多少却没有一定，且对於杂讯及离群值有著高敏感度。 本论文的研究动机主要来自以下几点说明： 第一，在讨论聚类演算法的论文中，多数都曾提及 Single Linkage 容易造成各群集之 间大者恒大，小者恒小的情形出

5、现，因此聚类的结果往往不如预期。但洪鹏翔学者的 研究中，却显示 Single Linkage 相较於 Complete Linkage 有更好的精确度表现。洪鹏翔学者 说明这是因为新闻类别中的新闻群聚并非是平均分布的，其中只有部分新闻需要形成新闻 群聚，与 Single Linkage 所产生的群聚分布类似(洪鹏翔，2000)。 第二，国内学者李谚泯将非阶层式聚类 K-means 及阶层式聚类 AHC 做一个结合，将 修改过后的 Modify K-means 演算法先对信息进行处理，之后采用阶层式聚类处理信息，进 而得到阶层式树状图。Hierarchical 可以将所有信息的差异求出，先用 P

6、artitioning 的方式对 信息进行分割处理，而 Hierarchical 就只需对群集进行处理即可，在信息量大时，可以达到 节省时间的目的(李谚泯，2003)。 研究目的 在此次的研究中，为了改善聚类在文件上的精确度，我们使用以 AHC(Agglomerative Hierarchical Clustering)阶层式聚类演算法求取出合适的 K 值，提供给 K-means 非阶层式聚 类演算法进行新闻文件聚类的动作。先进行阶层式聚类演算法可以针对聚类时的群数进行 控制，虽然实际上较花时间，但对於品质有较良好的表现。而取出合适的 K 值，可以让 K- means 非阶层式聚类演算法在处理

7、文件上能够达到加速收敛的目的，所以我们提出 AHC(Agglomerative Hierarchical Clustering)阶层式聚类演算法结合 K-means 非阶层式聚类演 算法进行文件聚类。聚类处理之前，我们将针对各个文件中去计算其关键字的平均值，以 平均值倍数的区间为门槛值，对超过或是未达此门槛值的关键字权重进行过滤，删除会影 响文件聚类的关键词，以提升类各类别的精确度。 文献探讨 特徵词汇 在做文件聚类之前，除了需要将文件做分词的处理接著就是选取文件中的关键词，并 找出能代表本篇文章的关键字，再和文件群比较看看哪些文章是相似的且需要被归为一类。 若特徵词取的好，可代表本文章的内容

8、；若特徵词选取的不好，将无法表现出此篇文章的 大意。因此，特徵词的选取会影响到是否能代表这偏文章的内容。事实上，在文章中有些 词出现的次数很多但却不是该篇内容的主要重点，如：我们，我的，他们等。这些词虽 然经常出现在文章里，但却不是最主要的内容。这一类的词需要我们去避免，才不会降低 文章的精确度及召回率。 与特徵词汇相关的国外文献，有利用 SVM 的分类器来做 Reuters 及在 20NG 文件上的 试验(Bekkerman，R. and El-Yaniv，R. and Winter，Y. and Tishby，N.，2001)。在 SVM 的 分类器上，拿出 Reuters 中的一个类别，

9、并针对该类别取出部份的特徵词汇加以分析 (Joachims，1998)。国内的部份，陈俊达将其研究结果与上述两位国外学者做比较，发现即 使中文词句的结构与英文是截然不同的，但不管是在其中文或是英文的特徵词选取上，皆 对分类器有著相同的影响(陈俊达，2004)。 文件聚类 文件聚类(Document Clustering)是指将文字文件自动地分成几个群集。因此，文件同属 在一个群集内的相似度会较高，而群与群之间的相似度就比较低。以往在文件自动分类的 研究，大多采用分类(Classification)的方式做文件自动分类(谢儒诚，2002)。而分类，指的 是事先以人工的方式定义各个类别建立好模型。

10、然而，聚类(Clustering)，则不需事先建立 模型，而以当时文件中最相近的视为一群。由於分类之类别是事先定义好的，每当有新的 文件产生而要加入时，如果其未在事先定义的类别中则会导致不知道该分至何类别。所以， 使用文件聚类的方式较不会产生上述的问题。 在文件聚类的研究上，杨绿渊学者以文件关键属性之撷取进行文件间相关性分析并以 此结果进行自动化文件聚类。再透过使用者阅读趋势之搜集与分析结合文件聚类结果，自 动推论文件接受对象，达成文件(或讯息)自动发布之目的，最后建立以文件相关性为基础 之企业知识聚类企业知识聚类与管理模式与系统技术，并以一案例验证此模式与技术的可行性(杨绿渊， 2004)。

11、谢儒诚学者以论文作者给定的关键字做为文件之属性，以 Jaccard 系数测量文件间 的相似度，采用 Complete-link 演算法来做聚类，由实验结果显示此法可将论文做适当的聚 类，区分不同科系或不同研究领域之论文(谢儒诚，2002)。江季洲学者提出了两种以最近 邻居为基础的聚类法，分别是最近邻居命中聚类法及共同最近邻居聚类法 。经由实 验结果来评估聚类效能及优缺点，发现实验结果最佳的共同最近邻居聚类法实作出聚类为 基础的使用者文件查询系统(江季洲，2002)。洪鹏翔学者利用计算字串相似度的方式求得 新闻标题之间的相似度，再以阶层式聚合演算法来完成聚类的动作。在训练过程中系 统调整聚类所需

12、的参数，藉此提高电脑自动聚类的准确度。尝试直接以统计的方法来求得 聚类所需的参数，并加以比较这两种方式所得到的聚类结果(洪鹏翔，2000)。郭家良学者的研究中，在新闻群聚上将一群描述相同或类似事件的新闻做群聚，并利用多文件摘要提 供读者初步了解新闻事件内容，可有效节省使用者阅读的时间(郭家良，2003)。 目前有两种主要的聚类技术型态为非阶层式聚类 Non-Hierarchical Clustering(分割式， Partitioning)及阶层式聚类 Hierarchical Clustering (树的聚类，Tree Clustering)(Jain and Dubes，1988)。而 A

13、gglomerative Hierarchical Clustering (AHC)，K-means 是两种最常被用 於文件聚类的聚类方法。 阶层式的聚类分为凝聚式(Agglomerative)与分裂式(Divisive)。本论文采用的是凝聚式 聚类。凝聚式聚类是从一颗树的最底层将两个相似的群集做合并，一直到树的最顶端。凝 聚式阶层式聚类(AHC，Agglomerative Hierarchical Clustering)有四种计算距离的方式，分别 为： a. 单一连结法(Single Linkage)：在两个群集间距离最近的两点。 b. 群平均连结法(Group Average Linkag

14、e)：两群集中各点与各点之间的 距离总和之平 均。 c. 完整连结法(Complete Linkage)：在两个群集间距离最远的两点。 d. 沃德法(Wards)：两群集中各维度的变异数之平均和。 在以上的四种距离当中，最常被使用的是单一链结法。单一链结法被认为是较易发生 链结效应与将负相关物件分在同一群。而完整链结法则较符合一般人信息聚类的目的。但 在洪鹏翔的研究中，指出单一链结法虽易造成各群聚间大者恒大，小者恒小的现象， 但在新闻聚类的使用上获得较好的结果。而完整链结法，虽使所有文章能较平均地分布於 各群聚中，但却与真实情况不相容(洪鹏翔，2000)。使用 AHC 的优点是在聚类的品质上较

15、 好，可利用阶层式的树状图表达，缺点则是执行效率差且不适合处理大量的信息。 在非阶层式的聚类里，K-means 演算法是非阶层式演算法的代表(Joachims，1998)。其 优点简单，易实做，在大量信息的处理上有较佳的效率表现。缺点在於其 K 值是随机的， 对於离群值的敏感度高结果易受其影响。因此，李谚泯学者使用阶层式聚类的凝聚式聚类 的观念在 K-means 方法中 update center 的步骤来修改 K-means 演算法，在中心点更新的方 式上，利用同一群中相互间差异性最小的物件当成新的中心点，使之较不易受离群值的影 响。再用阶层式方法求算丛集间的差异来省去信息量大时需将所有物件

16、的差异得知后才去 做处理，只需要知道要分割的丛集差异即可(李谚泯，2003)。 而 AHC 与 K-means 两者的最大差别在於 AHC 的品质要较 K-means 来的好。但在时间 的复杂度上来看，却是 K-means 优於 AHC。过去也有一些研究认为 AHC 的品质要比 K- means 来的好，如：在(Steinbach and Karypis and Kumar，2000)的研究中提到有一知名的研 究指出 AHC 优於 K-means，但却是用在非文件的信息上。不过在文件的领域里，此篇 Douglass 等学者使用混合式的近似法同时包含了 K-means 跟 AHC，其选用 K-means 的原 因是因为效率较好，选用 AHC 则是因为它的品质较好(Cutting and Karger and Pedersen and Tukey，1992)。 研究方法与架构 本论文主要将 2005 年 6 月至 7 月的联合新闻网内之新闻加以收录为母体样本，并依照 统计学原理随机抽样取得适当的样本数，再分别经过中文分词，计算词频，计算 IDF 等步 骤之