基于Web挖掘的层次凝聚类算法研究

杨金花

（西安铁路职业技术学 陕西 西安 710014）

随着网络资源越来越丰富，它容纳了海量的各种类型的原始数据，激增的数据背后隐藏着许多重要的信息，人们越来越多地关注如何从海量数据中提取有价值的信息。数据挖掘（Data Mining）是从大型数据库或数据仓库中提取人们感兴趣的、隐含的、尚未被认识到的有用知识。由于Web本身的特性，使得Web上的信息查找比传统的信息查找表现出更大的挑战性。解决从Web上查找信息的一个途径，就是将传统的数据挖掘技术和Web结合起来，进行Web数据挖掘[1]。

1 Web数据挖掘的特点

数据挖掘是通过对大量数据的分析，寻找每个数据规律的技术，它挖掘的是数据库中有模型的数据，更注重的是数据的精确性。Web数据挖掘不同于数据挖掘，它是指利用数据挖掘技术在Web数据中发现潜在的、有用的模式或信息，它更注重数据的模糊性，需要挖掘出来的是同一类的信息。传统的数据库都有一定的数据模型，或以此模型来具体描述。Web上的数据与传统的数据库中的数据不同[2]。Web是由文本，多媒体元素、超链接等内容组成。Web上的数据非常复杂，没有特定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性，从而是一种非完全结构化的数据。半结构化是形成了Web文本挖掘的特色。

Web上的大量数据是非结构化的、层次化的[3]，而其中80%以上的信息都是以文本的形式存在的、蕴含着巨大潜在价值的知识。人们迫切需要能够从Web上快速、有效地发现这些有价值的知识。正是这些问题推动了Web文本挖掘技术的产生和发展。

2Web文本挖掘

Web文本挖掘是从Web文本和Web活动中发现、抽取用户感兴趣的、潜在的、有用模式和隐藏的信息的过程。Web文本挖掘为Web用户深入使用Web资源开辟了新的渠道。Web文档中的标记给文档提供了额外的信息。借此可以提高Web文本挖掘的性能。Web文本挖掘可以使Web用户较准确地找到所需要的资料，缩短搜索时间，提高Web文档利用价值等。

3 传统的层次凝聚算法

目前，在Web文本挖掘上常用的方法大致可分为层次凝聚法[4]和平面划分法2种类型。文中主要研究层次凝聚类法。

传统的层次凝聚类算法思想是：对于给定的文档集合D=｛d1，…，di，…，dn｝，层次聚类的过程如下：

1）将D中的每一文档di作为一个聚类中心ci=｛di｝，形成D 的一个聚类集合 C=｛c1，…，ci，…，cn｝；

2）计算 C 中的每个聚类对（ci，cj）之间的相似度 sim（ci， cj），

3）选取具有最大相似度的 2 个聚类（ci，cj）|max sim（ci，cj），将合并成一个新的聚类ck=ci∪cj，同时合并ci和cj的特征矢量，从而要构成了 D的一个新的聚类集合 C=｛c1，…，ck，…，cn-1｝；

4）重复上述步骤，根据所要产生聚类的数目，得到最终聚类结果。

用伪语言来表述

传统的层次凝聚法[5]，每次需要计算两两类之间的相似度。假设有n个类，需要计算2个类之间的相似度，获得n！/（2×（n-1）！）个相似度，接着比较这些相似度大小，将最大相似度的两个类合并，计算合并后类的值，同时将删除合并的一个类，类的个数变为n-1，第1次的聚类完成。接下来在n-1个类中再计算两两类的相似度， 需要计算 （n-1）！/（2×（n-3）！次， 获得（n-1）！）/（2×（n-3）！个相似度，接着比较这些相似度，将相似度较大的两个类合并，删除一个合并类，类的个数变为n-2，第2次的聚类完成。按照前面所述如此执行下去，直到满足条件—聚类的个数等于给定的个数为止。传统的层次凝聚法，实现的是最大相似度的两个类合并，虽然能够比较精确地刻画样本点之间一些细微差别，但运算速度缓慢、时间复杂性较高，占用存储空间大，不能承担较大数据规模的样本。由于Web文本的挖掘，需要挖掘的是某一方面的信息，也就是挖掘的是某个类。更进一步指出，就是Web文本的挖掘需要的是模糊挖掘，只要包含关键字就可以了。假设，在低层循环中，我们最初按照给定的相似度合并类，此时的相似度值比较小，进行粗略的合并。到高层循环时，使相似度为动态变化的，此时相似值逐渐变大，进行的是更精细的合并。如果两两类的相似度大于或等于给定的相似度就合并这两个类，这样就可以实现一次合并若干个类，从而提高合并速度，减小计算时所占有的存储空间。

4 改进的层次凝聚算法

根据日常知识可以知道，对于Web数据挖掘，就是要求将某一类的文档内容挖掘出来，对于挖掘出来的内容完全一样的文档，是没有实际意义的。在实际Web数据挖掘中，如果相似度过大，挖掘出来的类就少，如果相似度过小，挖掘出来的类就多。所以需要设置一个合理的相似度，我们就可以挖掘出来若干个类。

