基于云計(jì)算平臺(tái)的知識(shí)庫(kù)構(gòu)建方案

劉利

（瀘州職業(yè)技術(shù)學(xué)院信息工程系，四川 瀘州 646005)

基于云計(jì)算平臺(tái)的知識(shí)庫(kù)構(gòu)建方案

劉利

（瀘州職業(yè)技術(shù)學(xué)院信息工程系，四川 瀘州 646005)

當(dāng)今互聯(lián)網(wǎng)已成為一個(gè)巨大的開放式知識(shí)庫(kù)，其中包含著許多有價(jià)值的信息?；ヂ?lián)網(wǎng)信息呈現(xiàn)形式多樣性的特點(diǎn)，如何初步篩選出有價(jià)值的網(wǎng)頁(yè)，是信息抽取的第一要?jiǎng)?wù)，也是構(gòu)建知識(shí)庫(kù)的基礎(chǔ)。本文在建立互聯(lián)網(wǎng)模型基礎(chǔ)上，利用Hadoop平臺(tái)下的Pagerank算法，旨在研究如何在節(jié)省時(shí)間和空間基礎(chǔ)上篩選出有價(jià)值的網(wǎng)頁(yè)，為從互聯(lián)網(wǎng)抽取有價(jià)值信息構(gòu)建知識(shí)庫(kù)提供解決方案。

Hadoop；Pagerank；知識(shí)庫(kù)；信息抽取

1 引言

互聯(lián)網(wǎng)像是一個(gè)巨大的知識(shí)庫(kù)，具有信息規(guī)模龐大、信息資源多樣、信息分散等特點(diǎn)。網(wǎng)頁(yè)被視為知識(shí)庫(kù)中的單位信息，但這些信息有很強(qiáng)的獨(dú)立性和自治性。搜索引擎好比是在這個(gè)知識(shí)庫(kù)中建立索引，方便用戶搜索。用戶用主流的搜索引擎比如google和百度搜索某個(gè)關(guān)鍵字時(shí)，會(huì)反饋許多已排序好的網(wǎng)址，排序過程是根據(jù)復(fù)雜的文本匹配算法和鏈接分析算法相結(jié)合的技術(shù)實(shí)現(xiàn)的。在用戶搜索之前，網(wǎng)頁(yè)間的等級(jí)劃分就已通過鏈接分析算法初步確定，鏈接分析算法成為評(píng)判網(wǎng)頁(yè)等級(jí)和重要性的標(biāo)準(zhǔn)之一。

2 鏈接分析算法

由互聯(lián)網(wǎng)信息所具有的特征可知，在擴(kuò)展網(wǎng)頁(yè)和超鏈接規(guī)模時(shí)，需判斷它們的重要性，選取質(zhì)量和信譽(yù)度好的網(wǎng)頁(yè)。本文采用鏈接分析方法作為網(wǎng)頁(yè)重要性的評(píng)判標(biāo)準(zhǔn)。

影響搜索引擎的鏈接排名的一個(gè)很重要的因素是鏈接分析算法。常見的鏈接分析算法主要有PageRank、HITS、 SALSA、Hilltop等等，這些算法的核心是PageRank[1]和HITS[2]，而后面的其他算法都是以它們?yōu)榛A(chǔ)延伸的。

HITS算法對(duì)待排序的網(wǎng)頁(yè)數(shù)量規(guī)模要求較小，網(wǎng)頁(yè)數(shù)量規(guī)模要求一般為1000至5000個(gè)，但由于需要從文本的搜索引擎中獲得中心類網(wǎng)頁(yè)集并以此擴(kuò)充權(quán)威類網(wǎng)頁(yè)集，這個(gè)過程消耗時(shí)間較長(zhǎng)，而PageRank算法處理的數(shù)據(jù)數(shù)量規(guī)模上遠(yuǎn)遠(yuǎn)超過了HITS算法。據(jù)Google官方介紹[3]，目前已經(jīng)收錄了1萬億以上的網(wǎng)頁(yè)并且規(guī)模還在不斷擴(kuò)大，而且PageR-ank算法是在用戶查詢前就已經(jīng)在服務(wù)器端獨(dú)立完成的，不會(huì)占用用戶查詢時(shí)間，因此從用戶體驗(yàn)時(shí)間來說其遠(yuǎn)比HITS要短。

