Dijkstra算法在Web结构挖掘的应用.pdf

74 福建电脑 2008年第1期 Dijkstra算法在Web结构挖掘的应用 林耀进t， 王晨曦2 (1、漳州师范学院计算机科学与工程系福建漳州3530002、漳州职业技术学院计算机工程系福建漳州353000) 绍Dijkstra算汝在兵挖掘结果的应用。 【关键词】：Web结构挖掘，PageRank算法，Dijkstra算法，权重 对公式(2)求解得公式(3) 有哪些信誉好的足球投注网站引擎Croogh的成功．取决于它采用了有效的Web信息 挖掘技术。Web挖掘指在WWW上挖掘潜在的、有用的模式及 2一ID 一；旦 9』=lOE 隐藏的信息过程fIl。Web挖掘分为Web内容挖掘、Web结构挖掘 2 和Web使用挖掘。其中结构挖掘则是从人为地链接结构中获取 直暑!+墨 4A=5口 2 3 17B=8C 有用知识的过程。在设计有哪些信誉好的足球投注网站引擎等服务时。对Web页面的连 c．：B+。D+旦 。8层 (3) 2 2 3 接结构进行挖掘以得出有用的知识是提高检索的重要手段。 20C=17D D；c+墨 3 本文从Web结构挖掘人手．对W幽结构挖掘的PageRank 9C=17E EI』+曼 20层=9D 算法结合概率论进行研究应用。然后介绍Dijkstra算法在挖掘结 2 2 果中的应用。 对于页面B，E。其中页面B、E存在直接链接关系：把W(B。 1．算法的介绍 E)声明为代表B-E的回顾因子权重。W(，)表示两个页面之问 1．1 PageRank算法 的紧密链接关系，W(，)值越大说明两个页面之间关系越紧密。 在PageRank方法中的PageRank被定义为P-1：设u是一个 Web页，Fu为所有11指向的页面的集合。Bu为所有指向U的页 式(3)，很容易得出图(2)Web带权重的页面结构。 面的集合。设Nu=lFuI为从u发出的链接的个数．那么U页面的 PageRank可以定义为： R似)=c’R“)／Nv — v。eBu～ (1) 其中c(1)为归一化因子(因为所有页面的RankPage之和 为一个常数)。PageRank算法的实现过程：将网页的URL对应成 -图(2)Web带权重的页面结构 唯一的整数．把每一个超链接用其整数ID存放到索引数据库 中，经过预处理后。设每个网页的初始PR值为l。通过以上的递 是一样的。如对图(2)，页面A到D存在多条路径，其中：R1： 归算法计算每一个网页的PageRank值，反复进行迭代，直至结 构收敛。显然，PageRank值越大，该页