目前，对于基于相似度的聚类算法的研究也不少，大多数是基于EM（Expectation-Maximization）算法，这种算法是一种含参数的潜在的概率模型，该模型描述了一个对象物体归属于某个聚类的可能性，但是这些聚类算法在时间和空间上花费太大了。文中提出一个相似度函数sim，且0≤sim≤1[6]。该算法与其他的一些聚类算法相似。算法开始精选出初始的簇，并对簇进行循环步骤以提高聚类效果。这种算法事先定义好了相似度值，减少了迭代次数，提高了运算速度，减少了占有的空间。

4.1 改进后算法

由于考虑Web数据挖掘是在海量级的数据中进行的，要求挖掘的是类数据。在最初的合并中，可以将相似度设计为sim，而在较高层次循环时的聚类算法改为一种可变的相似度的层次凝聚类算法，这样做，可以加快合并的速度，而且能挖掘出大量的同一类数据。设计公式 sim=sim+a（minsim+maxsim）。

基本思想如下：每一个对象仍单独成为一类，按给定的相似度合并。重复此操作，待循环进行到指定的次数后，重新计算相似度sim=sim+a（minsim+maxsim），进行下一层次的合并，重复以上步骤，直至满足结束条件。

假设给定包含 n 个对象的数据集合 D=｛d1，…，di，…，dn｝

4.2 算法分析

在传统的层次凝聚类法中，将n个对象最终合并为一个类中需要迭代n次，时间复杂性为O（n2），在改进的算法中，假定平均每次合并t个对象，则构迭代次数为n/t，其时间复杂性为 O（n2/t），当 t>1 时，O（n2/t）<

4.3 参数分析

在改进的算法中，最大相似度sim的选取直接影响到聚类结果的好坏。相似度值sim过大，就会出现所产生的聚类中的数据过少，有可能将有用信息丢掉；相似度值sim过小，就会出现所产生的聚类中的数据过多，同时产生了有可能是无关的信息。同时又存在相似度值越小，聚类的速度则越慢。从理论上来说要求0≤sim≤1，因此，试给出一个计算sim公式：sim=sim+a （minsim+maxsim），maxsim 为 最大相似 度 ，minsim为最小相似度，其中a为比例系数，其取值范围在0～0.1之间，sim为上次聚类的相似值。有关a的计算公式，还有待于更进一步的研究。

4.4 改进后的算法验证

对3组样本集合D1，D2，D3分别使用传统的层次凝聚算法和改进后的层次凝聚算法进行聚类，其结果比较如表1所示。

实验结果证明改进的层次凝聚类算法与传统的层次凝聚类算法的结果是基本相同的，而改进的层次凝聚类算法的速度却远远高于传统的算法，这表明改进的算法是可行而且高效的。

表1 传统的层次凝聚类算法与改进的层次凝聚类算法各项指标对照表Tab.1 Traditional agglomerative hierarchical clustering algorithm and the improved hierarchical agglomerative algorithms each index table

5 结束语

由于Web数据挖掘是从海量级数据进行挖掘的，它完成的是从大量的数据中挖掘用户感兴趣的信息类，使用传统的层次凝聚类算法，实现起来存在运算速度慢，占用的存储空间大等问题。为了提高挖掘的速度，减少计算时所占用的空间，本文提出了改进后的层次凝聚类算法，并对相似度值的取法进行了探索，给出了动态改变相似度值参考公式。但该算法仍有许多不足之处，需进一步完善改进，有关参数a的取值以及相似度的初始值、循环多少次后相似值采用公式来计算等问题，也有待于进一步的研究，希望找出更合适的取值。

[1]曹聪聪，康耀红.Web数据挖掘研究[J].现代电子技术，2007（4）：92-97.CAO Cong-cong，KANG Yao-hong.Research on Web data mining[J].Modern Electronic Technique，2007（4）：92-97.

[2]巩固，张虹.Web数据挖掘分析[J].电脑知识与技术，2006（6）：18-19.GONG Gu，ZHANG Hong.AnalysisofWebMining[J].Computer Knowledge and Technology，2006（6）：18-19.

[3]陈晓红，秦杨.基于Web数据挖掘高效关联规则研究[J].计算机工程与科学，2005，27（11）：48-51.CHEN Xiao-hong，QIN Yang.Research on the effective association rules for Web-based data mining[J].Computer Engineering&Science，2005，27（11）：48-51.

[4]郝洪星，朱玉全，陈耿，等.基于划分和层次的混合聚类算法[J].计算机应用研究，2011，1（28）：51-53.HAO Hong-xing，ZHU Yu-quan，CHEN Geng，et al.Hybrid dynamin clustering algorithm based on partition and hierarchical clustering[J]Application Research of Computers，2011， 1（28）：51-53.

[5]魏桂英，郑玄轩.层次聚类方法的CURE算法研究[J].科技和产业，2005，5（11）：22-24.WEI Gui-ying，ZHEN Xuan-xuan.Hierarchical clustering method CURE algorithm[J].Science Technology and Industry，2005，5（11）：22-24.

[6]姜亚莉，关泽群.用于Web文档聚类的基于相似度的软聚类算法[J].计算机工程，2006（2）：202-207.JIANG Ya-li，GUAN Ze-qun.A similarity-based Soft clustering algorithm for Web documents[J].Computer Engineering，2006（2）：202-207.

[7]刘兴波.凝聚型层次聚类算法的研究 [J].科技信息，2008（11）：202.LIU Xing-bo.Condensed type hierarchical clustering algorithm[J].Science and Technology Information，2008（11）：202.