大話(huà)SALSA算法

SALSA算法的初衷希望能夠結(jié)合PageRank和HITS算法兩者的主要特點(diǎn)，既可以利用HITS算法與查詢(xún)相關(guān)的特點(diǎn)，也可以采納PageRank的“隨機(jī)游走模型”，這是SALSA算法提出的背景。由此可見(jiàn)，SALSA算法融合了PageRank和HITS算法的基本思想，從實(shí)際效果來(lái)說(shuō)，很多實(shí)驗(yàn)數(shù)據(jù)表明，SALSA的搜索效果也都優(yōu)于前兩個(gè)算法，是目前效果最好的鏈接分析算法之一。
 從整體計(jì)算流程來(lái)說(shuō)，可以將SALSA劃分為兩個(gè)大的階段：首先是確定計(jì)算對(duì)象集合的階段，這一階段與HITS算法基本相同；第二個(gè)階段是鏈接關(guān)系傳播過(guò)程，在這一階段則采納了“隨機(jī)游走模型”。
6.5.1確定計(jì)算對(duì)象集合
 PageRank的計(jì)算對(duì)象是互聯(lián)網(wǎng)所有網(wǎng)頁(yè)，SALSA算法與此不同，在本階段，其與HITS算法思路大致相同，也是先得到“擴(kuò)充網(wǎng)頁(yè)集合”，之后將網(wǎng)頁(yè)關(guān)系轉(zhuǎn)換為二分圖形式。
擴(kuò)充網(wǎng)頁(yè)集合
 SALSA算法在接收到用戶(hù)查詢(xún)請(qǐng)求后，利用現(xiàn)有搜索引擎或者檢索系統(tǒng)，獲得一批與用戶(hù)查詢(xún)?cè)趦?nèi)容上高度相關(guān)的網(wǎng)頁(yè)，以此作為“根集”。并在此基礎(chǔ)上，將與“根集”內(nèi)網(wǎng)頁(yè)有直接鏈接關(guān)系的網(wǎng)頁(yè)納入，形成“擴(kuò)充網(wǎng)頁(yè)集合”（參考圖6.4.3-1）。之后會(huì)在“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)根據(jù)一定鏈接分析方法獲得最終搜索結(jié)果排名。

 轉(zhuǎn)換為無(wú)向二分圖
 在獲得了“擴(kuò)充網(wǎng)頁(yè)集合”之后，SALSA根據(jù)集合內(nèi)的網(wǎng)頁(yè)鏈接關(guān)系，將網(wǎng)頁(yè)集合轉(zhuǎn)換為一個(gè)二分圖。即將網(wǎng)頁(yè)劃分到兩個(gè)子集合中，一個(gè)子集合是Hub集合，另外一個(gè)子集合是Authority集合。劃分網(wǎng)頁(yè)節(jié)點(diǎn)屬于哪個(gè)集合，則根據(jù)如下規(guī)則：
如果一個(gè)網(wǎng)頁(yè)包含出鏈，這些出鏈指向“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)其它節(jié)點(diǎn)，則這個(gè)網(wǎng)頁(yè)可被歸入Hub集合；
如果一個(gè)網(wǎng)頁(yè)包含“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)其它節(jié)點(diǎn)指向的入鏈，則可被歸入Authority集合。
 由以上規(guī)則可以看出，如果某個(gè)網(wǎng)頁(yè)同時(shí)包含入鏈和出鏈，則可以同時(shí)歸入兩個(gè)集合。同時(shí)，Hub集合內(nèi)網(wǎng)頁(yè)的出鏈組成了二分圖內(nèi)的邊，根據(jù)以上法則，將“擴(kuò)充網(wǎng)頁(yè)集合”轉(zhuǎn)換為二分圖。
 圖6-15和圖6-16給出了一個(gè)示例，說(shuō)明了這個(gè)轉(zhuǎn)換過(guò)程。假設(shè)“擴(kuò)充網(wǎng)頁(yè)集合”如圖6-15所示，由6個(gè)網(wǎng)頁(yè)構(gòu)成，其鏈接關(guān)系如圖所示，同時(shí)為便于說(shuō)明，每個(gè)網(wǎng)頁(yè)給予一個(gè)唯一編號(hào)。圖6-16則是將圖6-15中的網(wǎng)頁(yè)集合轉(zhuǎn)換為二分圖的結(jié)果。以網(wǎng)頁(yè)6為例，因?yàn)槠溆谐鲦溨赶蚓W(wǎng)頁(yè)節(jié)點(diǎn)3和網(wǎng)頁(yè)節(jié)點(diǎn)5，所以可以放入Hub集合，也因?yàn)榫幪?hào)為1、3、10的網(wǎng)頁(yè)節(jié)點(diǎn)有鏈接指向網(wǎng)頁(yè)節(jié)點(diǎn)6，所以也可以放入Authority集合中。網(wǎng)頁(yè)節(jié)點(diǎn)6的兩個(gè)出鏈保留，作為二分圖的邊，

           圖6-15 擴(kuò)充網(wǎng)頁(yè)集合示例

 但是這里需要注意的是，在轉(zhuǎn)換為二分圖后，原先的有向邊不再保留方向，轉(zhuǎn)換為無(wú)向邊，而HITS算法仍然保留為有向邊，這點(diǎn)與SALSA略有不同。

 圖6-16 二分圖
 到這一步驟為止，除了SALSA將“擴(kuò)充網(wǎng)頁(yè)集合”轉(zhuǎn)換為無(wú)向二分圖，而HITS仍然是有向二分圖外，其它步驟和流程，SALSA算法與HITS算法完全相同，正因此，SALSA保證了是與用戶(hù)查詢(xún)相關(guān)的鏈接分析算法。
