基于PageRank和HITS的Web结构挖掘算法研究

维普资讯 http://doc.guandang.net

第 l卷第 4期 9 2O O6年 8月

山东科学S ND0 G C HA N SⅡ C E

V0 . 9 No 4 11 . Au 2 O g. 0 6

文章编号:024 2 (0 6O . l.4 l0.0 620 )40 1 0 0

基于 P gR n ae ak和 H T IS的 We b结构挖掘算法研究刘栋刘希玉郝婷婷 ,,(. 1山东师范大学信息科学与工程学院,山东济南 201;. 5042山东大学材料科学与工程学院,山东济南 206) 50 1 摘要:在对 we结构挖掘的典型算法探讨的基础上,出了一种 PgRn算法和 H S法相结合的改进算 b提 aea k l f算法,并对该算法进行了简要分析.关键词:据挖掘; b数 We结构挖掘;ae ak H S PgR n; f l中图分类号:P0 . T 3 16文献标识码: A

随着 I e e的快速发展, e nm t t W b正在成为一种新的数据源,中汇集了大量信息 .但是 we具有无结其 b构,动态,组织复杂的特点,给用户搜索数据造成了很大困难.这就急需一种能自动地从 W b e资源中发现, 获取信息的新技术, b We数据挖掘技术应运而生,并取得了一定的研究成果.本文分析了 PgR n a ak和 HT e I S算法,并在此基础上介绍了一种 We结构挖掘的改进算法. b

1 We数据挖掘分类 b一

般来讲, l数据挖掘可以分为 3: e Wb e类 wl b内容挖掘( b ot t iI)W b We Cn n Mn l, e结构挖掘( e rc r e i g W b t te Suu

Mn g~ We使用记录的挖掘( bUa in) in ) i b We s e n gn.如图 1 gM i所示.

图 I We数据挖掘分类 b

1 1 We . b内容挖掘

we内容挖掘是从大量的 we数据中发现并抽取有用信息的过程.这些数据既有文本和超文本数据, b b 也有图形,图像,语音等多媒体数据;既有来自于数据库的结构化数据,也有用 H M T L标记的半结构化数据和无结构的自由文本.其中, b we内容挖掘可以分为: ( fm tnrrv) I I o ao te方法和数据库方法.] R n r i ei e[ 212 We . b使用记录挖掘

we使用记录挖掘即通过挖掘用户的 we b b日志记录,发现用户访问 we页面的模式, b得到有价值的信息.这些数据包括:各类服务器日志记录,浏览器日志记录,用户注册信息,用户对话或交易信息等等.目前这一方面的研究较多,并且出现了很多种有商用价值的 we b日志挖掘技术和工具.收稿日期:0 6 30 20- -1 0

基金项目:泰山学者""建设工程专项经费资助;山东省自然科学基金重大项目(20 G 2, Z 0, 0 )山东省教育厅计划项目( 5 O ) t/ GI. 0作者简介:刘栋(93)男,士研究生, 18.,硕主要研究方向:数据挖掘,支持向量机.Em i l 2 1 6 . - a: 0 0@13一 ld

维普资讯 http://doc.guandang.net

1 2

山

东

科

学

20链 O6

13 We . b结构挖掘

We结构挖掘是从 WWW链接结构关系网络中推导知识b .它主要

是针对 We面之间的超链接结 b] b页

构,内部结构和 U L中的目录路径结构进行挖掘,中抽取知识, R从包括文档结构挖掘和站点结构挖掘.目前, b结构挖掘主要是基于超链接结构的挖掘 .通过对超链接结构的研究分析, We以提高搜索引擎的效率 .

2 We结构挖掘典型算法 b目, b前 We用户主要是使用搜索引擎在 Ie e上检索信息,目前的搜索引擎的效率不尽如人意, nmt t但往往会返回很大一部分重复的或者是与用户检索要求不相关的页面 .由此,如何利用 We有的结构特点, b独提

高搜索引擎的检索效率成为当前的一个研究热点问题. 目前基于超链接结构分析的 we结构挖掘算法主要是将 we看作为有向图或无向图的形式, b b结合一定的启发式方法,图论的方法进行分析研究 .用2 1 Pg~ n法 . ae k算

PgRn ae ak算法由 S no t fd大学的 Bi Pg提出, a r r n和 ae是评价网页权威性的一种重要工具 .著名的搜索引擎 Gol就是基于该算法实现的. og e

