用於對圖數據流中的對象分類的方法

2023-07-21 22:06:06 2

專利名稱：用於對圖數據流中的對象分類的方法
技術領域：
本發明涉及大規模圖流(graph stream)的分類。
背景技術：
在機器學習中，分類是將類別標籤指派給輸入對象。分類發生於若干領域(諸如，化學及生物數據、web及通信網路)的情境下。作為示例，web查詢主題分類/歸類涉及基於查詢的主題將web搜尋查詢(例如，輸入對象)指派給一個或多個預定義的類別(例如，類別標籤)。舉例而言，發出web查詢「蘋果」的用戶可能期望看到與水果蘋果相關的網頁，或其可能更願意看到與該計算機公司相關的產品或新聞。可根據由一查詢分類算法預測的種類來對搜尋結果頁進行分組。許多數據域(諸如，化學數據、生物數據及web)被結構化為圖。在化學及生物領域中，可從適度的概率庫取得圖的節點，且假定數據集具有適度的大小。另一方面，可在大規模的基礎節點全域上定義web圖、通信網絡及社交網絡。具有IO7以上的節點的圖可含有多達IO13個邊，且由此被視為大規模的。這些節點可對應於web圖中的URL地址、通信網絡中的IP位址或社交網絡中的用戶標識符。這些URL地址、IP位址及用戶標識符之間的連結為邊。在流傳輸應用中，將在某一外部環境中產生的數據異步地推送至處理此信息的伺服器。流傳輸應用的特徵為以及時及響應的方式處理高容量數據流的能力。大規模圖流可包括用戶在社交網絡中的通信模式(pattern)、所有用戶的瀏覽模式或通信網絡上的侵入通信流(traf f i c )。當大規模圖呈流形式時，這限制了可用以挖掘結構信息以用於未來分析的算法的種類。舉例而言，流約束僅允許在數據上執行一遍。此外，圖的邊可能在數據流中無序地到達。圖的大規模尺寸也對有效提取與分類相關的信息產生挑戰。舉例而言，難以在圖數據中存儲關於大量相異邊的概要信息。此外，由於結構行為是由大量相異邊的組合控制的，因此子結構判定問題的複雜性的指數級增加隨著子結構的基數而極為快速。在這樣的情況下，頻繁的辨別性子圖的判定可在計算及空間上效率低下至不能實行的程度。

發明內容
本發明的例示性實施例提供用於分類圖數據流中的對象的方法及電腦程式產品。該圖數據流可包括表示元素的多個節點及表示這些元素之間的連接的邊。該數據流中的對象可為一組節點連同這些節點之間的邊。在一例示性方法中，接收圖數據的訓練流，其中該訓練流包括多個對象連同與這些對象中的每一個相關聯的類別標籤。判定該訓練流中的用於類別標籤的辨別性邊集合(例如，子圖)，其中一辨別性邊集合為指示(但並非直接對應於)具有給定類別標籤的包括這些邊的對象的邊集合。接著接收該圖數據的一傳入數據流，其中尚未將類別標籤指派給該傳入數據流中的對象。基於這些辨別性邊集合，判定與該傳入數據流中的對象相關聯的類別標籤。將基於該第二判定的對象類別標籤對輸出至一信息儲存庫。