6.5.2 鏈接關(guān)系傳播
  在鏈接關(guān)系傳播階段，SALSA放棄了HITS算法的Hub節(jié)點(diǎn)和Authority節(jié)點(diǎn)相互增強(qiáng)的假設(shè)，轉(zhuǎn)而采納PageRank的“隨機(jī)游走模型”。

鏈接關(guān)系傳播概念模型
 如圖6-16所示，假設(shè)存在某個(gè)瀏覽者，從某個(gè)子集合中隨機(jī)選擇一個(gè)節(jié)點(diǎn)出發(fā)（為方便說(shuō)明，圖中所示為從Hub子集的節(jié)點(diǎn)1出發(fā)，實(shí)際計(jì)算往往是從Authority子集出發(fā)），如果節(jié)點(diǎn)包含多條邊，則以相等概率隨機(jī)選擇一條邊，從Hub子集跳躍到Authority集合內(nèi)節(jié)點(diǎn)，圖中所示為由節(jié)點(diǎn)1轉(zhuǎn)移到節(jié)點(diǎn)3，之后從Authority子集再次跳回Hub子集，即由節(jié)點(diǎn)3跳到節(jié)點(diǎn)6。如此不斷在兩個(gè)子集之間轉(zhuǎn)移，形成了SALSA自身的鏈接關(guān)系傳播模式。
 盡管看上去與PageRank的鏈接傳播模式不同，其實(shí)兩者是一樣的，關(guān)鍵點(diǎn)在于：其從某個(gè)節(jié)點(diǎn)跳躍到另外一個(gè)節(jié)點(diǎn)的時(shí)候，如果包含多個(gè)可供選擇的鏈接，則以等概率隨機(jī)選擇一條路徑，即在權(quán)值傳播過(guò)程中，權(quán)值是被所有鏈接平均分配的。而HITS算法不同，HITS算法屬于權(quán)值廣播模式，即將節(jié)點(diǎn)本身的權(quán)值完全傳播給有鏈接指向的節(jié)點(diǎn)，并不根據(jù)鏈接多少進(jìn)行分配。
 SALSA的上述權(quán)值傳播模型與HITS模型關(guān)注重點(diǎn)不同，HITS模型關(guān)注的是Hub和Authority之間的節(jié)點(diǎn)相互增強(qiáng)關(guān)系，而SALSA實(shí)際上關(guān)注的是Hub-Hub以及Authority-Authority之間的節(jié)點(diǎn)關(guān)系，而另外一個(gè)子集合節(jié)點(diǎn)只是充當(dāng)中轉(zhuǎn)橋梁的作用。所以，上述權(quán)值傳播模型可以轉(zhuǎn)化為兩個(gè)相似的子模型，即Hub節(jié)點(diǎn)關(guān)系圖和Authority節(jié)點(diǎn)關(guān)系圖。

Authority節(jié)點(diǎn)關(guān)系圖
 圖6-17是由6-16的二分圖轉(zhuǎn)化成的“Authority節(jié)點(diǎn)關(guān)系圖”，“Hub節(jié)點(diǎn)關(guān)系圖”與此類(lèi)似，兩者轉(zhuǎn)化過(guò)程是相似的，我們以“Authority節(jié)點(diǎn)關(guān)系圖”為例來(lái)看如何從二分圖轉(zhuǎn)化為節(jié)點(diǎn)關(guān)系圖。

