蚂蚁树在文档聚簇中的应用研究

向 军，陈志华，郑 钤

（湖北民族学院信息工程学院，湖北 恩施 445000）

蚂蚁树在文档聚簇中的应用研究

向 军，陈志华，郑 钤

（湖北民族学院信息工程学院，湖北 恩施 445000）

蚂蚁的自我聚集的行为可以形成蚂蚁聚簇，根据此行为提出一种基于蚂蚁树的文本文件的聚簇算法.算法中将对象属性作为为关键词，提取文本文件关键词组成一个关键词集合，一个集合代表一个对象（蚂蚁）.算法将计算关键词的相对频率和对象之间的相似度，然后比较对象相似度阈值和相异度阈值，最终完成文本文件对象的聚簇.

蚂蚁树；相对频率；相似度；聚簇

随着信息的爆炸性增长，信息文档将面临着组织和搜索困难的境地.虽然信息检索技术能够帮助组织和检索信息，但是系统同时得负责新的信息资源的录入，索引和编目，这个过程将是繁琐和耗时的.数据聚类方法刚好可以应用其自组织性对文件进行聚类.蚁群算法衍生出来的聚类算法，应用前景很广泛，文献［1］提出一种多信息素动态更新的蚁群算法MPDACO，可以适应服务组合优化过程中发生的服务无效以及服务中QoS变化等情况.文献［2］针对旅行售货员问题、多智能体的编队控制问题、车辆路由问题以及智能体路径规划问题，分别提出改进的蚁群算法进行求解，文献［3］针对传统量子蚁群算法在求解TSP时容易陷入局部最优以及收敛速度较慢，提出了一种求解旅行商问题的改进型量子蚁群算法（IQACA）.文献［4－5］对PDF文件的聚类进行研究，首先将PDF文档转换成文本文档，然后提取关键字组成集合，最后利用蚂蚁堆形成原理实现文档的聚类.这种方法收敛性比较差，通过逐渐减小拾起参数的值可以达到聚簇的收敛，但要达到蚂蚁聚簇的效果迭代次数比较大.本文提出基于蚂蚁树的聚簇方法对文本文件进行聚簇，蚂蚁通过相似度的比较在蚂蚁树上找到自己相应的位置，在迭代过程中没有找到位置的蚂蚁更新自己的相似度和相异度阈值继续进行迭代，整个过程收敛性较好.

1 基于蚂蚁树的文档聚簇原理及蚂蚁树的构造

蚂蚁通过自我聚集行为构建一个树状结构，称为蚂蚁树［6］.利用蚂蚁树进行的文档聚类是将文档视为具有不同属性的蚂蚁，根据蚂蚁表示的文档之间的相似性和树的局部结构，可以对文档进行归档聚簇，其结果直接以树状结构组织.蚂蚁树构造的基本原理是：用蚂蚁表示文档并代表该树的节点，初始时蚂蚁放在一个称为支点的固定点上，这个点相当于树根.蚂蚁在这棵树上或已经固定在树上的蚂蚁上移动，来寻找适合自己的位置［7］.为避免陷入局部最优，定义规则：

1）蚂蚁从根节点开始移动，直到找到自己的位置；

2）蚂蚁能到达并能粘在蚂蚁树的任何地方；

3）为了找到相应的位置，蚂蚁保持和更新自己的相似度和相异度阈值.

4）蚂蚁只有一个父节点，最多只有τ孩子节点.

每一只蚂蚁从树根开始检验与已经连接到根的蚂蚁的相似性［8］.刚开始树根没有孩子节点，则将蚂蚁连到树根.如果已经有一些蚂蚁连接到树根了，然后当前的蚂蚁找到连接的与它最相似的蚂蚁.遵循以下的规则用来定义相似和相异的蚂蚁：

1）如果ξ（i，j）＞βsim（i），那么蚂蚁i与蚂蚁j相似．

