D0I:10.13374/i.issnl00113.2008.02.022 第30卷第2期 北京科技大学学报 Vol.30 No.2 2008年2月 Journal of University of Science and Technology Beijing Feh.2008 基于非结构化数据挖掘结构模型的Web文本聚类算法 胡健) 杨炳儒)宋泽锋2)钱榕2) 1)江西理工大学信息工程学院，赣州3410002)北京科技大学信息工程学院，北京100083 摘要在非结构化数据挖掘结构模型一发现特征子空间模型(DSSM)一的运行机制下，提出了一种新的Wb文本聚 类算法一基于DFSS M的Wb文本聚类(WTCDFSSM)算法，·该算法具有自稳定性，无须外界给出评价函数：能够识别概念 空间中最有意义的特征，抗噪声能力强。结合现代远程教育网应用背景实现了WTCDFSSM聚类算法·结果表明：该算法可以 对各类远程教育站点上收集的文本资料信息自动进行聚类挖掘：采用网格结构模型，帮助人们进行文本信息导航：从海量文 本信息源中快速有效地获取重要的知识， 关键词W山文本挖掘：文本聚类：聚类评价；非结构化数据挖掘结构模型 分类号TP393.09 Web text clustering algorithm based on the nonstructural data mining model HU Jian),YANG Bingru2).SONG Zefeng2),QIA N Rong2) 1)School of Information Engineering Jiangxi University of Science and Technology Ganzhou 341000.China 2)School of Information Engineering.University of Science and Technology Beijing.Beijing 100083.China ABSTRACI Under the background of the nonstructural data mining model.a Web text clustering mining algorithm based on the discovery feature sub-space mode(DFSSM).WTCDFSS M algorithm,was proposed,which can distinguish the most meaningful fea- tures from the concept space without any evaluation function.The WTCDFSS M algorithm was applied in the modern long"distance e- ducation net.The result shows that it can automatically congregate the text information of education field,which is collected from ed- ucation sites on Internet,help people to browse the important information quickly by information navigation mechanism and acquire useful knowledge. KEY WORDS Web text mining:text clustering:clustering evaluation:non"structured data mining structure model 随着网络技术的飞速发展，Internet正以令人 文本聚类分析在文本挖掘研究中占有重要的位 难以相信的速度在飞速发展，越来越多的机构、团体 置，它和文本分类是相辅相成的，聚类分析依据的 和个人在Internet上发布信息、查找信息，虽然In 原则是使同一类中的对象具有尽可能大的相似性， ternet上有海量数据，但Web文档是无结构的、动态 而不同类中的对象具有尽可能大的差异性] 的，并且Wb页面的复杂程度远远超过了文本文 目前，常用的文本聚类分析方法主要有层次聚 档，人们想要找到自己需要的数据犹如大海捞针一 类分析方法、平面划分聚类分析方法（如K一平均聚 般。目前网上虽然有很多的搜索工具可以利用，但 类算法和K中心点聚类算法)、基于模型的聚类分 是其查全率和查准率都差强人意，而且它们不能针 析方法（如神经网络算法和统计学算法）等)，被 对特定的用户给出特定的服务，解决这个问题的途 广泛地使用在商业智能、知识管理及CRM等实用 径之一就是采用高效、灵活的Wb文本聚类分析 系统中，同时，它们也能用来解决智能检索系统目 算法 前存在的“信息过载”问题，过滤检索获得的大量文 本信息中的“噪声”，提高信息的含金量和准确度， 收稿日期.2006-10-29修回日期.2006-12-16 本文通过分析以上各类算法的优缺点，提出了 基金项目：国家自然科学基金重点资助项目(N。·69835001):教育 一种基于发现特征子空间模型(DFSSM)山的具有 部科技重点资助项目（教技司[2000]175）：北京市自然科学基金资助 项目(Na.4022008) 自稳定性的Wb文本聚类(WTCDFSSM)算法，它 作者简介：胡健(1967一)，男，副教授.博士 主要在Hilbert子空间一概念空间一的范畴，定
基于非结构化数据挖掘结构模型的 Web 文本聚类算法 胡 健1） 杨炳儒2） 宋泽锋2） 钱 榕2） 1） 江西理工大学信息工程学院赣州341000 2） 北京科技大学信息工程学院北京100083 摘 要 在非结构化数据挖掘结构模型———发现特征子空间模型（DFSSM）———的运行机制下提出了一种新的 Web 文本聚 类算法———基于 DFSSM 的 Web 文本聚类（WTCDFSSM）算法．该算法具有自稳定性无须外界给出评价函数；能够识别概念 空间中最有意义的特征抗噪声能力强．结合现代远程教育网应用背景实现了 WTCDFSSM 聚类算法．结果表明：该算法可以 对各类远程教育站点上收集的文本资料信息自动进行聚类挖掘；采用网格结构模型帮助人们进行文本信息导航；从海量文 本信息源中快速有效地获取重要的知识． 关键词 Web 文本挖掘；文本聚类；聚类评价；非结构化数据挖掘结构模型 分类号 TP393∙09 Web text clustering algorithm based on the nonstructural data mining model HU Jian 1）Y A NG Bingru 2）SONG Zefeng 2）QIA N Rong 2） 1） School of Information EngineeringJiangxi University of Science and TechnologyGanzhou341000China 2） School of Information EngineeringUniversity of Science and Technology BeijingBeijing100083China ABSTRACT Under the background of the nonstructural data mining modela Web text clustering mining algorithm based on the discovery feature sub-space model （DFSSM）WTCDFSSM algorithmwas proposedwhich can distinguish the most meaningful features from the concept space without any evaluation function．T he WTCDFSSM algorithm was applied in the modern long-distance education net．T he result shows that it can automatically congregate the text information of education fieldwhich is collected from education sites on Internethelp people to browse the important information quickly by information navigation mechanism and acquire useful knowledge． KEY WORDS Web text mining；text clustering；clustering evaluation；non-structured data mining structure model 收稿日期：2006-10-29 修回日期：2006-12-16 基金项目：国家自然科学基金重点资助项目（No．69835001）；教育 部科技重点资助项目（教技司［2000］175）；北京市自然科学基金资助 项目（No．4022008） 作者简介：胡 健（1967—）男副教授博士 随着网络技术的飞速发展Internet 正以令人 难以相信的速度在飞速发展越来越多的机构、团体 和个人在 Internet 上发布信息、查找信息．虽然 Internet 上有海量数据但 Web 文档是无结构的、动态 的并且 Web 页面的复杂程度远远超过了文本文 档人们想要找到自己需要的数据犹如大海捞针一 般．目前网上虽然有很多的搜索工具可以利用但 是其查全率和查准率都差强人意而且它们不能针 对特定的用户给出特定的服务．解决这个问题的途 径之一就是采用高效、灵活的 Web 文本聚类分析 算法． 文本聚类分析在文本挖掘研究中占有重要的位 置它和文本分类是相辅相成的．聚类分析依据的 原则是使同一类中的对象具有尽可能大的相似性 而不同类中的对象具有尽可能大的差异性［1—3］． 目前常用的文本聚类分析方法主要有层次聚 类分析方法、平面划分聚类分析方法（如 K—平均聚 类算法和 K—中心点聚类算法）、基于模型的聚类分 析方法（如神经网络算法和统计学算法）等［4—9］被 广泛地使用在商业智能、知识管理及 CRM 等实用 系统中．同时它们也能用来解决智能检索系统目 前存在的“信息过载”问题过滤检索获得的大量文 本信息中的“噪声”提高信息的含金量和准确度． 本文通过分析以上各类算法的优缺点提出了 一种基于发现特征子空间模型（DFSSM） ［1］ 的具有 自稳定性的 Web 文本聚类（WTCDFSSM）算法．它 主要在 Hilbert 子空间———概念空间———的范畴定 第30卷 第2期 2008年 2月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．2 Feb．2008 DOI:10．13374／j．issn1001－053x．2008．02．022
.218 北京科技大学学报 第30卷 义了文本聚类的类别及距离测度的概念，采用神经 文档的查全率(recall)、查准率(precision)及综合分 网络算法获得相应的聚类谱系图，对文本聚类模式 类率F1值(F1vaue),但是在文本聚类过程中并不 提出了客观的评价指标及评价算法 存在自动分类类别与手工分类类别确定的一一对应 1WEb文本聚类算法WTCDFSSM 关系，因而无法像文本分类一样直接以查全率和查 准率作为评价标准2].为此，本文将选择平均准 1.1 WTCDFSSM中类别及距离测度 确率0作为评价的指标.平均准确率通过考察任意 由于Wb文本纷繁芜杂的特性，以及在特征提 两篇文章之间类属关系是否一致来评价聚类的效 取过程中用来表示文本性质的特征变量的不同选择 果，任意两篇文章之间的关系，按照人工分类的标 方法，使得文本的表示形式多种多样，在不同的应用 准和自动聚类分析的标准可以有四种情况，见表1. 领域中类别的定义也是不同的，因此，在WTCDF- 表1文本之间的关系 SSM算法研究中，给出了概念空间中文本聚类的类 Table 1 Relationship between documents 别及距离测度的定义 人工分类时 聚类分析时 设P表示一个有n个文本的集合，d:表示其中 标识 属于同一类别 属于同一类别 的文本，α为预设阈值 Yes Yes a 定义1如果对于任意d:,d∈P,都有D(d:, Yes No d d)≤a,则P称为一个类别. No Yes c 设P1,P2为文本样本点集合，D(P1,P2)为衡 No No 量两类之间的相似性的测度函数，用于测量两篇文 档之间的相似程度，其值越小则两篇文档之间的相 平均准确率0定义为积极准确率与消极准 似程度越高，在WTCDFSSM聚类分析算法中，概 确率2的算术平均值，即： 念空间中常用的类间测度函数有以下几种 0=(0+02)/2 (5) 定义2根据如下公式定义的类间距离测度称 其中，积极准确率定义为： 为重心法距离测度： 01=a/(a+c) (6) D(P1,P2)=D(X,Y) (1) 消极准确率2定义为： 其中，X是P1的重心，Y是P2的重心，重心法是从 02=d/(b+d) (7) 物理意义的角度出发，以类的重心代表此类，使用两 通过如下的文本聚类评价算法（算法1）对于文 类重心之间的距离来描述类间相似性 本聚类结果进行评价，WTCDFSSM聚类结果的评 定义3根据如下公式定义的类间距离测度称 价算法： 为最小距离测度，它将使用两类间的最近两点的距 离来描述两类间的相似程度： Step1在每次新的训练结束后，按照式(5)， D(P1,P2)=minD(X,Y)lX∈P1,Y∈P2} 计算聚类结果的平均准确率： Step2当0大于等于指定的阈值a的时候，将 (2) 本次S0M聚类产生的权值矢量 定义4根据如下公式定义的类间距离测度称 为最大距离测度，它将使用两类间的最远两点的距 W=(Dj1,02…,Djn),j=1,2,,m 离来描述两类间的相似程度： 作为有效文本模式存放到衍生模式库中； D(P1,P2)=max D(X,Y)|X∈P1,Y∈P2} Step3当0小于指定的阈值a时，调整S0M 网络中的参数值（修正系数η(t)及侧反馈邻域 (3) 定义5根据如下公式定义的类间距离测度称 Se(t)); 为类平均法： Step4跳至Step 1,重复执行以上步骤. D(P1,P)=L∑∑D(X,Y)(④ 1.3DSSM中文本特征提取(TFE)算法描述 n1n2.xEP1小yez 给出了一个基于DFSSM模型新的文本特征提 类平均法使用P1,P2中两两文本样本点距离的平 取算法，其具体实现步骤如下所示： 均值来表示类间距离， 输入原始文本/特征项矩阵S=[w]m×n; 1.2 WTCDFSSM聚类评价算法 输出原始文本/特征项矩阵S的模式矢量 在文本分类算法中经常使用的性能评价指标为 Pk=(1,u2,…,4)及每一篇文档的特征模式矢量
义了文本聚类的类别及距离测度的概念采用神经 网络算法获得相应的聚类谱系图对文本聚类模式 提出了客观的评价指标及评价算法． 1 Web 文本聚类算法 WTCDFSSM 1∙1 WTCDFSSM中类别及距离测度 由于 Web 文本纷繁芜杂的特性以及在特征提 取过程中用来表示文本性质的特征变量的不同选择 方法使得文本的表示形式多种多样在不同的应用 领域中类别的定义也是不同的．因此在 WTCDFSSM 算法研究中给出了概念空间中文本聚类的类 别及距离测度的定义． 设 P 表示一个有 n 个文本的集合di 表示其中 的文本α为预设阈值． 定义1 如果对于任意 didj∈P都有 D（ di dj）≤α则 P 称为一个类别． 设 P1P2 为文本样本点集合D（ P1P2）为衡 量两类之间的相似性的测度函数用于测量两篇文 档之间的相似程度其值越小则两篇文档之间的相 似程度越高．在 WTCDFSSM 聚类分析算法中概 念空间中常用的类间测度函数有以下几种． 定义2 根据如下公式定义的类间距离测度称 为重心法距离测度： D（P1P2）＝ D（ XY ） （1） 其中X 是 P1 的重心Y 是 P2 的重心重心法是从 物理意义的角度出发以类的重心代表此类使用两 类重心之间的距离来描述类间相似性． 定义3 根据如下公式定义的类间距离测度称 为最小距离测度它将使用两类间的最近两点的距 离来描述两类间的相似程度： D（P1P2）＝min｛D（ XY ）｜X∈P1Y ∈P2｝ （2） 定义4 根据如下公式定义的类间距离测度称 为最大距离测度它将使用两类间的最远两点的距 离来描述两类间的相似程度： D（P1P2）＝max｛D（ XY ）｜X∈P1Y ∈P2｝ （3） 定义5 根据如下公式定义的类间距离测度称 为类平均法： D（P1P2）＝ 1 n1n2 i∑X i∈P1 j∑Y j∈P2 D（ XiY j） （4） 类平均法使用 P1P2 中两两文本样本点距离的平 均值来表示类间距离． 1∙2 WTCDFSSM聚类评价算法 在文本分类算法中经常使用的性能评价指标为 文档的查全率（recall）、查准率（precision）及综合分 类率 F1值（F1value）．但是在文本聚类过程中并不 存在自动分类类别与手工分类类别确定的一一对应 关系因而无法像文本分类一样直接以查全率和查 准率作为评价标准［12—13］．为此本文将选择平均准 确率θ作为评价的指标．平均准确率通过考察任意 两篇文章之间类属关系是否一致来评价聚类的效 果．任意两篇文章之间的关系按照人工分类的标 准和自动聚类分析的标准可以有四种情况见表1． 表1 文本之间的关系 Table1 Relationship between documents 人工分类时 属于同一类别 聚类分析时 属于同一类别 标识 Yes Yes a Yes No b No Yes c No No d 平均准确率 θ定义为积极准确率θ1 与消极准 确率θ2 的算术平均值即： θ＝（θ1＋θ2）／2 （5） 其中积极准确率θ1 定义为： θ1＝ a／（ a＋c） （6） 消极准确率θ2 定义为： θ2＝ d／（ b＋ d） （7） 通过如下的文本聚类评价算法（算法1）对于文 本聚类结果进行评价．WTCDFSSM 聚类结果的评 价算法： Step1 在每次新的训练结束后按照式（5） 计算聚类结果的平均准确率θ； Step2 当θ大于等于指定的阈值α的时候将 本次 SOM 聚类产生的权值矢量 Wj＝（ wj1wj2…wjn）j＝12…m 作为有效文本模式存放到衍生模式库中； Step3 当 θ小于指定的阈值α时调整 SOM 网络中的参数值（修正系数 η（ t ） 及侧反馈邻域 Sc（ t））； Step4 跳至 Step1重复执行以上步骤． 1∙3 DFSSM中文本特征提取（TFE）算法描述 给出了一个基于 DFSSM 模型新的文本特征提 取算法其具体实现步骤如下所示： 输入 原始文本／特征项矩阵 S＝［ wij ］ m× n； 输出 原始文本／特征项矩阵 S 的模式矢量 Pk＝（ u1u2…uk）及每一篇文档的特征模式矢量 ·218· 北 京 科 技 大 学 学 报 第30卷
第2期 胡健等：基于非结构化数据挖掘结构模型的Wb文本聚类算法 .219. Pp 2Web文本聚类分析算法WTCDFSSM的 Step 1 for j=l to m do 实现 {将S的所有特征词项t存入候选集C中； Step2对于候选集C中的所有特征词项，应 2.1文本聚类的测试语料库 用Zipf法则，删除出现次数低于3及高于1000的 结合本文的课题背景一教育部重点科技攻关 特征词条，并经此变换后生成矩阵S； 项目·“现代远程教育中的关键技术一信息挖掘和 Step 3 for i=1 to 3 do 智能搜索工具的研究”，对于上述提出的文本聚类算 {使用小波变换算法（采用凸3小波函数）对于 法WTCDFSS M在实际运行环境中进行了运行测 矩阵S所构成的二维文本数据进行分解，得到S的 试，该Wh文本挖掘软件系统通过了教育部组织 第i个分解层次的小波系数矩阵S,Sh,S, 的鉴定委员会的正式鉴定，并通过了中国软件评测 中心的软件鉴定测评. Spa: 采用如下两个语料库：其一，采用的测试数据集 Step4保存Sa,即将小波变换后得到的第3 是一个具有近1000篇中文文本的语料库（称为语 层低频部分的小波系数矩阵作为原始文本/特征词 料库1)，语料库中的文本均采自现代远程教育站点 条矩阵S的近似矩阵，rank(Sa)=r; 的教育类热点新闻.其二，为了进一步研究WTCDF- Step5计算S的奇异值分解(SVD),将该矩 SSM聚类算法的实际性能，扩展了所研究的语料范 阵分解成为三个矩阵U、A和V,U和V是正交矩 围.在一个含有约2300篇语料的新闻语料库（称为 阵(UU=I,VV=),A是奇异值的对角矩阵， 语料库2)上进行了实际运行测试，该新闻语料库中 并通过下式选取降维的因子数K(即潜在的语义结 的文本都是新闻电讯稿件，其中，两个语料库的测试 构数)，求最小的K满足 数据类别构成分别为表2及表3所示 表2测试语料库1的类别构成 (8) Table 2 Document categories in Corpus I 主题类别 文本篇数 主题类别 文本篇数 家庭教育 370 素质教育 203 Step6按照公式计算得到S的近似矩阵 考试聚焦 391 其他 32 Ak,然后用该矩阵的非零奇异值构造形成原始文本 表3测试语料库2的类别构成 集的模式矢量Pk=(u1,u2,…,k); Table 3 Document categories in Corpus 2 Step 7 for j=1 to size(C)do 主题类别 文本篇数 主题类别 文本篇数 {在候选集C中，删除SVD分解中消除的特征 政治与社会 607 教育 147 词项； 军事 407 航空航天 130 Step8用候选集C中的特征项子集替换原始 计算机 354 法律 81 文本空间的特征项，然后基于上述的近似矩阵A 体育 242 医疗卫生 70 构造生成每一个文档在“概念空间”范畴内的特征模 经济 198 旅游服务 56 式矢量PD,并用合适的数据结构存储模式矢量P 2.2 文本聚类分析算法WTCDFSSM性能分析 及PD, 为了考察WTCDFSSM算法的实际性能，采用 通过以上提出的DFSSM中的文本特征提取算 经典的K一平均聚类算法、K一中心点聚类算法和层 法(TFE)可以将特征词项空间转化到概念空间，在 次聚类分析算法5-]与本文提出的WTCDFSSM算 该转化过程中忽略重要程度特别低的概念（即特征 法在测试语料库1和语料库2的基础上作了实例对 词项)：由于这些概念蕴涵的信息量比较少，忽略掉 比分析，算法聚类结果如图1和2所示， 并不会影响全局，可以选择Ak的前K个特征值所 从以上的实验运行结果中可以看出：WTCDF- 对应的特征矢量，K的选取可以按照式(8)进行，其 S$M聚类分析算法的平均准确率比其他三种聚类 中，t是一个预先设定的阈值，表示信息损失的多 分析算法要高；该算法具有很强的自适应学习能力、 少，一般取t=0.80~0.90.也就是说，忽略掉一些 鲁棒性和容错能力，同时在实验观察结果中发现， 重要程度特别低的概念会造成信息的损失，但损失 WTCDFSS M聚类算法得到的集簇具有相当鲜明的 程度不超过0.100.20这个限度. 类别特征，即与一个主题类别相关的文本较集中地
PDi． Step1 for j＝1to m do ｛将 S 的所有特征词项 tj 存入候选集 C 中｝； Step2 对于候选集 C 中的所有特征词项应 用 Zipf 法则删除出现次数低于3及高于1000的 特征词条并经此变换后生成矩阵 S′； Step3 for i＝1to3do ｛使用小波变换算法（采用 db3小波函数）对于 矩阵 S′所构成的二维文本数据进行分解得到 S′的 第 i 个分解层次的小波系数矩阵 S i AS i HdS i Vd S i Dd｝； Step4 保存 S 3 a即将小波变换后得到的第3 层低频部分的小波系数矩阵作为原始文本／特征词 条矩阵 S 的近似矩阵rank（ S 3 a）＝ r； Step5 计算 S 3 a 的奇异值分解（SVD）将该矩 阵分解成为三个矩阵 U、A 和 VU 和 V 是正交矩 阵（ U T U＝ IV T V＝ I）A 是奇异值的对角矩阵 并通过下式选取降维的因子数 K（即潜在的语义结 构数）求最小的 K 满足 ∑ K i＝1 λi ∑ r i＝1 λi ≥t （8） Step6 按照公式计算得到 S 3 a 的近似矩阵 Ak然后用该矩阵的非零奇异值构造形成原始文本 集的模式矢量 Pk＝（ u1u2…uk）； Step7 for j＝1to size（C） do ｛在候选集 C 中删除 SVD 分解中消除的特征 词项｝； Step8 用候选集 C 中的特征项子集替换原始 文本空间的特征项然后基于上述的近似矩阵 Ak 构造生成每一个文档在“概念空间”范畴内的特征模 式矢量 PDi并用合适的数据结构存储模式矢量 Pk 及 PDi． 通过以上提出的 DFSSM 中的文本特征提取算 法（TFE）可以将特征词项空间转化到概念空间．在 该转化过程中忽略重要程度特别低的概念（即特征 词项）；由于这些概念蕴涵的信息量比较少忽略掉 并不会影响全局．可以选择 Ak 的前 K 个特征值所 对应的特征矢量K 的选取可以按照式（8）进行．其 中t 是一个预先设定的阈值表示信息损失的多 少一般取 t＝0∙80～0∙90．也就是说忽略掉一些 重要程度特别低的概念会造成信息的损失但损失 程度不超过0∙10～0∙20这个限度． 2 Web 文本聚类分析算法 WTCDFSSM 的 实现 2∙1 文本聚类的测试语料库 结合本文的课题背景———教育部重点科技攻关 项目“现代远程教育中的关键技术———信息挖掘和 智能搜索工具的研究”对于上述提出的文本聚类算 法 WTCDFSSM 在实际运行环境中进行了运行测 试．该 Web 文本挖掘软件系统通过了教育部组织 的鉴定委员会的正式鉴定并通过了中国软件评测 中心的软件鉴定测评． 采用如下两个语料库：其一采用的测试数据集 是一个具有近1000篇中文文本的语料库（称为语 料库1）语料库中的文本均采自现代远程教育站点 的教育类热点新闻．其二为了进一步研究 WTCDFSSM 聚类算法的实际性能扩展了所研究的语料范 围．在一个含有约2300篇语料的新闻语料库（称为 语料库2）上进行了实际运行测试该新闻语料库中 的文本都是新闻电讯稿件．其中两个语料库的测试 数据类别构成分别为表2及表3所示． 表2 测试语料库1的类别构成 Table2 Document categories in Corpus1 主题类别 文本篇数 家庭教育 370 考试聚焦 391 主题类别 文本篇数 素质教育 203 其他 32 表3 测试语料库2的类别构成 Table3 Document categories in Corpus2 主题类别 文本篇数 政治与社会 607 军事 407 计算机 354 体育 242 经济 198 主题类别 文本篇数 教育 147 航空航天 130 法律 81 医疗卫生 70 旅游服务 56 2∙2 文本聚类分析算法 WTCDFSSM性能分析 为了考察 WTCDFSSM 算法的实际性能采用 经典的 K—平均聚类算法、K—中心点聚类算法和层 次聚类分析算法［5—8］与本文提出的 WTCDFSSM 算 法在测试语料库1和语料库2的基础上作了实例对 比分析算法聚类结果如图1和2所示． 从以上的实验运行结果中可以看出：WTCDFSSM 聚类分析算法的平均准确率比其他三种聚类 分析算法要高；该算法具有很强的自适应学习能力、 鲁棒性和容错能力．同时在实验观察结果中发现 WTCDFSSM 聚类算法得到的集簇具有相当鲜明的 类别特征即与一个主题类别相关的文本较集中地 第2期 胡 健等： 基于非结构化数据挖掘结构模型的 Web 文本聚类算法 ·219·
,220 北京科技大学学报 第30卷 0.96 算法WTCDFSS M的平均准确率比其他三种聚类分 ◆WTCDFSSM 析算法高；WTCDFSSM得到的集簇具有鲜明的类 °092 聚类算法 ·K.平均聚类 别特征，能够有效地提取聚类集中的主题特征项， 0.88 算法 K-中心点 聚类算法 参考文献 0.84 “层次聚类 分析算法 [1]Yang B R,Tang J.The research of discovery feature sub-space 0.80 model (DFSSM)based on complex type data.Eng Sci,2003.5 家庭教育考试聚焦素质教育 (1):56 主题类别 (杨炳儒，唐菁.基于复杂类型数据的发现特征子空间模型 DFSSM的研究，中国工程科学，2003,5(1)：56) 图1在语料库1中WTCDFSSM聚类算法与其他算法聚类结果 [2]Wang JC.Pan JG,Zhang F Y.Research on Web text mining. 比较 J Comput Res Dev.2000.37(5):513 Fig.1 Comparison of experimental results between WTCDFSSM (王继成，潘金贵，张福炎.W山文本挖掘技术研究，计算机研 and related algorithms in Corpus 1 究与发展，2000,37(5)：513) [3]Han K S,Wang Y C.Text mining,data mining vs.knowledge 1.0 management:the intelligent information processing in the 21st century.JChina Soc Sci Tech Inf,2001.20(1):100 (韩客松，王永成.文本挖掘、数据挖掘和知识管理一二十一 0.8 世纪的智能信息处理.情报学报，2001,20(1)：100) 0.7 ◆WTCDFSSM聚类算法 [4]Feldman R.Dagan I.Knowledge discovery in textual database 。K。平均聚类算法 0.6 。K中心点聚类算法 (KDT)/Proceedings of Ist International Conference on Knowl- 州层次聚类分析算法 edge Discovery and Data Mining.Canada,1995:112 0.5 [5]Hodge V J.Austin J.Hierarchical word clustering:automatic thesaurus generation.Neurocomputing.2002,48(1):819 [6]Roussinov D.Zhao J L.Automatic discovery of similarity rela- 主题类别 tionships through Web mining.Decis Support Syst,2003.35 (1):149 图2在语料库2中WTCDFSSM聚类算法与其他算法聚类结果 [7]Runkler T A.Bezdek JC.Web mining with relational clustering 比较 Int JApproximate Reason.2003.32(2):217 Fig.2 Comparison of experimental results between WTCDFSSM [8]Pullwitt D.Integrating contextual information to enhance SOM- based text document clustering.Neural Networks.2002.15 and related algorithms in Corpus 2 (8):1099 聚为一类。因此，平均准确率只是从一个方面说明 [9]Wu B.Fu W P,Zheng Y,et al.A clustering algorithm based on swarm intelligence for Web document.JComput Res Dev.2002. 了WTCDFSSM算法具有良好的聚类特征； 39(11):1429 WTCDFSSM算法相比于其他各种聚类算法更重要 (吴斌，傅伟鹏，郑毅，等.一种基于群体智能的W山文档聚类 的优势为通过自组织特征映射发现文本集内在的主 算法.计算机研究与发展，2002,39(11)：1429) [10]Li G.Shao F J.Zhu B H.Research of the clustering algorithm 题特征项， based on neural network.JQingdao Unie Eng Technol Ed. 3结论 2001,16(4):21 (李戈，邵峰晶，朱本浩.基于神经网络聚类的研究.青岛大 本文提出并实现了Wb文本聚类算法 学学报：工程技术版，2001,16(4)：21) [11]Chen F J,Yang S L.A clustering method for Chinese Web doe- WTCDFSSM.该算法的基本特征是：(1)在Web文 ument based on SOM.JChina Soc Sci Tech Inf,2002,21(2): 本挖掘系统结构模型DFSSM所提供的运行机制下 173 具体实现的；(2)在概念空间中给出WTCDFSSM (陈福集，杨善林.一种基于S0M的中文Wb文档层次聚类 文本聚类算法的类别和距离测度的定义；(3)针对 方法.情报学报，2002,21(2)：173) [12]Jiang Ning ShiZZ.Bayesian posteriori model selection for text 挖掘形成的聚类模式提供有效的评价指标和评价 clustering.JComput Res Dev.2002.39(5):580 算法 (姜宁，史忠植，文本聚类中的贝叶斯后验模型选择方法·计 结合现代远程教育应用背景，在本文所提供的 算机研究与发展，2002,39(5)：580) 测试语料库1及测试语料库2的基础上，对比分析 [13]Jiang N.Gong X J.ShiZ Z.Text clustering in high dimension feature space.Comput Eng Appl.2002.10,63 了WTCDFSSM聚类分析算法及常用的K一平均聚 (姜宁，宫秀军，史忠植。高维特征空间中文本聚类研究。计 类算法、K中心点聚类算法和层次聚类分析算法， 算机工程与应用，2002,10,63) 实验结果表明：构建在概念空间中的文本聚类分析
图1 在语料库1中 WTCDFSSM 聚类算法与其他算法聚类结果 比较 Fig．1 Comparison of experimental results between WTCDFSSM and related algorithms in Corpus1 图2 在语料库2中 WTCDFSSM 聚类算法与其他算法聚类结果 比较 Fig．2 Comparison of experimental results between WTCDFSSM and related algorithms in Corpus2 聚为一类．因此平均准确率只是从一个方面说明 了 WTCDFSSM 算 法 具 有 良 好 的 聚 类 特 征； WTCDFSSM 算法相比于其他各种聚类算法更重要 的优势为通过自组织特征映射发现文本集内在的主 题特征项． 3 结论 本 文 提 出 并 实 现 了 Web 文 本 聚 类 算 法 WTCDFSSM．该算法的基本特征是：（1） 在 Web 文 本挖掘系统结构模型 DFSSM 所提供的运行机制下 具体实现的；（2） 在概念空间中给出 WTCDFSSM 文本聚类算法的类别和距离测度的定义；（3） 针对 挖掘形成的聚类模式提供有效的评价指标和评价 算法． 结合现代远程教育应用背景在本文所提供的 测试语料库1及测试语料库2的基础上对比分析 了 WTCDFSSM 聚类分析算法及常用的 K—平均聚 类算法、K—中心点聚类算法和层次聚类分析算法． 实验结果表明：构建在概念空间中的文本聚类分析 算法 WTCDFSSM 的平均准确率比其他三种聚类分 析算法高；WTCDFSSM 得到的集簇具有鲜明的类 别特征能够有效地提取聚类集中的主题特征项． 参 考 文 献 ［1］ Yang B RTang J．The research of discovery feature sub-space model （DFSSM） based on complex type data．Eng Sci20035 （1）：56 （杨炳儒唐菁．基于复杂类型数据的发现特征子空间模型 DFSSM 的研究．中国工程科学20035（1）：56） ［2］ Wang J CPan J GZhang F Y．Research on Web text mining． J Comput Res Dev200037（5）：513 （王继成潘金贵张福炎．Web 文本挖掘技术研究．计算机研 究与发展200037（5）：513） ［3］ Han K SWang Y C．Text miningdata mining vs．knowledge management：the intelligent information processing in the 21st century．J China Soc Sci Tech Inf200120（1）：100 （韩客松王永成．文本挖掘、数据挖掘和知识管理———二十一 世纪的智能信息处理．情报学报200120（1）：100） ［4］ Feldman RDagan I．Knowledge discovery in textual database （KDT）∥ Proceedings of 1st International Conference on Knowledge Discovery and Data MiningCanada1995：112 ［5］ Hodge V JAustin J．Hierarchical word clustering：automatic thesaurus generation．Neurocomputing200248（1）：819 ［6］ Roussinov DZhao J L．Automatic discovery of similarity relationships through Web mining． Decis Support Syst200335 （1）：149 ［7］ Runkler T ABezdek J C．Web mining with relational clustering． Int J App roximate Reason200332（2）：217 ［8］ Pullwitt D．Integrating contextual information to enhance SOMbased text document clustering． Neural Networks200215 （8）：1099 ［9］ Wu BFu W PZheng Yet al．A clustering algorithm based on swarm intelligence for Web document．J Comput Res Dev2002 39（11）：1429 （吴斌傅伟鹏郑毅等．一种基于群体智能的 Web 文档聚类 算法．计算机研究与发展200239（11）：1429） ［10］ Li GShao F JZhu B H．Research of the clustering algorithm based on neural network．J Qingdao Univ Eng Technol Ed 200116（4）：21 （李戈邵峰晶朱本浩．基于神经网络聚类的研究．青岛大 学学报：工程技术版200116（4）：21） ［11］ Chen F JYang S L．A clustering method for Chinese Web document based on SOM．J China Soc Sci Tech Inf200221（2）： 173 （陈福集杨善林．一种基于 SOM 的中文 Web 文档层次聚类 方法．情报学报200221（2）：173） ［12］ Jiang NingShi Z Z．Bayesian posteriori model selection for text clustering．J Comput Res Dev200239（5）：580 （姜宁史忠植．文本聚类中的贝叶斯后验模型选择方法．计 算机研究与发展200239（5）：580） ［13］ Jiang NGong X JShi Z Z．Text clustering in high-dimension feature space．Comput Eng Appl200210：63 （姜宁宫秀军史忠植．高维特征空间中文本聚类研究．计 算机工程与应用200210：63） ·220· 北 京 科 技 大 学 学 报 第30卷