7)23$$3 ; 1$ 计算机工程与科学 % 此如何对少数民族语种大量据进行自动归类已成为包括维吾尔文在内的新疆少数民族自然语言处理领域中的重要研究课题文本自动归类有分类和聚类两种方法其中聚类是一种无监督的归类方法其实质就是对事先不了解的数据集通过计算机自动进行分组使得同一组内的数据尽

Size: px

Start display at page:

Download "7)23$$3 ; 1$ 计算机工程与科学 % 此如何对少数民族语种大量据进行自动归类已成为包括维吾尔文在内的新疆少数民族自然语言处理领域中的重要研究课题文本自动归类有分类和聚类两种方法其中聚类是一种无监督的归类方法其实质就是对事先不了解的数据集通过计算机自动进行分组使得同一组内的数据尽"

由司马
7 years ago
Views:

1 - 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""($

2 7)23$$3 ; 1$ 计算机工程与科学 % 此如何对少数民族语种大量据进行自动归类已成为包括维吾尔文在内的新疆少数民族自然语言处理领域中的重要研究课题文本自动归类有分类和聚类两种方法其中聚类是一种无监督的归类方法其实质就是对事先不了解的数据集通过计算机自动进行分组使得同一组内的数据尽可能相似而不同组内的数据尽可能不同其目的是揭示数据分布及内在联系的真实情况对中英文来说技术方法早已成熟但维吾尔文等少数民族语种文字特点与中英文不同我们无法直接套用现有的中英文方法这就需要从不同语言文字特点出发开展系统的理论研究及算法研究进行仿真实验及评测在此基础上进行必要的改进或优化本文在较大规模文本语料库基础上用向量空间模型 1+)17 +/ 表示文本以 75)( 为开发平台分别设计并实现了基于和 /)$4 /)$3 的维吾尔文本聚类算法并进行了仿真实验及评测同时结合这两种算法的优缺点实现了一种划分和层次方法相结合的维吾尔文文本聚类算法给出了其结合前后的实验及评价结果维吾尔文文本预处理及文本表示文本聚类系统中首先要对待聚类的每一篇文本进行分词去除停用词等必要的预处理然后使用某一种文本表示模型对文本进行表示就是把文本表示成计算机可计算的形式最后采用某一种聚类算法对文本集进行聚类因此针对不同语言文本的语言特征要进行一些必要的处理建立一个较好的文本模型是文本聚类系统的关键它会直接影响聚类效率分词及停用词过滤维吾尔文属于阿尔泰语系突厥语族由个字母组成是一种拼音文字与英文类似词间是空格隔开因此将文本中的标点符号和非维吾尔文字符去除之后以空格作为自然分隔符很容易获取文本单词集文本聚类中从文本得到的单词集还不能作为特征集来表示文本因为它包含文本集各类文本中普遍出现的通用词和弱词性词这类词区分类别的能力普遍很弱甚至没有任何文本标引作用被称为停用词因此需要建立一个停用词表并按照此表从单词集中过滤所有的停用词从而降低特征空间维数减少噪音停用词的定义在文本聚类领域尚未达成共识根据文本分类涉及的具体领域和研究的需要可以自行建立停用词表在维吾尔文文本聚类研究工作中我们在较大规模文本集类篇文本的基础上以人工统计的方式建立如表所示的停用词表用于过滤单词集中的停用词 #$% 表维吾尔文停用词表词性维吾尔文停用词助词连词副词量词代词数词叹词词干提取维吾尔文文本聚类中词干提取是文本预处理中的关键它会极大地影响聚类效率因为维吾尔文中的一个词常会以不同词形词干构形词缀在同类文本中多次出现词干是词去掉构形附加成分后剩下的部分它包含着词的词汇意义以词干作为特征项一方面可以进一步缩小单词集大小降低特征空间维数比如说一个文本由同词干不同构形后缀的词集在学校从学校学校的往学校把学校组成这些词的本质含义就在于其词干学校如以词作为特征项那么文本在向量空间中的位数是如以词干作为特征项那么该文本在向量空间中的位数降到另一方面能够有效排除构形词缀对文本相似度计算的消极影响假如以上个词按整词看待那就是完全不同的个特征项如提取其词干那么完全是同一个特征项出现这些词干的文本之间存在一定的相似性中文的分词问题在维吾尔文中不是一个关键技术而其难点在于词干的切分因为维吾尔文是一种黏着语词缀连接词干产生的词法变化较复杂如元音弱化辅音弱化元音脱落等这就增加了词干提取的难度和算法复杂度在研究中我们深入研究维吾尔文词法规则用规则及统计语言模型结合的方法实现了一种高切分准确率的维吾尔