圖1示出大規模圖的部分；圖2示出根據本發明的一例示性實施例的用於分類圖數據流中的對象的方法的流程圖；圖3示出根據本發明的一例示性實施例的用於更新圖數據流的每一傳入邊的min-hash (最小哈希)索引的算法；圖4示出對應於圖3中所示出的算法的部分的流程圖；圖5示出根據本發明的一例示性實施例的用於通過列壓縮更新用於圖數據流的每一傳入圖的min-hash索引的算法；圖6示出對應於圖5中所示出的算法的部分的流程圖；以及圖7示出用於實施本發明的例示性實施例的裝置。
具體實施例方式下文將描述根據本發明的一例示性實施例的用於分類圖數據流中的對象的方法。該圖數據流可為大規模的。該對象可包括圖的節點及邊，這些節點及邊標識web衝浪的模式。舉例而言，受訪網站為節點，且自一個網頁至另一網頁的路徑為邊。因此，訪問網頁I且接著訪問網頁2且接著訪問網頁3的用戶很可能為具有某一屬性(即，很可能購買特定書籍)的用戶。本發明旨在識別這些模式，且接著將相關標籤指派給這些模式。為達成此目的，首先判定存在於圖數據的訓練流中的辨別性子圖，接著給予其類別標籤。簡言之，以減少傳入數據至小空間中的的二維(2D)哈希壓縮技術來判定相關的邊集合。接著，判定用於相關邊集合的主要類別標籤，且將其給予相應子圖作為最終類別標籤以獲得辨別性子圖。可接著使用這些辨別性子圖來推斷測試圖流中的對象的類別標籤。舉例而言，在於流處理器處接收到包括反映上述web衝浪模式的對象的測試數據流的情況下，可訪問包括辨別性子圖及其相關聯的類別標籤的存儲器以尋找對應於傳入對象的這些子圖。將傳入對象所對應的子圖的類別標籤給予該對象。在此情況下，類別標籤可指示該對象對應於很可能要購買特定書籍的用戶的模式。圖1示出大規模圖的部分。在此示例中，示出web圖100。然而，該大規模圖可為通信網絡、社交網絡等的圖。如圖1中所示，web圖100包括多個節點A — P及邊(即，這些節點之間的箭頭)。在圖1中僅示出web圖100的部分，因為web圖100可含有(例如)IO7個以上的節點及IO13個以上的邊。web圖100的節點A — P可表示網頁，且web圖100的邊可表示這些網頁之間的超連結。web圖100的連結結構保持了可用於多種數據挖掘目的的大量信息。舉例而言，經由挖掘而識別的web瀏覽模式可由政府使用以對威脅進行分類且對抗恐怖主義，或由公司使用以通過將其客戶所需準確地給予客戶來建立更好的客戶關係。圖2為根據本發明的一例示性實施例的用於分類圖數據流中的對象的方法的流程圖。返回參看圖1，對象可為一組節點A — P連同其邊。舉例而言，對象可包括節點A及B以及其間的單一邊，或更多得多的節點及其間的邊。如圖2中所示出，流處理器接收來自web圖100的數據訓練流(210)。該流處理器可為能夠執行諸如由紐約阿蒙克市的國際商業機器公司提供的InfoSphere Streams (先前稱為System S)的實時流處理平臺的計算環境。關於InfoSphere Streams 的細節提供於各種IBM 出版物中，包括(例如)2010年2月出版的Roger Rea及KrishnaMamidipaka 等人的題為 「IBM InfoSphere Streams, Redefining Real Time Analytics」的出版物。InfoSphere Streams 平臺使用被稱為流處理語言(SPL ;以前稱為SPADE)的高階程式語言。SPADE 描述於 「SPADE: System S Declarative Stream ProcessingEngine」(Gedik 等人，SIGM0D，2008 年 6 月 9 日至 12 日，第 1123-1134 頁)中。關於 SPL 的進一步細節描述於題為「SPL Stream Processing Language Specification」的IBM 研究報告(Hirzel 等人，RC24897 (W0911-044)，2009 年 11 月 5 日)中。InfoSphere Streams 及流處理語言支持可橫跨若干計算節點的分布式數據流處理應用。在一示例中，使用流處理語言聲明性語言以對這些多運算符應用進行編程。流處理語言的以流為中心的設計意味著基礎構建塊為流的語言。流處理語言的基於運算符的編程聚焦於圍繞最小可能的構建塊來設計應用，所述最小可能的構建塊是提供一應用被設計為執行的計算所必需的。在步驟210中接收的圖數據的訓練流含有多個對象連同與這些對象相關聯的類別標籤。流中的個別對象可由圖G1...Gn...表示。每一圖Gi與自中取得的類別標籤Ci相關聯。web圖100可被定義於節點集合N上。流中的數據按順序到達流處理器。舉例而言，數據可如以下方式到達:〈GraphIdXEdgeXClassLabel>。假定在流中，類別標籤始終附加至圖標識符。圖Gi的邊可能在流中無序地出現。對於諸如社交網絡及通信網絡的許多應用而言，一般都是這種情況，因為人們不能控制跨越不同邊的消息及通信的排序。變量(Edge)的值由其兩個構成節點定義。作為流中的一些數據的一示例，考慮標識符對應於侵入發生時的時間戳的網絡侵入應用。該侵入可誘發對應於子圖的一邊集合。因此，圖的標識符可為時間戳。邊可含有攻擊者及受害者的源及目的地IP位址。類別標籤可為侵入的類型(例如，「拒絕服務」攻擊)。響應於接收到圖數據的訓練流，判定該訓練流中用於類別標籤的辨別性邊集合(例如，子圖)(220)。在此步驟中，首先尋找相關的邊集合，接著將類別標籤給予這些相關的邊集合以獲得辨別性邊集合。舉例而言，首先尋找對應的共同發生的邊(作為一組)的出現遠高於統計預期的子圖。這種子圖在以下論述中被稱為顯著子圖。接著，判定傾向於辨別為特定類別的子圖。在論述如何找到並將類別標籤給予相關邊集合以獲得辨別性邊集合之前，現將介紹一些相關表示法及定義。顯著子圖P被定義為在其構成邊的相對頻率方面具有顯著統計出現率。這被稱為邊內聚性(coherence)。形式上如下定義此概念。令f fl (P)為G1...Gn中的圖的部分,在該部分中存在P的所有邊。令fU (P)為圖的部分，在該部分中存在P的邊中的至少一個或多個。於是，子圖P的邊內聚性C(P)由f n (P)/f U (P)表示。邊內聚性的此定義聚焦於子圖模式的相對出現率而非絕對出現率。這確保了僅找到顯著子圖。這也確保了不考慮具有高頻率但具有低顯著性的大量不相關模式。
如下定義邊集合P相對於類別標籤r E {1...m}的類別置信度。在含有子圖P的所有圖中，令s(P，r)為屬於類別標籤r的部分。此部分為模式P相對於類別r的置信度。接著如下定義用於特定子圖的主要類別置信度。主要類別置信度DI (P)或子圖P被定義為跨越所有不同類別的最大類別置信度。用於特定測試實例的DI (P)的顯著大值指示模式P對分類非常相關，且對應的主要類別標籤可為用於測試實例標籤的良好候選者。為了判定在絕對出現率方面引起興趣且對於特定類別有辨別性的子圖，也使用對應於邊內聚性及類別興趣率(class interest ratio)上的閾值參數的參數對(a，0 )。如果子圖P滿足以下兩個邊內聚性及類別辨別性約束，則可稱圖P為(a，0)顯著的。子圖P的邊內聚性C(P)至少為a。C(P)彡a。主要類別置信度DI (P)至少為0。DI (P)彡0。為了找到相關邊集合，根據本發明的一例示性實施例，使用2D哈希壓縮技術。此技術使用可判定用於分類的最相關辨別性子圖的可連續更新的數據結構。因為數據結構是小的，所以可將其維護於主存儲器中，且在傳入數據流到達期間的任何時刻使用。為了易於論述，該數據結構可為具有N個行及n個列的圖數據集的表狀二進位表示。N個行對應於存在於數據中的N個不同圖。列表示數據中的不同邊；然而，此並非一對一映射。n的選擇取決於在主存儲器中可用於保持表的空間。可根據本發明使用兩種2D哈希壓縮技術。一種僅在行上使用min-hash壓縮，其中每一列對應於相異邊。且一種通過使用常規哈希函數將多個列映射至單個列中，接著在行上使用min-hash壓縮。現將論述第一種技術。此min-hash方案的要旨為通過在數據中的行上使用排序順序來判定不同列上的值的共同發生。為了產生此排序順序，為數據中的每一行產生單個均勻隨機哈希值。按此哈希值的順序排序數據中的所有列。注意，這種方法導致以完全相同的隨機順序排序每一列。因此可觀測到以下情形。

