正在加载图片...
.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卷