基于云計算平臺的知識庫構(gòu)建方案

劉利

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

基于云計算平臺的知識庫構(gòu)建方案

劉利

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

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

Hadoop；Pagerank；知識庫；信息抽取

1 引言

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

2 鏈接分析算法

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

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

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

3 PageRank算法

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

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

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

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

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

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

4 實驗過程和結(jié)果分析

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

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

表1 集群信息

4.2 Hadoop配置和運行步驟

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

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

(3)用命令啟動Hadoop平臺，配置成功后，HDFS的存儲能力達到460多個G。

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

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

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

圖1 URL和checksum存儲格式

在計算網(wǎng)頁PageRank時，輸出格式是：checksum PR1 PR2，如圖2所示：

圖2 PageRank計算結(jié)果

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

5 結(jié)語

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

[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ù)挖掘。