（计算机应用技术专业论文）基于概念格与粗糙集的web文本聚类研究.pdf

扬州大学硕十学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含其他个人或 集体已经发表的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 学位论文作者签名： 乍、 臼表乃 签字日期： d g 年0 6 月o s 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交学位论文的复印件和电子文档，允许论文 被查阅和借阅。本人授权扬州大学可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编 学位论文。同时授权中国科学技术信息研究所将本学位论文收录到 文本信息预处理 预处理主要包括w e b 文本文档的分词处理。在中文文档的词频统计前， 需对中文文档进行分词处理。即在词条间加入分隔符，使之转换为分散的 田素方：基于概念格与粗糙集的、e b 文本聚类研究 词流形式。分词的基本算法有：( 1 ) 基于词典与规则匹配法【3 6 1 。基于词典与 规则的方法应用词典匹配，汉语词法或其它汉语语言知识进行分词，这类 方法简单、分词效率较高，但对词典的完备性、规则的一致性等要求比较 高。匹配策略有：最大匹配法、最小匹配法、逆向匹配法、增字或减字匹 配法、双向扫描法。( 2 ) 标志法【37 1 。如切分标志法、统计标引法。( 3 ) 词频 统计法【3 引。基于统计的分词方法将汉语基于字和闻的统计信息。完备性较 差。( 4 ) 语义语用法【39 1 。如后缀分词法。目前使用最多的是基于词库的分词 方法。 文本特征表示 文本特征值的提取是对从w e b 文档中抽取出来的代表其主题内容的元 数据( 特征项) 形成特征矢量来表示w e b 文本。在文档挖掘时用这些特征项 来评价未知文档与用户目标的相关度。从而实现对非结构化文档的处理。 特征值的提取现在已有多种方法，如：文档频次门限方法、信息增益方法 ，( i g ) 、x 2 统计方法( c h i ) 、互信息熵方法和基于奇异值分解的潜在语义索引 方法等。w e b 文档表示的模型有多种，其中矢量空间模型( v s m ) 是应用较多 且效果较好的特征表示方法之一，即将w e b 文本文档看成是一组词条 m ，r z ，厶) 构成，对于每一词条t i ，都根据其在文档中重要程度赋予一定的权 值w i ，可以将其看成是一个n 维坐标系，m ，w z ，协为对应的坐标值。因此每 一篇文档都可以映射为由一组词条矢量构成的向量空间。 文本聚类 根据文本聚类的结果不同。可以将聚类方法【4 0 ，4 1 1 分为两种类型：以 g h a c 等算法为代表的层次凝聚法4 2 ，4 3 1 ，又分为聚合聚类和分裂聚类：以 k m e a n s 等算法为代表的平面划分法【4 4 ，4 5 1 。层次聚类方法是最为常用的的聚 类方法，准确度较高，但在每两个簇合并时，需要全局地比较所有簇之间 9 一 1 0 扬州大学硕士学位论文 的相似度，确定适当的相似度阀值，选出最佳的两个簇。 1 3 论文创新 本文针对概念格、粗糙集和文本聚类的结合的多个方面进行了研究， 结合概念格和粗糙集的相关知识来解决文本聚类问题，弥补了现有方法的 不足。并用实验验证了本文方法的有效性。本文的主要目标是对w e b 搜索 结果进行聚类能帮助用户导航浏览、快速查找所需要的信息。本文的主要 的创新点如下： ( 1 ) 提出了基于概念格的w 曲文本聚类方法。首先把w e b 文档集表示 成形式背景，即文档中的特征词为形式背景中的属性，文档作为形式背景 中的对象，并定义了两个概念之间的相似度函数，通过概念中文档和概念 的相互关系，选取合适的概念来表示文档并度量两个文本间的相似度，从 而实现了基于概念格的w e b 文本概念聚类。由于概念中包含多个属性，并 且概念和文档存在关联。因而，用概念来表示文档和经典的空间向量模型 相比，使特征词的维数降低，可以减少计算的复杂度和提高计算的精确度。 ( 2 ) 提出了一种基于粗糙集模型的文本聚类方法，采用粗糙集模型来 表示w 曲文本，把在一定范围内的特征词权重转化为特定的属性值，从而 把文档数据库转化为文档决策表。利用粗糙集的上近似集来衡量属性之间 的最大粗糙度，根据划分的思想对文本进行聚类。 ( 3 ) 在国内外关于形式概念分析的已有研究中，绝大多数是针对标准形 式背景( 或称单值形式背景) 的，刘宗田等把模糊思想和形式概念分析相结 合，提出了一种模糊概念格模型【4 6 ，4 7 1 来处理一些模糊和不确定的信息。本 文通过概念格和粗糙集的相似研究，把粗糙思想和形式概念分析相结合， 田素方：基于概念格与租糙集的w e b 文本聚类研究 旦 提出了一种可变精度的粗糙概念格模型来处理一些粗糙和不精确的信息， 定义了粗糙概念中对象集和属性集的近似映射，引入了分别体现了概念外 延之间和概念内涵之间的粗糙程度的参数l 和2 。根据用户输入的不同的 参数值夕1 和罗2 ，可以得到不同粗糙程度的粗糙概念格。当输入的参数值 i = o ，2 = o 时，可变精度粗糙概念格就蜕化为标准的概念格。因而，可变 精度的粗糙概念格作为一种扩展模型具有更强的通用性，能处理现实中一 些粗糙和不精确的信息，并且能用粗糙概念格对文本进行粗糙的聚类。 1 4 论文的内容组织 本文共分为六章： 第一章主要介绍论文的研究背景、选题依据、研究意义以及论文选题 的创新点和主要研究内容。 第二章关于概念格、粗糙集和文本聚类的基本知识。主要介绍了概念 格的模型及其常见的构造算法、粗糙集合理论以及文本聚类的基本概念， 并论述了概念格和粗糙集的联系和区别。 第三章基于概念格的w e b 文本概念聚类方法。主要介绍了一种概念格 表示文本的模型，定义了文本之间的相似度计算公式，并针对空间向量模 型维数过高的特点，利用概念来表示文本中的特征词，利用可辨识矩阵对 属性进行约简，从而减少计算的复杂度、提高计算的精确度。 第四章基于粗糙集的w e b 文本聚类方法。提出了一种基于粗糙集模 型的文本聚类方法，采用粗糙集模型来表示w e b 文本，把在一定范围内的 特征词权重转化为特定的属性值，从而把文档数据库转化为文档决策表。 利用粗糙集的上近似集来衡量属性之间的最大粗糙度，根据划分的思想对 1 2 _ 一 扬州大学硕士学位论文 文本进行聚类。 第五章一种可变精度的粗糙概念格模型及其在w e b 文本聚类中的应 用。把形式概念分析与粗糙思想相结合，提出了一种粗糙概念格模型来处 理一些粗糙和不精确的信息，定义了粗糙概念中对象集和属性集的近似映 射，引入了分别体现了概念外延之间和概念内涵之间的粗糙程度的参数l 和2 。根据用户输入的不同的参数值l 和2 ，可以得到不同粗糙程度的粗 糙概念格。因而，可变精度的粗糙概念格作为一种扩展模型具有更强的通 用性，能处理现实中一些粗糙和不精确的信息，并且能对文本进行粗糙的 聚类。 第六章结束语。对全文进行了总结，并展望了进一步的研究工作。 田素方：基于概念格与粗糙集的w e b 文本聚类研究 2 概念格、粗糙集与文本聚类 2 1 概念格模型 2 1 1 概念格模型的数学基础 在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。 基于概念的这一哲学理解，德国的w i l l e 教授提出了形式概念分析，用于 概念的发现、排序和显示。在形式概念分析中，概念的外延被理解为属于 这个概念的所有对象的集合，而内涵则被认为是所有这些对象所共有的特 征( 或属性) 集，这实现了对概念的哲学理解的形式化。而概念格作为形式 概念分析中核心的数据结构，本质上描述了对象和特征之间的联系，表明 了概念之间的泛化与例化关系，其相应的h a s s e 图则实现了对数据的可视 化。作为序论和格论与实际应用结合的产物，概念格模型的研究具有重要 的理论意义。 序论中的定义基本定义： 定义2 1 设a 是一个集合，如果a 上的一个关系r ，对于溉，) ，z 彳， 满足如下条件： 触( 自反性) 脚，廊j x = + y ( 反对称性) x 缈，皿j 地( 传递性) 则称r 是a 上的一个偏序关系，记为” i 。序偶 彳，称为偏序集。 定义2 2 设 彳，为偏序集，对于b 彳，如有口彳，且对b 的任 扬州大学硕士学位论文 意元素x ，都满足x 口，则称a 为子集b 的上界。同理，且对b 的任意元 素x ，都满足口x ，则称a 为子集b 的下界。 定义2 3 设 彳，为偏序集，b 彳，a 为b 的任一上界，若对b 的 所有上界y 均有口y ，则称a 为b 的最小上界( 上确界s u p r e m u m ) 记为 s u p ( b ) 。同样，若b 为b 的任一下界，若对b 的所有下界z 均有z 6 ，则 称b 为b 的最大下界( 下确界i n f i m u m ) ，记为i n f ( b ) o 格论中的基本定义： 定义2 4 设 彳，是一个偏序集，如果a 中任意两个元素都有最小 上界和最大下界，则称 彳，为格。 定义2 5 设 彳，是一个格，如果在a 上定义两个二元运算v 和 ， 使得对于任意的口，6 彳，口v 6 等于a 和b 的最小上界，口 6 等于a 和b 的 最大下界，那么，就称 为由格 ) 。类似地分别 用v 召和 召来代替s u p ( b ) 和眦日) 。 定义2 6 设 彳，是一个偏序集如果对于任意非空的集合s 彳，都 存在有v s ，则 彳，被称为是一个完全并半格，类似地，如果对于任意 非空的集合ss 彳都存在有 s ，则 彳，被称为是一个完全交半格。如 果 彳，既是完全并半格，也是完全交半格，则它是一个完全格。 2 1 2 概念格模型的基本概念 定义2 7 给定数据信息表足= ( g ，m ，d ，如表2 1 所示，在形式概念分 析中被称为形式背景( f o r m a lc o n t e x t ) 。其中g 是对象集合，m 是属性集 合，i 两者之间的二元关系。为了表示一个对象g ( g 回和一个属性聊m ) 田素方：基于概念格与粗糙集的w e b 文本聚类研究 望 在关系i 中，可以写成g i i i l 或( g ，所) ，表示对象g 具有属性m 。 定义2 8 形式背景的对象集4 只g ) ，属性集b p ( 之间连接关系如 下：厂( 彳) = 棚miv g 彳，gi m ) ；g ( 口) = g glv 册b ，gi m 则称从形式背景中得到的每一个满足彳= g ( 曰) 且b = 厂( 么) 的二元组( 彳，b ) 为 一个形式概念( f o r m a lc o n c e p t ) ，简称概念( c o n c e p t ) 。 定义2 9a 是对象幂集p ( g ) 的元素，称之为概念似，b ) 的外延；b 是属 性幂集尸( m ) 的元素，称之为概念似，艿) 的内涵。 定义2 1 0 给定两个概念c 。= ( 彳，骂) 和c 2 = ( 4 ，垦) ，若两者满足 4 4 ，则称( 4 ，局) 为子概念( 或亚概念) ，( 彳：，垦) 为父概念( 或超概念) ， 记为( 彳，蜀) ( 4 ，岛) ；若不存在概念c 3 = ( 坞，马) ， 满足 ( 彳。，蜀) c l 的节点c 3 ，有 砌纪聊( c 3 ) r 、厂 。) 觑纪，s e c 肋甩；则c l 被称为是一个产生子格节点。 一个更新格节点c 显然不是一个产生子格节点，因为 砌册s e c 砌刀= qn 厂( x ) = q 。如果l 中的一个概念节点既不是更新格节点也 不是产生子格节点，则它被称为是一个不变节点。 对于r 中的任意一个节点c ，如果不存在l 中的某个节点c 。满足 觑纪耐( c 1 ) = 砌纪班( c ) ，则c 被称为一个新生节点；否则它被称为一个继承节 点。如果c l 是一个产生子格节点，节点( 凰纪耐( c 1 ) u 缸。 ，砌纪埘( c 1 ) n 厂 ) ) 显 田素方：基于概念格与粗糙集的w e b 文本聚类研究 旦 然是f 中的一个新生节点，它被称为是由c 。产生的新生的节点。 渐进式生成算法的一般步骤： ( 1 ) 初始化格l 为一个空格； ( 2 ) 从g 中取一个对象g ； ( 3 ) 对于格l 中的每个概念c - = ( 彳t ，召，) ，如果b - 厂( g ) ，则把g 并到a l 中； ( 4 ) 如果同时满足：西n ( g ) ；丑n ( g ) 晟和不存在( a l ，b 1 ) 的某个父 节点( a 2 ，b 2 ) 满足b 22b - n 厂( g ) ，则要产生一个新节点； ( 5 ) 对新产生的节点加入到l 中，同时调整节点之间的链接关系； ( 6 ) 反复( 2 ) ( 5 ) ，直至形式背景中的对象处理结束； ( 7 ) 输出概念格l 。 概念格的渐进式生成算法在产生所有概念节点的同时，还产生了概念 之间的亚概念一超概念连接关系，同时它非常适合于处理动态数据库，被 认为是一种生命力很强的概念格生成算法。 2 2 粗糙集合理论 粗糙集理论是一种刻画不确定性和不完整性知识的数学工具。粗糙集 理论提供了一整套方法从数学上严格地处理数据分类问题。根据粗糙集理 论的方法，知识推理就是给定知识表达系统的条件属性和结论( 决策) 属性， 求出所有符合该知识的最小决策算法。粗糙集理论仅仅分析隐藏在数据中 的事实，并没有带入人为的模糊性，是采用精确的数学方法分析不精确系 统的一种理想方法。 2 2 1 基本概念 定义2 1 3 ( 信息系统) 信息系统用一个列表的形式给出研究对象的信 息，表的行对应于研究对象，表的列对应于对象的属性。信息系统可表示 为一个四元组s = ( u ，彳，y ，门，其中u 是对象的非空有限集合，称为论域； 扬州大学硕士学位论文 a 是属性的非空有限集合，彳= c u d ，c ud = 囝，v a 是属性a 的值域； 厂：u 么专y 是一个信息函数，即厂( x ，口) 玩，v 口么，x u 。 信息系统也称为知识表达系统，为了简化符号，通常也用s = ( u ，彳) 来 代替s = ( u ，彳，矿，d 。 表2 2 给出了一个关于某些病人的信息系统，其中 u = x z ，彳2 ，x s ，x 4 ，x s ，z 6 ) ，a = 头痛，肌肉痛，体温 。 表2 2 一个关于某些病人的信息系统 定义2 1 4 ( 决策表) 决策表是一类特殊而重要的信息系统，多数决策 题都可以用决策表形式来表达。设s = ，彳，y ，力为一个信息系统， p 彳，c 称为条件属性，d 称为决策属性。具有条件属性和决策属性的 信息系统称为决策表。 一个决策表中决策属性有时是唯一的，称为单一决策；有时是不唯一 的，称为多决策。对于具有多个决策属性的决策表我们可以变换成为单一 决策表，这样有利于问题的简化和求解。 定义2 1 5 ( 不可区分关系) 令尸4 ，定义属性集p 的不可区分关系 加d ( p ) 为加d ( 尸) = ( x ，y ) u x u i v 口尸，厂( x ，口) = ( y ，口) ) 如( x ，y ) f 玎d ( 尸) ，贝0 称 x 和y 是p 不可区分的。卯彳，不可区分关系俐( d 是u 上的等价关系， 符号u 翮( p ) u i n d ( p ) ( 简记为u p ) 表示不可区分关系砌d ( 尸) 在u 上导出 田素方：基于概念格与粗糙集的w e b 文本聚类研究 型 的划分，加d ( 尸) 中的等价类称为p 基本集。符号 x 】p 表示包含x u 的p 等 价类。 例如，在表2 2 中由属性集p = 头痛，肌肉痛) 划分的所有等价类为： u p = x l ，x 2 ，x 3 ， x 4 ，x 6 ， x 5 。 2 2 2 近似空间 一个近似空间可以看成是一个信息系统s = ( u ，彳，几力，设x u ，如 果集合x 能用一个不可区分关系r 下的等价类的并集表示，那么称集合x 是可定义的，否则称集合x 是不可定义的，需要通过逼近来刻画集合x 。 定义2 1 6 ( 下近似) 给定信息系统s = ，彳，y ，门，对于每个子集x u 和一个等价关系灭么，x 相对于r 的下近似定义为： r ( x ) = 】f ul 【x 】月互x 尺( x ) 实际就是那些根据已有知识判断肯定属于x 的对象所组成的最 大集合，也称为在关系r 下x 的正区域( p o s i t i v er e g i o n ) ，记作朋r ( j ) 。 事实上r ( x ) 为x 中的最大可定义集。 定义2 1 7 ( 上近似) 给定信息系统s = ，彳，y ，门，对于每个子集x 互u 和一个等价关系rs 彳，x 相对于r 的上近似定义为： r ( x ) = 工ui 【x 】r x ) 足( x ) 实际上就是那些根据已有知识判断可能属于x 的对象所组成的最 小集合。事实上r ( x ) 为含有x 的最小可定义集。由上近似的定义知 2 2 扬州大学硕士学位论文 n e g r = u r ( x ) 就是那些根据已有知识判断肯定不属于x 的集合，称为在关 系r 下x 的负区域( n e g a t i v er e g i o n ) 。 定义2 1 8 ( 边界域) 设x u ，定义集合x 相对于r 的边界域为： 6 凇( x ) = r ( x ) 一足( 功 边界域就是在关系r 下，即可能属于x 也可能不属于x 的对象的集 合，也是集合x 的不确定体现。如果6 凇( x ) ，说明不存在不确定性， 在关系r 下，x 可以被精确定义：6 ，2 r ( x ) ，说明存在不确定性，在关 系r 下，x 不可以被精确定义，这时x 为关于r 的粗糙集或者非精确集。 在粗糙集理论中，集合的不精确性是由于边界区域的存在而引起，集 合的边界区域越大，其精确性则越低。为了更精确的表达这一点，引入精 度的概念。 定义2 1 9 ( 近似精度) 由等价关系r 定义的集合x 的近似精度为： r ( x ) i 伽( x ) = 二- i r ( x ) l 其中工，i x i 表示集合x 的基数。 精度用来反映人们根据现有知识对集合x 的了解程度。显然，对于每 一个r 和x u 有0 m ( x ) 1 。当触( x ) = 1 时，集合x 的r 边界域为空集， 集合x 为r 可定义的；当m ( x ) 空间分割一 数据分割。 这样不直接对数据进行处理的优点是网格数据的增加使得基于网格的聚 类技术不受数据次序的影响，因此，处理速度非常快，其处理时间独立于 数据对象的数目，只与量化空间中每一维的单元数目有关。s t i n g 是基于 网格聚类算法的典型例子。c l i q u e 和w a v e c l u s t e r 这两种算法既是基于 网格的，又是基于密度的聚类算法。 2 5 本章小结 本章简要介绍了概念格和粗糙集的基本定义、相关数学定理以及多种 概念格生成算法，文本聚类的基本知识。粗糙集理论的主要特点是利用对 象的不可辨识关系推导近似算子，形式概念分析则是构造形式概念和概念 格。粗糙集理论的发展是以对象的等价关系为基础的，通过对象集和属性 集构成的二元关系来提取规则，而二元关系恰恰是形式概念分析中的基本 概念，这就提供了研究粗糙集和概念格的公共基础。把概念格和粗糙集结 3 2 扬州大学硕七学位论文 合起来来处理文本聚类问题能取得更好的效果。又介绍了文本聚类的几种 常见的文本特征词选择方法、文本聚类的常见算法及其性能的比较。 田素方：基于概念格与粗糙集的w e b 文本聚类研究 3 基于概念格的w e b 文本聚类 w e b 文本聚类大多是基于空间向量文本表示模型的，它没有考虑特征 词之间的语义关系，并且特征词的维数非常高，造成文本语义信息的损失 和时间复杂度的增加。本文把文本作为对象，文本中的特征词作为对应的 属性，形成了基于文本的形式背景，从中提取概念来表示文本并度量文本 之间的相似度，从而降低了特征词的维数，减少了计算的复杂度，取得了 良好的聚类结果。 近年来，随着w e b 信息资源急剧增长，信息在网络上传播速度迅速提 升，如今因特网已经成为当今世界上最大的信息库，并且成为全球范围内 传播信息的最主要的渠道之一。由于w e b 网页数量巨大，搜索引擎执行一个 检索提问要搜索5 0 亿多个网页，返回结果成千上万。并且多数结果并不是 用户所需要的。因此自动有效组织w 曲文本搜索结果是一个巨大的挑战，而 对文本搜索结果进行聚类能帮助用户导航浏览，快速准确的查找所需要的 信息。 对于w e b 文本聚类研究比较早的有z a m i a 等人提出的聚类器【6 5 1 是第 一个基于w 曲搜索结果的聚类系统，它采用后缀树聚类算法，w 曲搜索结 果被表示成树结点。把具有相同词和词组的w e b 搜索结果汇成族，用出现 最频繁的特征词作为类标记。典型的概念聚类方法有l i n g o 【6 6 ，6 7 1 ，它首先 从w 曲文本搜索结果确定概念文档，并抽取特征词作为类标记，把与类标 记相似的文档聚合成类。德国卡尔斯鲁厄大学的h o t h o 和s t a a b 提出了基 于本体论( o n t o l o g y ) 的文本聚类【6 8 ，6 9 1 ，将w o r d n e t 作为背景知识来构造文 本特征空间，开创了将本体论应用于文本聚类的先河。这几种基于概念的 扬州大学硕上学位论文 文本聚类算法在实验中都取得了良好的结果。但也存在一些问题：很多聚 类方法大多是用空间向量模型来表示w e b 文本，文本特征词的维数过高， 从而使计算复杂度增加。而用概念格中的概念来表示文本能很好的解决这 个问题。 本文提出了一种基于概念格的w e b 文本概念聚类方法，首先把w e b 文档 集表示成形式背景，即文档中的特征词为形式背景中的属性，文档作为形 式背景中的对象，并定义了两个概念之间的相似度函数，通过概念中文档 和概念的相互关系，选取合适的概念来表示文档并度量两个文本间的相似 度，从而实现了基于概念格的w 曲文本概念聚类。由于概念中包含多个属性， 并且概念和文档存在关联。因而，用概念来表示文档和经典的空间向量模 型相比，使特征词的维数降低，可以减少计算的复杂度和提高计算的精确 度。 3 1w e b 文本预处理和特征词的选择 对网页进行预处理操作，包括去掉网页标签( t a g ) 、停用词过滤、词缀 剪枝( s t e m m i n g ) 、索引项的选取以及归类组织等。其中停用词过滤只需要用 s t o p w o r d s 算法的停用词列表( s t o p l i s t ) 就可以完成，而词缀剪枝可以采用 m a r t i np o t t e r 博士的p o r t e r 词干分析算法，此算法是对英文中因时态、语态、 复数等原因引起的词尾变化进行移除的处理过程，可将每个单词的各种形 式还原为词干原型，例如以下几个单词：b r e a t h e ，b r e a t h e s ，b r e a t h i n g ， b r e a t h e d ，经过p o n e r 词干还原器的处理都会被还原为b r e a t h 。 1 ) 根据词频( t e r mf r e q u e n c y ) 提取特征，如l i r a 和d i c a l i r a 所采用的方法是去除文档中的停止词( s t o pw o r d ，频繁出现但无 田素方：基于概念格与租糙集的w e b 文本聚类研究 翌 实际意义的词，如英文中的“t h e ”) ，采用p o r t e rs u m x s t r i p p r i n g 算法将所 有同根词归为一个词根，统计所有词的词根，最后选出2 7 ，0 0 0 个词构成 一个字典集d = 酗i 汪1 ，2 2 7 0 0 0 ) ，d i 为字典集的词根；同时统计包含词根 d i 的文档数目d f ( i ) 。文档d o c 中的每个词根d i 的权重v i ： 2 ( 吣+ o 5 裂 ( - 唱南)l 歼基人。卿q ) 其中，t f ( i ) 是指词根d i 在文档中出现的次数，n 是文档总数，t f m a x 是指t f ( i ) 中的最大值，即豫m a ) 【= m 戤 豫( f ) ，i = 1 ，2 ，2 7 0 0 0 。出于对计算量 的考虑，l i r a 选取1 0 个权值最高的词根作为特征，f = l ，2 ，1 0 。这样每 个文档都可以成特征矢量空间f = 厂1 2 1 0 的一个矢量 矿= ，y ：，_ 。) ，v i 为对应词根d i 在该文档中的权重。如果文档不包含d i ， 则v i - 0 。 2 ) 根据词频倒置文档频率( t e r mf r e q u e n c y i n v e r s e d o c u m e n t f r e q u e n c y ) 提取特征，如t f 幸i d f o t f i d f 是建立在这样的假设基础上的：如果特征项t i 在文档中的作用 较大，必然有较高的项频和相对较低的文档频率。假设文档集 d = 鲫，jdj = j ，i dj 表示集合在d 中元素的个数，特征项集丁= 研，j 丁i = 朋。 定义特征项t j 在文档d i 中的权重w i j 为： w i j = 桷| 勘。 其中帕为特征项t j 在文档中出现的频率，称为项频；d 巧是文档集d 中出现特征项t i 的文档的数量，称为文档频率。 3 ) 根据互信息量( m u t u a li n f o r m a t i o n ) 提取特征。 扬州大学硕士学位论文 如w w w 在文档特征提取中，可以通过计算词的互信息量确定该词能 否作为文档的特征。w w w 考虑文档中出现的词和类值，定义词的互信息 量为 胁加蛳”。聊。g 剖 其中p ( c i ) 是第i 类文档出现的概率，p ( w ) 是词w 出现的先验概率， p ( w c i ) 是词w 在c i 类文档中出现的后验概率。互信息高意味着区分文档 类别的能力强。由于w w w 将文档只分为两类，即用户感兴趣类与用户不 感兴趣类，所以词的互信息量高就意味着该词区分用户感兴趣类和不感兴 趣类的能力强。毫无疑问，选取互信息量高的词作为特征词可以比较准确 的反映文档的含义。 4 ) 贮统计( c h i ) 它是统计学中常用的分类方法，认为特征t 非独立关系，类似于具有 一维自由度的) c 2 分布，特征t 与c 类文档之间的) c 2 统计值贮( t ，c ) 的计算 如下： ，、n i a d c b 1 2 ( t c ) 2 面刁币盖丽石萄而) 其中，a 为特征t 与文档类c 同时出现的次数，b 为出现而c 类文档 不出现的次数，c 为c 类文档出现而特征t 不出现的次数，d 为特征t 与文 档类c 均不出现的次数，n 为文档总数。 在上述的文本聚类中存在的问题是文本的表示模型，既如何选择合适 的模型来表示文本，来提高文本聚类的质量。如：基于空间向量的文本表 示模型，构成文档集的特征词很多，表示成向量的文本的维数很高，计算 量较大，而用概念格来表示文本能很好的解决这个问题，用概念来表示文 档，能够降低文本的维数，提高聚类的效率。 田素方：基于概念格与粗糙集的w e b 文本聚类研究 翌 3 2w e b 文本聚类的概念格表示模型 对于文本的聚类需要解决以下几个问题：文本的表示模型，特征词的 抽取，聚类算法的实现以及聚类结果的评价。传统的文本表示模型分为： 布尔模型、概率模型和空间向量模型三种： ( 1 ) 布尔模型：布尔模型通过文本标识与用户给出的检索式进行逻辑 比较来检索文档。用户表达式是把用户给出的检索词用布尔运算符a n d o r 连接起来的式子。设文档集d = - ，d z ，赢) ，西( 扛1 ，2 ，疗) 为文档集中的某一 文档；又设乃= p - ，f ：，埘为西的标引词集。则对于形如q = t 形z 职， 如果形- 丁，形z 丁z ，孵乃。则西为检索到的文档，西也称为命中文档， 否则西为不命中文档。而对于形如q = 形- v z v 矾的检索式，如果至少存 在某个胍a ，( 后= 1 ，2 ，) 则d i 为命中文档，若不存在胍a ( 后= 1 ，2 ，) ， 则历为不命中文档。布尔模型其优点是检索简单，速度快，缺点是逻辑式 的构造方式不宜反映用户的需求。 ( 2 ) 概率模型：概率模型是基于提问词在相关和非相关文档中的概率 分布。其主要思想是根据关键词在相关文档和非相关文档出项的概率来判 断关键词的权重，其计算公式为： 觋= 三昭2 p r 一，) ( ( 刀一，) ( 一力一r + ，) ) 】 其中，w i j 为标引词i 在提问j 的权重，r 是提问j 所得到的相关文献 中包含标引词的文献数量，r 是与提问j 相关的文献总数，n 是用于检索 的所有文献中包含索引词i 的文献数量，n 是文献总集中包含的文献数量 概率模型的优点是：采用严格的数学理论为依据，为人们提供了一种数学 理论基础来进行计算；采用相关反馈原理，可开发出理论上更为坚实的方 法。缺点是：增加存储和计算资源的开销。 扬州大学硕上学位论文 ( 3 ) 空间向量模型：其思想是把文档表示成高维空间的一个向量，向 量的分量为文档中出现的特征词的权值，文档集中的特征词按一定的顺序 排列便构成了文档空间的维。同时，把用户输入的查询也经过同样的处理 形成向量，这样就可以用向量夹角余弦或其它的公式来表示文档和用户查 询之间的相似度。其权值的大小可以由公式i f 宰i d f 来计算。即： 够矽 ，动) = 矿 ，历) 三d gl 乃i i 乃) i 矿( 办，西) = 1 + 三d g ( ( 矗，西) ) 中乃文档总数，n ( 疗) 表示在乃中出现的文档数， ( 矗，盔) 表示特征词方在文档西中出现的次数。 空间向量模型是基于特征词出现的频数，优点为标引词引进权值，通 过标引词权值的大小来反映标引词与被标引文档的相似度，克服了传统布 尔检索的缺陷，满足用户多样化或检索多样化的需要。其缺点是文档由词 构成的，词与词之间的关系要比向量复杂的多，存在一词多义，一义多词， 同义词，多义词等情况，容易造成对文档处理的差错，相似度的计算量大， 标引词的权值难确定，并且没有充分考虑文档特征词之间可能存在的语义 关系，两个文档之间虽存在语义关系，但由于出现的次数不同，而被归于 不同的类。更糟糕的是用空间向量模型表示文档会导致文本特征词的维数 过高，从而使计算的复杂度增加。 但利用概念来表示文档能很好的解决这个问题。因为概念中包含多个 属性，与空间向量模型相比维数有所降低，从而降低了计算的复杂度。我 们设定w e b 文档为概念格中的对象集，文档中的关键词或术语( t e r m ) 构成属 性集。从而得到基于文档的形式背景的定义： 定义3 1 ：一个基于文档的形式背景是一个三元组k = ( d ，丁，) ，其中d 是文档( 对象) 集，t 是关键词( 属性) 集，i 是一个二元关系，它表明文档d 中 是否有关键词t 。如果t 是d 的关键词，则记为栅或( d ，r ) ，。 田素方：基于概念格与粗糙集的、忱b 文本聚类研究 形式背景可以用一个二维表来表示，二维表的行表示文档，列表示关 键词。如表3 1 表示一个形式背景，文档集d = ( d ，d 2 ，d ，d ，小 ，关键词集 z = 口，6 ，c ，d ，表3 1 中的”1 ”表示文档中有该关键词，”0 ”表示文档中没有该 关键词。 定义3 2 ：在形式背景k = ( d ，丁，) 中，若对象集彳p ( 功，属性集 b p ( 丁) 之间按如下关系连接： 厂( 彳) = p 丁iv d 4 ，删)g ( b ) = d dv f b ，脚 则称从形式背景中得到的每一个满足么= g ( b ) ，召= 厂( 彳) 的二元组( a ，b ) 为一个形式概念。其中a 是对象密集p ( d ) 的元素，称为概念( a ，b ) 的外延， b 是属性密集p ( t ) 的元素，称为概念( a ，b ) 的内涵。 表3 1 形式背景示例 abcd d l 1111 d 2 1100 d 3 0l 1 1 d 4 o10o d 5 ol10 利用经典的构格算法构造表3 1 所示形式背景的概念格。该概念格包含 6 个概念，概念我们用c 来表示，所有概念的集合c = c ，c z ，c s ，c ，c 5 ，c s ) 。对 于任何两个概念之间的相似程度，通过定义的相似度函数计算。设 g = ( 彳，b ) ，其中a 是概念c i 的外延，b 是概念c i 的内涵。c j = c ，表示其中的 一个概念。概念之间的相似度函数可以由定义3 3 确定： 定义3 3 ：( 概念相似度函数) 二掷翱- ( 1 州勰州器 3 9 _ 一 扬州大学硕士学位论文 其中w 为赋予的权值，范围在0 与1 之间。我们可以通过调整w 值的大 小来反映属性的重要程度。 当两个概念c i 和c j 没有任何相似对象和属性时，j 砌( g ，o ) = 0 当c i 和 c j 完全相同时s 砌( d ，g ) = 1 ，s f 朋( c f ，g ) 的数值越接近l 时，两个概念之间的相 似度越大；反之，数值越接近o 时，两个概念的相似度越小。例如从表3 1 形式背景中得到的5 个概念分别为：c l = ( d l ，d 2 ，d 3 ，d 4 ，d 5 ， b ) ) ，c 2 = ( d l ， d 3 ，d 5 ， b ，c ) ) ，c 3 = ( d l ，d 3 ) ， b ，c ，d ) ) ，c 4 = ( d l ，d 2 ， a ，b ) ) ，c 5 = ( d 1 ) ， a ，b ，c ，d ) ) 。我们取w = o 5 则利用定义3 3 的相似度函数可以求得 s 砌( c i ，c 2 ) = o 5 5 0 0 s 砌( c l ，c 4 ) = 0 4 5 0 0 。 从概念中我们很容易得出和文档相关的概念，若概念中包含该文档说 明概念和该文档是相关的。如概念c 3 的对象有d l 和d 3 两篇文档，即文档d l 和d 3 与概念c 3 都是相关的，从而可以得到与每个文档相关的所有概念。如 下表3 2 所示： 表3 2 文档及关联概念 d lc lc 2c 3c 4c 5 d 2c lc 4 d 3c l c 2c 3 d 4c l d 5c lc 2 表3 2 列出了表示文档的每个概念，利用概念表示文本，通过概念的 相似度可以度量文本之间的相似度。文本相似度函数由定义3 4 确定： 定义3 4 ：( 文本相似度函数) 跏( 妣 ) ： s 砌( c j ，g ) 田素方：基于概念格与租糙集的w e b 文本聚类研究 竺 其中m 为文档d i 中包含的概念个数，n 为文档d j 中包含的概念个数，k = m 枣n 为两个文档中概念个数的乘积。例如：在定义6 中我们取w = 0 5 ，则 跏( 九妁= 三( j 砌( c t ，c ) + j 砌( c ，c ：) ) = 三( 1 + o 5 5 ) = o 7 7 5 0 砌行( d 2 ，d s ) = ( s i n ( c l ，c 1 ) + j 砌( c - ，c 。) + j 砌( c 2 ，c 1 ) + j 砌( c 2 ，c 4 ) ) = o 5 8 2 9 3 3 概念格的属性约简 聚类的相似性度量非常重要，以上是解决聚类问题的一个相似度函数。 作为解决聚类问题的概念格模型，随着对象和属性的增加，形式背景以及 格结构都变的非常庞大和复杂，对此我们可以利用粗糙集的可辨识矩阵来 约简概念格的属性，从而去掉冗余的对象和属性，使形式背景更为简洁。 概念格的属性约简可通过可辨识矩阵来实现。 定义3 5 ：对于一个形式背景k = ( d ，丁，d ，d = ( d ，d 2 ，砌 ，乃( 西) 表 示对象谚在属性l 的取值( o 或1 ) 。c d g 歹) ) 表示可辨识矩阵第i 行j 列的元素。 c d ( f ，) = 肛k m 如( 西) ! = 如( 西) 其中f ，= l ，2 ，刀。 则由定义3 5 可求出表3 1 的可辨识矩阵为： q c dqn c dc i d o ( 1 c d c i n c oc dd 0c o 由粗糙集定义m 个布尔变量t l ，t 2 ，t m 的不可分辨函数 声( f l ，厶) = v c d ( f ，) 1 1 _ ，f 甩，c d ( f ，州= 斜，c d ( f ，) = 砷c d ( f ，肼 扫的蕴含式决定了背景的属性的所有的约简集 4 2 _ _ 一 扬州大学硕士学位论文 扫( 口，6 ，c ，d ) = ( c v d ) 口 ( 口v c v d ) 人( 口v d ) ( 口v c v d ) 口人( 口v c ) ( c v d ) d c = 口 c 人d 约简后的形式背景如表3 3 所示： 表3 3 约简后的形式背景 acd d l 111 d 2 10o d 3 011 d 5 o1o 通过对属性的析取和合取运算，可以去掉冗余信息，从而使聚类效果 和精确度都有很大的提高。简化计算，减少时间复杂度。 3 4 基于概念格的k - m e a n s 文本聚类算法( t c u c c ) 现在常用的聚类算法有：分割聚类算法，层次聚类算法，基于密度的 聚类算法，以及基于网格的聚类算法等。其中凝聚层次聚类和k m e a n s 聚类 是应用较为广泛的聚类算法。考虑到k m e a n s 聚类算法效率较高，用k m e a n s 算法的思想来实现基于概念格的w e b 文本的概念聚类。首先选择一个文摘 集，并抽取文档中的特征词，形成初始的形式背景。从形式背景中获取概 念，用概念来表示文本。具体算法如下： 基于概念格的k m e a n s 文本聚类算法 输入：n 篇文档集d 的形式背景，k 为类的数目，6 为类间的相 似阈值 输出：d 中的k 个类 田素方：基于概念格与粗糙集的w e b 文本聚类研究 从形式背景中选择合适的概念来表示文档 随机从d 中选取k 个文档作为初始类d l ，d 2 ，d k d or e p e a t f o re a c hd i d ，i = l ，2 nd o f o re a c hd k ，k = l ，2 kd o 计算文档d i 和d k 之间的相似度跏( 历，眈) i f & 聊( 西，眈) 万t h e n 把文档d i 划入d k e n di f e n df o r 1 1 ：e n df o r u n t i l 达到最大的迭代次数或两次迭代次数变化小于临 1 2 ： 界值 1 3 ：处理没有归入的文档到o t h e r 类 k m e a n s 算法的流程为：首先随机地选择n 个对象，每个对象初始代表 一个簇的平均值或中心；将剩余的对象，分别归与簇中心距离最近的簇。 然后重新计算每个簇的平均值；这个过程不断重复，直到准则函数收敛。 这种聚类算法比较简单，且当结果簇是密集的，而簇与簇之间区别明 显时，它的效果较好；它的时间复杂度是o ( k n t ) 。其中n 是所有对象的数 目，k 是簇的数目，t 是迭代的次数，在处理大数据集时，有相对可伸缩性 和高效率。 l k z 殳 今 殳 良 死 耻 叭 “ 4 4 _ 一 扬州大学硕上学位论文 3 5 实验分析 运行环境为w i n d o w sx p 操作系统，2 8 0 g 的c p u ，2 5 6 m b 的内存，算 法是在v c + + 6 0 的环境下开发。用预先分类好的文档集合来此测试聚类算 法。本文使用m i n i n e w s g r o u p s 集合，这个集合在文档分类实验中得到