一種基於冪率分布的連結相似度快速計算系統和方法

2023-06-03 08:59:06

專利名稱：一種基於冪率分布的連結相似度快速計算系統和方法
技術領域：
本發明涉及相似度計算領域，尤其是涉及一種基於冪率分布的連結相似度快速計 算系統和方法。
背景技術：
目前的實際應用中，相似度計算是在信息檢索領域，協同過濾領域，聚類領域等不 可或缺的重要環節。舉例來說，在一個網上書店購書時，系統會將與用戶已經購買圖書相似 的數目列表按照相似的程度推薦給用戶，其中就涉及相似度計算。典型的相似度計算主要分為基於內容的相似度計算和基於連結的相似度計算。基 於內容相似度計算的代表方法為向量空間模型，用向量之間夾角的餘弦值來衡量對象之間 的相似程度。基於連結相似度計算的代表方法為SimRank，通過迭代計算的相似度得分來衡 量對象之間的相似程度。然而，現實世界中的許多數據，並沒有給出或者並不關注對象的內 容，而是對對象之間的聯繫特別感興趣，並期望通過連結關係來獲得對象之間的相似度，這 就是連結相似度計算所面對的主要問題，也是本發明所面向的領域。對於計算連結相似度來說，這個想法首先由史丹福大學的研究者提出，基於隨機 遊走的理論基礎，基於的假設為「如果兩個對象指向了相似的對象，則這兩個對象很可能相 似」。這樣如果將現實的數據抽象為圖以及節點之間的關係，各個節點對的得分實際上就是 它們在圖中分別碰面的概率和。但基於連結的相似度計算存在一個明顯的缺陷時間複雜 度過高。對於一個包含10000個節點和30000條邊的圖來說，目前主流PC機的計算時間可 能會超過5個小時。對有更大圖結構的計算，將不得不忍受漫長的計算過程。在實際的相似度計算過程中，人們往往只關心哪些對象最相似，而不是關心哪些 對象不相似。現實的數據只要規模達到一定程度往往會服從冪率分布，相似度值也是如此， 即絕大多數節點對的相似度得分都比較低，只有少數節點對的相似度得分非常高。這樣在 各個節點對相似度迭代計算的過程中關注少數得分高的節點對將無疑在提升性能的同時 避免過多的精確度損失。

發明內容
根據本發明的一個方面，提供了一種基於冪率分布的連結相似度快速計算方法， 包括A、輸入一個圖，所述圖結構包含多個節點之間的連結情況；B、對所述圖中的冪率分布特性進行分析及處理；C、迭代計算所述圖中的各個節點對的相似度。D、當相鄰兩次計算的結果收斂和/或所述結果的接近程度已經達到用戶的要求 時，完成迭代循環過程。根據本發明的另一個方面，提供了一種基於冪率分布的連結相似度快速計算系 統，其特徵在於包括
輸入單元，用於輸入一個圖，所述圖結構包含多個節點之間的連結情況；分析處理單元，用於對所述圖中的冪率分布特性進行分析和處理；迭代計算單元，用於對所述圖中的各個節點對之間的相似度進行迭代計算；判斷收斂單元，用於當相鄰兩次計算的結果收斂和/或所述結果的接近程度已經 達到用戶的要求時終止迭代循環過程。