3 吐尔地托合提等一种结合和的维吾尔文文本聚类算法文词干提取算法软件登记号 1 并将其引用到文本聚类的词干提取中获取了基于词干的特征集有效降低了特征空间维数本文实验中我们将类篇文本作为实验数据分别以词和词干作为特征表示文本进行对比词和词干特征下的 1+ 向量维数对比如图所示 :$31+53() 图维吾尔文词及词干 1+ ( 文本表示文本表示的模型有多种如布尔模型概率模型向量空间模型和潜在语义索引等不同的模型有不同的理论基础和性能特征在效率和计算复杂性上也有所区别其中向量空间模型 1+ 构造简单系统易于实现还提供了简单的计算特征项权重的方法通过调节对应权重的大小来反映特征项与所在文档的相关程度易于对向量进行修改目前被广泛接受本文也是用向量空间模型来表示维吾尔文文本经过将待聚类的每一篇文本转换成词干集的形式之后采用某种权重计算函数计算出每一个词干在文本中的权值然后把权值大于一定值的词干作为特征向量依次加入向量空间中而权重小于给定值的词干不予考虑常用的权重计算函数有布尔函数频度函数开根号函数对数函数熵函数及 :: 函数其中 :: 函数作为特征权值函数在文本处理领域应用广泛并且取得了不错的效果本文也是通过 :: 函数来计算特征项词干权重根据向量空间模型的相关概念定义文档 ) 为一个文本文档并记为定义特征项为文档中所含有的基本语言单位本文中为词干并记为定义特征项权重 $3() 为表示特征项在文档中的重要程度并记为对于含有个特征项的文档如果特征项的权重用表示那么文档就可用表示简记为那么表示特征项对文档的重要程度就可用表示其计算公式是其中表示特征项在文档中出现的次数值越高意味着特征项对于文档越重要表示特征项的反比文档频数值越高意味着特征项对于文档的区别作用越大 /3 其中是全部文档的总数量表示包含特征项的文档数量值越高意味着特征项在衡量文档之间相似性方面的作用越低如果一个特征项仅出现在一个文档中则 /3 如果一个特征项出现在所有的文档中则 /3 为防止出现的意外常用 /3 其中为常数通常取一个比较小的值如 " 作为影响因子防止分母出现的情况发生另外还应考虑到文档的长度对公式归一化调整后得到槡 ( 文本聚类算法 /3 /3 聚类算法是一种无监督机器学习算法其实质就是对我们事先不了解的数据集进行分组使得同一组内的数据尽可能相似而不同组内的数据尽可能不同其目的是揭示数据分布的真实情况目前已有很多聚类算法可供选择如基于划分的聚类方法 $-1 等基于层次的聚类方法 2(/ 等基于密度的聚类方法等基于网格的聚类方法 <=24/) 1- 等基于神经网络的聚类方法 1+ 等这些算法都有各自的优点和缺点几种常用的文本聚类算法性能对比如表所示从表中可以看出 91-<=2 1+ 等算法因为较低的聚类质量和准确率特征空间的高维性较高的计算复杂度等缺点很难满足大规模数据集的聚类需求算法以其极高的准确率较低的特征维数及聚类粒度的灵活性强等聚类能力在聚类算法中被排在前列但其高计算性的缺点使算法在大规模文本聚类中没能得到广泛应用算法收敛速度快能扩展以用于大规模的数据集但对值的选择没有准则可依循聚类结构可能不平衡也很难得到较

