- 11-%& 计算机工程与科学 7)23$$3 ; 1$ 第 卷第 % 期 年 % 月 /-%,/ 文章编号 %&%% 一种结合 和 的维吾尔文文本聚类算法 吐尔地 托合提 艾海麦提江 阿布来提 米也塞 艾尼玩 艾斯卡尔 艾木都拉 新疆大学信息科学与工程学院 新疆乌鲁木齐 摘 要 介绍了 和 聚类算法思想和两种特征提取方法对维吾尔文文本表示及聚类效率的影响 在较大规模文本语料库基础上 分别用 和 的方法进行维吾尔文文本聚类实验及性能对比分析 针对经典 算法对初始聚类中心的过分依赖性及不稳定性缺点以及 的高计算复杂性 提出了一种结合 和 的维吾尔文聚类算法 本算法分两步完成聚类操作 首先是 模块从少量文本集中获取最优的初始类中心 然后是 模块对大量文本集进行快速聚类 实验结果表明 新算法在聚类准确率和时间复杂度上都有了显著的提高 关键词 维吾尔文 文本聚类 结合算法 中图分类号 文献标志码 "#"$"%&""%" " "#$% & % ()$*+,-./)+011 $1 */ 1(/)$1$23$$3&$#$3$4$)56$($ (77$))()()(/)$3)()($ 7)))8))$)(53()8)7))$/)$3$$5"9 )(/3/)8)7.)()()()(/)$3 )() 5)53()8)/)$387$)77)$4/5$"4$)( ()$3)())()($47))($$)$//))$).// )(($3(7))$/7/8$)5)( )()($777753()8)/) $3/3$)(.$$3)()()("(77/3$)(())7" :$)/5)(7)$/$$)$//))$.)$)(/))8)).5)( )("1/5)(/3))8))$)/).5)()("287$)/ /)()())(77/3$)( ($3$$)$)(/)$35)( )$7/8$)5" $53()8))8)/)$3.$/3$)( 引言 随着新疆地区信息化建设的快速发展 维吾 尔文等少数民族语种大量的文字信息开始以数字化形式呈现 或过去积累的海量纸质文字信息开始数字化存储 众多应用领域都需要通过计算机自动归类的方法去整合及有效利用海量文本信息 因 收稿日期 % 修回日期 基金项目 国家自然科学基金资助项目 新疆维吾尔自治区高技术研究发展计划项目 新疆维吾尔自治区高校科研计划重点项目 &,2 教育部新世纪优秀人才支持计划资助项目 -2 通讯地址 新疆乌鲁木齐市胜利路 号新疆大学信息科学与工程学院 号楼 室 9$/$31(/)$1$23$$3&$#$3$4$)51(3/$6$ &$#$3""($
7)23$$3 ; 1$ 计算机工程与科学 % 此 如何对少数民族语种大量据进行自动归类 已成为包括维吾尔文在内的新疆少数民族自然语言处理领域中的重要研究课题 文本自动归类有分类和聚类两种方法 其中聚类是一种无监督的归类方法 其实质就是对事先不了解的数据集通过计算机自动进行分组 使得同一组内的数据尽可能相似而不同组内的数据尽可能不同 其目的是揭示数据分布及内在联系的真实情 况 对中英文来说 技术方法早已成熟 但维吾尔文等少数民族语种文字特点与中英文不同 我们无法直接套用现有的中英文方法 这就需要从不同语言文字特点出发开展系统的理论研究及算法研究 进行仿真实验及评测 在此基础上进行必要的改进或优化 本文在较大规模文本语料库基础上 用向量空间模型 1+)17 +/ 表示文本 以 75)( 为开发平台 分别设计并实现了基于 和 7 43 33/)$4 /)$3 的维吾尔文本聚类算法 并进行了仿真实验及评测 同时 结合这两种算法的优缺点 实现了一种划分和层次方法相结合的维吾尔文文本聚类算法 给出了其结合前后的实验及评价结果 维吾尔文文本预处理及文本表示 文本聚类系统中 首先要对待聚类的每一篇文本进行分词 去除停用词等必要的预处理 然后使用某一种文本表示模型对文本进行表示 就是把文本表示成计算机可计算的形式 最后采用某一种聚类算法对文本集进行聚类 因此 针对不同语言文本的语言特征 要进行一些必要的处理 建立一个较好的文本模型是文本聚类系统的关键 它会直接影响聚类效率 分词及停用词过滤 维吾尔文属于阿尔泰语系突厥语族 由 个字母组成 是一种拼音文字 与英文类似 词间是空格隔开 因此将文本中的标点符号和非维吾尔文字符去除之后 以空格作为自然分隔符很容易获取文本单词集 文本聚类中 从文本得到的单词集还不能作为特征集来表示文本 因为它包含文本集各类文本中普遍出现的通用词和弱词性词 这类词区分类别的能力普遍很弱甚至没有任何文本标引作用 被称为停用词 因此 需要建立一个停用词表 并按照此表从单词集中过滤所有的停用词 从而降低特征空 间维数 减少噪音 停用词的定义在文本聚类领域尚未达成共识 根据文本分类涉及的具体领域和研究的需要 可以自行建立停用词表 在维吾尔文文本聚类研究工作中 我们在较大规模文本集 类 篇文本 的基础上 以人工统计的方式建立如表 所示的停用词表 用于过滤单词集中的停用词 #$% 表 维吾尔文停用词表 词性维吾尔文停用词助词连词副词量词代词数词叹词 词干提取维吾尔文文本聚类中 词干提取是文本预处理 中的关键 它会极大地影响聚类效率 因为 维吾尔文中的一个词 常会以不同词形 词干 构形词缀 在同类文本中多次出现 词干是词去掉构形附加成分后剩下的部分 它包含着词的词汇意义 以词干作为特征项 一方面可以进一步缩小单词集大小 降低特征空间维数 比如说 一个文本由同词干不同构形后缀的词集 在学校 从学校 学校的 往学校 把学校 组成 这些词的本质含义就在于其词干 学校 如以词作为特征项 那么文本在向量空间中的位数是 如以词干作为特征项 那么该文本在向量空间中的位数降到 另一方面 能够有效排除构形词缀对文本相似度计算的消极影响 假如 以上 个词按整词看待 那就是完全不同的 个特征项 如提取其词干 那么完全是同一个特征项 出现这些词干的文本之间存在一定的相似性 中文的分词问题 在维吾尔文中不是一个关键技术 而其难点在于词干的切分 因为维吾尔文是一种黏着语 词缀连接词干产生的词法变化较复杂 如元音弱化 辅音弱化 元音脱落等 这就增加了词干提取的难度和算法复杂度 在研究中 我们深入研究维吾尔文词法规则 用规则及统计语言模型结合的方法 实现了一种高切分准确率的维吾尔
吐尔地 托合提等 一种结合 和 的维吾尔文文本聚类算法 文词干提取算法 软件登记号 1 并将其引用到文本聚类的词干提取中 获取了基于词干的特征集 有效降低了特征空间维数 本文实验中 我们将 类 篇文本作为实验数据 分别以词和词干作为特征表示文本 进行对比 词和词干特征下的 1+ 向量维数对比如图 所示 :$31+53() 图 维吾尔文词及词干 1+ ( 文本表示文本表示的模型有多种 如布尔模型 概率模型 向量空间模型和潜在语义索引等 不同的模型有不同的理论基础和性能特征 在效率和计算复杂性上也有所区别 其中 向量空间模型 1+ 构造简单 系统易于实现 还提供了简单的计算特征项权重的方法 通过调节对应权重的大小来反映特征项与所在文档的相关程度 易于对向量进行修改 目前被广泛接受 本文也是用向量空间模型来表示维吾尔文文本 经过将待聚类的每一篇文本转换成词干集的形式之后 采用某种权重计算函数计算出每一个词干在文本中的权值 然后把权值大于一定值的词干作为特征向量依次加入向量空间中 而权重小于给定值的词干不予考虑 常用的权重计算函数有布尔函数 频度函数 开根号函数 对数函数 熵函数及 :: 函数 其 中 :: 函数作为特征权值函数在文本处理领域应用广泛 并且取得了不错的效果 本文也是通过 :: 函数来计算特征项 词干 权重 根据向量空间模型的相关概念 定义文档 ) 为一个文本文档并记为 定义特征项 为文档中所含有的基本语言单位 本文中为词干 并记为 定义特征项权重 $3() 为表示特征项在文档中的重要程度并记为 对于含有 个特征项的文档 如果特征项 的权重用 表示 那么文档就可用 表示 简记为 那么表示特 征项 对文档 的重要程度 就可用 表示 其计算公式是 其中 表示特征项 在文档 中出现的次数 值越高 意味着特征项 对于文档 越重要 表示特征项的反比文档频数 值越高意味着特征项 对于文档的区别作用越大 /3 其中 是全部文档的总数量 表示包含特征项 的文档数量 值越高 意味着特征项 在衡量文档之间相似性方面的作用越低 如果一个特征项 仅出现在一个文档中 则 /3 如果一个特征项 出现在所有的文档中 则 /3 为防止出现 的意外 常用 /3 其中 为常数 通常取一个比较小的值 如 " 作为影响因子 防止分母出现 的情况发生 另外 还应考虑到文档的长度 对公式 归一化调整后得到 槡 ( 文本聚类算法 /3 /3 聚类算法是一种无监督机器学习算法 其实质就是对我们事先不了解的数据集进行分组 使得同一组内的数据尽可能相似而不同组内的数据尽可能不同 其目的是揭示数据分布的真实情况 目前已有很多聚类算法可供选择 如基于划分的聚类方法 $-1 等 基于层次的聚类方法 2(/ 等 基于密度的聚类方法 91-11 等 基于网格的聚类方法 <=24/) 1- 等 基于神经网络的聚类方法 1+ 等 这些算法都有各自的优点和缺点 几种常用的文本聚类算法性能对比如表 所示 从表 中可以看出 91-<=2 1+ 等算法 因为较低的聚类质量和准确率 特征空间的高维性 较高的计算复杂度等缺点 很难满足大规模数据集的聚类需求 算法 以其极高的准确率 较低的特征维数及聚类粒度的灵活性强等聚类能力 在聚类算法中被排在前列 但其高计算性的缺点 使算法在大规模文本聚类中没能得到广泛应用 算法 收敛速度快 能扩展以用于大规模的数据集 但对 值的选择没有准则可依循 聚类结构可能不平衡 也很难得到较
7)23$$3 ; 1$ 计算机工程与科学 % )""$%% 表 常用聚类算法性能对比 算法 效率 聚类对象形状 噪音及异常数据的敏感性 数据输入顺序的敏感性 高维性 计算复杂度 一般 凸形 敏感 不太敏感 一般 较低 较高 任意形 不敏感 不太敏感 一般 较高 91- 一般 任意形 敏感 敏感 一般 较高 <=2 较低 凸形或球形 一般 不太敏感 高 较高 1+ 一般 任意形状 敏感 敏感 高 较高 高的聚类效率 根据以上算法的综合性能 本文选择了 和 算法 对维吾尔文文本进行聚类分析 并在两种算法的优缺点上找到了一种巧妙的结合 从而在准确率和时间复杂度的综合性能上 得到一定的提高和改善 ( 聚类算法 在算法的开始 首先从待聚类的数据点集合中随机选取 是由用户指定 个数据点作为初始的聚类中心 然后 计算每个数据点与各个种子聚类中心之间的距离 把每个数据点分配给距离它最近的聚类中心 一旦全部数据点都被分配完了 每个聚类的聚类中心会根据聚类中现有的数据点被重新计算 这个过程将被不断重复直到满足某个终止条件 终止 收敛 条件可以是以下 的任何一个 没有 或最小数目 数据点被重新分配给不同的聚类 没有 或最小数目 聚类中心再发生变化 误差平方和 112 局部最小 $"% "# 其中 表示给定的聚类数目 # 表示第 个聚类 % 是聚类 # 的聚类中心 # 中所有数据点的均值向量 $"% 表示数据点 " 和聚类中心 % 之间的距离 在欧氏空间中 聚类的均值可以用以下公式计算 % # " # " 其中 # 表示 # 中的数据点的个数 数据点 " 和聚类均值 % 之间的距离可以被计算如下 $" % " &% 槡 " &% " &% " &% 聚类的特点是使各聚类本身尽可能地紧凑 而各聚类之间尽可能地分开 从而得到同 一聚类中的对象相似度较高 而不同聚类中的对象相似度较小 ( 聚类算法 是属于自底向上的凝聚层次聚类算法 这种方法首先将每个数据点作为一个簇 然后合并这些原子簇为越来越大的簇 直到所有的数据点都在一个簇中 或者某个终结条件被满足 给定要聚类的 个对象 数据点 以及 的距离矩阵 或者是相似性矩阵 聚类方法的基本 % 步骤如下 * 将每个对象归为一类 共得到 类 每类仅包含一个对象 类与类之间的距离就是它们所包含的对象之间的距离 这里定义距离为类间数据两两距离的平均值 用组平均距离 7 43<$>3 来度量类间距离 其公式为 43 & * 找到最接近的两个类并合并成一类 总类数减少一个 *( 重新计算新的类与所有旧类之间的距离 *+ 重复 1)7 和 1)7 直到最后合并成一个类为止 此类包含了 个对象 (( 和 的结合 聚类初始中心的选择对古典 算法非常重要 初始中心选择不当会使迭代很快结束 使聚类陷入局部最优解 并且随机选择的初始中心会带来聚类结果的波动 因此 很多学者也针对初始中心的选择问题作了较深入的研究并提出了一些 有效的改进方法 在一定程度上提高了聚类效果 古典 算法的缺点就是过分依赖于初始类中心 但它在算法简单易于实现 快速处理大量数据等方面很有优势 因此它作为划分聚类中的代表性算法被广泛应用 层次聚类的 算法中不牵涉到初始类中心选择问题 稳定性好 但
吐尔地 托合提等 一种结合 和 的维吾尔文文本聚类算法 对大量数据的高计算性也是评价算法性能时的一个不足之处 本文针对古典 算法的不稳定性及 算法的高计算性采取一种前后互补平衡的方法 我们实现的结合算法是两种聚类算法的巧妙结合 前端是 而后端是 因此要有对应的两种输入文本集 < <37 和 1 1/7 其中 < 是待聚类的大文本集 是后端 的输入 1 是 < 的少一部分 是前端 的输入 算法聚类过程是这样的 * 输入 1 进行 聚类 * 计算 1)7 聚类结果中的每一类的类中心 质心向量 其计算公式如下 % 其中 为 类的质心向量 为 类中的文档向量 为 类中文档的数量 *( 将 作为初始类中心输入给后端 再对文本集 < 进行 快速聚类并输出 的计算复杂性对文本量特别敏感 但稳定且准确 因此将 1 作为前端输入 在不提高时间复杂性的前提下快速获取较准确的类中心 时间复杂度较低 如不考虑对初始类中心的过分依赖性及稳定性 那么是大量文本集聚类中的最佳选择 因此 将前端输出的较优类质心向量作为初始类中心 再经过后端 快速聚类 得到了对文本集 < 较准确的聚类结果 本算法在聚类准确率 召回率及时间复杂度上都体现出了优越性 算法流程如图 所示 :$3.$)$ /3$)(753()8)/)$3 图 和 结合的维吾尔文文本聚类算法流程 + 文本聚类实验及分析 + 数据集对于中 英文的文本分类 聚类研究 国内外已经有相对标准的 开放的文本语料库 这样就可以在共同的文本集上比较不同的特征选择和聚类方法的性能 但是 文本分类 聚类研究在维吾尔文中刚刚起步 目前还没有标准 开放的文本集可供使用 所以 我们从互联网维吾尔文网站收集 篇维吾尔文文本 属于房地产 计算机 健康和体育类 每类均为 篇文本 本文为了进行对比实验 分别建立了两种实验文本集 < 和 1 < 是包含全部 篇文本的大文本集 再从 类 篇文档中选取每类 篇组成 篇文本的小文本集 1 + 评价指标常用的评价指标包括准确率 $$ 召回率 / 和 值等 准确率 聚类正确的 实际聚类的 召回率 聚类正确的 应有的 在实验中 采用以上三种指标分别衡量古典 及结合 和 的结合 算法效率的同时 本文还将算法时间复杂度看成相当重要的性能指标来评价算法 +( 聚类实验及分析本文用跨平台开发工具 75)( 分别设计并实现了古典 和结合聚类 和 的结合 的维吾尔文本聚类系统 实验是在配置为 )/ 双核 2%"*? 处理器 9 内存 操作系统为 $% 的 机上进行的 本文实验中 将文本集 < 和 作为实验数据 分别进行古典 及结合算法的文本聚类实验 其中 和 的输入是 < 而结合算法的输入是 1 和 < 实验结果及算法效率对比如表 表 所示 从表 给出的三种算法性能对比中可以看到 我们的结合算法比 算法用更短的时间 得到了比古典 更高的聚类效率 因为结合算法在这两种算法的优缺点上 找到了一种巧妙的结合
7)23$$3 ; 1$ 计算机工程与科学 % (%%" 类别 表 ( 古典 聚类实验结果 聚类结果原有聚类正确实际聚类 聚类效率 @@ 体育 " 房产 %" 健康 " " 计算机 " " 类别 +%%" 表 + 聚类实验结果 聚类结果原有聚类正确实际聚类 聚类效率 @@ 体育 " " 房产 % %" " 健康 " %" 计算机 % " ",%%" 类别 表, 结合算法聚类实验结果 聚类结果原有聚类正确实际聚类 聚类效率 @@ 体育 % % " 房产 % " 健康 " %" 计算机 % " " -)""."% 表 - 三种聚类算法的性能对比 算法 @ @ 时间 %" " " " " " " " 结合算法 " " "% " 古典 中 算法从待聚类文本集中随机选取 个文本点作为初始类中心 如果被随机选的 个文本点恰恰是最优的类中心 那么得到较好的聚类效果 但是 这种可能性是不确定的 因此对同样的数据集进行多次聚类 可能得到不同的聚类结果 这是 的一个致命缺点 如果解决这种随机性 并给算法提供较优的初始类中心 在大规模文本聚类中成为一个快速 高效的聚类算法是完全可能的 是一种自底向上的层次聚类算法 根 本就不存在初始类中心的选取问题 通过较复杂的向量计算得到较高的聚类准确率 因此数据量的稍微增加也会大大延长计算时间 本文实验中 对 篇文本 1 的 聚类用时为 " 秒 而 篇文本 < 的聚类用时为 " 秒 结合算法中 前端用 算法对小规模 本实验中 篇 文本进行聚类 在不增加计算时间的前提下得到了较准确的聚类结果 并把它作为后端 的初始类中心 再对大规模 本实验中 篇 文本进行快速聚类 本算法是 和 优缺点上的一种平衡 在大规模文本聚类中 会体现出比 和 更优越的综合性能, 结束语 本文介绍了维吾尔文特点 文本预处理及文本表示方法 较深入研究 和 聚类算法思想 并在此基础上提出了一种结合 和 的维吾尔文文本聚类算法 在较大规模文本语料库基础上 分别用 和 的方法进行维吾尔文文本聚类实验及性能对比分析 综合考虑经典 算法对初始聚类中心过分依赖的缺点 以及 算法高计算性缺点 实现了两种算法前后巧妙结合的一种高效聚类算法 从实验结论得知 本文采取的方法是可行的 有效的 参考文献 1 $>1#5 ") $$3)(5 7)$+": +$3-$(353)/)$"9$ #$3($+($ "$($ $()$$$ +#>*/"5)( $653(?>535?/)8)(3$ )$4/4,"7)23$$3 %"$($ 9,$/3")$)$4/5) $3. )(4$)7/,",/)$% "$($" A(3 0331($$3<B,$"74) 77/$)$::)(.)8)/$$)$," 7)23$$3 %%"$($ <$&$3$<$,")$$3>/3$45 +"9$#$3*$3(2)$"$($ <$9$3".) $$3+"0 03&$3 *$35$)/)$"9$#$3$3($4$)5 "$($ %+&$530"(($($//)$3
吐尔地 托合提等 一种结合 和 的维吾尔文文本聚类算法 /3$)(,"7)1$%"$ ($ (3"8)/)$3$/)$5). $74 /3$)(,"7) 1$/)$ %%"$($ A(3 $3,$30&$#$")8) /)$3/3$)(.$)5)$3(.,",/7)77/$)$% "$($ <$0/$<$&$5"/)$3/3$)(. $)5,"7) 23$$3 77/$)$ %"$($ 附中文参考文献 1$>1#5" 数据挖掘基础教程 +" 范明 牛常勇 译 " 北京 机械工业出版社 " 吐尔地 托合提 维尼拉 木沙江 艾斯卡尔 艾木都拉 " 维 哈 柯全文搜索引擎检索器的关键技术," 计算机工程 %" 包金龙 " 基于向量空间模型的信息检索系统的设计," 情报杂志 % " 张玉芳 彭时名 吕佳 " 基于文本分类 :: 方法的改进与应用," 计算机工程 %%" 李雄飞 李军 " 数据挖掘与知识发现 +" 北京 高等教育出版社 " 刘兵 ". 数据挖掘 +" 俞勇 薛贵荣 韩定一 译 " 北京 清华大学出版社 " % 马晓艳 唐雁 " 层次聚类算法研究," 计算机科学 %" 潘大胜 " 基于改进的 算法的文本聚类仿真系统," 计算机仿真 %%" 张文明 吴江 袁小蛟 " 基于密度和最近邻的 文本聚类算法," 计算机应用 %" 刘艳丽 刘希云 " 一种基于密度的 均值算法," 计算机工程与应用 %" 作者简介 吐尔地 托合提 % 男 新疆拜城人 博士生 副教授 : 会员 + 研究方向为自然语言处理及文本挖掘 /)58#"" #01.$%( $)$)7:.+($ ($))$/)//337$3 )8)$$3" 艾海麦提江 阿布来提 男 新疆疏附人 硕士生 研究方向为自然语言处理 /.4()".$+1 $)($ ( $)) $/ )//337$3" 米也塞 艾尼玩 女 新疆莎车人 硕士生 研究方向为文本挖掘 / %%66" #**0. $ +1 $)( ( $))$ /)8)$$3" 艾斯卡尔 艾木都拉 % 男 新疆叶城人 博士后 教授 : 会员 + 研究方向为多语种信息处理 />8#"" *0 %.$%7) )7:. +($($ ))$//)$/$3/$)$7$3"