基于关联规则的web文档聚类算法a

《基于关联规则的web文档聚类算法a》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1000-9825/2002/13(03)0417-07©2002JournalofSoftware软件学报Vol.13,No.3基于关联规则的Web文档聚类算法Ã宋擒豹,沈钧毅(西安交通大学计算机科学与技术系,陕西西安710049)E-mail:qbsong@mail.xjtu.edu.cn;jyshen@mail.xjtu.edu.cnhttp://www.xjtu.edu.cn摘要:Web文档聚类可以有效地压缩搜索空间,加快检索速度,提高查询精度.提出了一种Web文档的聚类算法.该算法首先采用向量空间模型VSM(vectorspacemodel)表示主题,根据主题表示文档;再以文档

2、为事务,以主题为事务项,将文档和主题间的关系看作事务的形式,采用关联规则挖掘算法发现主题频集,相应的文档集即为初步文档类;然后依据类间距离和类内连接强度阈值合并、拆分类,最终实现文档聚类.实验结果表明,该算法是有效的,能处理文档类间固有的重叠情况,具有一定的实用价值.关键词:文档聚类;关联规则;Web挖掘;WWW中图法分类号:TP311文献标识码:A随着WWW的飞速发展,Internet上的资源和服务均呈现出爆炸性增长的趋势.为了帮助人们有效地使用这些资源和服务,陆续有一些功能强大的搜索引擎问世了.这些搜索引擎在给人们带来很大便利的同时也暴露出搜索结果不能很好地满足用户需求的问题.Web

3、文档聚类技术可以缩减搜索空间,加快检索速度,提高查询精度,[1~6]因而受到了人们的广泛关注.[5,6]Web文档聚类主要有基于概率和基于距离的两类方法.基于概率的方法以贝叶斯概率为理论基础,用概率的分布方式描述聚类结果,可以处理类间相互重叠的情况;缺点是当特征空间维数较高或特征值间呈现出较[4]强的相关性时,聚类精度和效率均不能令人满意.基于距离的方法,如K-均值和最近邻等,都以传统的特征向量表示文档,再将文档看作是向量空间中的一个点,通过计算点之间的距离进行聚类,比较形象直观;缺点是特征向量必须经过规范化处理以避免由于文档长度不同或各个文档间关键词出现的频度各异而产生的畸变,特别是当

4、数据维数较高时,聚类的质量和算法的性能都明显下降.[7]我们用主题表示文档,将文档和主题间的关系描述成事务的形式,根据臻于成熟的关联规则挖掘算法初步划分文档类,然后依照类间耦合度和类的内聚性进行聚类确认,有效地解决了上述方法中普遍存在的扩展性问题.1Web文档的结构化表示Web文档是一种半结构化数据,为便于检索和查询,需要进行结构化处理.Web文档表示就是抽取和描述其特征,并在此基础上建立特征的结构化描述的过程.在对Web文档进行结构化表示的时候,我们首先用向量空间模型VSM(vectorspacemodel)表示每一个主题,并根据建立的主题特征向量和文档内容形成文档的主题向量,再依此分

5、别计算给定文档与这些主题间的关联度,然后根据关联度创建文档-主题事务矩阵.最后,对文档-主题事务矩阵中的行向量(即事务)进行规范化处Ã收稿日期:2000-04-04;修改日期:2000-08-28基金项目:国家自然科学基金资助项目(60173058);国家863青年基金资助项目(863-306-QN2000-5)作者简介:宋擒豹(1966－),男,陕西华县人,博士,副教授,主要研究领域为数据挖掘,知识工程,计算机网络安全;沈钧毅(1939－),男,江苏扬州人,教授,博士生导师,主要研究领域为数据库理论,数据挖掘,数据仓库.418JournalofSoftware软件学报2002,13(3

6、)理,将它转换成单位向量,以使关联度之间具有可比性.下面我们依次对上述Web文档结构化过程中用到的概念进行具体定义和阐述.定义1.主题特征向量.设T是主题的集合,对于其中的每一个主题Ti∈T,我们用特征向量[()()()()]TT=k,w,k,w,...,k,w,...,k,wii,1i,1i,2i,2i,ji,ji,li,l表示.其中,ki,j代表主题Ti中的第j个关键字/短语;wi,j为第j个关键字/短语ki,j对应的权值,表示该关键字/短语在该主题中的重要程度,且∑wi,j=1,1≤j≤l;l=Ti,为主题Ti中关键字/短语的个数,各个主题的l依实际情况而定,可以不同.用VSM定义

7、主题特征向量,代表主题的关键字/短语及其重要性可以根据具体情况来设定,各个主题的关键字个数也可以不同,这就充分兼顾了不同主题各自的具体情况,具有广泛的适用性和较强的可维护性.定义2.文档的主题向量.设D是文档的集合,其中每一个文档Dj∈D关于主题Ti的向量ToDj(Ti)表示文档Dj对主题Ti的贡献,定义为[jjjj]TToD(T)=µ,µ,...,µ,...,µ,jii,1i,2i,ki,l(2)j×wi,kµ=∪K∪D,