4 7)23$$3 ; 1$ 计算机工程与科学 % )""$%% 表常用聚类算法性能对比算法效率聚类对象形状噪音及异常数据的敏感性数据输入顺序的敏感性高维性计算复杂度一般凸形敏感不太敏感一般较低较高任意形不敏感不太敏感一般较高 91- 一般任意形敏感敏感一般较高 <=2 较低凸形或球形一般不太敏感高较高 1+ 一般任意形状敏感敏感高较高高的聚类效率根据以上算法的综合性能本文选择了和算法对维吾尔文文本进行聚类分析并在两种算法的优缺点上找到了一种巧妙的结合从而在准确率和时间复杂度的综合性能上得到一定的提高和改善 ( 聚类算法在算法的开始首先从待聚类的数据点集合中随机选取是由用户指定个数据点作为初始的聚类中心然后计算每个数据点与各个种子聚类中心之间的距离把每个数据点分配给距离它最近的聚类中心一旦全部数据点都被分配完了每个聚类的聚类中心会根据聚类中现有的数据点被重新计算这个过程将被不断重复直到满足某个终止条件终止收敛条件可以是以下的任何一个没有或最小数目数据点被重新分配给不同的聚类没有或最小数目聚类中心再发生变化误差平方和 112 局部最小 $"% "# 其中表示给定的聚类数目 # 表示第个聚类 % 是聚类 # 的聚类中心 # 中所有数据点的均值向量 $"% 表示数据点 " 和聚类中心 % 之间的距离在欧氏空间中聚类的均值可以用以下公式计算 % # " # " 其中 # 表示 # 中的数据点的个数数据点 " 和聚类均值 % 之间的距离可以被计算如下 $" % " &% 槡 " &% " &% " &% 聚类的特点是使各聚类本身尽可能地紧凑而各聚类之间尽可能地分开从而得到同一聚类中的对象相似度较高而不同聚类中的对象相似度较小 ( 聚类算法是属于自底向上的凝聚层次聚类算法这种方法首先将每个数据点作为一个簇然后合并这些原子簇为越来越大的簇直到所有的数据点都在一个簇中或者某个终结条件被满足给定要聚类的个对象数据点以及的距离矩阵或者是相似性矩阵聚类方法的基本 % 步骤如下 * 将每个对象归为一类共得到类每类仅包含一个对象类与类之间的距离就是它们所包含的对象之间的距离这里定义距离为类间数据两两距离的平均值用组平均距离 7 43<$>3 来度量类间距离其公式为 43 & * 找到最接近的两个类并合并成一类总类数减少一个 *( 重新计算新的类与所有旧类之间的距离 *+ 重复 1)7 和 1)7 直到最后合并成一个类为止此类包含了个对象 (( 和的结合聚类初始中心的选择对古典算法非常重要初始中心选择不当会使迭代很快结束使聚类陷入局部最优解并且随机选择的初始中心会带来聚类结果的波动因此很多学者也针对初始中心的选择问题作了较深入的研究并提出了一些有效的改进方法在一定程度上提高了聚类效果古典算法的缺点就是过分依赖于初始类中心但它在算法简单易于实现快速处理大量数据等方面很有优势因此它作为划分聚类中的代表性算法被广泛应用层次聚类的算法中不牵涉到初始类中心选择问题稳定性好但

5 吐尔地托合提等一种结合和的维吾尔文文本聚类算法对大量数据的高计算性也是评价算法性能时的一个不足之处本文针对古典算法的不稳定性及算法的高计算性采取一种前后互补平衡的方法我们实现的结合算法是两种聚类算法的巧妙结合前端是而后端是因此要有对应的两种输入文本集 < <37 和 1 1/7 其中 < 是待聚类的大文本集是后端的输入 1 是 < 的少一部分是前端的输入算法聚类过程是这样的 * 输入 1 进行聚类 * 计算 1)7 聚类结果中的每一类的类中心质心向量其计算公式如下 % 其中为类的质心向量为类中的文档向量为类中文档的数量 *( 将作为初始类中心输入给后端再对文本集 < 进行快速聚类并输出的计算复杂性对文本量特别敏感但稳定且准确因此将 1 作为前端输入在不提高时间复杂性的前提下快速获取较准确的类中心时间复杂度较低如不考虑对初始类中心的过分依赖性及稳定性那么是大量文本集聚类中的最佳选择因此将前端输出的较优类质心向量作为初始类中心再经过后端快速聚类得到了对文本集 < 较准确的聚类结果本算法在聚类准确率召回率及时间复杂度上都体现出了优越性算法流程如图所示 :$3.$)$ /3$)(753()8)/)$3 图和结合的维吾尔文文本聚类算法流程 + 文本聚类实验及分析 + 数据集对于中英文的文本分类聚类研究国内外已经有相对标准的开放的文本语料库这样就可以在共同的文本集上比较不同的特征选择和聚类方法的性能但是文本分类聚类研究在维吾尔文中刚刚起步目前还没有标准开放的文本集可供使用所以我们从互联网维吾尔文网站收集篇维吾尔文文本属于房地产计算机健康和体育类每类均为篇文本本文为了进行对比实验分别建立了两种实验文本集 < 和 1 < 是包含全部篇文本的大文本集再从类篇文档中选取每类篇组成篇文本的小文本集 1 + 评价指标常用的评价指标包括准确率 $$ 召回率 / 和值等准确率聚类正确的实际聚类的召回率聚类正确的应有的在实验中采用以上三种指标分别衡量古典及结合和的结合算法效率的同时本文还将算法时间复杂度看成相当重要的性能指标来评价算法 +( 聚类实验及分析本文用跨平台开发工具 75)( 分别设计并实现了古典和结合聚类和的结合的维吾尔文本聚类系统实验是在配置为 )/ 双核 2%"*? 处理器 9 内存操作系统为 $% 的机上进行的本文实验中将文本集 < 和作为实验数据分别进行古典及结合算法的文本聚类实验其中和的输入是 < 而结合算法的输入是 1 和 < 实验结果及算法效率对比如表表所示从表给出的三种算法性能对比中可以看到我们的结合算法比算法用更短的时间得到了比古典更高的聚类效率因为结合算法在这两种算法的优缺点上找到了一种巧妙的结合

6 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

7 吐尔地托合提等一种结合和的维吾尔文文本聚类算法 /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"

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位自然科学版文章编号视网膜图像中视盘的快速自动定位方法赵晓芳林土胜李碧摘要基于眼底视网膜血管的分布结构及视盘本身的特点提出一种快速自动定位视盘的方法首先根据视网膜血管的网络分布结构大致定位视盘的垂直坐标然后根据视盘的亮度信息及视盘与血管的关系来定位视盘的水平坐标最后把视盘限定在以粗定位的视盘为中心的一个小窗口内用变换精确定位视盘中心该方法不需要事先分割视网膜血管也不需要对算法进行训练