面向变异短文本的快速聚类算法
黄永光，刘挺，车万翔，胡晓光
（哈尔滨工业大学信息检索实验室，哈尔滨  150001）
摘要：本文研究了变异短文本的聚类技术，提出了一种快速准确的聚类算法，它在原有的去重算法基础上，针对变异短文本这一特殊情况，采取了特定的特征串抽取方法，并融合了压缩编码的思想，加快了处理速度。实验表明，基于该算法的聚类系统对于大量的变异短文本有着很高的执行效率和准确率。
关键词：检索；特征串；聚类
Abnormal Short Texts Fast Clustering
Algorithm
Huang Yongguang,Liu Ting,Che Wanxiang,Hu Xiaoguang
（Information Retrieval Lab，Harbin Institute of Technology，Harbin 150001）
Abstract: This paper discusses the clustering technology about the abnormal short texts and proposes an efficient clustering algorithm based on the duplication information deletion algorithm. It concerns about the features of the abnormal short texts and takes some special methods such as extracting feature code and compressing code to solve this problem. Experiments show that the clustering system based on this algorithm can depose lots of abnormal short texts with high accuracy and high speed.
key words:  Retrieve; Feature string; Clustering
1引言
随着互联网和通讯产业的快速发展，各种形式的信息扑面而来。聊天室，即时通讯软件，短信的出现无时无刻不在影响着人们的日常生活。这些形式的信息都有一些共同特点：字数不多，大多数为100字以内，但是数量非常大。并且这些信息经过一些变化，表面看起来形式不同，但内容上却是一样的。我们称这些信息为变异短文本。由于这些信息，数量非常大，处理起来非常不方便，所以需要在进行其他分析之前，对它们先进行聚类分析。将主体内容一样，但形式上略有差别的短
作者简介：黄永光（1981-），男，硕士生；Email:hyg@ir.hit.edu
文本聚到一类。这样我们只需对同类中具有代表性的短文本进行分析即可，不仅可以节省用户很多精力，而且还可以提高分析效率。本文首先介绍了相关技术背景，然后重点地讲解了针对变异短文本的快速聚类算法，并给出了相关的算法分析和实验结果，最后得出了结论。
2 技术背景
2.1变异短文本的概念
变异短文本是指那些用少量词语表达一定语义关系的书写不规范的文字。拼音输入法的使用是造成此类现象的主要原因。这些变异短文本常会出现在各种聊天工具中，如QQ ，MSN 中。另外聊天室中的语言，手机短信中出现的语言也属于变异短文本。这些文字的一个共同特点是语句比较短，并且文字大多都不太规范。比如文字“好”，在聊天过程中常常会打成“hao ”。再比如由于平时不注意语言规范，使用的输入法是拼音输入法，人们常常会把各种同音字打错，弄混。如“想你”错打成了“向你”。另外，在短文本中，也会常常出现很多间隔符，并且根据个人习惯不同，使用不同的分隔符。虽说分隔符不同，却不影响正常的阅读。如“今天下雨，你带雨衣了吗？”，错打成“今天下雨你带雨衣了吗”，后一句虽然没有间隔符，但是仍然表达了同样的意思。
综上所述，我们的处理对象，不同于传统的自然语言处理的文本，而是针对现今在一些传媒中出现的语言不规范的短本文。本文也正是针对变异短文本提出了一套算法，可以对其进行大规模的快速聚类，能
把形式上不同，而内容上极其相似的短文本聚成一类。
2.2 普通聚类算法失效
正如上面提到的，我们是要针对变异短文本进行处理，那么我们也可以先尝试一下使用普通的聚类方法来解决这个问题。我们将常用的6763个简体汉字组成一个向量，然后将每个汉字在短文本里面出现的次数作为分量的值，将这个向量作为短文本的特征向量。通过计算相似度，比较它与聚类中心向量的相似度，来确定该短文本是否属于该类[1]。根据变异短文本的定义，内容极为相似的短文本才能算作一类，所以计算时，相似度非常高的短文本才能归为一类，换句话说，要求它们的向量夹角非常小，向量的模的大小相近。
但是，这种普通的聚类思想并不适合于这个问题。首先，聚类思想是通过一定的阈值，将某种特征相似的元素聚为一类，这通常适合于类别较少的情况，当类别非常大的时候，比较次数会增长得非常快，效率下降得也很快。它的时间复杂度为)(2
n  [2]。而这种短文本由于数量非常大，常常是千万级的，所以如果使用普通聚类算法，时间上是无法忍受的。另外聚类中阈值的确定也是很困难的事。字符串常量表示方法
采用普通聚类算法，不仅时间上消耗非常大，而且准确率也会受到很大的影响。因为我们面向的是变异
短文本，由于它的形式灵活，以及用法不规范，这就可能会导致将两个内容一样，形式上差别比较大的短文本无法聚到一类。比如：同样是说一个意思，却有多种的表现形式，如“明天有雨，记得带伞”错写成了“明天由于，记得带三”，或者也有可能写成“mingtian 有雨，记得带san ”，这些形式在我们平常聊天中常常会出现，虽然交流的双方都会理解其中的含义，但是如果采用普通的聚类算法，可能就不会把它们聚成一类了。
3 算法设计
3.1 算法的总体设计思想
根据以上的分析，我们认为，对于这种短文本的处理，主要有两个难点：第一，短文本中参杂了许多干扰信息。诸如：同音字的干扰，拼音的干扰，特殊符号的干扰。第二，在大规模的数据量下，如何进行快速的聚类，正如前面所提到的，普通的聚类算法已经不再适合。根据这两个难点和需求，我们提出来一种聚类算法。它是将压缩编码的思想融合到去重的思想中，然后根据短文本的特征，又提出了一种针对短文本的特征选择的方法。该算法首先是将不规范的短文本转化为规范的短文本，然后从规范的短本文中抽取出特征串，用这些特征串来表征这些短文本。接着通过检索的方式，将每个类的特征串逐一检索起来，构成一个检索系统，通过查特征串的方式，来确定该短文本属于哪一个类。最终当所有的短
文本处理完毕时，也就得到了聚类结果[3]。
3.2 变异短文本的规范化
变异短文本的规范化，是指将变异短文本进行转化，去掉所有可能对聚类结果产生影响的干扰信息。使得产生的结果可以直接对其进行聚类分析。
具体的说来：第一步，应该清除所有的干扰字符，这里干扰字符包括诸如标点、特殊字符等，比如*&^*，因为这些字符对于短文本来说没有什么实际意义，而且还会造成对聚类的干扰。所以第一步就应该将它们都去掉。例如：“我--------好想;)回家!!!”，将所有的非法字符去掉，得到“我好想回家”
然后，由于变异短文本的特点，经常会出现一些同音异型的字，而且还可能会有用拼音来代替汉字的情况，所以针对这两种情况，我们采用的方法就是，将所有的汉字都转化为拼音串，并且将能够构成拼音的英语字符串也转化为拼音。这样就解决了同音字问题和拼音替换的问题。例如: “爱你一晚年”“爱你一万年”“爱你yi万年”这三个短文本都可以转化为“ainiyiwannian”
第三步，在上一步的基础上，去掉那些转换不了的英语字符串，因为这些英语字母串通常没有什么含义，对于聚类来说意义不大，而且可能会产生误差。比如：“我喜欢吃apple”由于apple无法构成拼音，所以将’apple’去掉，转化之后得到“woxihuanchi”
第四步，由于数字对于短文本的实际表意来说意义并不大，比如“1999年12月10日”和“2003年12月10日”，还比如“请拨打1375665****”和“请拨打1323234****”。这样的短文本虽然在内容上有所不同，但是在大体含意上却是相同的，所以在处理的时候也要把这样的数字全部去掉。
经过这一系列的处理后，基本大部分的干扰信息都可以被去除掉。
3.3 用检索的思想解决聚类问题
3.3.1 特征串选择
当我们进行完短文本的预处理之后，我们将要对每个短文本抽取它的特征串，以期将特征串投入到检索系统中。特征串是指能够代表该短文本特征的一组字符。
对一个文本提取特征串有很多方法，比如：可以采用在一篇文本中抽取一个最长的句子作为该文本的特征串，也可以在中文标点符号左右各取若干字符作为一篇文本的特征串。这些方法对于文
本较长或是网页形式的文本效果很好，通过这种方法抽取的这些特征串可以很好的代表该文本。
但是，由于本文针对的是短本文进行的处理，以上的方法都不很适合。因为上面的方法的提出主要是针对于长文本，而当文本比较小的时候，可能没有一个句子可供选择，或者可选择的特征非常少，这样当有一两个字的差别时，就会导致很大的误差。
所以，我们针对短文本，提出了一个新的特征量抽取方法。从上个步骤中，我们得到了一系列的拼音串，将每四个拼音作为一个特征，然后选择出所有的连续组合，也就是选择1到4个拼音组成一个特征，2到5个拼音组成为一个特征，这样依次类推。如果一个短文本少于4个拼音串，那么就将所有的拼音串作为一个特征。把得到的所有特征，组成一个特征组，来表征这个短文本。举个例子：一个短文本如果有10个拼音组成，那么将会抽取出7个特征，它们共同的表征了该短文本。
这样抽取特征串的好处是，当两条内容相似的短文本，如果仅有一些字的差别，无论差别的位置在哪，它们大部分的特征串都是相同的，所以肯定不会影响聚类结果。
3.3.2压缩编码
经过上面处理，得到了每个短文本的所有特征串。如果直接使用该特征串进行查和检索，速度会慢很多。这里我们采用了一种压缩编码的方法，也就是将一个拼音转换成一个数字，这里拼音是指没有音标区分的。那么汉语中总共有403种有效拼音，这也就相当于有403类。如果把每一类都进行编号，那么总共需要403个类。因为403超过了256，所以每个编号都需要9个机器字，这样为了表示一个类号，需要
两个字节编码，那么在速度上肯定要比使用一个字节慢的多，所以我们的想法是将两个字节的编码转化为一个字节的编码[4]。
具体采用的方法就是：将大于256的数减去256，这样所有的类别编码都小于了256，那么所有的编码都可以表示在一个字节内了。
比如“哈”字归为168类，因为168小于256，所以它的编码仍为168。
比如“滨”字归为364类，因为364大于256，所以它的编码为364-256=108
但是这样势必会产生冲突，我们将会到后面进行区分，以抵消掉这样做产生的误差。
经过这样的变化，每个拼音都转化为占一个１个机器字节的数。而每个特征串都有四个拼音，这样经过转化，每个特征串都占了4个字节。我们知道，一个int整型数是占4个字节的，而我们抽取的特征串也是占4个字节的，所以从效率上考虑，我们将一个特征串转化为一个int整型的数。使用这个整数作为键值去查，这样速度要远比用拼音串做键值快。
我们通过实验证明，如果采用拼音串作为键值进行查，10万条短文本需要处理200秒，而如果采用上面的方法，在同样的机器配置上，10万短文本只需要处理20秒。可见我们采用压缩编码的方法，将速度提高了10倍。
3.3.3建立HASH表进行查
我们把拼音串压缩编码，目的就是为了能够快速的查特征串在那些类别中出现过。我们为了更快的查，使用了Hash表的结构。具体的过程是：使用一个整数作为除数，并开辟一个这么大的空间，将所有的特征串编码除以这个数，所得到的余数作为桶的位置。在每个桶中保存一个二叉树的指针，使用这个二叉树的目的就是当一个桶中的元素中产生冲突的时候，用二叉树进行存储，这样就解决了冲突[5]。
具体来说：首先把一个短文本抽取出多个特征串，用这些特征串来表征这个短文本。然后将每个特征串变成一个数字。投入到由各类别代表短文本的特征串所组成的检索系统中。如果一个特征串在检索系统中匹配上一类短文本，那么就先记下来这个类别号。当所有的特征串都匹配完毕之后，
选出匹配次数中最大的那个类别，然后再与已经设定好的阈值比较，如果超过这个阈值，那么则说明这个短文本和该类别代表短文本很相似，可以断定它属于这个类别。如果没有超过这个阈值，则说明这条短文本所代表的类别没有出现过，那么便将这个短文本的所有特征量都加入到现有的检索系统中，单独作为一个新类来使用。并将这个短文本作为该类的代表短文本。
在判断一个特征串是否在索引库中出现时，首先要将这个特征串转化为一个整数，然后将这个整数利用
HASH 表进行查，如果没有查到，说明这个特征串没有在索引库中出现，如果查到，还要特别查看一下，该特征串所表示的拼音串是否是也被索引过。如果此时没有查到，则说明这个特征串真的没有在索引库中出现，如果查到了，则说明该特征串在索引库中出现过。之所以要进行如此的判断，是因为我们在压缩编码的时候，产生了冲突，所以在这里就解决了这个冲突。 4 算法分析
4.1 算法的正确性分析
在进行聚类的过程中，多次提到了阈值的概念。阈值的选择对聚类的准确性有很大的影响。我们是将一个短文本每4个字抽取出来作为一个特征串，这样如果一个文本的所有特征串在某一类中出现的次数最多，并且出现次数超过了一定的阈值，则断定该短文本属于此类。经过后面的实验表明，我们选择这个阈值为6个。也就是说只要有6个特征串与一个类别中的特征串重复，那么就能判断出这个短文本属于这个类别。如果一个类别的特征串少于6个，那么只需把阈值调整为特征串的数量减1即可。我们之所以做出这样的判断，是根据短文本的这种特殊形式，因为属于同一类别的短文本相差不是很大，那么他们大部分应该都是相同的，这样我们就可以根据形式上的相似，去判断短文本的类别了。
对于阈值的选择，我们可以做出这样的分析。如果阈值比较大，那么准确率就非常高，但是有可能没有把所有的短文本聚类到一起。如果阈值比较小，那么准确率就会很低。我们如果选择6作为阈值，假设这些特征串是连续出现的，那么至少有9个字音标是完全相同的。如果这些特征量都没有重叠，那么至
多有24个字的音标是完全相同的。我们拿概率最大的情况进行分析，如果是9个音标完全相同，那么它的近似概率为：249105.3403
1-⨯≈，其中403为有效拼音的个数。这也表明了9个音标完全相同的概率是很小的，那么如果有两个短文本至少9个音标完全相同，就可以判断出它们为一类了。这个概率当然也和文本的长度有关，文本的长度越长，出现完全相同的概率越大，那么聚类的准确率越低，文本的长度越小，出现完全相同的概率越小，那么聚类的准确率越高。由于我们处理的是短文本，所以这种方法是适用的。
4.2 算法的效率分析
该算法的效率与输入短文本的数量以及索引库的大小有关。索引库越大，短文本的数量越大，执行时间越长。在将变异短文本规范化的过程中，每个短文本的处理时间只与该条短文本的长度有关，这里设短文本的平均长度为L ，对于n 条短文本来说，这个步骤的时间复杂度为)(L n O ⨯。在进行特征抽取和压缩编码的过程中，处理时间也只和该条短文本长度有关，所以这个步骤的时间复杂度也为)(L n O ⨯。实际上，对于每一个短文本，可以抽取出L-3个特征串，然后将它们逐一的投

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。