2）如果 ξ（i，j）＜βdissim（i），那么蚂蚁i与蚂蚁j相异．

3）如果 ξ（i，j）≥βdissim（i）且 ξ（i，j）≤βsim（i），那么蚂蚁i既不与蚂蚁j相似也不相异，需要进一步处理．

在以上的规则中，i代表当前的蚂蚁，j代表连接在树根与之最相似的蚂蚁．ξ（i，j）代表蚂蚁j与蚂蚁i的相似度，它的计算由（4）式给出，βsim（i）代表蚂蚁i的相似度阈值，βdissim（i）代表蚂蚁i的相异度阈值，相似度和相异度阈值初始时分别为ρ／2和0．如果蚂蚁i最终与蚂蚁j相异，则i将连接到树根上．如果树根的孩子节点数已经达到临界值，则跳过蚂蚁i继续执行．如果蚂蚁i最终与蚂蚁j相似，则蚂蚁i向蚂蚁j方向移动．在下一次迭代中，蚂蚁i检验与孩子节点j的相似度，重复以上步骤直到找到最终的合适位置．如果i最终与所有的当前位置的孩子节点相异，那么它朝着与自己最相似的节点移动．第三阶段，如果i与j既不相似也不相异也就是满足规则3），则用式（1）和式（2）来更新阀值．当i更新阈值的时候，其他的蚂蚁可以继续构建蚂蚁树．直到所有的蚂蚁固定到蚂蚁树上，迭代过程结束．最终树根的每一个孩子节点都有蚂蚁聚集在一起，形成一个分区聚簇．

2 阈值的更新规则和相似度的测算

每一只蚂蚁维持着相似度和相异度阈值.在蚂蚁树构建中，蚂蚁可能不能连接到树，这个时候就得更新阈值允许蚂蚁更加灵活，并在下一次的迭代中增加被连接的可能性．他们的更新规则如下：

i代表阈值将要更新的蚂蚁，βsim（i）和βdissim（i）的值分别初始化为ρ／2和0，ρ就是相似度取值的最大值．

为了聚簇文本文件，需要把它们转换成关键词的集合．每个集合相当于一个蚂蚁对象．计算关键词在文件中的出现的相对频率，fj（w）代表w在文件中出现的频率，Fj（w）代表关键词在文件中出现的相对频率，等式如下：

注意：0＜Fj（w）＜1并且∑vFj（w）．这个公式的目的不是考虑文件中关键词的数目，而是测算在同一文件中一个关键词比较其关键词的相对重要性．

文本文件相似度的测量是基于关键词相对频率的比较．每只蚂蚁对应一个文档的关键字集合，检测与连接到树根的节点的相似度．基于相似度的比较和更新，蚂蚁可以在蚂蚁树上找到相应的位置．相似度的测算如下：

接着每一个文件转换成一个对象，该对象具有L个属性（每个属性代表一个关键词），表示如下：O＝｛X1，X2，…，Xl｝，用x1x2xl代表提取的相关关键词的相对频率．表1表示每个文件关键字相对频率，具有代表性．

3 相似度最大值ρ的取值规则

表1 代表文件的对象Tab.1 Objects of files

ρ的取值很重要，找到一个合适的ρ值不是很容易．如果ρ太小，由于大多数蚂蚁会与连接在树根的蚂蚁相异从而连接到树根下，这样树根的孩子节点数将很快会达到临界值（将这个值设为τ）并且树根的孩子节点的聚簇也会很小，在第二轮迭代之前，没有连接的蚂蚁将会有不少，它们中一部分是由于树根的孩子节点数达到临界值而无法连接到树根下，另一部分是与树根的孩子节点既不够相似也不够相异．在下一轮迭代过程中，ρ的更新规则如下：

其中：λ表示没有连接的蚂蚁数目，α是一个常量，τ是树根允许的孩子节点数的临界值．然而，另外一个情况可能出现，那就是由于ρ较大，导致实际树根的孩子节点数目小于树根允许的孩子节点数的临界值，这时ρ可以按照下面的规则减小：