結合隨後的附圖，從下面的詳細說明中可顯而易見的得出本發明的上述及其他目 的、特徵及優點。在附圖中圖1給出了根據本發明的基於冪率分布來快速計算連結相似度的方法的流程圖；圖2給出了根據本發明的對圖中冪率分布特性進行分析及處理的流程圖；圖3給出了根據本發明的兩種方法性能比較的具體情況；圖4給出了根據本發明的基於冪率分布來快速計算連結相似度的系統的方框圖；圖5給出了根據本發明的分析處理單元的詳細方框圖；圖6給出了能夠實施本發明的一個示例環境的示意圖。
具體實施例方式本發明的一個基本構思在於關於連結相似度的假設「如果兩個對象指向了相似 的對象，則這兩個對象很可能相似」和定義將會予以保留，這保證了本發明所得到的結果的 合理性；同時通過避免大量沒必要的計算，從而以較小的精確度損失換來較大的性能提升。 本發明的一個目的是提出一種基於冪率分布來快速計算連結相似度的系統和方法。為了更全面地理解本發明及其優點，下面結合附圖及具體實施例對本發明做進一 步詳細地說明。首先，參考圖1，對根據本發明的基於冪率分布來快速計算連結相似度的方法進行 說明。如圖1所示，基於冪率分布來快速計算連結相似度的方法包括步驟A、輸入一個圖結構(步驟101)。該圖結構一般是以鄰接表的形式給出，例如有一 個包含10000個節點的圖，與之對應的鄰接表包含10000行，每行包含特定節點與其它節點 的連結情況。這個鄰接表可以存放在文件中，也可以直接置於內存中。B、對圖中的冪率分布特性進行分析及處理(步驟102)。因為大量的現實數據符合 冪率分布，並且我們關心的是哪些節點最相似。所以我們先按照正常的相似度計算方法迭 代計算若干次，此時不同的節點對將被賦予不同的得分。一般來說是這樣的，目前的得分低 的節點對在迭代計算收斂時的得分往往很低。於是對所有節點對的得分進行升冪排序，例 如，得分較小的前80%的節點對將被鎖定，以後只計算得分較大的20%節點對直到收斂。 這無疑會大大降低每次迭代計算的時間。隨後參考圖2，對該步驟進一步進行詳細說明。C、迭代計算各個節點對的相似度(步驟103)。每進行一次迭代，就會對該圖中的 任意兩個節點之間的相似度進行更新，這個過程是循環的，第K次循環的結果將作為第K+1 次循環的輸入。D、當相鄰兩次計算的結果收斂，或其接近程度已經達到用戶的要求，完成迭代循環過程(步驟104)。接下來，參考圖2，進一步說明對圖中的冪率分布特性進行分析及處理的過程。圖 2給出了根據本發明的對圖中的冪率分布特性進行分析及處理的流程圖。如圖2所示，對圖中的冪率分布特性進行分析及處理的步驟包括B1、前r次迭代計算各節點對的相似度(步驟201)。具體地說，在前r次迭代計 算的過程中按常規計算各個節點對的相似度。這裡基於一個假設如果在圖中兩個節點可 達，則它們之間可以通過圖中的六條邊可達，這就是著名的六度可達理論。這樣我們在前六 次按常規迭代計算各個節點對的相似度值。B2、對所有節點對的相似度值進行升冪排序(步驟202)。通過前一步計算出各個 節點對的相似度值，然後對這些節點對的相似度值從小到大進行升冪排序。B3、將升冪排序中的某點定為閾值(步驟203)。通過前一步對節點對的相似度值 進行升冪排序後，根據80-20原則(例如社會上前20%人的財富總量佔社會總財富的80% 左右)，將20%的節點對對應的得分設為閾值，在後續的計算中參照此閾值。B4、對相似度值小於閾值的部分進行標記(步驟204)。通過前一步得到閾值，在此 步驟中各個節點對的相似度值均與該閾值作比較，小於該閾值的相似度點對將被置標記， 在後續的計算中鎖定此相似度值。B5、對後期的迭代計算只更新未標記的節點對(步驟205)。接下來的迭代計算過 程只計算為被標記的節點對，因為大部分節點對在前面的計算中都被標記，這將大大提升 性能，避免不必要的計算。這個過程直到迭代計算滿足收斂條件終止。在這個方面中，其中圖結構採用鄰接表形式。在這個方面中，其中在步驟C中每進行一次迭代，就會對該圖中的任意兩個節點 之間的相似度值進行更新，這個過程是迭代的，第K次循環的結果將作為第K+1次循環的輸 入。現在，參考圖3，該圖給出了兩種方法性能比較的具體情況。在這個給定的數據集中我們很容易發現在前6次的迭代計算過程中，原方法和改 進方法每次迭代的計算時間幾乎相同。但是從第7次迭代計算開始改進方法每次迭代計算 的時間大概為原方法的五分之一，並且改進方法的收斂速度很快。從圖中我們可以看出經 過25次迭代計算改進的方法收斂，而原方法需要經過46次迭代計算才收斂。計算時間由 每次迭代計算的時間和迭代次數共同確定。通過計算，改進的方法在性能上的提升大概為 400%。接下來，參考圖4，對根據本發明的基於冪率分布來快速計算連結相似度的系統進 行詳細地描述。如圖4所示，根據本發明的基於冪率分布來快速計算連結相似度的系統包括輸 入單元401、分析處理單元402、迭代計算單元403、以及判斷收斂單元404。輸入單元401用於輸入一個圖結構(該單元401與輸入一個圖結構101的作用相 同)。該圖結構一般是以鄰接表的形式給出，例如有一個包含10000個節點的圖，與之對應 的鄰接表包含10000行，每行包含特定節點與其它節點的連結情況。這個鄰接表可以存放 在文件中，也可以直接置於內存中。分析處理單元402用於對該圖結構中的冪率分布特性進行分析和處理(圖2的整)。該單元402首先通過正常的相似度計算方法迭代計算若 幹步，這裡基於一個假設根據小世界理論，一般來說任意兩點會通過六步可達。所以說通 過前若干次迭代計算後相似度值的變化不會很明顯，並且我們的目的是為了得到哪些節點 對最相似。然後我們對前若干次迭代得出的相似度值進行排序，根據需要設定一個合理的 閾值，大於此閾值的得分會在後續的迭代計算中不斷更新，小於閾值的得分將會被鎖定。迭代計算單元403，用於通過迭代來計算各個節點對之間的相似度。每進行一次迭 代，就會對該圖中的任意兩個節點之間的相似度進行更新，這個過程是循環的，第K次循環 的結果將作為第K+1次循環的輸入。判斷收斂單元404，用於當相鄰兩次計算的結果收斂或其接近程度已經達到用戶 的要求時終止迭代循環過程。接下來，參考圖5，分析處理單元進一步包括前r次迭代計算模塊501、相似度值排 序模塊502、閾值設定模塊503、判斷及標記模塊504以及後期迭代計算模塊505。前r次迭代計算模塊501用於前r次按照既定的步驟迭代計算連結相似度。具體 地說，在前r次迭代計算的過程中按常規計算各個節點對的相似度。根據一個具體實施方 式，這裡基於一個假設如果在圖中兩個節點可達，則它們可以通過圖中的六條邊可達，這 就是著名的六度可達理論。這樣我們在前六次按常規迭代計算各個節點對的相似度值。相似度值排序模塊502用於對前r次各個節點對的相似度值進行排序。通過前一 步計算出各個節點對的相似度值，然後對這些節點對的相似度值從小到大進行升冪排序。閾值設定模塊503用於通過對相似度值進行排序後將從大到小例如20%的節點 對應的值設定為閾值。通過前一步對節點對的相似度值進行升冪排序後，根據80-20原則 (例如社會上前20%人的財富總量佔社會總財富的80%左右)，將20%的節點對對應的得 分設為閾值，在後續的計算中參照此閾值。判斷及標記模塊用於判斷節點對的相似度值是否小於閾值，若小於閾值則對其節 點對標記。通過前一步得到閾值，在此步驟中各個節點對的相似度值均與該與之作比較，小 於閾值的相似度點對將被置標記，在後續的計算中鎖定此相似度值。後期迭代計算模塊用於迭代計算節點對的相似度值，遇到被標記的節點對則跳至 下一節點對的計算。接下來的迭代計算過程只計算為被標記的節點對，因為大部分節點對 在前面的計算中都被標記，這將大大提升性能，避免不必要的計算。這個過程直到迭代計算 滿足收斂條件終止。圖6顯示了根據本發明的一個實施例的基於冪率分布的連結相似度快速計算系 統的硬體結構。如圖6所示，該基於冪率分布的連結相似度快速計算系統包括CPU核心器件單元， 其中該CPU核心器件單元包含了 CPU 601、主機控制器602、ROM 603、RAM 604、以及輸入/ 輸出控制器607。該計算機還包括通信接口 609、存儲設備608、光碟機610、以及圖形控制器 606。主機控制器602依照存儲在ROM 603,BIOS以及RAM 604中的程序來操作，並且由 此控制系統的各個部分。圖結構數據可通過多種輸入設備輸入，如存儲設備(硬碟，快閃記憶體)， 光碟機，鍵盤輸入或通過網絡傳輸。在邏輯結構上，這種圖結構數據有多種表現形式，最常見 的是鄰接矩陣表示方法和鄰接表表示方法。圖結構隨後會被讀入存儲設備608。存儲設備
7608還存儲供連結相似度快速計算系統使用的本發明的程序、應用、作業系統等等的代碼和 數據。此後，所讀取的程序和數據將被加載到RAM 604中以供CPTO01使用。從上述結構實例中可以看出，任何具有通用計算機功能的硬體都可以用作本發明 需要的硬體。應該指出的是，圖6僅示出了本發明的基於冪率分布的連結相似度快速計算 系統的一個實施例的硬體結構。相應地，對其他各種結構的本發明實施例也是可行的。此 外，圖6所示的實施例的組件並不全是本發明的必要組件(如光碟機610和通信接口 609並 不是本發明的必要組件)。至此，已結合實施例對本發明進行了描述。與同類方法橫向比較，本發明提出的方 法可以避免大量沒必要的計算，從而大幅提升性能，這是最大的優點。其次，本發明建立在 合理的理論模型上，以較小的精確度損失換來較大的性能改善。對於本領域的普通技術人員來說可顯而易見的得出其他優點和修改。因此，具有 更廣方面的本發明並不局限於這裡所示出的並且所描述的具體說明及示例性實施例。因 此，在不脫離所附權利要求書及其等價體所限定的一般發明構思的精神和範圍的情況下， 可對其做出各種修改。
權利要求
基於冪率分布的連結相似度快速計算方法，包括A、輸入一個圖，所述圖結構包含多個節點之間的連結情況；B、對所述圖中的冪率分布特性進行分析及處理；C、迭代計算所述圖中的各個節點對的相似度；D、當相鄰兩次計算的結果收斂和/或所述結果的接近程度已經達到用戶的要求時，完成迭代循環過程。
2.根據權利要求1的方法，其特徵在於所述步驟B進一步包括 Bi、迭代計算所述各節點對的相似度；B2、對所有節點對的相似度值進行升冪排序； B3、將升冪排序中的一個預定點定為閾值； B4、對其相似度值小於所述閾值的部分進行標記； B5、只對未標記的節點對進行更新迭代計算。
3.根據權利要求1的方法，其中所述圖採用鄰接表形式。
4.根據權利要求1或2的方法，其中在所述步驟C中，每進行一次迭代都對所述圖中的 任意兩個節點之間的相似度進行更新，該更新過程是循環的，其中第K次循環的結果將作 為第K+1次循環的輸入。
5.根據權利要求2的方法，其特徵在於在所述步驟Bl中迭代計算所述各節點對的相似度的操作是在前N次迭代操作中進行 的，且N的取值為6;所述閾值被設定為對相似度值進行排序後從小到大80%處的節點所對應的值。
6.一種基於冪率分布的連結相似度快速計算系統，其特徵在於包括 輸入單元，用於輸入一個圖，所述圖結構包含多個節點之間的連結情況； 分析處理單元，用於對所述圖中的冪率分布特性進行分析和處理；迭代計算單元，用於對所述圖中的各個節點對之間的相似度進行迭代計算； 判斷收斂單元，用於當相鄰兩次計算的結果收斂和/或所述結果的接近程度已經達到 用戶的要求時終止迭代循環過程。
7.根據權利要求6的系統，其特徵在於所述分析處理單元進一步包括 迭代計算模塊，用於迭代計算所述節點對的相似度；相似度值排序模塊，用於對各個節點對的相似度值進行排序； 閾值設定模塊，用於將所述相似度值的排序中的一個預定點定為閾值； 判斷及標記模塊，用於判斷節點對的相似度值是否小於所述閾值，並對其相似度值小 於所述閾值的節點對進行標記；後期迭代計算模塊，用於迭代計算節點對的相似度值，其中遇到被標記的節點對則跳 至下一節點對的計算。
8.根據權利要求6或7的系統，其中所述圖具有鄰接表形式。
9.根據權利要求6的系統，其特徵在於所述計算單元每進行一次迭代，就會對該圖中 的任意兩個節點之間的相似度進行更新，該更新過程是循環的，第K次循環的結果將作為 第K+1次循環的輸入。
10.根據權利要求7的系統，其特徵在於在所述迭代計算模塊進行的所述各節點對的相似度的迭代計算操作是在前N次迭代操作中進行的，且N的取值為6 ；所述閾值被設定為對相似度值進行排序後從小到大80%處的節點所對應的值。
全文摘要
基於冪率分布的連結相似度快速計算的系統和方法，其中該方法包括步驟輸入一個圖結構；對該圖結構中的冪率分布特性進行分析及處理；通過迭代計算各個節點對的相似度；當相鄰兩次計算的結果收斂，或其接近程度已經達到用戶的要求，完成迭代循環過程。本發明保證精度損失上界的同時性能顯著提升。
文檔編號G06F17/30GK101853281SQ20101017902
公開日2010年10月6日 申請日期2010年5月20日 優先權日2010年5月20日
發明者何軍, 劉紅巖, 杜小勇, 蔡元哲, 賈旭 申請人:清華大學