第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 A‚S i Hd‚S i Vd‚ S i Dd｝； Step4 保存 S 3 a‚即将小波变换后得到的第3 层低频部分的小波系数矩阵作为原始文本／特征词 条矩阵 S 的近似矩阵‚rank（ S 3 a）＝ r； Step5 计算 S 3 a 的奇异值分解（SVD）‚将该矩 阵分解成为三个矩阵 U、A 和 V‚U 和 V 是正交矩 阵（ U T U＝ I‚V T V＝ I）‚A 是奇异值的对角矩阵‚ 并通过下式选取降维的因子数 K（即潜在的语义结 构数）‚求最小的 K 满足 ∑ K i＝1 λi ∑ r i＝1 λi ≥t （8） Step6 按照公式计算得到 S 3 a 的近似矩阵 Ak‚然后用该矩阵的非零奇异值构造形成原始文本 集的模式矢量 Pk＝（ u1‚u2‚…‚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）‚语料库中的文本均采自现代远程教育站点 的教育类热点新闻．其二‚为了进一步研究 WTCDF￾SSM 聚类算法的实际性能‚扩展了所研究的语料范 围．在一个含有约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所示． 从以上的实验运行结果中可以看出：WTCDF￾SSM 聚类分析算法的平均准确率比其他三种聚类 分析算法要高；该算法具有很强的自适应学习能力、 鲁棒性和容错能力．同时在实验观察结果中发现‚ WTCDFSSM 聚类算法得到的集簇具有相当鲜明的 类别特征‚即与一个主题类别相关的文本较集中地 第2期 胡 健等： 基于非结构化数据挖掘结构模型的 Web 文本聚类算法 ·219·