计算机论文：维吾尔文无监督自动切分及无监督特征选择

    摘 要 维吾尔文常用切分方法会产生大量的语义抽象甚至多义的词特征，因此学习算法难以发现高维数据中隐藏的结构． 提出一种无监督切分方法 dme-TS 和一种无监督特征选择方法 UMRMR-UFS． dme-TS 从大规模生语料中自动获取单词 Bi-gram 及上下文语境信息，并将相邻单词间的 t-测试差、互信息及双词上下文邻接对熵的线性融合作为一个组合统计量( dme) 来评价单词间的结合能力，从而将文本切分成语义具体的独立语言单位的特征集合．UMRMR-UFS 用一种综合考虑最大相关度和最小冗余的无监督特征选择标准( UMRMR) 来评价每一个特征的重要性，并将最重要的特征依次移入到特征子集中． 实验结果表明 dme-TS 能有效控制原始特征集的规模，提高特征项本身的质量，用 UMRMR-UFS 的输出来表征文本时，学习算法也表现出其最高的性能．

       关键词 维吾尔文切分，互信息，t-测试差，邻接对熵，无监督特征选择
       1 引 言英文中，以词间分隔符( 空格) 切分的方法非常容易获取文本的词特征，但中文即需要进行特殊的分词处理，这也是中文自然语言处理中的一个难点．而维吾尔文就跟英文一样，词之间也是以空格隔开，通常也是用与英文完全一样的方法获取词特征，但同样的算法在维吾尔文处理中的效果远达不到英文． 这是因为维吾尔文中能作为重要特征的名词、专业词和术语不一定是单词，很多情况下是多词关联模式，是不可分割的独立运用语言单位． 然而，维吾尔文基于词间空格的切分方法( Inter-Word SpaceBased Text Segmentation，iws-TS) 将这些语义上的一个词拆分成语法结构上的多个词，因此特征空间维数显然较高，且还会导致以下更严重的问题:
　　1) 在文本中充当一个词作用的关联模式，被拆分 成 与 本 词 义 根 本 不 符 的 若 干 个 片 段，如" "( 软件) 被拆分成一个形容词" "( 软) 和一个抽象名词" "( 器件) ，因此一个完整语义信息从特征空间中消失;2) 从一个多词关联模式中拆分出来的单词，其语 义 是 抽 象 的， 甚 至 是 多 义 的， 如" "( 数据库) 被拆分成三个多义词，即" "( 数量，期，名额，大腿等) ，" "( 数据，报道，学识，记载，情报等) 和" "( 新疆地名，仓库，堆栈等) ，这样的单词特征对原始文本的表征能力存在一定的缺陷，有时还会出现较大偏差，这与中文字特征的文本表征非常类似．从语义表达能力上进行对比，一个维吾尔文多词关联模式相当于一个中文词，再说一个中文词也是中文字的关联模式，是一个独立的语言单元，其内部结合紧密，不可分割． 因此，以相邻汉字之间的结合程度作为切分依据，或将它作为补充手段来消除歧义，在中文分词方法中已起到较好的作用． 如孙茂松等从大规模生语料中获取汉字二元信息，并用互信息及 t-测试差的线性叠加值来衡量相邻汉字之间的结合能力，设计一种无词表及无指导学习的自动分词算法． 王思力等用双字耦合度和 t-测试差的线性叠加值来消除分词中的交叉歧义，但他们是从熟语料中获取二元模型． 费洪晓等分别用 N-gram、互信息及 t-测试 3 种统计量来判断双字构成词的可能性． 还有王芳等用互信息定量估计相邻两个基本词间的结合可信度，提出一种基于可信度的中文完整词自动识别方法． 何赛克等将字串邻接变化数( Accessor Variety，AV) 引入基于条件随机场的中文分词系统中，提高分词系统性能． 基于词典的分词方法 Mmseg 中，蒋建洪等用互信息来度量并过滤非邻接词，使分词系统性能得到提高．受上述论文研究工作的启发，本文引入另外一种统计量---邻接对熵( Entropy of Adjacency) ，并将 t-测试差( Difference of t-Test) ，互信息( Mutual In-formation) 及邻接对熵的线性融合作为一个新的统计量 dme，提出一种无指导学习及无词典支持的维吾尔文自动切分方法( dme Based Text Segmentation，dme-TS) ． 切分算法所需要的所有统计信息机器从大规模生语料中自动获取，无人工介入． 与 iws-TS相比，用 dme-TS 切分的原始特征集规模更小、质量更好，但还有很多特征是冗余的甚至是不相关的． 因此，需进行特征选择以去除更多的冗余和不相关特征( 噪音) ．特征选择方法大体上可分为有监督和无监督两种． 因为，实际数据环境中类别间的复杂关系、类别分布的不平衡性、标注瓶颈及类别信息的不确定性等问题，使有监督特征选择方法很难适应新的文本类型和更为复杂的实际应用需求． 因此，在大规模未标注样本分析的迫切需求推动下，无监督特征选择算法逐渐发展起来．
      近年来，研究者们在无监督特征选择方面做了很多工作，如 Mitra 等使用最大信息压缩指标来度量特征之间的相似性以检测冗余特征，提出一种针对数值型数据的无监督特征选择方法． 之后何中市等把这种方法和 DF 结合用到文本特征选择中，但最终学习算法性能的提高不太明显． 刘涛等提出一种无监督特征选择算法( K-meams BasedFeature Selection，KFS) ，他们在 K-means 多次聚类结果的基础上再使用 CHI 进行特征选择． 类似地，朱颢东等也提出基于 K-means 聚类的无监督特征选择方法，与文献不同的是，他们用 IG． 还有叶菲等先用 K-means 迭代聚类法确定特征子集的最佳分类数，然后用中心距离比值准则来评价特征子集的分类性能． 王连喜等采用一趟聚类算法先对数据集进行聚类，然后用 Gini 指标的统计量来度量特征的重要程度． 然而，上述方法几乎都是8 46模式识别与人工智能 26 卷Wrapper( 包装) 模型的特征选择方法，其通用性差、时间复杂度较高，且选用的聚类算法及聚类结果的好坏始终会起到决定性作用．本文提出一种基于 Filter( 过滤) 模型的无监督特征选择方法( Unsupervised Minimum Redundancyand Maximum Relevancy-Unsupervised Feature Selec-tion，UMRMR-UFS) ，其搜索方式为前向搜索． UM-RMR-UFS 中，用一种基于最小冗余及最大相关性度量的无监督评价标准 UMRMR 对所有的候选特征进行打分，即一个候选特征在原始特征集中的平均互信息量越大( 最大相关) ，则它在已选特征集中平均互信息量越小( 最小冗余) ，那么该特征得分就越高． UMRMR-UFS 每次选一个得分最高的候选特征并将它移入到已选特征集中，最后输出一个给定数量的有序特征序列( 特征子集) 或整个特征集的有序序列．本文提出的 dme-TS 和 UMRMR-UFS 是文本预处理中关系密切的两个子过程，即 dme-TS 的输入是待处理的文本集，其输出是经过 dme-TS 切分的原始特征集，然后 UMRMR-UFS 将这个原始特征集作为输入、输出一个最优特征子集． 在整个过程中，无任何指导策略和已知信息的支持，完全符合开放环境中的文本处理需求．
       2 无监督文本切分 dme-TS对于一个独立语言单元，内部词与词( 字与字)之间的结合程度应非常紧密，而它与外部上下文的关系应该是非常松散，这种"紧密"或"松散"性可用某种统计量来度量，而这个统计量也能非常容易地从大规模真实语料中获取．
       2． 1 基本统计量: 互信息根据互信息( Mutual Information) 原理，对以空格隔开的维吾尔文有序词串 AB中，单词A，B之间的互信息定义为mi( A，B) = log2P( A，B)P( A) P( B)，其中，P( A，B) 为词串 AB 在语料库中出现的概率，P( A) 为单词 A 出现的概率，P( B) 为单词 B 出现的概率． 假定它们在语料库中出现的次数分别计为count( A) 、count( B) 、count( A，B) ，n 是语料库中的词频总数，则P( A，B) =count( A，B)n，P( A) =count( A)n，P( B) =count( B)n．互信息 mi( A，B) 反映单词串 AB 间的关联程度． 如果 mi( A，B) ≥ 0，则 AB 间是强关联的; 如果mi( A，B) ≈ 0，则 AB 间是弱关联的; 如果 mi( A，B)＜ 0，则 AB 间是互斥的． 随着 mi( A，B) 的增加，紧密程度也增加，当 mi( A，B) 大于给定的一个阈值 Tmi时，可认为 AB 是不可分割的．从计算式看出，互信息反应相邻单词AB之间的静态结合能力，而不考虑它们的上下文，因此仅依靠互信息这个绝对度量，有时也会出现错误的判断．
       2． 2 基本统计量: t-测试差Church 等首次引入t-测试，以度量一个英文单词A与其它任意两个单词x和y的结合紧密程度．之后孙茂松等对 t-测试的计算公式进行改进，提出 t-测试差( Difference of t-test) 的概念，并与互信息结合应用到中文分词中．根据定义，维吾尔文单词串 x A y 的 t-测试值计算式为tx，y( A) =p( y A) － p( A x)σ2( P( y A) ) + σ2( P( A x槡) )，其中，p( y A) 和p( A x) 分别是单词串A y和x A的Bi-gram 概率，σ2( P( y A) ) 和 σ2( P( A x) ) 分别是二者的方差． 可看出，若tx，y( A) ＞ 0，则A与后继y结合的强度大于与前趋 x 结合的强度，此时 A 应与 x分开，而与y 连． 若tx，y( A) ＜ 0，则A与前趋x 结合的强度大于与后继 y 结合的强度，此时 A 应与 y 分开，而与x连． 若tx，y( A) =0，则A与其前趋和后继的结合强度相等，无法判断 A 跟哪连或分开．t-测试是基于字的统计量，而不是基于字间位置，因此为能在中文分词中直接用来计算相邻字间连断概率，孙茂松等提出 t-测试差的概念．根据定义，对于维吾尔文单词串 xABy，相邻单词 A，B 之间的 t-测试差值计算公式为dts( A，B) = tx，B( A) － tA，y( B) ．当 dts( A，B) ＞ Tdts( Tdts为阈值) 时，AB 单词间位置更倾向于判断为连，反之判断为断． 与互信息不同，t-测试差反映的是相邻单词之间的动态结合能力，因为它综合考虑一个单词的上下文结合趋向，因此总的效果比互信息好，但也不能否认互信息的贡献．
       2． 3 基本统计量: 邻接对熵作为一个独立语言单元，多词关联模式在真实文本中有一定的流通度，能应用于多种不同的上下文环境，而不是某种特殊语境下的临时性组合． 因此，可根据相邻两个单词上下文语言环境的变化程度来衡量这个词对的独立性和完整性，从而判断它们词间是要连接还是要断开的．9 期 吐尔地·托合提 等: 维吾尔文无监督自动切分及无监督特征选择847如文献提出的新词识别方法中，计算一个词串的左邻接熵和右邻接熵，当左右邻接熵大于一个阈值时，认为该词串是一个独立语言单元，并将该词串提取为一个新词，否则将它舍去．本文将以上思路引入到文中研究，发现以左右邻接熵判断词间位置，就无法整体获取三词关联模式． 如，判断三词关联模式 ABC 中的 A 和 B 间位置时，词对 AB 的左邻接可能是变化多样的，但右邻接是确定不变的，也就是 C． 根据信息熵的定义，AB 的右邻接熵是0( 最小值) ，因此 AB 间的位置被错误地判断为断( B 和 C 间位置也是被错判为断) ． 针对以上情况，如果将问题改成计算邻接对熵( Entropy ofAdjacency) 及基于邻接对熵的词间位置连、断判断问题，那就适合文本的研究需求．定义1 对维吾尔文有序单词串xABy( x和y是任何一个维吾尔文单词) ，AB 在文本中每次出现的左邻接元素 x 和右邻接元素 y 构成一个邻接对 ＜x，y＞，那么 AB 所有邻接对组成邻接对集合 adg= { ＜ xi，yi＞ } ，m 是集合中所有邻接对个数，c 是集合邻接对种类数( 不重复邻接对个数) ，ni是每个邻接对 ＜ xi，yi＞ 的频次，则 A B 的邻接对集合的信息熵( 邻接对熵) 的计算式为ea( A，B) = －∑ci = 1nimlognim( )．由上式得，邻接对熵的最小理论值0( 当c =1时) ，而最大理论值为 logm( 当 c = m 时) ． 如果 ea( A，B) 取值越大，表明词串 AB 的语言环境变化多样，是不依赖于上下文的语言单元． 如果 ea( A，B) 取值越小，则表明 AB 的独立性不强，很可能是一种偶然性组合． 因此，当 ea( A，B) ＞ Tea( Tea为阈值) 时，AB 的单词间位置更倾向于判断为连，反之判断为断．本文发现，ea 总的切分准确率比 mi 和dts 稍低，大部分错误发生在应为断的词间位置上，但它对于新词词间位置体现出比 mi 和 dts 更准确的判断能力． 特别是，当 count( A) 和 count( B) 极大，而count( A，B) 极小的情况下，mi 和 dts 几乎都会做出错误判断，但 ea 与词频关系不大，它只考虑双词上下文语言环境的变化多样性，因此能做出正确的切分判决．
       2． 4 基于组合统计量 dme 的自动切分不管是互信息、t-测试差还是邻接对商，都是将词在语言环境中某一方面的信息特征作为计算依据，因此必然存在一定的局限性． 中文分词中成功的案例表明，可将基本统计量加以组合从而各取所长． 此外，本文分别用互信息、t- 测试差和邻接对熵进行切分实验，发现将它们结合互补的较大可行性． 在实验中，t -测试差的切分准确率最高，其次是互信息和邻接对熵，因此以 dts 为主，将 3 个基本统计量进行线性叠加，融合成一个新的统计量 dme，并完全根据 dme 来判断词间位置，从而提高切分准确率．以上基本统计量取值范围相差较大，因此线性迭加之前要进行归一化处理，即dts*( A，B) =dts( A，B) － μdtsσdts，mi*( A，B) =mi( A，B) － μmiσmi，ea*( A，B) =ea( A，B) － μeaσea，其中，μdts、μmi、μea分别是 dts、mi 及 ea 的均值，而σdts、σmi、σea分别是 dts、mi 及 ea 的均方差，这6 个值均由大规模语料中统计得到． 3 者的叠加值为dme( A，B) = dts*( A，B) + λmi*( A，B) + γea*( A，B) ，( 1)其中，λ 和 γ 的值经实验测定，发现 λ = 0． 35 ，γ= 0． 30 时的切分准确率最高． 且 dme 既能在 dts、mi和ea判断一致时保持判断不变，又能在各自判断不一致时，一定程度上进行互补．对待处理文本进行切分之前，同样先对其进行词干提取处理，然后切分算法计算待处理文本中各相邻单词( 词干) 之间的 dme 值，如 dme( A，B) ＞Tdme( Tdme= 0) ，则保留它们之间的关联性，否则以分隔符( 本文用" ") 将它们隔开，以 dme-TS 切分的 1 个例子Fig． 1 An example of dme-TS segmentation可看出，如用传统的切分方法iws-TS来切分，就把图 1 中的维吾尔文句子切分成语义不完整的 8 个特征词，但 dme-TS 的输出是 5 个特证词，且都是语义具体而独立的语言单元．
       3 无监督特征选择相关研究结果表明，移走 90% 左右的噪音特征和冗余特征时学习算法的性能和效果不会收到影响，甚至移走高达 98% 的特征时，学习算法性能仍会保持最佳． 说明，本文得到较优的原始特征集，但其中绝大部分特征是冗余的甚至是不相关的，冗余特征的存在会降低学习算法的效果，而不相关特征( 噪音特征) 的存在会损害学习算法的性能． 因此，不增加分析代价的前提下，从高维原始特征空间中尽量移走全部噪音特征及冗余特征，从而以数量极少但蕴含信息量最大的特征子集来构造更紧凑、泛化能力更强的文本模型是特征选择研究的追求目标．
      3． 1 基本假设假设特征集 U 由 n 个特征( f1，f2，…，fn) 来表示文本集D，P( ft) 是特征ft的概率，则ft在特征空间中独自提供的信息量( 初始不确定性) 可由以下信息熵度量:H( ft) =－∑ftP( ft) log P( ft) ．在已确定另一特征 fk取值之后，ft取值的不确定性会变小，也就是说 fk的出现会使 ft独自提供给学习算法的信息量变小，此时 ft取值的不确定性可由条件熵来度量:H( ftfk) =－∑fkP( fk)∑ftP( ftfk) log P( ftfk) ．当 ft与 fk完全独立时，ft的信息量不会因为 fk的出现而变少，此时H( ft) =H( ftfk) ; 如ft与fk关系密切，则 H( ftfk) 取值很小． 在此基础上，两个特征ft与 fk之间的互信息可定义为mi( ft，fk) = H( ft) － H( ft，fk) = mi( fk，ft) ．显然，互信息是可看作是特征 fk的取值被确定之后特征 ft不确定性的减少量，也就是二者共同含有的信息量，互信息越大，它们共同蕴含的信息量也越大． 从以上分析可知，特征选择的目的应是寻找这样一个特征子集Sd=( l1，l2，…，ld) ，Sd?U，1 ≤d≤n，即Sd中d个特征共含的信息量基本或全部覆盖原始特征集U中的信息量． 因此，特征选择算法应该选择那些与其它特征具有最大互信息的特征．
       3． 2 基于 UMRMR 评价的最优特征选择根据以上基本假设，本文特征选择过程经 d － 1次排序及选择操作完成，每次只选一个特征移入到Sd，d 是给定所需的特征个数． 第一步，算法从原始特征集U中选取一个平均互信息值最大的特征作为l1移入到 Sd中，即Umi( fi) =1n∑nj = 1mi( fi，fj) ，l1= arg max1≤i≤n{ Umi( fi) } ．第二个最优特征选择开始，算法就进入基于"最小冗余 -最大相关"( Minimum Redundancy andMaximum Relevancy，MRMR)［18］评价标准的特征排序及选择过程． MRMR 是有监督特征选择方法中着名的评价标准． 对于已选入 m － 1 个特征的特征子集Sm －1= ( l1，l2，…，lm －1) ，2 ＜ m ＜ d + 1，，选择第m 个特征 lm时，MRMR 的选择依据为lm=arg max1≤i≤n{mi( fi，c) －1m － 1∑lt∈Sm －1mi( fi，lt) fi∈ U}，( 2)其中，第一项是"最大相关"条件，取值越大使MRMR 更倾向选择和目标类别 C 具有最大相关的特征; 第二项是"最小冗余"条件，取值越大使 MRMR更倾向选择互斥的特征． 因此，通过式( 2) 取值最大的特征就是与目标类别 C 具有最大相关又是最小冗余的特征，即被选为第 m 个最优特征移入到 Sd中．然而，MRMR 是有监督特征选择方法中的评价标准，在无监督特征选择中无法用它来评价候选特征，但在思路的基础上，用信息论相关知识提出一种无监督特征选择中的评价标准 UMRMR 是完全可能的．本文提出的无监督特征选择中，为 Sm －1选择第m 个特征 lm的选择依据: 如 lm= fi，则相对于 U 中的其他特征，fi应该与 U 是最大程度的相关，同时与Sm －1是最小程度的冗余． 为此，本文定义 UMRMR 中的"相关度"和"冗余度"条件．定义2 对于一个候选特征fi，其相关度定义为Re l( fi，U) =1n∑nj = 1mi( fi，fj) ．选择算法寻找的最优特征子集 Sd是原始特征集 U的精华，因此 Sd包含的特征个数应是原始特征集 U中的很少一部分，但它应包含 U 中全部或绝大部分信息． 因此，从 U 中每次选取一个特征 fi并把它移入到 Sd的前提是: 跟 U 中其它特征相比，fi蕴含的信息量是最大的，也就是它与整个特征集的平均互信息是最大的．本文又从 Sd所需的信息角度考察候选特征，Sd期望一个新特征的选入为它带来最大信息，且这个信息应是目前 Sd中没有的"新"信息，这样 Sd包含的信息尽快与原始特征集 U 接近．定义 3 一个候选特征 fi，对于 Sd的冗余度定义为Re d( fi，Sd) =1m － 1∑m －1t = 1mi( fi，lt) lt∈ Sd．对于 Sd来说，如果候选特征 fi与 Sd的相关度越大，9 期 吐尔地·托合提 等: 维吾尔文无监督自动切分及无监督特征选择849表明 fi与 Sd内已有的特征共同包含的信息量较大，fi的到来不能为 Sd提供"新"的信息，因此 fi对Sd来说是冗余的．这样，综合考虑候选特征 fi与原始特征集的相关度及它与已选特征子集 Sd的冗余度，提出无监督特征选择中的"最小冗余-最大相关"特征评价标准( UMRMR) :UMRMR( fi) =1n∑nj = 1mi( fi，fj) －1m － 1∑m－1t = 1mi( fi，lt) ，因此，选择第m个最优特征lm时，先以UMRMR评价所有候选特征的重要度，再选取其中最大的，即lm= arg max1≤i≤n{ UMRMR( fi) } ．以类似方法逐步选择后续特征，直至给定期望个数的特征全部选完为止( 最大为 n － 1 个) ．
      4 实验与结果分析根据研究内容，本文实验包括3个部分: 1) 考察dme-TS 的切分准确性及开放环境中的有效性; 2) 观察两种切分方法 iws-TS 和 dme-TS 的切分结果对分类算法分类准确性的影响; 3) 评价无监督特征选择方法 UMRMR-UFS 的性能． 本文实验数据均由新疆大学智能信息处理重点实验室提供，包括: 1) 单词Bi-gram 训练用生语料库 URC，共含维吾尔文单词及标点 9 443 290 个，未经切分; 2) 封闭测试用熟语料库UCC1，共含维吾尔文单词及标点135 708 个，经人工切分; 3) 切分开放测试用熟语料库UCC2，共含维吾尔文单词及标点154 411 个，经人工切分; 4) 分类文本集 UCC3，共含 6 类( 01 经济，02 体育，03 政治，04教育，05法制，06健康) 3000篇文本( 每类500篇) ． 以上数据都经过词干复原处理．
      4． 1 无监督文本切分实验中，本文以生语料库 URC 得到维吾尔文单词( 词干) Bigram 模型，以 UCC1为对象考察用不同统计量的切分效率并调整阈值，以及确定式( 1) 中的 λ 值和 γ 值． 实验目的是验证组合统计量 dme 的有效性，及切分算法 dme-TS 在开放环境下的健壮性． 因此，本文分别在封闭测试集和开放测试集上进行切分实验，观察 dts、mi、ea 组合前和组合后词间位置正确判断情况．以分隔符" "替换成所有标点符号之后，封闭测试集 UCC1共含维吾尔文单词 120 948 个，需要判断的词间位置有 108 998 个; 开放测试集 UCC2共含维吾尔文单词 137 757 个，需判断的词间位置有 125 699 个． 切分实验结果汇总如表 1 所示．表 1 切分实验结果Table 1 Segmentation results测试方法 切分策略判断正确的词间位置数切分准确率 /%封闭测试dtsmieadme8517482024798199621178． 1475． 2673． 2388． 27开放测试dtsmieadme97881954469093611087777． 8775． 9372． 3488． 21从表 1 可看出，用组合统计量 dme 的切分准确率总是比用单个统计量高，更让人高兴的是算法在开放测试中的性能也没下降，这表明本文提出的组合统计量 dme及各类参数的确定是有效、正确的． 当然，与 100% 切分准确率是有一定的距离，但对于切分结果的原始特征集，通常情况下要扔掉 90% 左右的特征，与此相比，dme-TS 的 12% 左右的切错率是完全可以被接受的．
       4． 2 两种不同特征集及学习算法效果本实验分别用 iws-TS 和 dme-TS 对分类文本集UCC3进行切分，形成两个原始特征集 Uiws和 Udme．表 2 2 种切分结果的原始特征集Table 2 Original feature sets of 2 segmentation methods特征集 特征粒度 特征个数 降维率 /%Uiws单词 93692 -Udme单词或多词关联模式58436 37． 6从表2 可看出，因 dme-TS 能完整地切取文本中强关联的多词关联模式，而不把它们切分成多个单词，因此起到了初步降维作用，从更小的特征空间中搜索最优特征，这显然会降低特征选择算法的时空开销． 更重要的是，以 dme-TS 的切分结果表征文本时学习算法效率有明显提高，才能接受 dme-TS 的切分代价． 因此，选用性能最好的有监督特征选择方法IG 分别对 Udme和 Uiws进行特征选择，经过排序的特征序列中递增地选取 N 个( N 的增量为100) 特征组成一个特征子集，并将其作为朴素贝叶斯分类器的输入． 在评价分类器的性能时，本文将 5 次 5-fold 交叉验证运行结果的分类准确性的平均值作为最终的8 50模式识别与人工智能 26 卷分类准确性． 在两种特征集下不同 N 值的分类效果易看出，同一学习算法在同一数据集的两种特征集下的效果有明显区别． 对于 Uiws，选取前 4500 ～5500( 7． 7% ～9． 4% ) 个特征时，学习算法才达到最高准确率为 80． 34%，在 Udme上选取更少的特征就达到比 Uiws更高的分类准确率，即选取前 2000 ～2500( 3． 4% ～4． 3% ) 个 特 征 时 的 最 高 准 确为 89． 11%． 结果表明，因为 Uiws中的特征项是在语法结构上的独立语言单元，而 Udme中的特征项是在实际语言环境中蕴含具体而完整语义信息的独立语言单元，因此与更多语义抽象的单词相比，Udme中少量的特征就能为学习算法提供充足而有用的信息．
       4． 3 UMRMR-UFS 的性能一个优秀的特征选择算法，应能识别出原始特征集中最重要的特征，因此它找到的特征子集会有效提高学习算法的性能． 为验证UMRMR-UFS性能，本文以同样方法从UMRMR-UFS对于Udme的输出列表中递增地选取 N 个特征并组成一个特征子集，观察朴素贝叶斯分类器的分类效果． 同样，将 5 次5-fold 交叉验证运行结果的分类准确性平均值作为最终的分类准确性．图3给出分别从IG和UMRMR-UFS输出序列中递增的选取N个特征来表征文本时分类器的分类准确性的变化趋势． 易看出，从UMRMR-UFS生成的特征序列中选取相对于 IG 更少量特征时 ( 3． 3%～ 3． 8% ) ，分类器提早达到相当于 IG 的最高准确率88． 49% ，且分类器的分类准确性高于其在完全特征集上的准确性． 结果表明，UMRMR-UFS 确实将具有代表性和富含信息的重要特征放在特征序列前面．此外，随着特征个数的增加，分类准确性起初急速提高，到迏最高点后保持临时不变并开始下降． 这是由于越来越多的冗余或不相关的特征被包含进来，它们不能给学习算法提供新的信息甚至会误导学习算法．图 3 IG 和 UMRMR-UFS 特征选择的分类效果of IG andUMRMR-UFS实现UMRMR-UFS的时间复杂度主要取决于原始特征集 U 的规模，也就是 U 中任意两个特征间的互信息计算，时间复杂度为 O( n2) ． 因此，在大规模文本处理特征选择中，先用典型的快速方法( 如文档频数) 移除大量的噪音特征，再用 UMRMR-UFS获取最终一个良好的特征子集应是最好的选择．
       5 结 束 语本文提出的无词典文本切分方法 dme-TS，将词与词之间的静态结合能力、动态结合能力及词对上下文的独立性等多方面度量的综合值作为切分依据，因此较准确的切分出文本中的独立语言单元( 单词或多词关联模式) ． 因为 dme-TS 所需的所有统计信息完全是从大规模生语料中自动获取，无人工干预，因此算法在开放环境中体现出其有效性和健壮性． 将 dme-TS 作为文本预处理中的切分方法，在以下 2 方面明显提高原始特征集的质量: 1) 有效避免传统切分方法导致的大量碎片( 噪音) 特征出现，特征空间的维数得到有效控制，在一定程度上减轻后续特征选择算法的负荷． 2) 特证项蕴含较完整的语义信息，因此，少量特征就能为学习算法提供足够的信息． 在这种较优的原始特征集的基础上，本文提出的无监督特征选择方法 UMRMR-UFS 能将最优特征排在特征序列的首位，从而以更少的最优特征来生成更紧凑、更具有泛化能力的文本模型，因此学习算法也达到相当于有监督特征选择的最高性能．9 期 吐尔地·托合提 等: 维吾尔文无监督自动切分及无监督特征选择851本文的研究工作虽然在维吾尔文语言环境中进行且经过验证，但其思路和方法完全可引用到其它语言的文本处理中．
      参 考 文 献［1］Sun Maosong，Xiao Ming，Tsou B K． Chinese Word Segmentationwithout Using Dictionary Based on Unsupervised Learning Strategy．Chinese Journal of Computers， 2004， 27 ( 6 ) : 736 － 742 ( inChinese)( 孙茂松，肖 明，邹嘉彦． 基于无指导学习策略的无词表条件下的汉语自动分词． 计算机学报，2004，27( 6) : 736－742)［2］Wang Sili，Wang Bin． A Chinese Overlapping Ambiguity ResolutionMethod Based on Coupling Degree of Double Characters． Journal ofChinese Information Processing， 2007， 21 ( 5 ) : 14 － 17 ( inChinese)( 王思力，王 斌． 基于双字耦合度的中文分词交叉歧义处理方法． 中文信息学报，2007，21( 5) : 14－17)［3］Fei Hongxiao，Kang Songlin，Zhu Xiaojuan，et al． Chinese WordSegmentation Research Based on Statistic the Frequency of theWord． Computer Engineering and Applications，2005，30( 7) : 67－69 ( in Chinese)( 费洪晓，康松林，朱小娟，等． 基于词频统计的中文分词的研究．