考慮一 P邊的集合。令P』為對應於P的表中的列。以按哈希值排序的順序檢查這些列。針對P』中的每一列的具有I值的第一行的索引相同的概率等於邊內聚性C(P)。容易驗證上述觀察，因為P』中的任一列中具有I的第一行的索引也是P』的任一邊在其中存在的第一行。此行跨越相關列含有所有I值的概率為邊內聚概率C(P)。此方法可用於建構邊內聚概率的採樣估計。舉例而言，k個不同哈希值可用於建構排序順序，且可通過計算針對其所有值為I的k個樣本的比率來估計上述概率。現在，將論述使用完整表的第一技術的實施。在此情況下，假定該表具有E個列，其中E=N (N-1) /2為數據中可能相異的邊的數目。使用min-hash索引以建構基礎數據的事務表示。為進行此操作，首先以k個不同哈希值應用min-hash方法以產生具有k X E大小的表。現在，檢查來自此min-hash表示的特定樣本。令iv..rE為在對應列中具有I的第一行的行索引。接著，將集合A...rE分區到min-hash索引值相同的組。由此,如果將iv.rE分區到Q1...Qh，則每一 ri G 具有相同值(對於固定j)。對於每一分區％，產生含有對應列的索引的分類事務。舉例而言，如果Qj= Ir2, r23, r45, r71},則產生事務Tj= {2，23，45，71}。最後，建構對應於同索引分區Q1.Qh的事務T1...Th。因為每一索引集合產生一對應事務集合,因此可通過重複此採樣過程k次並產生k個不同索引集合來改良估計過程的精確性。舉例而言，對於每一索引集合，將對應事務集合添加至總事務集合T。進行以下觀測。
令T為自min-hash索引集合建構的事務。於是，邊集合P的內聚概率C (P)可被估計為事務集合T中的P』的絕對支持(absolute support)除以k。將具有高內聚概率C(P)的邊判定為相關邊集合。此觀測為先前觀測的直接擴展。這是因為若且唯若P』中的邊的min-hash索引在從其建構事務的對應min-hash樣本中為相同的情況下,列集合P』支持T1...Th中的事務。注意，在一給定時間，表示特定圖中的邊出現的表的行可能不可用。這是因為在流場景中用於給定圖的邊可並不連續地到達。此外，數據通常為非常稀疏的，表中的大部分值為O。因此，本發明使用可在稀疏無序邊情況下工作的新穎更新過程。此過程的一示例由圖3中的算法300示出。如圖3中所示，對於流中的每一傳入圖邊e G G(具有圖標識符Id(G)),產生k個隨機哈希值h(l, Id(G))...h(k, Id(G))。第i個哈希值h(i, Id(G))由Pi表示。哈希函數h(*, )使用Id(G)作為輸入，因此當在流中的稍後階段遇到來自相同圖G的邊時可產生相同隨機哈希值。為了產生隨機哈希值，可在對應於h(*， )的兩個參數的字符串的串接上使用標準哈希函數。令L為至此在流中已遇到的相異邊的數目的動態(running)估計。算法300維護k L個動態最小哈希值的集合V連同k L個對應圖標識符(針對其獲得這些最小值)的集合I。L的值將在數據流的進展期間隨著愈來愈多的相異邊由該流接收而增大。V中的每一項呈(e, MinHashValue)的形式,且I中的每一項呈(e, Graphldentifier)的形式。對於至此在數據流中遇到的每一相異邊，V及I中均存在k個這樣的項。對於每一邊e，V中的第i個最小哈希樣本表示含有e的所有圖G上的h(i，Id(G))的最小值。I中用於特定邊e的k個項表示k個圖標識符(針對其獲得V中的這些最小值)。因為流中的邊可能無序地出現，所以通過應用算法300，每一邊與流中其對應的圖標識符相關聯。在此情況下，對於每一傳入邊e及圖標識符Id(G)，由算法300如下更新集合V及I。產生k個不同哈希值P1=Iid, Id(G))...pk=h(k, Id(G))。在至此尚未遇到邊e的情況下，在V及I中將 不存在其信息。在這種情況下，遞增L的值，且將用於e的對應項分別包括於V及I中。具體言之，將V中用於此新跟蹤到的邊的k個哈希值設定為k個最近產生的哈希值P1...pk。因此，將項(e，P1)...(e，pk)包括於V中。相應地，將項(e, Id(G))...(e，Id(G))添加至V。另一方面，如果已經在流中遇到邊e，則在V中檢查對應項(e, MinHashValue1) ..(e, MinHashValuek)。在新產生的哈希值 Pi 小於 MinHashValuei的情況下，則由(e, Pi)替代(e, MinHashValuei)。另外，I中的對應項由(e, Id(G))替代。圖4為示出更新用於每一傳入邊的min-hash索引的過程的流程圖，其反映圖3中的算法300的部分。具體言之，圖4示出每一傳入圖流所需的步驟。在步驟410中，產生用於每一行的k個隨機哈希值，其中該行本質上是流中的傳入圖。該k個隨機哈希值在圖3中也被稱為P1...Pk。在步驟420中，更新用於每一行的min-hash索引。在步驟430中，更新用於每一行的min-hash值。僅在所產生min-hash值低於其當前值的情況下才執行這些更新。由圖3的最內循環執行此產生步驟。如可見的，參考圖3及圖4論述的過程連續地維護傳入圖的概要表示。因為這些概要統計維護於主存儲器中，所以可在任何時間對其加以利用以判定內聚邊模式，也即，相關邊集合。
注意，在使用圖3的算法300的情況下，主要常項為概要統計V及I具有大小0(k L)，其中L為至此已遇到的相異邊的數目。此處的問題在於，由於本公開中所論述的大規模圖假定，L的值可能非常大。可能並不容易在盤上或主存儲器中維護如此大的概要，而這對於此場景中的高效更新過程來說是需要的。因此，以圖5中的算法500所示出的過程來補充圖3的min-hash行壓縮算法300。圖5中所示出的過程為第二 min-hash技術,其使用列壓縮以減小數據結構的大小。這導致同時的行及列壓縮，但以不同於圖3中的列壓縮方式執行圖5中的列壓縮。圖5的算法500類似於圖3的算法300，只是首先通過使用一均勻隨機哈希函數將數據中的每一邊映射至範圍[l，n]中的一整數，且接著應用圖3的算法300的步驟。因此，在此情況下，判定範圍 [l，n]中的整數上的模式，而不是判定實際邊上的模式。另外，就使用列壓縮大小n作為輸入且使用它將每一邊映射至[l，n]中的整數的意義而言，圖5的算法500不同於圖3的算法。在算法300中，通過使用均勻哈希函數來完成此映射。通過串接兩端的節點標籤來建構邊的字符串表示。接著將哈希函數應用至此字符串表示。可基於存儲考慮來挑選n的值，且其通常遠低於相異邊的數目。N的選擇產生於存儲大小與精確度之間的取捨。因為多個邊可映射至同一整數，所以此方法可能造成計算精確度的一定程度的進一步降級。然而，列壓縮方案以相對小的質量降級顯著減小了空間需求。圖6中為示出通過列壓縮更新用於每一傳入圖的哈希索引的方法的流程圖，該流程圖反映圖5的算法500的部分。除了將邊映射至更有限的哈希值集合以外，此流程圖類似於圖4中所示出的流程圖。這樣做是因為相異邊的數目可能過大以致不能跟蹤所有相異邊的哈希值。如圖6中所示出的，在步驟610中，以常規哈希函數將邊映射至一有限偽列集合。隨後的步驟類似於圖4中的那些步驟。在步驟620中，產生用於不同行的哈希值。在步驟630及640中，如果所產生min-hash值低於至此在流中已遇到的其當前值，則分別產生當前min-hash索引及值。在執行min-hash方案時還跟蹤類別標籤。如早先所提及的，假定圖的類別標籤附加至用於每一圖G的標識符Id(G)。因此，跟蹤類別標籤連同圖標識符。具體言之，圖標識符的最後部分為該圖的類別標籤。因為min-hash索引含有圖標識符，所以其也隱含地含有類別標籤。這些類別標籤用於從經壓縮的數據概要來計算辨別性邊集合。這是通過判定與特定類別標籤高度相關的min-hash索引中的邊的頻繁模式(換言之，內聚或相關邊模式)而實現的。具體言之，判定與在min-hash階段中所判定的頻繁模式有關的主要類別標籤，且保留類別出現率高於用戶定義閾值的所有模式集合。現參看圖2中的步驟230，流處理器接收傳入的圖數據流。注意，此流類似於訓練流，只是尚未將類別標籤指派給該流中的對象。這種流的一示例可為尚未判定侵入的性質、但已接收到對應於侵入的子圖的侵入應用。使用傳入的圖數據流作為輸入，將類別標籤與該傳入數據流中的對象相關聯(240)。這是通過使用在步驟220中判定的辨別性邊集合來完成的。具體言之，在傳入圖中找到對應於在訓練階段中判定的辨別性子圖的對象。接著將其唯一對應子圖的類別標籤或其對應子圖的多數類別標籤指派給所找到的對象。可接著從流處理器輸出這些對象類別標籤對，且將其存儲於信息儲存庫中(250)。可處理這些對以提供用於很多種應用的有用信息。詳言之，用戶可定義將在傳入數據流中發現的特定模式(260)。舉例而言，在侵入偵測應用中，用戶可能想要知曉侵入攻擊的性質(例如，其是否為「拒絕服務」攻擊)。對象類別標籤對可通過將傳入流中的類別標記為「拒絕服務」來提供關於這種攻擊的性質的信息。現將參考圖7中的裝置701描述本發明的一例示性實施例。裝置701可為計算機，其包括存儲器702、盤703及諸如中央處理單元(CPU) 704的處理器。應理解，本文中所使用的術語「處理器」意欲包括任何處理器件，例如包括CPU及/或其他形式的處理電路的處理器件，諸如上文中參考圖2論述的流處理器。此外，術語「處理器」可指一個以上的個別處理器。術語「存儲器」意欲包括與處理器或CPU相關聯的存儲器，諸如RAM、ROM、固定存儲器器件(例如，硬碟)、可拆裝存儲器器件(例如，軟盤)、快閃記憶體等。另外，本文中所使用的詞組「輸入及/或輸出接口」意欲包括(例如)用於將數據輸入至處理單元的一個或多個機構(例如，滑鼠)及用於提供與處理單元相關聯的結果的一個或多個機構(例如，印表機)。如圖7中所示的，當裝置701經由輸入接口接收諸如訓練流的圖數據流時，它可將該圖數據流存儲在存儲器702中的如上文參考圖2至圖6所描述的2D數據結構中。圖數據流可來自任何類型的大規模圖。輸入圖數據由CPU704處理來以上文參考圖2至圖6所描述的方式判定辨別性邊集合。這些辨別性邊集合連同其類別標籤可存儲於盤703中。當裝置701經由輸入接口接收到非訓練/測試圖數據流時，可將該輸入數據流置放於存儲器702中。可接著訪問存儲於盤703中的辨別性邊集合，且以上文參考圖2至圖6所描述的方式來判定與該非訓練/測試圖數據流中的對象相關聯的類別標籤。可接著經由裝置701的輸出接口將基於此判定的對象類別標籤對輸出至信息儲存庫705。該信息儲存庫705可呈其上存儲有對象類別標籤對的盤存儲器件的形式。這些對象類別標籤對可存儲於任何類型的資料庫中以用於未來的處理。為了識別非訓練圖數據流中的所需模式，可由裝置701或另一計算裝置從信息儲存庫705訪問對象類別標籤對。可接著分析這些對象類別標籤對以判定所需模式。舉例而言，可找到指示用戶在訪問特定網站時的行為的對象類別標籤對。在一些實施例中，執行模式識別的請求710可輸入至裝置701中，諸如自用戶輸入的搜尋請求。在一些實施例中，從裝置701輸出對請求的響應720。所屬技術領域的技術人員知道，本發明可以實現為系統、方法或電腦程式產品。因此，本公開可以具體實現為以下形式，即:可以是完全的硬體、也可以是完全的軟體(包括固件、駐留軟體、微代碼等)，還可以是硬體和軟體結合的形式，本文一般稱為「電路」、「模塊」或「系統」。此外，在一些實施例中，本發明還可以實現為在一個或多個計算機可讀介質中的電腦程式產品的形式，該計算機可讀介質中包含計算機可讀的程序代碼。可以採用一個或多個計算機可讀的介質的任意組合。計算機可讀介質可以是計算機可讀信號介質或者計算機可讀存儲介質。計算機可讀存儲介質例如可以是一但不限於——電、磁、光、電磁、紅外線、或半導體的系統、裝置或器件，或者任意以上的組合。計算機可讀存儲介質的更具體的例子(非窮舉的列表)包括:具有一個或多個導線的電連接、可攜式計算機磁碟、硬碟、隨機存取存儲器(RAM)、只讀存儲器(ROM)、可擦式可編程只讀存儲器(EPR0M或快閃記憶體)、光纖、可攜式緊湊磁碟只讀存儲器(CD-ROM)、光存儲器件、磁存儲器件、或者上述的任意合適的組合。在本文件中，計算機可讀存儲介質可以是任何包含或存儲程序的有形介質，該程序可以被指令執行系統、裝置或者器件使用或者與其結合使用。計算機可讀的信號介質可以包括在基帶中或者作為載波一部分傳播的數據信號，其中承載了計算機可讀的程序代碼。這種傳播的數據信號可以採用多種形式，包括——但不限於——電磁信號、光信號或上述的任意合適的組合。計算機可讀的信號介質還可以是計算機可讀存儲介質以外的任何計算機可讀介質，該計算機可讀介質可以發送、傳播或者傳輸用於由指令執行系統、裝置或者器件使用或者與其結合使用的程序。計算機可讀介質上包含的程序代碼可以用任何適當的介質傳輸，包括一但不限於一無線、電線、光纜、RF等等，或者上述的任意合適的組合。可以以一種或多種程序設計語言或其組合來編寫用於執行本發明操作的電腦程式代碼，所述程序設計語言包括面向對象的程序設計語言一諸如Java、Smalltalk、C++，還包括常規的過程式程序設計語言一諸如」C」語言或類似的程序設計語言。程序代碼可以完全地在用戶計算機上執行、部分地在用戶計算機上執行、作為一個獨立的軟體包執行、部分在用戶計算機上部分在遠程計算機上執行、或者完全在遠程計算機或伺服器上執行。在涉及遠程計算機的情形中，遠程計算機可以通過任意種類的網絡一包括區域網(LAN)或廣域網(WAN)—連接到用戶計算機，或者，可以連接到外部計算機(例如利用網際網路服務提供商來通過網際網路連接)。下面將參照本發明實施例的方法、裝置(系統)和電腦程式產品的流程圖和/或框圖描述本發明。應當理解，流程圖和/或框圖的每個方框以及流程圖和/或框圖中各方框的組合，都可以由電腦程式指令實現。這些電腦程式指令可以提供給通用計算機、專用計算機或其它可編程 數據處理裝置的處理器，從而生產出一種機器，這些電腦程式指令通過計算機或其它可編程數據處理裝置執行，產生了實現流程圖和/或框圖中的方框中規定的功能/操作的裝置。也可以把這些電腦程式指令存儲在能使得計算機或其它可編程數據處理裝置以特定方式工作的計算機可讀介質中，這樣，存儲在計算機可讀介質中的指令就產生出一個包括實現流程圖和/或框圖中的方框中規定的功能/操作的指令裝置(instructionmeans)的製造品(article of manufacture) 也可以把電腦程式指令加載到計算機、其它可編程數據處理裝置、或其它設備上，使得在計算機、其它可編程數據處理裝置或其它設備上執行一系列操作步驟，以產生計算機實現的過程，從而使得在計算機或其它可編程裝置上執行的指令能夠提供實現流程圖和/或框圖中的方框中規定的功能/操作的過程。附圖中的流程圖和框圖顯示了根據本發明的多個實施例的系統、方法和電腦程式產品的可能實現的體系架構、功能和操作。在這點上，流程圖或框圖中的每個方框可以代表一個模塊、程序段或代碼的一部分，所述模塊、程序段或代碼的一部分包含一個或多個用於實現規定的邏輯功能的可執行指令。也應當注意，在有些作為替換的實現中，方框中所標註的功能也可以以不同於附圖中所標註的順序發生。例如，兩個連續的方框實際上可以基本並行地執行，它們有時也可以按相反的順序執行，這依所涉及的功能而定。也要注意的是，框圖和/或流程圖中的每個方框、以及框圖和/或流程圖中的方框的組合，可以用執行規定的功能或操作的專用的基於硬體的系統來實現，或者可以用專用硬體與計算機指令的組合來實現。此處使用的術語僅是為了描述特定實施例，且不旨在限制本發明。如在此使用的，單數形式「一」、「一個」和「該」也旨在包括複數形式，除非上下文另有清楚的規定。還將理解，術語「包括」和/或「包含」，當在本說明中使用時，明確說明存在所陳述的特點、整體、步驟、操作、元件和/或組件，但不排除一個或多個其他的特點、整體、步驟、操作、元件、組件和/或其組的存在或添加。以下權利要求中的所有裝置或步驟加功能元件的相應的結構、材料、動作和等價物，旨在包括用於結合在權利要求中特別聲明的其他元件而執行所述功能的任何結構、材料或動作。本發明的說明已出於解釋和描述的目的被展示，但不旨在是窮盡性的，或將本發明限制在公開的形式。許多修改和變化對於本領域普通技術人員來說是明顯的，而不脫離本發明的精神和範圍。選擇並描述實施例是為了最好地解釋本發明的原理和實際應用，且使得本領域普通技術人員能理解本發明的具有適用於所打算的特定用戶的各種修改各種實施例。
權利要求
1.一種用於分類圖數據流中的對象的方法，該圖數據流包括表示元素的多個節點及表示這些元素之間的連接的邊，且其中該數據流中的一對象為一組節點連同這些節點之間的邊，該方法包含: 接收圖數據的訓練流，該訓練流包括多個對象連同與這些對象中的每一個相關聯的類別標籤； 第一判定該訓練流中用於所述類別標籤的辨別性邊集合，其中一辨別性邊集合為指示含有這些邊的具有給定類別標籤的對象的邊集合； 接收該圖數據的傳入數據流，其中尚未將類別標籤指派給該傳入數據流中的對象； 基於這些辨別性邊集合，第二判定與該傳入數據流中的對象相關聯的類別標籤；以及 基於該第二判定將對象類別標籤對輸出至信息儲存庫， 其中該方法是使用處理器執行的。
2.如權利要求1的方法，其中不同對象的邊在該圖數據中無序地出現。
3.如權利要求1的方法，其中該第一判定包含: 在二維(2D)數據結構中安排該訓練流的第一傳入邊； 產生用於該2D數據結構的每一行及列中的邊的哈希值，這些哈希值是使用min-hash函數產生的； 識別相關邊集合，其中一相關邊集合為與該訓練數據中的一特定對象相關的邊集合，其中具有相同min-hash值的一邊集合為一相關邊集合； 將類別標籤指派給這些相關邊集合以獲得所述辨別性邊集合，其中被指派給一特定相關邊集合的類別標籤為該相關邊集合的主要類別標籤；以及 將所述辨別性邊集合連同其給定類別標籤一起存儲於數據集中，其中該數據集存儲於盤上或存儲於主計算機存儲器中。
4.如權利要求3的方法，其中該2D數據結構存儲於該主計算機存儲器中。
5.如權利要求3的方法，其進一步包含: 接收該訓練流的第二傳入邊； 產生用於該2D數據結構的每一行及列中的邊的新哈希值； 基於這些新哈希值更新該2D數據結構的索引及值；以及 使用該經更新的2D數據結構重複權利要求5的該識別步驟、該指派步驟及該存儲步驟。
6.如權利要求1的方法，其中該第一判定包含: 在2D數據結構中安排該訓練流的第一傳入邊； 使用第一哈希函數將該2D數據結構的列映射至偽列中，每一偽列包括映射至其的多個列； 產生用於該2D數據結構的每一行及偽列中的邊的哈希值，這些哈希值是使用min-hash函數產生的； 識別相關邊集合， 其中一相關邊集合為與該訓練數據中的一特定對象相關的邊集合，其中具有相同min-hash值的一邊集合為一相關邊集合； 將類別標籤指派給所述相關邊集合以獲得所述辨別性邊集合，其中被指派給一特定相關邊集合的類別標籤為該相關邊集合的主要類別標籤；以及將所述辨別性邊集合連同其給定類別標籤一起存儲於數據集中，其中該數據集存儲於盤上或存儲於主計算機存儲器中。
7.如權利要求6的方法，其中該2D數據結構存儲於該主計算機存儲器中。
8.如權利要求6的方法，其進一步包含: 接收該訓練流的第二傳入邊； 使用該第一哈希函數將該2D數據結構的放置有所述第二傳入邊的列映射至偽列中； 產生用於該2D數據結構的每一行及偽列中的邊的新哈希值； 基於這些新哈希值更新該2D數據結構的索引及值；以及 使用該經更新的2D數據結構重複權利要求7的該識別步驟、該指派步驟及該存儲步驟。
9.如權利要求1的方法，其中該第二判定包含: 針對該傳入數據流中的特定對象，(a)訪問存儲有該訓練流中用於所述類別標籤的所述辨別性邊集合的存儲器，且(b)尋找對應於該對象的辨別性邊集合；及將這些辨別性邊集合的主要類別標籤指派為該對象的類別標籤。
10.如權利要求1的方法，其進一步包含: 接收在該傳入數據流中尋找用戶定義模式的請求； 搜尋存儲於該信息儲存庫中的對應於該用戶定義模式的參數的對象類別標籤對；以及 將該搜尋的結果顯示給用戶。
11.如權利要求10的方法，其中該用戶定義模式包括社交網絡中的用戶在特定時間窗內的通信模式、web圖的用戶在進入一特定網頁中時的瀏覽模式，或在通信網絡上的侵入通"[目流。
12.如權利要求1的方法，其中該圖數據是從web圖、社交網絡或通信網絡提供的。
13.如權利要求12的方法，其中該web圖的節點包括統一資源定位器(URL)地址，且該web圖的邊包括這些URL地址之間的連結，該社交網絡的節點包括用戶標識符，且該社交網絡的邊包括這些用戶標識符之間的連結，或該通信網絡的節點包括網際協議(IP)地址，且該通信網絡的邊包括這些IP位址之間的連結。
14.一種用於分類圖數據流中的對象的電腦程式產品，該圖數據流包括表示元素的多個節點及表示這些元素之間的連接的邊，且其中該數據流中的一對象為一組節點連同這些節點之間的邊，該電腦程式產品包含: 計算機可讀存儲媒體，其體現有計算機可讀程序代碼，該計算機可讀程序代碼包含: 被配置為執行以下步驟的計算機可讀程序代碼: 接收圖數據的訓練流，該訓練流包括多個對象連同與這些對象中的每一個相關聯的類別標籤； 第一判定該訓練流中用於所述類別標籤的辨別性邊集合，其中一辨別性邊集合為指示含有這些邊的具有給定類別標籤的對象的邊集合； 接收該圖數據的傳入數據流，其中尚未將類別標籤指派給該傳入數據流中的對象； 基於這些辨別性邊集合，第二判定與該傳入數據流中的對象相關聯的類別標籤；以及 基於該第二判定將對象類別標籤對輸出至信息儲存庫。
15.如權利要求14的電腦程式產品，其中該第一判定包含:在二維(2D)數據結構中安排該訓練流的第一傳入邊； 產生用於該2D數據結構的每一行及列中的邊的哈希值，這些哈希值是使用min-hash函數產生的； 識別相關邊集合，其中一相關邊集合為與該訓練數據中的一特定對象相關的邊集合，其中具有相同min-hash值的一邊集合為一相關邊集合； 將類別標籤指派給這些相關邊集合以獲得所述辨別性邊集合，其中被指派給一特定相關邊集合的類別標籤為該相關邊集合的主要類別標籤；以及 將所述辨別性邊集合連同其給定類別標籤一起存儲於數據集中。
16.如權利要求14的方法，其中該第一判定包含: 在2D數據結構中安排該訓練流的第一傳入邊； 使用第一哈希函數將該2D數據結構的列映射至偽列中，每一偽列包括映射至其的多個列； 產生用於該2D數據結構的每一行及偽列中的邊的哈希值，這些哈希值是使用min-hash函數產生的； 識別相關邊集合，其中一相關邊集合為與該訓練數據中的一特定對象相關的邊集合，其中具有相同min-hash值的一邊集合為一相關邊集合； 將類別標籤指派給所述相關邊集合以獲得所述辨別性邊集合，其中被指派給一特定相關邊集合的類別標籤為該相關邊集合的主要類別標籤；以及 將所述辨別性邊集合連同其給定類別標籤一起存儲於數據集中。
17.一種用於分類圖數據流中的對象的方法，該圖數據流包括表示元素的多個節點及表示這些元素之間的連接的邊，且其中該數據流中的一對象為一組節點連同這些節點之間的邊，該方法包含: 接收圖數據的訓練流，該訓練流包括多個對象連同與這些對象中的每一個相關聯的類別標籤，但未與邊所屬於的對象一起接收該訓練流中的這些邊； 第一判定該訓練流中用於類別標籤的辨別性邊集合，其中一辨別性邊集合為屬於含有這些邊的具有一給定類別標籤的對象的邊集合； 接收該圖數據的傳入數據流，其中尚未將類別標籤指派給該傳入數據流中的對象； 基於所述辨別性邊集合，第二判定與該傳入數據流中的對象相關聯的類別標籤；以及 基於該第二判定將對象類別標籤對輸出至信息儲存庫， 其中該方法是使用處理器執行的。
18.如權利要求17的方法，其中對該訓練流的圖數據執行該第一判定，將該圖數據以具有行及列的數據結構的形式存儲於主計算機存儲器中。
19.如權利要求18的方法，其中該第一判定包含對該數據結構中的邊數據執行哈希過程以判定相關邊集合，一相關邊集合為包括相對於一特定對象具有一高內聚概率的邊的邊集合;
20.如權利要求19的方法，其中該第一判定進一步包含判定用於該相關邊集合的主要類別標籤，該主要類別標籤為對於此邊集合具有最高絕對頻率的類別標籤。
全文摘要
一種用於分類圖數據流中的對象的方法，其包括接收圖數據的訓練流(210)，該訓練流包括多個對象連同與這些對象中的每一個相關聯的類別標籤；第一判定該訓練流中用於所述類別標籤的辨別性邊集合(220)，其中一辨別性邊集合為指示含有這些邊的具有一給定類別標籤的對象的邊集合；接收該圖數據的傳入數據流(230)，其中尚未將類別標籤指派給該傳入數據流中的對象；基於該辨別性邊集合第二判定與該傳入數據流中的對象相關聯的類別標籤(240)；以及基於該第二判定將對象類別標籤對輸出至信息儲存庫(250)。
文檔編號G06F7/00GK103189836SQ201180052233
公開日2013年7月3日 申請日期2011年3月30日 優先權日2010年8月30日
發明者C·阿加瓦爾 申請人:國際商業機器公司