一种基于站点资源的主题提取算法.pptVIP

一种基于站点资源的主题提取算法 郭立山 董守斌 袁华 目录 经典的主题提取算法 HITS算法描述 HITS算法存在的缺陷 相关的改进算法 HAC算法 算法解决的问题 算法的描述 实验结果 结论 HITS算法描述 1）Hub 网页和Authority网页: Hub网页即是出度高的网页； Authority网页即是入度高的网页； 2）好的Hub网页指向很多好的Authority网页；而好的Authority网页会被很多好的Hub网页指向。 HITS算法存在的缺陷 1）容易产生主题泛化现象和主题漂移现象。 2）一些无关的链接，如交换链接等，很容易影响HITS算法的精度。 3）HITS算法的时间开销比较大，体现在两个方面：一是构建邻接有向图；二是迭代运算直至收敛。 4） HITS忽略了站点内的超链接，不能很好地满足以站点为资源的查询。 相关的改进算法 1）ARC算法处理了主题漂移问题；并且ARC算法的目标只是找到前15个重要的网页，大大降低了算法的迭代次数。 2）SALSA算法取消了Hub网页和Authority网页的相互加强关系。对于TKC现象有较好的表现。 但目前所有的HITS算法的改进算法没有注意到HITS算法在对以站点作为资源的查询上的先天不足。 HAC算法解决的问题 将页面以站点分组，对站内的超链接分析，能有效地找出站内的Hub页面；考虑站点粒度的超链接，可以有效地抑制站点间过分的相互加强的Hub/Authority关系。 在对链接分析的过程中，加入对页面和链接文本的内容分析，从而有效控制主题漂移。 HAC算法描述 将页面以站点分组 1）理由： 如果只考虑站内范围时，HITS的假设可以很自然地延伸，既然所有的页面都属于同一个作者，那作者显然也会推荐出相对有价值的页面。 超链接结构可以用于识别站点内部的各个独立的信息子系统，正向超链接体现了文档之间的层次结构关系 2）方法： 对页面的URL进行模式匹配，提取’host’域，作为站点的区分标志。 Hash GroupBySite() { 创建哈西表HT; for(集合T中每个页面p) { String strSiteName=Site(p); 根据键值strSiteName将页面p加入到HT中; } return HT; } 在站点内计算Hub/Authority值 页面a的Hub值Ha可由公式1计算而得 ： HAC算法计算站内链接的目的也是找出站内相对少数的Hub页面，所以只要求Hub/Authority的前10个值趋于稳定。 void CalSiteInner() { for(HT中每个桶BP) { 以集合BP构造邻接图GB; for(图GB中每个节点t) { 初始化节点的Hub/Authority值：Ht=At=1.0; } while(GB中节点的Hub/Authority前10个值趋于稳定) { for(图GB中每个节点t) { 利用公式1计算节点t的Hub值; 利用公式2计算节点t的Authority值; …… 在站点间计算Hub/Authority值 以站点为粒度对超链接进行分析的目的是降低站点间的Hub/Authority循环的互相加强关系。当站点A有m个页面指向另外一个站点B的同一个页面a时，那么计这m个页面对页面a的Authority总贡献值应为1，即每个页面的贡献值为1/m。 页面a的Authority值可由公式3计算而得： void CalSite() { 以集合T构造邻接图GT; while(GT中节点的Hub/Authority收敛) { for(图GT中每个节点t) { 利用公式3计算节点t的Authority值; 利用公式4计算节点t的Hub值; } } } 排序 SEWM-2004竞赛中的主题提取任务是找出Hub值高的页面，并且尽量保证排名在前10的页面来自不同的站点。所以，HAC算法以Hub值为第一排序因子，而Authority值为第二排序因子。首先从10个不同的站点获取Hub/Authority值最高的网页作为前10个结果，再将剩下的网页进行排序。 List Sort() {