3 PageRank算法

PageRank算法有單機(jī)模式和并行運(yùn)算模式。單機(jī)模式運(yùn)算規(guī)模較小，對(duì)內(nèi)存空間要求較大，而本文面向的是上億的URL鏈接，鑒于此，選擇并行運(yùn)算模式。通過PageRank算法算出每個(gè)網(wǎng)頁(yè)的等級(jí)，等級(jí)越高說明網(wǎng)頁(yè)質(zhì)量和可信度就越高。決定網(wǎng)頁(yè)等級(jí)的主要因素有：鏈入數(shù)量、鏈入網(wǎng)頁(yè)的等級(jí)、鏈出數(shù)量。

計(jì)算網(wǎng)頁(yè)的等級(jí)就等價(jià)于計(jì)算網(wǎng)頁(yè)的PR值。網(wǎng)頁(yè)的PR值定義為：鏈入網(wǎng)頁(yè)（比如A網(wǎng)頁(yè)）的所有頁(yè)面的PR值除以各自頁(yè)面里面鏈出數(shù)量之和。算法如公式1所示：

其中，PR(A)表示A頁(yè)面的等級(jí)，PR(Ti)表示Ti頁(yè)面的等級(jí)，Ti頁(yè)面指向A頁(yè)面（即Ti鏈出到A），C(Ti)表示Ti頁(yè)面的鏈出總數(shù)，d是0到1間的常數(shù)，稱為阻尼系數(shù)。根據(jù)Lawrence Page等人給出的值，應(yīng)用中一般設(shè)置為0.85。PR(Ti)／C(Ti)表示頁(yè)面Ti鏈到A頁(yè)面的概率，隨著i值的變化，即可算出模型中達(dá)到A頁(yè)面的總概率。根據(jù)上述公式進(jìn)行迭代計(jì)算，當(dāng)算出相鄰兩次頁(yè)面的PR值收斂時(shí)計(jì)算結(jié)束，得到的PR值為每個(gè)頁(yè)面最終的PR值。

本文以網(wǎng)頁(yè)質(zhì)量好、可信度高為原則對(duì)網(wǎng)頁(yè)為基礎(chǔ)，采用網(wǎng)絡(luò)爬蟲的思想，最終收集并整理8億多的URL，這對(duì)整個(gè)互聯(lián)網(wǎng)來說是很小的，若利用現(xiàn)有的方式計(jì)算各個(gè)URL對(duì)

應(yīng)網(wǎng)頁(yè)的PR值將導(dǎo)致兩級(jí)分化，究其原因在于計(jì)算過程中，有的網(wǎng)頁(yè)只有鏈接入沒有鏈出，這將導(dǎo)致有的PR值將特別大，而有的PR值將特別小，也會(huì)導(dǎo)致計(jì)算結(jié)果的不準(zhǔn)確，這有悖于互聯(lián)網(wǎng)閉環(huán)的特點(diǎn)。因此，在計(jì)算之前建立互聯(lián)網(wǎng)模型很有必要，將沒有鏈出的網(wǎng)頁(yè)，讓它的鏈出指向包括自身在內(nèi)的每一個(gè)網(wǎng)頁(yè)。

PageRank迭代計(jì)算并致收斂后，有些網(wǎng)頁(yè)的PR值大于1，就可認(rèn)為該網(wǎng)頁(yè)等級(jí)比平均網(wǎng)頁(yè)等級(jí)高，可視為質(zhì)量好的網(wǎng)頁(yè)。

4 實(shí)驗(yàn)過程和結(jié)果分析

4.1 相關(guān)準(zhǔn)備