其中n表示实际树根的孩子节点数目．等式（5）和式（6）一起在迭代中调整ρ的值使其值达到比较合适的水平．

4 算法实现

上述用来解决文件归类的蚁群聚簇算法的伪代码形式如下：

5 结语

蚂蚁算法衍生出来的聚类算法应用前景很广泛.利用蚁群聚族算法进行文档聚类，能够快速地将不同类型的文档进行聚类.同时由于算法内部阀值动态更新，收敛性强，聚类效果明显.文献［9］将改进蚁群算法应用到车间调度中，文献［10］研究大规模软件项目管理中PERT网络中结构蚁群算法优化问题.基于蚂蚁自我聚集行为的聚类算法能够很好的应用在文档的聚类上面，可以将文档文件根据关键字进行聚类，那么在同一类的文本之间他们会有很大的相似度，这样可以对文件进行归档处理，还就可以对论文进行进一步的查重的操作，下一步将是利用蚂蚁聚类算法并在实验中进行相应的改进，应用到论文的归档和查重的实践中.

［1］夏亚梅，程渤，陈俊亮，等.基于改进蚁群算法的服务组合优化［J］.计算机学报，2012，35（2）：270－281.

［2］王沛栋.改进蚁群算法及在路径规划问题的应用研究［D］.青岛：中国海洋大学，2012.

［3］贾瑞玉，李亚龙，管玉勇.求解旅行商问题的混合量子蚁群算法［J］.计算机工程与应用，2013（22）：36－39.

［4］Vizine A L，De Castro L N，Gudwin R R.Text Document Classinfcation Using Swarm Intelligence［C］／／In Proceedings of 2005 IEEE International Conference on Integration of Knowledge Intensive Multi－Agent Systems2005：134－139.

［5］Channa A H，Rajpoot N M，Rajpoot K M.Texture Segmentation Using Ant Tree Clustering［C］／／Engineering of Intelligence Systems，2006 IEEE In⁃ternational Conference on IEEE，2006：1－6.

［6］张建华，江贺，张宪超.蚁群聚类算法综述［J］.计算机工程与应用，2006，42（16）：171－174.

［7］李长进.基于蚁群算法的混合聚类算法研究［D］.青岛：中国石油大学，2010.

［8］苏艳，吕北生，廖文和，等.基于功能蚁树的定制客户动态聚类［J］.机械科学与技术，2008，27（5）：607－613.

［9］张利平，吴正佳，王魁，等.改进蚁群算法在车间作业调度中的应用研究［J］.三峡大学学报：自然科学版，2009，31（2）：75－78.

［10］崔梦天，张荣虎，程国忠.大规模软件项目管理系统中PERT网络的优化问题研究［J］.西南民族大学学报：自然科学版，2012，38（4）：638－641.

责任编辑：时 凌

The Application Research of Ant Tree Clustering in Documents

XIANG Jun，CHEN Zhihua，ZHENG Qian
（School of Information Engneering，Hubei University for Nationalities，Enshi 445000，China）

The ants′self－aggregation behavior can form ants clustering.According to this we proposed clustering algorithm for text files.In the algorithm object attributes are the keywords，extracting keywords from text files and consisting of a set of keywords collection，a collection represents an object（ant）.The algorithm will calculate the relative frequency of keywords and the similarity between objects，compare with the dissimilarity threshold and the similarity threshold and complete the clustering of text file objects.

ant tree，relative frequency，similarity，cluster

TP391.9

A

1008－8423（2015）03－0297－03

10.13501／j.cnki.42－1569／n.2015.09.018

2015－06－16.

国家自然科学基金项目（61362012）；文化部科技提升计划项目（201307）；湖北省自然科学基金项目（2009CDB069）.

向军（1978－），男，博士，副教授，主要从事数据库安全、实时数据库系统的研究.