·46 智能系统学报 第3卷 而增大，对赢者对手的抑制作用随增大而减小，所 随机变量，互信息NMI公式定义为NMI(X,Y)= 以需要选取一个合适的1值.实验结果表明，？的取 IX:Y ，I(X:Y)为变量X,Y的互信息 值取所有方向数据向量x到聚类中心向量w:的最 JH(x)·H(Y) 大相似性的0.01~0.2左右较为合适，故文中模糊 量，H9,H(Y)为变量X和Y的熵.平均准确率 程度常数取0.15. atb 基于定理3，得到具有更好鲁棒性的模糊方向 AA的公式定义为：AA(X,)=nx.)/2其中 相似性聚类算法RFDSC.下面给出RFDSC算法的 a表示任意2个样本在X、Y中同属于一类的个数， 完整描述： b表示任意2个样本都不属于同一类的个数，n表示 1)初始化聚类数目c(2≤c≤N),阈值e(1=1 数据集的样本个数.互信息NMI和平均准确率AA 为迭代次数、权重指数m、尺度参数k、模糊程度常 的范围均为0,1]，值越高表示聚类结果越准确，值 数刀和最大迭代次数T,并随机产生并归一化中心 越小2种划分差距越大，在X、Y完全一致的情况 向量w: 下，NMI和AA值为1. 2)根据式7)计算样本的隶属度值1： 3.2实验数据集说明 3)根据式8)计算归一化中心向量W: 实验采用20 Newsgroups!11的数据集及部分 4如果‖1-‖<e或者1>T则停止，算 来自CLUTO文本聚类工具箱的10种数据集.数 法结束，否则1=1+1，跳转2)： 据集含有的样本数从204个到19949不等，数据维 5)当算法收敛，得到各类的中心向量w和样本 数最小的为5832维，最大的为43586维，实际聚类数 集模糊隶属度 最小的为3个，最大的为20个，从以上特征看出这 些数据集很好的反映了不同文本数据集所具有的特 3 实验结果及分析 征.其中NG20数据平均地选自来自20个不同新闻 在本节中首先介绍聚类性能的评价标准，然后 组，经过的Bow toolkit!s]对20 Newsgroups文本 分别对文本数据集进行说明，最后通过使用SPK 进行了预处理后含有19949个向量文本数据. means)、soft-movMF2、FDSC和RFDSC4种相 NG17-19是NG20数据的一个子集，以往的聚类算 似性聚类算法对文本数据集进行测试，以检测各种 法对该数据集的聚类结果表明，因为类与类之间有 聚类算法的性能.由于DSCM算法在处理高维大量 重叠导致对该数据集的聚类难度较高.其他数据均 数据时，算法速度太慢，对文本数据集的有所有样本 来自CLUTO工具箱4，，这些数据集均已经过预处 无法通过有限次迭代过程，自组织的找到所有不动 理为向量文本数据.数据集的详细说明见表1， 点，因此没有对DSCM算法进行比较 表1文本数据集的简要说明 3.1算法性能评价准则 Table 1 Summary of text datasets 对于聚类结果有效性的度量，可以分为面向分 Data Source Kbalance 类的和面向相似性的2种度量方式.第1种度量方 NG20 20-Newsgroups 1994943586200.991 式，如互信息(normalized mutual information, 3 overlapping/ NM)、纯度和F度量，这些度量评估聚类结果包含 NG1719 299815810 30.998 subgroups from N(20 单个类的对象的程度.第2种度量方式，如平均准确 ohscal OHSUMED-233445 1116211465100.437 AA(averaged accuracy or rand index)Jaccard klb WebACE 234021839 6 0043 度量，这些方法度量在多大程度上，同一个类的2个 hitech San Jose Mercury(TREC) 230110080 60.192 对象在同一簇中，或相反⑧1.而衡量传统信息检索系 la12 LA Times(TREC) 627931472 60282 统的性能参数：召回率(Recall)和精度(Precision)也 trll TREC 414 6429 9 0046 是衡量分类算法性能的常用指标，然而聚类的过程 tr23 TREC 2045832 60.066 中并不存在自动分类类别与手工分类类别确定的一 tr41 TREC 878 7454100.037 一对应关系，因而无法像分类一样直接以精度和召 tr45 TREC 6908261100.088 回率作为评价标准.为此在文中采用互信息 注：a代表文本数（样本数），代表词项维数)k代 NMI和平均准确率AA2)分别作为算法的面 表文本实际类别数，balance是数据的平衡系数即包含最少 向分类和面向相似性的2种评价标准.假设X代表 文本数的类与包含最多文本数的类中的文本数之比，这个值 己知的文本类标随机变量，y代表聚类结果的类标 反映了数据集内类与类之间的平衡性 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net而增大 ,对赢者对手的抑制作用随η增大而减小 ,所 以需要选取一个合适的η值. 实验结果表明 ,η的取 值取所有方向数据向量 x 到聚类中心向量 wi 的最 大相似性的 0101～012 左右较为合适 ,故文中模糊 程度常数η取 0115. 基于定理 3 ,得到具有更好鲁棒性的模糊方向 相似性聚类算法 RFDSC. 下面给出 RFDSC 算法的 完整描述 : 1) 初始化聚类数目 c (2 ≤c ≤N) ,阈值ε( l = 1 为迭代次数) 、权重指数 m、尺度参数 k、模糊程度常 数η和最大迭代次数 T ,并随机产生并归一化中心 向量 w 1 i ; 2) 根据式(7) 计算样本的隶属度值 u l + 1 ij ; 3) 根据式(8) 计算归一化中心向量 w l + 1 i ; 4) 如果 ‖u l + 1 ij - u ( l) ij ‖<ε或者 l > T 则停止 ,算 法结束 ,否则 l = l + 1 ,跳转 2) ; 5) 当算法收敛 ,得到各类的中心向量 wi 和样本 集模糊隶属度 uij . 3 实验结果及分析 在本节中首先介绍聚类性能的评价标准 ,然后 分别对文本数据集进行说明 ,最后通过使用 SP K2 means [ 1 ] 、soft2movMF [ 2 ] 、FDSC 和 RFDSC 4 种相 似性聚类算法对文本数据集进行测试 ,以检测各种 聚类算法的性能. 由于 DSCM 算法在处理高维大量 数据时 ,算法速度太慢 ,对文本数据集的有所有样本 无法通过有限次迭代过程 ,自组织的找到所有不动 点 ,因此没有对 DSCM 算法进行比较. 311 算法性能评价准则 对于聚类结果有效性的度量 ,可以分为面向分 类的和面向相似性的 2 种度量方式. 第 1 种度量方 式 , 如 互 信 息 ( normalized mut ual information , NMI) 、纯度和 F 度量 ,这些度量评估聚类结果包含 单个类的对象的程度. 第 2 种度量方式 ,如平均准确 率 AA ( averaged accuracy or rand index) 、J accard 度量 ,这些方法度量在多大程度上 ,同一个类的 2 个 对象在同一簇中 ,或相反[8 ] . 而衡量传统信息检索系 统的性能参数 :召回率(Recall) 和精度(Precision) 也 是衡量分类算法性能的常用指标. 然而聚类的过程 中并不存在自动分类类别与手工分类类别确定的一 一对应关系 ,因而无法像分类一样直接以精度和召 回率作为评价标准[9 ] . 为此在文中采用互信息 NMI [10 ]和平均准确率 AA [11212 ] 分别作为算法的面 向分类和面向相似性的 2 种评价标准. 假设 X 代表 已知的文本类标随机变量 , Y 代表聚类结果的类标 随机变量 ,互信息 NMI 公式定义为 NMI( X , Y) = I ( X ; Y) H ( X) ·H ( Y) , I ( X ; Y) 为变量 X , Y 的互信息 量 , H ( X) , H ( Y) 为变量 X 和 Y 的熵. 平均准确率 AA 的公式定义为 :AA ( X , Y) = a + b n ×( n - 1) / 2 ,其中 a 表示任意 2 个样本在 X 、Y 中同属于一类的个数 , b表示任意 2 个样本都不属于同一类的个数 , n 表示 数据集的样本个数. 互信息 NMI 和平均准确率 AA 的范围均为[0 ,1 ] ,值越高表示聚类结果越准确 ,值 越小 2 种划分差距越大 ,在 X 、Y 完全一致的情况 下 ,NMI 和 AA 值为 1. 312 实验数据集说明 实验采用 202Newsgroup s [13 ] 的数据集及部分 来自 CL U TO [ 14 ]文本聚类工具箱的 10 种数据集. 数 据集含有的样本数从 204 个到19 949不等 ,数据维 数最小的为5 832维 ,最大的为43 586维 ,实际聚类数 最小的为 3 个 ,最大的为 20 个 ,从以上特征看出这 些数据集很好的反映了不同文本数据集所具有的特 征. 其中 N G20 数据平均地选自来自 20 个不同新闻 组 ,经过的 Bow toolkit [ 15 ] 对 202Newsgroup s 文本 进行了预 处理后含 有 19 949 个 向 量 文 本 数 据. N G17219 是 N G20 数据的一个子集 ,以往的聚类算 法对该数据集的聚类结果表明 ,因为类与类之间有 重叠导致对该数据集的聚类难度较高. 其他数据均 来自 CL U TO 工具箱[14 ] ,这些数据集均已经过预处 理为向量文本数据. 数据集的详细说明见表 1. 表 1 文本数据集的简要说明 Table 1 Summary of text datasets Data Source nd nw K balance N G20 202Newsgroup s 19 949 43 586 20 01991 N G17219 3 overlapping/ subgroups from NG20 2 998 15 810 3 01998 ohscal O HSUMED2233445 11 162 11 465 10 01437 klb WebACE 2 340 21 839 6 01043 hitech San Jose Mercury( TREC) 2 301 10 080 6 01192 la12 LA Times( TREC) 6 279 31 472 6 01282 tr11 TREC 414 6 429 9 01046 tr23 TREC 204 5 832 6 01066 tr41 TREC 878 7 454 10 01037 tr45 TREC 690 8 261 10 01088 注 : nd 代表文本数 (样本数) , nw 代表词项 (维数) , k 代 表文本实际类别数 , balance 是数据的平衡系数即包含最少 文本数的类与包含最多文本数的类中的文本数之比 ,这个值 反映了数据集内类与类之间的平衡性. ·46 · 智 能 系 统 学 报 第 3 卷