圖6-17 Authority節(jié)點(diǎn)關(guān)系圖

 這里需要注意的是：Authority集合內(nèi)從某個(gè)節(jié)點(diǎn)i轉(zhuǎn)移到另外一個(gè)節(jié)點(diǎn)j的概率，與從節(jié)點(diǎn)j轉(zhuǎn)移到節(jié)點(diǎn)i的概率是不同的，即非對(duì)稱(chēng)的，所以轉(zhuǎn)換后的Authority節(jié)點(diǎn)關(guān)系圖是個(gè)有向圖，以此來(lái)表示其轉(zhuǎn)移概率之間的差異。
 對(duì)于圖6-17這個(gè)“Authority節(jié)點(diǎn)關(guān)系圖”來(lái)說(shuō)，圖中包含的節(jié)點(diǎn)就是二分圖中屬于Authority子集的節(jié)點(diǎn)，關(guān)鍵在于節(jié)點(diǎn)之間的邊如何建立以及節(jié)點(diǎn)之間轉(zhuǎn)移概率如何計(jì)算。

節(jié)點(diǎn)關(guān)系圖中邊的建立
 之所以在“Authority節(jié)點(diǎn)圖”中，節(jié)點(diǎn)3有邊指向節(jié)點(diǎn)5，是因?yàn)樵诙謭D中，由節(jié)點(diǎn)3通過(guò)Hub子集的節(jié)點(diǎn)6中轉(zhuǎn)，可以通達(dá)節(jié)點(diǎn)5，所以?xún)烧咧g有邊建立。
這里需要注意的是：在二分圖中，對(duì)于Authority集合內(nèi)某個(gè)節(jié)點(diǎn)來(lái)說(shuō)，一定可以通過(guò)Hub子集的節(jié)點(diǎn)中轉(zhuǎn)后再次返回本身，所以一定包含一條指向自身的有向邊。節(jié)點(diǎn)1因?yàn)橹挥兄修D(zhuǎn)節(jié)點(diǎn)2使得其返回Authority子集中自身節(jié)點(diǎn)，所以只有指向自身的一條邊，和其它節(jié)點(diǎn)沒(méi)有邊聯(lián)系，所以例子中的“Authority節(jié)點(diǎn)關(guān)系圖”由兩個(gè)連通子圖構(gòu)成，一個(gè)只有節(jié)點(diǎn)1，另外一個(gè)連通子圖由剩余幾個(gè)節(jié)點(diǎn)構(gòu)成。

節(jié)點(diǎn)之間的轉(zhuǎn)移概率
 至于為何“Authority節(jié)點(diǎn)關(guān)系圖”中，節(jié)點(diǎn)3到節(jié)點(diǎn)5的轉(zhuǎn)移概率為0.25，是因?yàn)榍懊娼榻B過(guò)，SALSA的權(quán)值傳播模型遵循“隨機(jī)游走模型”。在圖6-16的二分圖中，從節(jié)點(diǎn)3轉(zhuǎn)移到節(jié)點(diǎn)5的過(guò)程中，節(jié)點(diǎn)3有兩條邊可做選擇來(lái)跳轉(zhuǎn)到Hub子集，所以每條邊的選擇概率為1/2，可以選擇其中一條邊到達(dá)節(jié)點(diǎn)6，同樣，從節(jié)點(diǎn)6跳回到Authority子集時(shí)，節(jié)點(diǎn)6也有兩條邊可選，選中每條邊的概率為1/2。所以從節(jié)點(diǎn)3出發(fā)，經(jīng)由節(jié)點(diǎn)6跳轉(zhuǎn)到節(jié)點(diǎn)5的概率為兩條邊權(quán)值的乘積，即為1/4。
 對(duì)于指向自身的有向邊，其權(quán)重計(jì)算過(guò)程是類(lèi)似的，我們?nèi)匀灰怨?jié)點(diǎn)3為例，指向自身的有向邊代表從Authority子集中節(jié)點(diǎn)3出發(fā)，經(jīng)由Hub子集的節(jié)點(diǎn)再次返回節(jié)點(diǎn)3的概率。從6-16的二分圖可以看出，完成這個(gè)過(guò)程有兩條路徑可走，一條是從節(jié)點(diǎn)3到節(jié)點(diǎn)1返回；另外一條是從節(jié)點(diǎn)3經(jīng)由節(jié)點(diǎn)6后返回；每一條路徑的概率與上面所述計(jì)算方法一樣，因?yàn)閮蓷l路徑各自的概率為0.25，所以節(jié)點(diǎn)3返回自身的概率為兩條路徑概率之和，即為0.5。圖中其它邊的轉(zhuǎn)移概率計(jì)算方式也是類(lèi)此。
 建立好“Authority節(jié)點(diǎn)關(guān)系圖”后，即可在圖上利用“隨機(jī)游走模型”來(lái)計(jì)算每個(gè)節(jié)點(diǎn)的Authority權(quán)值。在實(shí)際計(jì)算過(guò)程中，SALSA將搜索結(jié)果排序問(wèn)題進(jìn)一步轉(zhuǎn)換為求Authority節(jié)點(diǎn)矩陣的主秩問(wèn)題，矩陣的主秩即為每個(gè)節(jié)點(diǎn)的相應(yīng)Authority得分，按照Authority得分由高到低排列，即可得到最終的搜索排序結(jié)果。