为了描述 Pg ak ae n算法, R我们作如下定义:定义 1 G(,表示 We面间的超链接结构有向图,为 We面的集合, V E) b页 b页 E为页面间链接的集

合.其中,有向边(, ) P q∈E代表从页面P指向页面 q的超链接.定义 2页面 P的出度是指从页面 P出发的超链接 ( i—otp ) Ln u( )的总数, e即为 Ii—otp I其入度 n L e u();是指所有指向页面 P的超链接 ( n i( )的总数,为 I n—i( ). i L e np )记 e np I i L—

定义 3 I I义为 We向图中 We面结点的总数,中,定义为页面 i向的所有页面的集 定 b有 b页其 指合,即为 Ln oti; i e u( B定义为指向页面 i )的所有页面的集合,即为 L e i( .特殊地, i—n i n )对每个出度为 0的—

结点 s记 R={向图中全部Ⅳ个结点}相应地所有其他节点的 B{ Us., s有, }由前面的定义,面 i页的等级 PgR值可 P ( )以通过以下两步计算得出: ae~ R i可

() 1以概率 (一随机取 we上任一页面 i 1 m) b; () 2以概率 m随机取指向当前页面 i的页面 f,.

则 PgR算法的具体迭代公式为: a~ e

咫 ()=1 i - m+m枷 (Rj/ I∑ P( I ) )I

其中,参数 m是取值范围在 0到 1间的衰减因子,常被置为 0 8.之通 .5 PgRn ae ak算法可以通过递归检索计算索引数据库中的超链接记录来实现,在 we并 b超链接结构分析中

取得了成功,被著名的搜索引擎 Gol所采用.但是它也存在一定的缺陷, og e比如 PgRn算法检索主题的 aeak无关性 .目前,很多文献中提出了对 Pg~k法的改进 .如文献[] aR算 e 4给出了 PgRn值

的另一种加速算 aeak法—— B c ak l rh文献[3 l n gi m; 0 A ot 5讨论了具有时间反馈的 PgRn算法. a~k e22 HT . IS算法 u 19 99年 Ke br[提出了 HT ( yelkIdcdTpcSac)法来评定网页内容的重要性 .他认为 li e 6 n g IS Hprn— ue oi erh算 i n

网页的重要性应该依赖于用户提出的检索主题.而且对每一个网页应该将其 A t ry u ot权重 ( hi由网页的 ot k决定) H b ui l n和 u权重(由网页的 ii决定) nn lk分开来考虑.根据页面之间的超链接结构,将页面分为 H b u页和 A t r页,中, u页是一个指向权威页的超链接集合的 we页, A t r页是被许多 H页指 u ot其 hi y H b b而 u ot hi y b u向的权威的 We . b页

因此,个 H页应该指向许多好的权威页,被许多 H页指向的一定是权威页 .这种 H与权威一 b u而 b u b u

页面之间的相互作用,可用于权威页面的挖掘和高质量 We结构和资源的自动发现.具体算法描述如下: b

维普资讯 http://doc.guandang.net

第4期

刘

栋,:等基于 PgR n ae ak和 HT IS的 We结构挖掘算法研究 b

1 3

首先, IS HT由用户的检索主题得到一初始结果集,构成算法的根集( o s ) r te .比如由基于索引的搜索引 o t擎进行查询 .一般地,根集页面取 20个左右即可 . 0

其次,将根集进一步扩展为基本集(a t, bs s )它包含了所有由根集中的页面所指向的页, ee以及所有指向 根集页面的页.可以为基本集设定一个上线,指明扩展的尺度. 最后,按照公式()( ) 1,2递归地计算基本集中每个页面的 A t r权重和 hb u ot hi y u权重 .其中,和 h值初始为同一个常数 .根据线性代数理论, 可以证明 和 h与权重的初始设置无关. 口=

V g P:=

∑∑口q

( 1 ) ( 2 )

Vp:

其中,—g p是指由页面P指向g的超链接.

3基于 PgR n和 HT的改进算法 aeak IS传统的 PgR n算法完全忽略掉了网页的内容, HT算法存在" a~ak而 IS主题漂移"的现象.如用户在查询"量子物理学",时由于算法中需要对初次检索结果的根集扩充成基集,最终的检索结果中会包含大量的有关"物理学"的站点n. …… 此处隐藏：5523字，全部文档内容请下载后查看。喜欢就下载吧 ……