Web結(jié)構(gòu)的數(shù)據(jù)挖掘HITS算法論文
Web擁有海量的信息，為人們提供豐富多樣的信息服務(wù)。隨著信息技術(shù)的發(fā)展和Web信息量的指數(shù)級(jí)增長(zhǎng)，快速準(zhǔn)確地從Web網(wǎng)絡(luò)中獲取信息變得愈發(fā)重要。因此，如何從海量的Web網(wǎng)絡(luò)中尋找有價(jià)值的數(shù)據(jù)信息已然是現(xiàn)階段Web結(jié)構(gòu)挖掘的一個(gè)非常重要的研究課題。在實(shí)際應(yīng)用場(chǎng)景中，用戶往往需要在獲得Web頁(yè)面的基礎(chǔ)上快速找到高質(zhì)量的所謂權(quán)威頁(yè)面。在Web結(jié)構(gòu)挖掘中鏈接分析的作用非常重要，而以鏈接分析為基礎(chǔ)建立的HITS算法能夠高效地篩選出Web頁(yè)面中的權(quán)威資源。常常用于分析超鏈接以確定權(quán)威信息源。本文研究HITS算法，分析了傳統(tǒng)HITS算法存在的問(wèn)題，并在此基礎(chǔ)上運(yùn)用基本集縮減法優(yōu)化HITS算法，從而實(shí)現(xiàn)更有效率的權(quán)威網(wǎng)頁(yè)檢索，提高提高算法的效率和靈活性。
一、HITS算法基本原理
作為數(shù)據(jù)提起算法的典型算法之一，HITS算法的應(yīng)用和需要檢索的主題有直接關(guān)系。HITS算法的基本思想是先提取出Web鏈接結(jié)構(gòu)中用戶需要檢索的相關(guān)頁(yè)面，組成Web鏈接結(jié)構(gòu)子圖，再運(yùn)用HITS算法分析計(jì)算這個(gè)連接結(jié)構(gòu)子圖。而Web鏈接主要有以下幾點(diǎn)特征。其一，有些鏈接的作用是廣告或?qū)Ш�，只有具有注釋性的鏈接才能用于�?quán)威性的評(píng)判。其二，商業(yè)競(jìng)爭(zhēng)因素的影響下，權(quán)威網(wǎng)頁(yè)鏈接至Web網(wǎng)頁(yè)競(jìng)爭(zhēng)領(lǐng)域的情況很少。其三，一般來(lái)說(shuō)，權(quán)威網(wǎng)頁(yè)都缺少明顯的描述，如百度搜索主頁(yè)并不會(huì)將與Web信息檢索引擎有關(guān)的具體描述信息呈現(xiàn)給用戶�？梢�(jiàn)，Web鏈接的實(shí)際情況與平均分配權(quán)值不相符。因此，在HITS算法中新增了一種新的網(wǎng)頁(yè)類型，也就是Hub網(wǎng)頁(yè)。Hub網(wǎng)頁(yè)集中了鏈接至權(quán)威網(wǎng)頁(yè)的鏈接。實(shí)際上，很少有網(wǎng)頁(yè)指向Hub網(wǎng)頁(yè)，但是Hub網(wǎng)頁(yè)中集中了鏈接至權(quán)威網(wǎng)頁(yè)的鏈接。如，排列在課本主頁(yè)上的一列參考文獻(xiàn)。在常規(guī)情況下，高質(zhì)量的Hub網(wǎng)頁(yè)指向了大量的權(quán)威網(wǎng)頁(yè)，而一個(gè)高質(zhì)量的權(quán)威網(wǎng)頁(yè)擁有許多指向它的Hub網(wǎng)頁(yè)，但是一個(gè)頁(yè)面的authority等于鏈接至這個(gè)頁(yè)面的全部hub的和；一個(gè)頁(yè)面的hub等于它指向的頁(yè)面的全部authority的和。而Hub和Authority網(wǎng)頁(yè)之間的關(guān)系是自動(dòng)查詢權(quán)威網(wǎng)頁(yè)和Web結(jié)構(gòu)和資源的重要工具。這就是HITS算法的基本原理。
二、傳統(tǒng)HITS算法存在的問(wèn)題
傳統(tǒng)的HITS算法主要存在以下幾個(gè)問(wèn)題。第一，下載、分析網(wǎng)頁(yè)包含的鏈接，并且排除重復(fù)的鏈接需要耗費(fèi)大量的時(shí)間，計(jì)算量比PageRank算法大。第二，某些情況下，大量主機(jī)A上的網(wǎng)頁(yè)會(huì)指向另一臺(tái)主機(jī)B上的某一個(gè)特定網(wǎng)頁(yè)，從而使主機(jī)A上的網(wǎng)頁(yè)Hub值和主機(jī)B上網(wǎng)頁(yè)的Authority增加，反之也一樣。HITS算法假設(shè)決定某一個(gè)網(wǎng)頁(yè)權(quán)威值的.組織和個(gè)人不同，上述情況對(duì)主機(jī)A和B上網(wǎng)頁(yè)的Hub和Authority的值有所影響。第三，網(wǎng)頁(yè)中的一些無(wú)關(guān)鏈接指向的網(wǎng)頁(yè)中包含的無(wú)關(guān)鏈接對(duì)Hub和Authority值的計(jì)算造成影響。網(wǎng)頁(yè)在制作的過(guò)程中往往會(huì)被加入一些無(wú)關(guān)鏈接，如廣告、友情鏈接都對(duì)HITS算法的精確度有影響。第四，主題漂移是HITS算法存在的最大問(wèn)題。Web鏈接結(jié)構(gòu)的自組織性，使WWW中主題一樣或相關(guān)的頁(yè)面通過(guò)超鏈接形成一個(gè)個(gè)緊密鏈接區(qū)域。當(dāng)用戶查詢范圍較寬的定義主題或者多個(gè)主題時(shí)，鏈接結(jié)構(gòu)子圖會(huì)因?yàn)槎鄠�(gè)子主題對(duì)應(yīng)多個(gè)信息形成多個(gè)相對(duì)緊密鏈接區(qū)域。而HITS算法屬于迭代算法，因此，緊密鏈接區(qū)域的頁(yè)面權(quán)值必然會(huì)增大，從而干擾檢索的精確度，使用戶獲得的結(jié)果發(fā)生漂移，這種現(xiàn)象叫做主題漂移。第五，在查詢主題時(shí)采用HITS算法時(shí)有一定的幾率出現(xiàn)主題泛化的現(xiàn)象，也就是說(shuō)結(jié)果中出現(xiàn)了新的與查詢無(wú)關(guān)的主題。
三、利用基本集縮減法優(yōu)化
HITS算法在HITS算法的基本集中含有很多互相之間毫無(wú)關(guān)聯(lián)的網(wǎng)頁(yè)，因此，需要對(duì)基本集進(jìn)行精簡(jiǎn)�？梢酝ㄟ^(guò)剔除與根集沒(méi)什么關(guān)系的網(wǎng)頁(yè)，從而有效抑制主題偏移問(wèn)題，同時(shí)大大降低運(yùn)算量。為了實(shí)現(xiàn)這個(gè)目的，可以對(duì)HITS算法進(jìn)行優(yōu)化，以優(yōu)化獲取基本集的方式，產(chǎn)生新的HITS算法改進(jìn)方案———基本集縮減法。所謂基本集縮減法，是指通過(guò)考慮指向或來(lái)自根集中網(wǎng)頁(yè)的鏈接數(shù)目縮減基本集，再?gòu)奶崛∵m當(dāng)?shù)腤ebCommunities。基本集縮減法向S中加入被S引用的網(wǎng)頁(yè)和引用S的網(wǎng)頁(yè)將S擴(kuò)展成一個(gè)更大的集合T。HITS算法改進(jìn)：首先加入所有的根集網(wǎng)頁(yè)指向的網(wǎng)頁(yè)以及最多d個(gè)指向根集R中網(wǎng)頁(yè)的Web網(wǎng)頁(yè)，將根集R的規(guī)模擴(kuò)展至n，構(gòu)建基本集S，再篩選已建立的基本集S，只選擇指向至少k個(gè)根集網(wǎng)頁(yè)以及被至少k個(gè)根集網(wǎng)頁(yè)鏈向的網(wǎng)頁(yè)，從而實(shí)現(xiàn)基本集的縮減。由此，可以總結(jié)出采用基本集縮減算法提取authorities網(wǎng)頁(yè)的步驟。第一步，輸入特定的關(guān)鍵詞，檢索到的r個(gè)等級(jí)的結(jié)果網(wǎng)頁(yè)構(gòu)成根集Rσ。第二步，擴(kuò)展根集R的規(guī)模至n，構(gòu)建基本集Sσ，加入所有的根集網(wǎng)頁(yè)指向的網(wǎng)頁(yè)以及最多d個(gè)指向根集R中網(wǎng)頁(yè)的Web網(wǎng)頁(yè)，將根集R的規(guī)模擴(kuò)展至n，構(gòu)建基本集S，再篩選已建立的基本集S，只選擇指向至少k個(gè)根集網(wǎng)頁(yè)以及被至少k個(gè)根集網(wǎng)頁(yè)鏈向的網(wǎng)頁(yè)，從而實(shí)現(xiàn)基本集的縮減。第三步，用G(Sσ)表示根據(jù)基本集Sσ中的網(wǎng)頁(yè)鏈接關(guān)系推導(dǎo)而來(lái)的結(jié)構(gòu)子圖，則G(Sσ)中包含內(nèi)鏈、外鏈兩種鏈接。所謂外鏈?zhǔn)侵赣蛎煌腤eb網(wǎng)頁(yè)之間的鏈接，內(nèi)鏈?zhǔn)侵赶嗤蛎木W(wǎng)頁(yè)之間的鏈接，在實(shí)際情況下，只考慮了外鏈，而忽略基本集Sσ中的所有內(nèi)鏈。第四步，結(jié)合基本集Sσ構(gòu)造鄰接矩陣矩陣A和轉(zhuǎn)置矩陣AT，計(jì)算其每個(gè)特征值及所對(duì)應(yīng)的特征向量。第五步，特征向量歸一化后會(huì)以authorities值返回具有較大絕對(duì)值的元素�？s減基本集可以減少鄰接矩陣階數(shù)，降低特征值的計(jì)算量�？s減基本集方法中的計(jì)算量的預(yù)估方法如下：從與基本集S對(duì)應(yīng)的一個(gè)n*n鄰接矩陣中選取出鏈接至根集R中元素的多個(gè)網(wǎng)頁(yè)，從鄰接矩陣中從第n-r行中選擇前r個(gè)元素之和≥2的行，可預(yù)估其計(jì)算量為r(n—r)。與之類似，選取多個(gè)根集網(wǎng)頁(yè)鏈接的網(wǎng)頁(yè)所需計(jì)算量一樣。運(yùn)用該方法可以將基本集縮減為原先的一半，考慮到計(jì)算與Web數(shù)據(jù)挖掘中HITS算法有關(guān)的特征向量的計(jì)算量為n3，計(jì)算是加上2r(n—r)的額外計(jì)算量，運(yùn)用基本集縮減法還可以有效減少計(jì)算量，同時(shí)基本集縮減法能夠有效抑制主題偏移問(wèn)題。四、結(jié)語(yǔ)綜上所述，HITS算法雖然存在一些問(wèn)題，但是相對(duì)于其他Web結(jié)構(gòu)挖掘算法來(lái)說(shuō)，優(yōu)勢(shì)非常明顯。HITS算法的基本思想以頁(yè)面之間的鏈接關(guān)系為基礎(chǔ)。從Web結(jié)構(gòu)挖掘的本質(zhì)入手，分析了HITS算法的基本思想，探討了HITS算法的基本原理。但是由于篇幅限制無(wú)法進(jìn)一步深入研究其算法，通過(guò)分析HITS算法的缺陷，找到相應(yīng)的改進(jìn)方案，進(jìn)而提高HITS算法的使用效果，促進(jìn)其在信息檢索領(lǐng)域的運(yùn)用。在研究改進(jìn)HITS算法的過(guò)程中，應(yīng)該先深入研究傳統(tǒng)的HITS算法中存在的不足，針對(duì)主題偏移現(xiàn)象和減少基本集鄰接矩陣特征值和特征向量的計(jì)算量，提出使用基本集縮減法對(duì)HITS算法進(jìn)行改進(jìn)，根據(jù)網(wǎng)頁(yè)與根集元素之間的鏈接數(shù)量進(jìn)一步提取基本集，使基本集規(guī)模進(jìn)一步縮減，從而使搜索結(jié)果更加集中于根集，有效降低計(jì)算開(kāi)銷，從而有效提升HITS算法的計(jì)算效率和精確度。
參考文獻(xiàn):
[1]劉軍.基于Web結(jié)構(gòu)挖掘的HITS算法研究[D].中南大學(xué),2008.
[2]盧虹宇.Web結(jié)構(gòu)挖掘中HITS算法的研究[D].西南交通大學(xué),2008.
[3]范聰賢,徐汀榮,范強(qiáng)賢.Web結(jié)構(gòu)挖掘中HITS算法改進(jìn)的研究[J].微計(jì)算機(jī)信息,2010,26(3):160-162.
[4]馬潔.web結(jié)構(gòu)挖掘中HITS算法的研究[J].軟件:電子版,2013(5).
【W(wǎng)eb結(jié)構(gòu)的數(shù)據(jù)挖掘HITS算法論文】相關(guān)文章：
算法類論文開(kāi)題報(bào)告11-11
論文提綱結(jié)構(gòu)09-04
語(yǔ)文寫(xiě)作創(chuàng)新力的挖掘與培育論文07-31
論文開(kāi)題報(bào)告的結(jié)構(gòu)怎么寫(xiě)08-15
績(jī)效工資的算法10-13
失業(yè)保險(xiǎn)的算法06-10
論文的提綱構(gòu)建的基本結(jié)構(gòu)介紹07-05