以戴爾PowerEdge R8201的硬件服務(wù)器搭建的Hadoop平臺(tái)，1臺(tái)master和2臺(tái)slave。軟件安裝：JDK版本為jdk-6u31-linux-i586.bin[5]；Hadoop版本是hadoop-1.2.1.tar.gz[6]。集群信息如表1所示。

表1 集群信息

4.2 Hadoop配置和運(yùn)行步驟

(1)將每個(gè)服務(wù)器都安裝JDK、解壓Hadoop，并保存和安裝在各服務(wù)器上的路徑相同；

(2)配置各服務(wù)器的緩存大小、接口、通信等，需要設(shè)置各個(gè)服務(wù)器上的四個(gè)配置文件：core-site.xml、hadoop-env.sh、hdfs-site.xml和mapred-site.xml；

(3)用命令啟動(dòng)Hadoop平臺(tái)，配置成功后，HDFS的存儲(chǔ)能力達(dá)到460多個(gè)G。

(4)編寫Hadoop要求的程序并提交。

4.3 網(wǎng)頁(yè)和超鏈的收集整理

為減少在計(jì)算時(shí)所要求的空間性能，在計(jì)算之前先將URL轉(zhuǎn)化為對(duì)應(yīng)的checksum編碼[7]。轉(zhuǎn)化URL的保存格式是：URL##checksum,如圖1所示。

圖1 URL和checksum存儲(chǔ)格式

在計(jì)算網(wǎng)頁(yè)P(yáng)ageRank時(shí)，輸出格式是：checksum PR1 PR2，如圖2所示：

圖2 PageRank計(jì)算結(jié)果

在PageRank收斂后，選取PR值大于1的網(wǎng)頁(yè)，最終整理出網(wǎng)頁(yè)5000多萬的URL，并以此為基礎(chǔ)下載網(wǎng)頁(yè)數(shù)據(jù)構(gòu)建知識(shí)庫(kù)。

5 結(jié)語(yǔ)

本文描述了一種以互聯(lián)網(wǎng)為基礎(chǔ)的構(gòu)建知識(shí)庫(kù)的方案，在大規(guī)模URL基礎(chǔ)上建立互聯(lián)網(wǎng)模型，通過Hadoop平臺(tái)的Pagerank算法篩選出有價(jià)值的URL，并下載對(duì)應(yīng)網(wǎng)頁(yè)，方便后續(xù)構(gòu)建知識(shí)庫(kù)的研究提供解決方案。

[1]Page L，Brin S，Motwani R，Windograd T．The Pagerank citation ranking：Bring order to the web．1998．

[2]Kleinberg J．Authoritative sources in a hyperlinked environment．Proceedings of the 9th ACM-SIAM symposium on Discrete Algorithms．New Orleans：ACM Press，1997：668-677．

[3]google官方微博[EB/OL]．http：//readwrite．com/2008/07/25/ google_hits_one_trillion_pages．

[4]周傲英，曾大聃．Hadoop權(quán)威指南（中文版）[M]．北京：清華大學(xué)出版社．2010．

[5]jdk下載[EB/OL]．http：//www．oracle．com/technetwork/java/ javase/index．html．

[6]hadoop下載及配置[EB/OL]．http：//www．a(chǎn)pache．org/dist/hadoop/core/．

[7]checksum編碼講解[EB/OL]．http：//baike．baidu．com/view/ 93743．htm．Knowledge Base Constructing Scheme Based on Cloud Computing Platform

Liu Li
(Luzhou Vocational and Technical College,Luzhou 646005,Sichuan)

The network has become the biggest knowledge base and contains a lot of valuable information.The presentation form of Internet information is diversified.How to discover valuable page is top priority of information extraction and the foundation of building knowledge base.Based on the Internet model,this article researches how to discover valuable pages using Pagerank algorithm in Hadoop platform saving time and space,to provide solutions for knowledge base construction.

Hadoop;Pagerank;knowledge base;information extraction

TP391.1

A

1008-6609(2016)08-0077-02

劉利，男，四川瀘州人，碩士，講師，研究方向：人工智能、數(shù)據(jù)挖掘。