6.5.3Authority權(quán)值計(jì)算

                   圖6-18 SALSA節(jié)點(diǎn)權(quán)值計(jì)算公式

     經(jīng)過(guò)數(shù)學(xué)推導(dǎo)，可以得出SALSA與求矩陣主秩等價(jià)的Authority權(quán)值計(jì)算公式。圖6-18示意圖表明了SALSA算法中某個(gè)網(wǎng)頁(yè)節(jié)點(diǎn)的Authority權(quán)值是如何計(jì)算的。如圖右上角公式所示，決定某個(gè)網(wǎng)頁(yè)i的Authority權(quán)值涉及到4個(gè)因子：
 Authority子集中包含的節(jié)點(diǎn)總數(shù)|A|。其實(shí)這個(gè)因子對(duì)于Authority集合中任意節(jié)點(diǎn)來(lái)說(shuō)都是相同的，所以對(duì)于最終的根據(jù)節(jié)點(diǎn)Authority權(quán)值進(jìn)行排序沒(méi)有影響，只是起到保證權(quán)值得分在0到1之間，能夠以概率形式表示權(quán)值的作用；
 網(wǎng)頁(yè)i所在連通圖中包含的節(jié)點(diǎn)個(gè)數(shù)|Aj|。網(wǎng)頁(yè)所在的連通圖包含的節(jié)點(diǎn)個(gè)數(shù)越多，則網(wǎng)頁(yè)的Authority權(quán)值越大；
 網(wǎng)頁(yè)i所在連通圖中包含的入鏈總數(shù)|Ej|。網(wǎng)頁(yè)所在的連通圖包含的入鏈總數(shù)越少，則網(wǎng)頁(yè)的Authority權(quán)值越大；
 網(wǎng)頁(yè)i的入鏈個(gè)數(shù)|Bi|。節(jié)點(diǎn)入鏈越多，則Authority權(quán)值越大，這個(gè)因子是唯一一個(gè)和節(jié)點(diǎn)本身屬性相關(guān)的。由此可見(jiàn)，SALSA權(quán)值計(jì)算和節(jié)點(diǎn)入鏈個(gè)數(shù)成正比。
 之前圖6-17的“Authority節(jié)點(diǎn)關(guān)系圖”由兩個(gè)連通子圖組成，一個(gè)由唯一的節(jié)點(diǎn)1構(gòu)成，另外一個(gè)由節(jié)點(diǎn)3、5、6三個(gè)節(jié)點(diǎn)構(gòu)成，兩個(gè)連通子圖在圖6-18中也被分別圈出。
 我們以節(jié)點(diǎn)3為例，看其對(duì)應(yīng)的四個(gè)計(jì)算因素取值：
Authority子集共包括4個(gè)節(jié)點(diǎn)；
節(jié)點(diǎn)3所在連通圖包含3個(gè)節(jié)點(diǎn)；
節(jié)點(diǎn)3所在連通圖共有6個(gè)入鏈；
節(jié)點(diǎn)3的入鏈個(gè)數(shù)為2；
  所以，節(jié)點(diǎn)3的Authority權(quán)值為：（3/4）*(2/6)=0.25。其它節(jié)點(diǎn)權(quán)值的計(jì)算過(guò)程與此類(lèi)似。SALSA根據(jù)節(jié)點(diǎn)的Authority權(quán)值由高到低排序輸出，即為搜索結(jié)果。
 由上述權(quán)值計(jì)算公式可以推論出：如果整個(gè)Authority子集所有節(jié)點(diǎn)形成一個(gè)完整的連通圖，那么在計(jì)算authority權(quán)值過(guò)程中，對(duì)于任意兩個(gè)節(jié)點(diǎn)，4個(gè)因子中除了節(jié)點(diǎn)入鏈個(gè)數(shù)外，其它三個(gè)因子總是相同，即只有入鏈個(gè)數(shù)起作用，此時(shí)，SALSA算法退化為根據(jù)節(jié)點(diǎn)入鏈個(gè)數(shù)決定排序順序的算法。
 從SALSA計(jì)算Authority得分過(guò)程中可看出，SALSA算法不需像HITS算法一樣進(jìn)行不斷迭代計(jì)算，所以從計(jì)算效率角度看要快于HITS算法。另外，SALSA算法解決了HITS算法的計(jì)算結(jié)果主題漂移的問(wèn)題，所以搜索質(zhì)量也優(yōu)于HITS算法。SALSA算法是目前效果最好的鏈接算法之一。