（管理科学与工程专业论文）基于粗糙集的数据及文本挖掘方法研究.pdf

天津大学博士论文摘要 中文摘要 数据挖掘和文本挖掘是当前信息技术中的一个重要研究领域：将软计算方 法之一的粗糙集理论应用于数据及文本挖掘方法研究，具有较大的理论意义和 实用价值。本文研究了基于粗糙集的数据挖掘和文本挖掘方法，主要包括数据 挖掘和文本挖掘中的属性约简问题、聚类问题；文本挖掘中的分类规则抽取问 题；以及粗糙集同模糊集相结合的数据挖掘方法。所做主要工作内容包括： 将粗集和遗传算法相结合成功应用于文本模糊聚类。在聚类过程中，将权 重参数的设定也通过编码由遗传算法确定，从而使得权重参数的设定具有科学 性和可操作性。 给出了近似规则的定义，并对z 2 值的意义进行了讨论。在此基础上提出 了一种将特征选取和粗集方法相结合的文本分类规则抽取方法。该方法大大提 高了文本规则抽取的效率，并使其更趋实用化。 对相关文献中隶属函数的定义进行了改进，并且利用隶属函数的性质提出 了一种从定量决策表转换为定性决策表的转换规则，利用此转换规则可以将原 来的定量决策表转换为一个同样大小的定性决策表，这样大大减少了后面利用 粗集理论进行规则抽取的计算量，而且提取的规则质量也有了很大提高。 将模式聚合理论和潜在语义索弓l 理论相结合，提出了一种文本降维新方 法。它首先用p a 理论对文本特征进行初步降维，在此基础上利用l s i 方法对 文本特征进一步降维，抽取隐藏在文本中的主要语义信息。 提出了一种改进的基于粗集和t a b u 搜索的属性约简算法。改进后的算法 既具有较高的算法效率，又能以较大的概率得到最小属性约简。 提出了基于知识简洁度的粗集聚类方法，它首先计算对象集合在每个属性 下的划分；然后在对初始划分进行合并时，引进了不可分辨度的概念；在形成 最终聚类结果时，引进了知识简洁度作为凝聚的终止条件。 将基于次胜对手惩罚的竞争学习算法应用于文本聚类，这种方法既能自动确 定聚类的数目，又具有较好的算法复杂度。 关键词：粗糙集数据挖掘文本挖掘属性约简聚类分类 天津大学博士论文 摘要 a b s t r a c t r e c e n t l y d a t a m i n i n g a n dt e x t m i n i n g a r ei m p o r t a n tr e s e a r c ha r e a si n i n f o r m a t i o n t e c h n o l o g y a p p l y i n gr o u g hs e tt h e o r y , o n eo fs o f tc o m p u t i n g t e c h n o l o g i e s ，t od a t am i n i n ga n dt e x tm i n i n gh a sag r e a tt h e o r ys i g n i f i c a n c ea n d p r a c t i c ev a l u e m e t h o d so fd a t am i n i n ga n dt e x tm i n i n gh a v eb e e nr e s e a r c h e di nt h i s p a p e r , w h i c hm a i n l yi n c l u d e s ：a t t r i b u t er e d u c t i o nm e t h o d s ，c l u s t e r i n gm e t h o d s ，at e x t c l a s s i f i c a t i o nr u l ee x t r a c t i o nm e t l l o da n dad a t am i n i n gm e t h o dc o m b i n e dr o u g hs e t t h e o r ya n df u z z ys e tt h e o r yf u l l y t h em a i n l yw o r k sa r es h o w na sf o l l o w s ： at e x tf u z z yc l u s t e r i n ga l g o r i t h mw h i c hc o m b i n e sr o u g hs e ta n d g e n e t i c a l g o r i t h mf u l l yi sp r e s e n t e d i nt h ec l u s t e r i n gp r o c e s s ，t h ew e i g h t sp a r a m e t e r sa r ea l s o d e s c r i b e db y g e n e t i ca l g o r i t h m ，w h i c hm a k e sp a r a m e t e r sm o r es c i e n t i f i ca n d o p e r a t i o n a l t h ed e f i n i t i o no fp r o x i m a t er u l ei sp r o p o s e da n dt h em e a n i n go fz 2v a l u ei s d i s c u s s e d 耽e nat e x tc l a s s i f i c a t i o nr u l ee x t r a c t i o nm e t h o dw h i c hc o m b i n e sy v a l u ef e a t u r es e l e c t i o na n dr o u g hs e tt h e o r yf u u yi sp r o p o s e d n 屺m e t h o di m p r o v e s t h ee f f e c t i v e n e s sa n dt h ep r a c t i c a b i l i t yo f e x t r a c t i n gt e x tr u l eg r e a t l y n l cd e f i n i t i o no fm e m b e r s h i pf u n c t i o nm e n t i o n e di nt h er e l a t i v el i t e r a t u r ei s i m p r o v e d ，a n dt h et r a n s f o r m i n gr u l e sf r o mt h eq u a n t i t a t i v ed e c i s i o nt a b l et ot h e q u a l i t a t i v ed e c i s i o nt a b l ea r ep r o p o s e d n l er u l e sc a nc h a n g ea nn d i m e n s i o n a l q u a n t i t a t i v ed e c i s i o nt a b l ei n t oa nn - d i m e n s i o n a lq u a l i t a t i v ed e c i s i o nt a b l ei n s t e a do f a3 n - d i m e n t i o n a lo n e s oi tg r e a t l yd e c r e a s e st h ef o l l o w i n gc o m p u t i n gc o m p l e x i t yo f r u l ee x t r a c t i o nu s i n gr o u g hs e tt h e o r y , a n di n c r e a s e st h eq u a l i t yo fe x t r a c t e dr u l e s an e wt e x td i m e n s i o nr e d u c t i o nm e t h o db yu s i n gt h et h e o r yo fp a t t e r n a g g r e g a t i o na n dl a t e n ts e m a n t i ci n d e x i n gi sp r e s e n t e d 1 1 1 em e t h o df i r s t l yr e d u c e s t e x td i m e n s i o nw i t hp a t t e r na g g r e g m i o nt h e o r yt h a tu s e sc l a s sl a b e l ，t h e nm a k e st h e t e x td i m e n s i o nf u r t h e rl o w e rb vl s im e t h o d a ni m p r o v e da l g o r i t h mo fa t t r i b u t er e d u c t i o nb a s e do nr o u g hs e ta n dn 山u s e a r c hi s d e v e l o p e d t h ee f f e c t i v e n e s s o ft h e a l g o r i t h m i sd e m o n s t r a t e db y e x p e r i m e n t s ar o u g hs e tc l u s t e r i n gm e t h o db a s e do nk n o w l e d g es i m p l i c i t y d e g r e ei s p r e s e n t e d w i t hi n t r o d u c i n gt h ei n d i s c e m i b i l i t yd e g r e ea n dt h ek n o w l e d g es i m p l i c i t y d e g r e e ，t h en e wc l u s t e r i n gm e t h o dm a k e st h ec l u s t e r i n gr e s u l tm o r es c i e n t i f i ca n d r e a s o n a b l e t h er p c lm e t h o di sa p p l i e dt ot e x tc l u s t e r i n g w h i c hc a nd e t e r m i n et h en u m b e r o fc l u s t e r i n ga u t o m a t i c a l l ya n dh a sg o o de f f e c t i v e n e s s k e y w o r d s ：r o u g hs e t , d a t am i n i n g ，t e x tm i n i n g a t t r i b u t er e d u c t i o n ，c l u s t e r i n g ， c a t e g o r i z a t i o n 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨洼盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：易巧移参 签字日期：如r 年j ，月，占日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘茎有关保留、使用学位论文的规定。 特授权鑫注盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 鳓夯 导师签名 签字日期：巧年r 月，曰 签字日期： 仍 目砍秒 貌埘 天津大学博士学位论文 第一章绪论 第一章绪论 本章首先介绍选题的研究背景和意义；然后对数据挖掘和文本挖掘的重要概念、过程、 技术进行阐述；接下来熏点论述了粗糙集的基本概念及其在数据挖掘和文本挖掘中的应用： 最后介绍了本论文的主要工作和未来研究方向。 1 1 选题的研究背景和意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更 高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了 “数据爆炸但知识贫乏”的现象。面对这一挑战，数据挖掘和知识发现技术应运 而生，并显示出强大的生命力。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别 有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。最近，国 际权威机构g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未 来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理 体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。 文本挖掘是数据挖掘的一个分支，是以文本型信息源作为挖掘对象，利用定 量计算和定性分析的办法，从中寻找信息的结构、模型、模式等隐含的具有潜在 价值的新知识的过程。由于文本型数据的快速增长，文本挖掘的重要性也日益增 强。同时由于文本数据具有不同于一般数据的无结构或半结构化、高维数等特点， 原来的数据挖掘算法不一定再适合于文本挖掘。目前，文本挖掘已经成为数据挖 掘的一个重要研究分支。 由于数据集体现出越来越多的无标签性、不确定性、不完整性、非均匀性和 动态性，传统的数据挖掘算法往往对此无能为力，而以神经网络、粗糙集、模糊 逻辑和遗传算法为主要组成部分的软计算，通过协同工作提供一种灵活的处理此 类数据的能力。 粗糙集理论作为一个处理不确定、不精确、不完备信息的数学工具，在人工 天津大学博士学位论文 第一章绪论 智能和认知科学，特别是在智能信息处理方面，诸如知识的表达与推理、数据分 析、机器学习和知识发现等领域得到了广泛的应用。在世界各地也掀起了粗糙集 理论研究和应用的热潮。许多国际性的学术会议、专题讨论和众多的知名学者纷 纷将粗糙集引入自己的研究项目和计划，涌现了大量高质量、高水平的学术论文 和研究成果，使粗糙集理论取得了进一步的发展和丰富。 然而，将粗糙集理论应用于数据挖掘和文本挖掘还有许多值得研究的地方， 如：基于粗糙集的数据挖掘方法仍存在许多不足，需要进一步进行改进；将粗糙 集方法应用于文本挖掘，目前的的国内外研究还处于起步阶段，也是当前的一个 研究重点；将粗糙集同其他软计算方法结合以及粗糙集的应用研究也是当前的研 究方向。 根据以上分析，数据挖掘和文本挖掘是当前的一个重要研究领域；作为软计 算重要组成部分的粗糙集方法具有一些传统方法不具备的优点，正在数据和文本 挖掘领域发挥着越来越大的作用；而目前将粗糙集理论应用于数据挖掘和文本挖 掘还有许多值得研究的地方。基于以上原因，进行基于粗糙集的数据及文本挖掘 方法研究具有较大的理论意义和实用价值。 1 2 数据挖掘与文本挖掘概述 1 2 1 数据挖掘概述 1 2 1 1 数据挖掘的的定义 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术，是知识发现过程中的关 键和核心步骤，其起源于商业、科学、工程领域中对隐藏在数据集背后知识的发 现和利用的需求上。数据挖掘是一门交叉型学科，涉及机器学习、模式识别、统 计学、数据库、知识获取、知识表达、专家系统、神经网络、模糊数学、遗传算 法等多个领域，内涵和研究热点非常广泛：所谓数据挖掘就是从大量的、不完全 的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、以前未知 的、具有潜在的或者现实应用价值的信息和知识的过程。 与数据挖掘相近的同义词有数据分析、知识发现和决策支持等。这个定义包 含以下几层含义：数据源是真实的、大量的、含噪声的；发现的是用户感兴趣的 知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知 识，仅支持特定的发现问题。 天津大学博士学位论文 第一章绪论 1 2 1 2 数据挖掘的基本任务 数据挖掘的基本任务或者功能如下：( 1 ) 分类，根据已知训练数据的特征和 分类结果，为每一类找到一个合理的描述或模型，然后再根据这些分类的描述或 模型对新的数据进行分类；( 2 ) 聚类，根据对象属性实现未知空间分布的样本集 的划分，同一组中数据的相似性最大，组间的差异性最大；( 3 ) 关联规则挖掘， 发现数据变量之间或者数据集或者其一部分之间的特征值之间的重要相关性；f 4 ) 预测与趋势性规则挖掘，发现数据集中普遍演变行为的规则，包括各类回归方法、 时间序列挖掘等；( 5 ) 特征与辨识规则挖掘，发现数据集的所有数据满足的一般 性特征和用于不同数据集区分的辨识特征；( 6 ) 偏差检测，应用所得到的模式发 现异常或者最重要的变化。 1 2 1 3 数据挖掘中主要技术 1 、统计方法：典型的技术包括贝叶斯推理、对数回归【1 1 、a n o v a 分析田、对数 线形模型； 2 、聚类分析：传统的聚类技术包括分裂算法、凝聚算法、划分聚类和增量聚类 等非神经网络方法； 3 、决策树和决策规则：典型的技术包括c l s 方法、1 d 3 算法、c 4 5 算法及其对 应的剪枝算法： 4 、关联规则方法：包括购物篮分析、演绎算法和w w w 路径遍历模式； 5 、人工神经网络：反向传播学习的b p 神经网络和k o h o n e n 的自组织映射神经 网络、多层感知机等神经网络； 6 、遗传算法：基于生物进化原理设计了一系列的基因组合、交叉、变异、自然 选择等过程，进行问题优化； 7 、模糊方法：基于模糊集合、模糊逻辑、模糊决策等 8 、粗糙集方法：作为研究不确定性的数学工具，属于集合论的扩展，主要用于 研究不完全和不完整信息描述，可以用于聚分类、特征规约和最小属性子集 规约； 9 、可视化方法：采用直观的图形方式将数据模式、关联、趋势呈现出来，可以 通过可视化的交互技术分析数据间的关系，其包括几何学、基于图形、象素 导向和分层等技术 1 2 1 4 数据挖掘的应用 目前，数据挖掘技术在各个领域引起了广泛的关注，特别是在科学研究、市 场行销、金融投资、欺诈甄别、产品制造、通信网络管理、1 n t e r n e t 应用方 天津大学博士学位论文 第一章绪论 面已经开发了比较成熟的系统。例如：s k i c a t ( s k y i m a g e c a t a l o g i ga n d a n a l y s j s f 0 0 1 ) ，用它已经发现了1 6 个新的极其遥远的类星体；f i d e l i t ys t o c ks e l e c t o r ，它 使用神经网络来选择投资；l b sc a p i t a lm a n a g e m e n t 使用了专家系统、神经网络 和基因算法来辅助管理多达6 亿美元的有价证券；c a s s l o p e e ，已用于诊断和 预测在制造波音飞机过程中可能出现的问题。在国内，宝钢在生产中也采用了数 据挖掘技术，创造了近亿元的经济效益。 1 2 1 5 数据挖掘的研究重点和方向 当前，数据挖掘研究方兴未艾，其研究与开发的总体水平相当于数据库技术 在7 0 年代所处的地位。预计在本世纪，数据挖掘的研究还会形成更大的高潮， 研究焦点可能会集中在以下几个方面： l 、研究新的数据挖掘算法及原有数据挖掘算法的改进研究； 2 、对各种复杂数据的挖掘，如对文本数据、图形图像数据、空间数据和多 媒体数据的挖掘； 3 、基于面向对象数据库的数据挖掘技术： 4 、研究在网络环境下的数据挖掘技术，特别是在因特网上建立数据挖掘服 务器，并且与数据库服务器配合，实现w e b m i n g ： 5 、寻求数据挖掘过程中的可视化方法，使数据挖掘的过程能够被用户理解， 也便于在数据挖掘的过程中进行人机交互； 6 、挖掘语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也 许会像s q l 语言一样走向形式化和标准化； 7 、数据挖掘在实践中的应用技术及挖掘软件的研制。 1 2 ，2 文本挖掘概述 文本挖掘是数据挖掘的一个分支，是以文本型信息源作为挖掘对象，利用定 量计算和定性分析的办法，从中寻找信息的结构、模型、模式等隐含的具有潜在 价值的新知识的过程。最近研究表明，公司信息有8 0 包含在文本中，由于存储 信息使用最多的是文本，文本挖掘的重要性也日益增强。 文本挖掘处理的对象是半结构化和非结构化的数据，而且自然语言文本中往 往包含多层次的歧异( 词汇、语法、语义、语用等) ，必然涉及自然语言处理的问 题，但文本挖掘和自然语言处理侧重点并不相同，文本挖掘目的是从文本集中寻 找潜在有价值的知识，并不试图改进自然语言理解和处理，并不要求对自然语言 的理解达到过高的水平，而只是期待可以利用自然语言处理的研究成果。 的理解达到过高的水平，而只是期待可以利用自然语言处理的研究成果。 天津大学博士学位论文 第一章绪论 1 2 2 1 文本数据的特点： ( 1 ) 无标签：一般需要进行处理后才可以进行分类、检索等相关操作。 ( 2 ) 分布式：来源多样性和类型多样性，决定文本收集的复杂性，因而文本 在进行处理前一般都需要进行预处理，比如；对于h t m l 类型的文本文件一般预 处理的必须步骤为去除h t m l 的语法标签。 ( 3 ) 半结构化或者无结构化：比如半结构化的h t m l 文本和无结构化的f r e e t e x t ，具有很强的非线性的特征，很难用传统模型来描述，也就不能采用传统的 方法进行处理。 ( 4 ) 时变：要求文本处理方法具有一定的柔性，可以处理随时间变化的文本 即随时间变化可以更新原有文本和接纳新的文本，具备学习能力( 尤其是无监 督) ；要求具备长期记忆能力、短期记忆能力，详细模式记忆和粗略模式记忆等 多种记忆功能。 ( 5 ) 高维：文本最重要的特点，文本向量的维数一般都可以高达上万维，一 般的数据挖掘、数据检索的方法由于计算量过大或代价高昂而不具有可行性( 比 如多元统计分析中的主因素分析) ，因而有必要对现有方法加以改变以适应高计 算量、高资源消耗的文本处理特点；同时也可以研究文本表示的新方法或者有效 的维数约简方法。 ( 6 ) 语义性：文本检索本身是语义检索，由于一词多义、多词一义，在时间 和空间上的上下文相关等情况，文本检索本身就具有内在相关、非确定性、非精 确性等特点，传统的严格关键词布尔检索方法难于适应具有上述特点的文本检 索，因而有必要在检索词表示、文本表示、匹配算法等各方面进行语义性扩充或 者研究。 ( 7 ) 高数据量：般文本检索的文本库中都会存在最少数千个文本样本，对 这些文本进行预处理、编码、训练神经网络等的工作量是非常庞大的，因而手工 方法一般是不可行性，文本处理必须是自动化或者半自动化，比如自动分词系统 和下文所述的主要相关技术。 1 2 2 2 文本挖掘的主要任务包括： ( 1 ) 文本分类：文本分类是指按照预先定义的主题类别，为文本集合中的每 个文本确定一个类别。这样用户不但能够方便地浏览文本，而且可以通过限制搜 索范围来使文本的查找更容易、快捷。 ( 2 ) 文本聚类：聚类与分类的不同之处在于，聚类没有预先定义好的主题类 别，它的目标是将本文集合分成若干个簇，要求同一簇内文本内容的相似度尽可 能的大，而不同簇之间的相似度尽可能的小。 天津大学博士学位论文 第一章绪论 ( 3 ) 文本结构分析和自动摘要：进行文本结构分析是为了更好地理解文本的 主题思想，了解文本所表达的内容及采用的方式，包括识别文本的各个层次及分 析各个层次间的联系。以结构分析为基础，找出文本主题句，经整理组合构成文 本文摘； ( 4 ) 文本预处理。文本中包含的内容非常复杂，为了降低文本挖掘等的计算 量和复杂度，为排除噪声，为了转变为适合神经网络等模型处理的输入模式，一 般必须对文本进行预处理。常见的预处理步骤为：分词和预过滤，以避免非常短 或者非常长的关键词以及不是单词的关键词；高、低通过滤器，过滤那些很不常 用和诸如辅助动词那些出现频率很高的常用词；词频统计，以词频为自变量的函 数是目前流行的各类以统计方法为数学基础的文本处理方法的基本处理对象。 1 2 2 3 文本的预处理 ( 1 ) 文本特征表示 文本信息具有有限的结构或者没有结构，文本的内容是人类所使用的自然语 言，计算机很难处理其语义。文本的这些特殊性使得现有的数据挖掘技术无法直 接应用于其上，所以要对文本进行特征表示，将这些特征用结构化的形式保存， 以便于处理。 文本特征指的是关于文本的元数据，分为描述性特征，例如文本的名称、日 期、大小、类型等，以及语义性特征，例如文本的作者、机构、标题、内容等。 对于内容这个难以表示的特征，首先要找到一种能够被计算机所处理的表示方 法。 从文本所蕴含的信息的角度看，一个中文文本可以由字、词、短语等语义特 征项及其之间的顺序来完整表达。如果要表示文本中特征项之间的顺序信息，就 必须使用有向的指针结构，整个文本就变成了一个复杂的图结构，比如树或者网。 然而信息检索和文本分类聚类要求定义一种距离函数，以表示文本之间的相似程 度。如果使用复杂的图结构表示文本，则很难定义一种合理的距离函数。因为有 这样的问题：怎样的两棵树才能说很近似? 又是什么样的两个网才能说是距离比 较小? 向量空间模型仅仅使用文本中特征项的频率信息，它使用一个向量表示文 本。若是用向量空间模型，数学中有很多种定义距离的方式可资使用，如欧式距 离、相关系数等，从而能够很方便地计算和操作。但它的缺点是，仅仅采用频率 信息不能精确反映人们所理解的语义。尽管如此，现在使用比较普遍的仍然是向 量空间模型。 在向量空间模型f v s m ) 中，文本空间被看作是由一组正交词条向量所张成的 天津大学博士学位论文 第一章绪论 空间，每一个词条称为一个特征项，每一个文本d 则表示为空间内的一个向量或 者空间点，一般表示为： y p ) = ( w “w ( t ：) ，砸，k ，w ( f 。) ) 其中t ；为张成文本空间的词条，n 为文本空间的维数，当一个文本被表示成 为文本空间的一个向量时，数据挖掘中基于向量的挖掘算法就可以被用于文本挖 掘工作；特征表示中的w ( 。) 是函数，其基本功能是计算词条t i 在文本向量中的 权重，函数的自变量是词条在文本中的出现频率和在整个文本集中出现的频率， 可以认为函数w ( ) 由2 部分组成： w ( 。) = l ( i j ) + c ( i ) 第一部分为局部权值l ( i 0 ) 表示第i 个词在第j 篇文本中的重要权值，第二部 分为全局权值c ( i ) 表示第i 个词在整个文本集中的重要权值，设蛾和西表示词 i 在第i 篇文本中出现的频度和在整个文本集中出现的频度，曲为文本集中包含 词i 的文本数目，n d o e s 为文本集文本总数，则常见的局部权值公式l ( i j ) 有： 词频法：t f i j 布尔函数法：器象三： 平方根法：万 对数词频法：l o g 妩+ 1 ) 常见的全局权值公式c ( i ) 有： n o n n a l 法： 磷引( 警 + ， 天津大学博士学位论文 第一章绪论 e n t r o p y 法：。一莩禁 文献【3 】表明局部权值公式采用对数词频法而全局权值公式采用e n t r o p y 法 时效果较好。 ( 2 ) 文本特征的提取或者标引、文本词性标注 文本特征提取或者标引是很复杂的过程，自然语言理解在文本挖掘中的最主 要运用就体现在这个步骤，这里涉及很多具体步骤，包括通过停用词表的预过滤， 高、低通过滤器，过滤那些很不常用和诸如辅助动词那些出现频率很高的常用词， 根据在文本结构中不同位置给予不同权重以及同义词分析，一词多义分析，词性 变化分析等等。而中文文本处理还存在特殊的分词问题，由于中文特殊的书写形 式、灵活多变的构词方式以及对句子采取不同的分词形式可能产生完全不同的语 义，因而汉语的自动切分相当困难，虽然目前存在词典分词法、切分标记分词法、 单汉字标引法、智能分词法等多种分词方法，但分词效果仍然存在很大提高潜力； 分词问题将来的研究依赖于自然语言理解研究的进展，另外也有在基于非分词方 式进行文本挖掘的研究。 文本词性标注主要是将文本中兼类词的词性根据上下文确定下来。兼类词的 词性包括同型异性异义、同型同性同义、异型同性同义等多种情况；文本挖掘主 要依赖于文本中的名词、动词等词性，而很少依赖于形容词、副词、冠词等词性； 因而确定兼类词词性是及其重要的。目前主要的自动词性标注方法有基于概率统 计的标注办法和基于规则的标注办法，更好的自动词性标注方法也依赖于自然语 言理解的进展。 文本特征的提取或者标引和文本词性的标准对于文本挖掘是非常重要的，数 据挖掘的方法能否移植到文本挖掘领域，在很大程度上取决于文本特征提取或者 标引和文本词性标注的效果。 1 2 2 4 特征集缩减，即文本空间降维算法研究： 使用词集表示法来表示文本时，表示文本的特征向量会达到数十万维的大 小。有人曾对y a h o o 上的4 9 6 0 0 个文本提取作为特征的词串，最后得到3 2 0 0 0 0 个特征词串。如此高维的特征对将进行的机器学习未必全是重要的、有益的，而 且高维的特征可能回大大增加机器的学习时间而仅产生与小得多的特征子集相 关的学习结果，因此对文本进行机器学习时特征子集的选取便显得异常重要。 特征选取包括特征抽取和特征选择。“特征抽取”指的是：从高维的测量空 间通过映射( 或变换) 的方法降低维数得到特征空间的过程。“特征选择”指的 天津大学博士学位论文第一章绪论 是：从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的的过 程。从定义中可以看出实际上“特征选择”是“特征抽取”的特例。 ( 1 ) 基于评估函数的方法 基于评估函数的特征集缩减算法 4 1 一般使用特征独立性假设以简化特征选 择。算法的般步骤是：用某种评估函数独立地对每个特征计算，然后把特征按 计算结果进行排序，选择事先确定数目或者超过阈值的若干计算值较高的特征。 当选择不同的评估函数时也就形成了各种名目的特征集缩减算法；常见的评 估函数有：信息增益、期望交叉熵、互信息、文本频数、文本证据权、优势率、 词频等。其公式分别定义如下：设f 是对应于单词w 的特征，p ( w ) 是单词w 出 现的概率，p ( c i ) 为第i 类出现的概率，p ( c ，i 形) 为单词w 出现时属于第i 类的 概率，t f ( w ) 为单词w 在文本集中出现的次数，p o s 表示正例集的情况，n e g 表 示负例集的情况： 文本频数：t f ( w ) 妒浑州帮卜醛| _ ) l 。 期 期望交叉熵：p 妒浑嘲峨( 雩掣 互腻y p ( c 瑚。g ( 帮 文本证飘尸缈浑p ( c j 帧( e ( c , l x l r v x 一1 粥- p ( c 刚, ) ) l 优势率： 。器捌 特征的z 2 统计：单词w 在类别c j 中的z 2 值计算如下： 9 天津大学博士学位论文 第一章绪论 ：旦型旦! 苎笪一 ( 1 1 ) 。 ( q + 他) ( 坞+ n 4 ) x ( m + 坞) ( 也+ t 1 4 ) 、。 其中玛、h ：、n ，和n 。分别表示单词w 和类别c 。的4 种共现情况的频数，这4 种 共现情况分别为：( 矽，c ，) ；( i , v ，e - , ) ；( 旷，c 。) 和( p c ，c j ) ；且 = + 2 + 传+ 聆4 为总数。 在这7 种评估函数中，文献 5 指出互信息和c h i 方法比期望交叉熵和文本 证据权方法效果好，因为前者对不同的类别抽取不同的特征项，而后者只考虑了 各个特征在每个类别中的分布情况。 ( 2 ) 潜在语义索引【6 1 0 ( l a t e n ts e m a n t i ci n d e x ：l s i ) 对文本词条矩阵。利用奇异值分解1 1 1 计算矽的广秩近似矩阵 醒( r m i n ( n x m ) ) ，经奇异值分解，矩阵形可表示为三个矩阵的乘积： w = u , 4 矿7 u 和v 分别为与矩阵对应的左、右奇异向量矩阵，爿为由矩阵的奇异 值按递减顺序排列构成的对角矩阵，取u 和矿最前面的列构建r 秩近似矩阵阢： w ，= u ，a y ： 豳：扣留鼎 x mn x r 孵 ； 珥d ， 图卜1 ：l s l 分解图示 u ，和的列向量为正交向量，即有： u 7 u = 矿1 矿= j r 用以来近似表示文本词条矩阵缈，u ，和一行向量分别作为文本向量和词向 量。在此基础上来进行文本聚类或其它处理。 尽管l s i 也是用文本中包含的词来表示文本的语义，但却并不把文本中所有 的词看作是文本概念的可靠表示，正相反，文本中用词的多样性很大程度上掩盖 了文本的语义结构，l s i 通过奇异值分解和取，_ 秩近似矩阵，一方面，消减了原 文本一词条矩阵中包含的“噪声”因素，更加凸现出文本和词条之间的语义关系； 天津大学博士学位论文第一章绪论 另一方面，使得文本一词条向量空间大大缩减，可以提高文本挖掘算法的效率。 在经过合理的上述文本预处理步骤和特征集缩减后，文本聚类和分类的算法 和数据挖掘中相应算法基本相同，文本相似性判断标准也和数据相似性判断标准 基本相同；目前独特的只适用于文本的聚类和分类算法和相似性判断标准还没有 出现比较多的进展。 1 2 2 5 文本挖掘目前尚存在的问题 ( 1 ) 数据挖掘方法在大规模高维文本中应用的局限性。由于当数据分类和聚 类操作中，距离计算是其最重要和核心的操作，对于文本，在通常的向量空间文 本表示法中，维数很容易达到成千上万维，而聚类中心( 映射个数) 一般也不会 是几个，通常也达到数十上百。过高的时间复杂度会限制一些数据挖掘算法的应 用，如基于神经网络的分类和聚类算法等。另外一方面，过高的文本空间维数会 导致挖掘所需要的空间异常增大，空间代价非常高昂，而且目前的挖掘算法很多 属于非增量算法，要求一次性将数据读入内存进行处理，过高的空间复杂度也会 限制一些挖掘算法的实际应用。 文本空间的高维还会带来大样本问题。上述基于评估函数的特征集缩减算 法，般要求计算出现概率或者条件概率，但文本空间的分布概率或者分布条件 概率一般是不知道( 这些概率分布往往正是文本挖掘的目的) ，因而空间的这些概 率值往往是以样本的对应样本值来近似计算的。只有样本集足够大能够充分表现 文本空间时，这些对应的样本值的应用才是有意义的，但大样本集带来的问题就 是降维算法本身的计算代价过于高昂，何况计算样本统计值的时候文本空间还处 于未降维的状态。另外，在实际的文本分类和聚类中，有时我们不能得到足够多 的样本，使得最终的分类和聚类结果会出现一定的偏差。 过高的维数往往也带有大量冗余并含有带躁声的特征，这往往会降低聚类分 类的精度。 另外高维数据还会带来一些其他一些问题。例如在聚类过程中，当维数过高 时，无论怎样定义样本间的相似性都难以发现类的形成趋势，样本到其最近邻点 与到其他点的差距不明显，这样所有基于最近邻的算法都不再适用。 ( 2 ) 文本分类规则抽取问题。 常用的文本分类方法主要有基于向量比较的文本分类技术和基于规则抽取 的文本分类技术【1 2 l 。基于向量比较的文本分类技术主要包括k 近邻算法、支持 向量机算法等，这类方法追求的是较高的文本分类正确率，但不能抽取出使人易 于理解的文本分类规则。基于规则抽取的文本分类技术是一个可长期得到应用的 文本分类技术，如u s e n e t 客户软件所使用的文章过滤器k i l 卜f i l e 和v a nd e n 天津大学博士学位论文 第一章绪论 b e r g 的自动电予邮件过滤器p r o c m a i l ，均采用了这种技术。 有的研究者对对文本分类规则抽取方法进行了研究，但是要么有的算法计 算复杂度太高且得到的规则不易理解，要么有的算法得到的规则虽然易于理解， 但挖掘出的质量不高。研究既具有较好的算法复杂度又能得到较高质量规则的文 本分类规则抽取方法是当前的一个研究方向。 ( 3 ) 文本模糊聚类问题。典型的文本聚类算法：k 一均值算法、球形k 一均值 算法等都认为文本可以被唯一地归到一个类。但由于汉语文本的多样性和大量 性，一个文本相对于一个类的成员关系有可能不能精确定义，一个文本有可能是 一个以上类的候选成员。为了克服以上算法的缺点，文献【1 3 】提出了模糊c 一原型 ( f c m d d ) 算法；文献【1 4 】对此算法进行改进，提出了基于非欧几里德关系的竞 争凝聚算法；但这两种算法的缺点是都需要预先给定隶属度。文献 1 5 3 和文献 1 6 将粗集和遗传算法相结合，分别对高速公路和网站访问者进行了聚类，其缺点是 人工设定适应度函数中的权重参数，使得算法的执行缺乏科学性和可操作性。所 以研究科学的文本模糊聚类算法，具有一定的理论意义和实际意义。 1 3 数据挖掘文本挖掘的主要技术 数据挖掘和文本挖掘涉及到众多的学科领域和技术，这些技术和方法可以粗 分为机器学习方法、统计方法、软计算方法。机器学习方法包含归纳学习、基于 案例学习、支持向量机等。统计学习方法包含回归分析、判别分析、贝叶斯分类 等。软计算方法包含神经网络、粗糙集、遗传算法和模糊逻辑等。下面对数据挖 掘中的分类技术和聚类技术进行简要介绍： 1 3 1 分类技术 数据挖掘中的分类技术就是针对数据集构造分类器，形成类别判别面，从 而对未知类别样本赋予类别标签的一项技术。基于机器学习的分类技术主要包括 支持向量机( s v m ) 0 7 j 8 、k 近邻( k n n ) 1 9 , 2 9 、决策树【2 l l 、基于关联规则的分类 算法；基于统计的分类算法主要包括贝叶斯分类算法、判别分析算法、回归算法 等。基于软计算4 5 a 6 1 的分类算法主要包括神经网络分类算法、粗糙集分类算法等。 1 3 1 1 基于机器学习的分类技术 ( 1 ) 基于关联规则( c b a ：c a s s i f i c a t i o nb a s e do na s s o c i a t i o nr u l e ) 的分 类算法。 该算法【2 2 】分两个步骤构造分类器。第一步：发现所有形如x 。 x 。：jc 。的关 天津大学博士学位论文 第一章绪论 联规则，即右部为类别属性值的类别关联规则，( c l a s s i f i c a t i o na s s o c i a t i o n r u l e sc a r ) 。第二步：从已发现的c a r 中选择高优先度的规则来覆盖训练集，也 就是说，如果有多条关联规则的左部相同，而右部为不同的类，则选择具有最高 置信度的规则作为可能规则。 c b a 算法主要是通过发现训练集中的关联规则来构造分类器。关联规则的发 现采用经典算法a p r i o r i l 2 3 , 2 4 ，其通过迭代检索出数据集中所有频繁项集，该算 法对于发现隐藏于大量交易记录之中的关联规则来说是比较有效的。此算法的优 点是其分类准确度较高，因为它发现的规则相对较全面。算法的主要缺点是当潜 在频繁2 项集规模较大时，算法就会效率低下、时间代价过于高昂。针对a p r i o r i 算法过高的时间代价，提出了若干改进算法。l i g ( l a r g ei t e m sg e n e r a t i o n ) 算 法o ”在求解频繁l 项集的同时计算相应项的相关区间，以此得到项集规模大大缩 小的潜在频繁2 项集。f p ( 频繁模式增长) 算法【2 5 讲1 则放弃利用潜在频繁项集求解 频繁项集的做法，而是提出称为频率增长的算法，该算法通过扫描数据集得到频 繁项的集合以及各项的支持度，并按支持度大小降序排列构成频繁项目的列表， 然后通过构造一个f p - 树来进行关联规则挖掘。 ( 2 ) k 近邻( k n n ) 分类算法【2 8 2 9 k n n 方法基是一种非参数的分类技术，对于未知和非正态分布可以取得较高 的分类准确率，具有鲁棒性、概念清晰、易于实现等诸多优点。其基本原理为： k n n 分类算法搜索样本空间，计算未知类别向量与样本集中每个向量的相似程度 值，在样本集中找出k 个最相似的文本向量，分类结果为k 个相似样本中相似样 本最多的一类。但在大样本集分类中，尤其是文本分类中，k n n 方法的缺陷也突 出地暴露出来，主要有：首先k n n 算法是懒散的分类算法，对于分类所需的计算 都推迟到分类时才进行，因此对于高维文本向量或样本集规模较大的情况其时间 和空间复杂度较高；其次k n n 方法是建立在v s m 模型上的，它认定各维对于分类 的贡献是相同的，显然这是不符合实际情况的，进而影响分类精度。 ( 3 ) 决策树分类算法 决策树学习是以实例为基础的归纳学习算法。它采用自顶向下的递归方式， 在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分 支，在决策树的叶节点得到结论。 q u i n l a n 提出的i d 3 3 2 学习算法通过选择窗口来形成决策树，它利用信息 论中的互信息( 信息增益) 寻找数据库中具有最大信息量的属性字段来建立决策 树的一个节点，再根据该属性字段的不同取值建立树的分支：在每个分支子集中 重复建立树的下层节点和分支过程。这种方法的优点是描述简单，分类速度快， 产生的分类规则易于理解。存在的主要问题有：互信息的计算依赖于属性取值的 天津大学博士学位论文 第一章绪论 数目较多的特征，而属性取值较多的属性不一定最优；是非递增学习算法；抗噪 性差，训练例子中正例和反例较难控制。其后推出改进的c 4 5 分类算法，但仍 然存在需要反