大規模數據聚類分析的並行化的製作方法

2023-10-09 11:40:19 1

專利名稱：大規模數據聚類分析的並行化的製作方法
技術領域：
本說明書涉及並行處理。
背景技術：
並行處理通常指的是將ー個或多個計算任務劃分為兩個或更多子任務的概念，每個子任務可以在単獨的處理器上運行。換句話說，把一個較大的計算任務分成若干子任務，然後將這些子任務分配到兩個或多個處理器上執行。與僅使用所述處理器中的一個處理器可能達到的效果相比，通過使用這樣的並行處理技術，在許多情況下，可以以更快速並且更有效的方式完成計算任務。然而，實際上，可能存在大量障礙使得難以或者無法執行給定計算任務的並行處理，特別是對於特定類型或者類別的計算任務。舉例來說，一般地，要求至少與並行處理關聯的計算開銷要小。舉例來說，對於一項將並行運行的給定計算任務來說，可能需要將與該計算任務相關的數據的部分或者全部複製到將使用的每ー個處理器中。更一般來說，可以理解，最好沒有為並行處理而進行的數據分割或複製而帶來的計算開銷。而且，在並行運行的處理器中的任意ー個處的延遲或困難可能導致該任務的計算整體上的延遲。而且，因為子任務在兩個或更多處理器處完成，所以可能需要計算資源來整合在兩個或更多處理器中的每ー個處執行的並行處理的結果，以便得到該計算任務整體的統ー計算結果。因此，由於可能與在並行處理中處理子任務的劃分、計算以及整合相關聯的這些計算開銷，在許多情況下利用並行處理技術可能是不現實的。舉例來說，特定類型的計算任務可能需要對相對來說非常大的數據集的每一元素與相對較小的數據集的每一元素的比較或者其它操作。例如，在一個為了說明的特定例子中，可能出現需要將ー個包括三百萬個記錄——每ー個記錄有300個屬性——的數據集與第二數據集的100個記錄中的每ー個相比較(諸如，舉例來說，當希望將三百萬個記錄中 的每ー個分組到被認定是最相似的100個聚類中的一個中時)。因此，這樣的計算將需要三百萬乘300再乘100次単獨計算。而且，將數據集劃分以使用単獨的處理器處理是不可行的，因為該計算的本質是將第一較大數據集的全部記錄和屬性與第二較小數據集的個個元素都進行比較。因此，從在這些以及其它類型的計算場景(context)中使用並行處理技術得到顯著的益處可能是不可能的或者是行不通的。

發明內容
根據ー個一般方面，計算機系統可以包括記錄在計算機可讀介質上的指令。該系統可以包括聚類選擇器，其被配置為確定多個樣本聚類，以及在多個處理核中的每ー個處再現所述多個樣本聚類。該系統可以包括樣本劃分器，其被配置為將存儲在資料庫中的具有關聯屬性的多個樣本劃分為數目相應於所述多個處理核的數目的樣本子集，並且還被配置為將所述數目的樣本子集中的每ー個與所述多個處理核中的對應ー個關聯。該系統可以包括整合操作器，其被配置為基於所述多個處理核中的每個對應核處的每個樣本子集中的每個樣本的關聯屬性，執行所述每個樣本相對於在所述對應處理核處再現的多個樣本聚類中的每ー個的比較。實施方式可以包括一個或多個下列特徵。例如，所述聚類選擇器可以被配置為通過圖形用戶界面(GUI)從用戶接收的多個樣本聚類的數目。所述系統可以包括合併器，其被配置為合併所述在多個處理核中的每ー個處執行的比較的比較結果，以便由此以所述多個樣本填充所述樣本聚類。樣本子集的數目可以等於所述多個處理核的數目，並且每個樣本子集可以包括相等數目的樣本。所述系統可以包括屬性劃分器，其被配置為將與每個樣本關聯的屬性劃分為屬性子集，以供在執行所述比較期間對其進行並行處理。所述比較可以包括在多個處理核中的每ー個處執行的、在每個樣本子集的每個樣本與每個聚類的中心之間的相似性比較。可以使用包括在每個聚類中的樣本的平均屬性值來確定每個聚類的中心。所述整合操作器可以被配置為基於所述比較將樣本從第一聚類重新指派到第二聚類。合併器可以被配置為合併所述比較的比較結果，以及可以被配置為根 據需要使用經合併的比較結果來更新每個聚類的每個中心的值。所述合併器可以被配置為基於被重新指派的樣本的數目來確定每個聚類內樣本的穩定性。根據另ー個一般方面，一種計算機實現方法可以包括確定存儲在資料庫中的具有關聯屬性的多個樣本；確定多個樣本聚類；在多個處理核中的每ー個處再現所述多個樣本聚類。該方法可以包括將所述多個樣本劃分為數目與所述多個處理核的數目對應的樣本子集；將所述數目的樣本子集中的每ー個與所述多個處理核中的對應ー個關聯；以及基於在所述多個處理核的每個對應核處的每個樣本子集的每個樣本的關聯屬性，執行所述每個樣本相對於在對應處理核處再現的多個樣本聚類中的每ー個的比較。實施方式可以包括一個或多個下列特徵。例如，可以合併所述在多個處理核中的每ー個處執行的比較的比較結果，以便由此以所述多個樣本填充所述樣本聚類。而且，執行所述比較可以包括將與每個樣本關聯的屬性劃分為屬性子集，以便在執行所述比較期間對其進行並行處理。執行所述比較還可以包括在多個處理核中的每ー個處執行每個樣本子集中的每個樣本與每個聚類的中心之間的相似性比較。根據另ー個一般方面，一種電腦程式產品可以被有形地具體實施在計算機可讀介質上並且可以包括指令，當被運行時所述指令可以被配置為如下確定存儲在資料庫中的具有關聯屬性的多個樣本；確定多個樣本聚類；以及在多個處理核中的每ー個處再現所述多個樣本聚類。所述指令當被運行時還可以被配置為將所述多個樣本劃分為數目與所述多個處理核的數目對應的樣本子集；將所述數目的樣本子集中的每ー個與所述多個處理核中的對應ー個關聯；以及基於在所述多個處理核的每個對應核處的每個樣本子集的每個樣本的關聯屬性，執行所述每個樣本相對於在對應處理核處再現的多個樣本聚類中的每ー個的比較。實施方式可以包括一個或多個下列特徵。例如，所述指令當被運行時可以被配置為合併所述在多個處理核中的每ー個處執行的比較的比較結果，以便由此以所述多個樣本填充所述樣本聚類。所述指令當被運行時可以被配置為將與每個樣本關聯的屬性劃分為屬性子集，以便在執行所述比較期間對其進行並行處理。所述比較可以包括在多個處理核中的每ー個處執行的、每個樣本子集中的每個樣本與每個聚類的中心之間的相似性比較。
所述指令當被運行時可以被配置為基於所述比較將樣本從第一聚類重新指派到第二聚類。所述指令當被運行時可以被配置為基於所述被重新指派的樣本的數目確定每個聚類內的樣本的穩定性。在附圖以及下面的說明中闡述了一個或多個實施例的細節。其他特徵將從說明書和附圖以及從權利要求中變得明顯。


圖I是用於對大規模數據聚類分析執行並行處理的系統的框圖。
圖2是示出圖I的系統的操作的更為詳細的例子的框圖。圖3是示出圖I和圖2的系統的示範性操作的流程圖。圖4是示出在k均值聚類算法的場景中使用圖I-圖3的系統和操作的流程圖。圖5A和圖5B是示出與圖I-圖4關聯的處理技術的計算本質的框圖。
具體實施例方式圖I是在聚類分析期間執行並行處理大數據集的系統100的框圖。在圖I的例子中，如圖所示，聚類管理器102可以被配置為分隔相對較大數據集內的多個樣本104以定義多個聚類(cluster) 106，以及用樣本104中適合的樣本來填充聚類106中的每ー個。而且，如這裡所述，聚類管理器102可以被配置為以利用並行處理技術的方式生成聚類106以及用樣本104中適合的樣本來填充聚類106，該並行處理技術被設計為充分利用多個處理核的計算能力，所述多個處理核如圖I中核108、110和112所示。這樣，可以以高可配置且高效的方式形成聚類106，並且通過使用這裡描述的並行處理技術，可以以比使用核108、110、112中的單個核可能達到的效果明顯更快地提供聚類106。正如上所述，並且如這裡所詳細描述的那樣，聚類管理器102可以被配置為使系統100的用戶能夠選擇或者另外定義樣本104以供後續對其聚類。舉例來說，用戶可以從多個可能的樣本資料庫中選擇樣本104，和/或可以選擇樣本104為包括來自ー個較大資料庫內的數據的子集。在下面的許多例子中，樣本104被描述為企業的多個客戶數據記錄，其中每個客戶用多個預先定義的屬性進行描述。舉例來說，企業可以維護全部過去的、現在的以及潛在的客戶記錄，並且可以將這些客戶的身份連同多個相關客戶屬性(諸如像住址/地址、年收入、購買歷史、職業之類)或者可能公認與企業的能力相關的許多其它潛在客戶屬性一起以適當的方式(setting)中存儲(例如，客戶關係管理(CRM)系統內)，以維持高水平的盈利能力以及客戶滿意度。當然，樣本104以及相關屬性的這些示範性描述應當理解為並非對範圍的限制，並且具體來說，可以理解，在其它示範性實施方式中，樣本104可以表示許多其它類型的數據以及關聯屬性。舉例來說，樣本104可以是已經或者可以由企業出售的貨物或者服務(例如，諸如可以在庫存管理系統內找到的)。在其它例子中，樣本104可以是企業的資源(例如，與設施和/或信息技術資產相關的資源)。更一般地，樣本104可以因此被理解為表示可以使用大數據集或者與大數據集關聯的企業的幾乎任何方面，該大數據集包括多個記錄以及關聯屬性。甚至更一般地，可以理解，這些數據集可以存在於(並且因此可以從這裡所描述的技術中受益)各種非企業環境中，諸如，像包括學校、政府、軍隊、慈善或者各種其它場景的環境中。在所有這些環境中，可能期望將樣本104中的各個樣本分組到多個聚類106中。舉例來說，在客戶關係管理的場景中，樣本104可以包括多個客戶數據記錄以及關聯屬性，如上面所述。因此，對系統100的用戶來說，可能期望將樣本104分組到聚類106中的對應聚類中，其中可以根據用戶可能感興趣的、客戶關係管理的某個方面來定義聚類106。舉例來說，在ー個特定情景中，根據近期將進行大量購買的可能性等級將客戶劃分到各個聚類106。舉例來說，特定準則可以與定義這樣的可能性以及對這樣的可能性進行評級(rating)相關聯。舉例來說，共享諸如高年收入、最近的大量購買以及被認為與將來的購買可能性相關的其它基於屬性的因素之類的特徵的客戶可以被分組到第一聚類106(1)內，該第一聚類106(1)將因此包括被圖示為樣本104(1)的樣本子集。同時，反之，具有非常不同屬性值(例如，較低年收入、無最近購買歷史以及被認為與近期購買的較低可能性相關的其它基於屬性的因素)的客戶可以被聚類到另外的聚類內，在圖I的例子中被示為聚類M106 (M),其由此包括被示為樣本104 (M)的樣本子集。
當然，儘管圖I的簡化例子僅明確地示出兩個聚類，但是可以理解，可以形成期望數目的聚類。舉例來說，在剛剛提供的圖示例子中，可以形成總數目為M的聚類，其中，根據所預測的這裡包括的客戶將來購買的可能性的等級來定義聚類。當然，可以使用圖I的系統100形成許多其它類型的聚類，並且不需要根據剛剛提到的線型分布類型來形成。更一般地來說，可以理解，與聚類106的定義和形成相關的各種概念本身在本領域是公知的，並且因此除了可能對於理解圖I的系統100的操作是必要的或者有幫助的內容之外，不在這裡更為詳細地描述。相反，在這裡一般來說針對圖I的系統100中出於並行化與針對樣本104形成、定義、填充以及以其它方式管理聚類106相關聯的計算過程的目的而實現的特定示範性技木，並且更具體地說，針對在以針對使用可用核108、110、112來充分利用各種並行處理技術的方式執行聚類106的這樣的管理中聚類管理器102的各種特徵和功能，來提供圖I的系統100的更進一歩的描述。對於此點，可以理解，核108、110、112意欲表示幾乎任何已知或者將來的並行處理平臺或者場景。舉例來說，核108、110、112中的每ー個都可以表示獨立的伺服器或者包括一個或多個處理器的其它計算裝置。在另外的或者替換實施方式中，核108、110、112中的每ー個可以包括在單個伺服器或者其它計算裝置內。因此，核108、110、112中的每ー個都可以理解為表示或者包括任何多計算平臺，在該多計算平臺中，多個處理器、中央處理單元(CPU)或者其它處理資源是可用的，包括網絡/設備群(cluster)。舉例來說，並行處理可以利用現有SMP/CMP(對稱多處理/晶片級多處理)伺服器。因此，在本說明書中，應當理解，術語「核」表示具有處理能力的単元。因此，可以理解，系統100可以被配置為在剛剛提到的各種並行處理平臺和/或未特別提到的其它並行處理平臺或者它們的組合中的任意一種平臺的場景中操作，並且被配置為充分利用剛剛提到的各種並行處理平臺和/或未特別提到的其它並行處理平臺或者它們的組合中的任意一種平臺的特徵和功能。因此，如前所述，聚類管理器102可以被配置為使得能夠使用多個處理核——在圖I的例子中以核108、110、112表示——來並行化相對較大數目的樣本(以及它們各自的屬性)到相對較小數目的聚類106的整合(joint)操作。更具體來說，如圖所示，樣本104可以被劃分成多個樣本子集114、116、118。如圖所示，樣本子集114、116、118中的每ー個都可以分布到核108、110、112中的相應ー個。圖I的例子示出與三個可用核108、110、112相應的三個樣本子集114、116、118。當然，更ー般地，樣本104可以被分成任意合適或者期望數目的子集，例如，其數目與可用核的數目對應。在這裡所描述的不範性實施方式中，樣本104可以被劃分成多個樣本子集，以使得姆ー個樣本子集都包含近似相等數目的樣本104。然而，在其它示範性實施方式中，可以存在樣本子集具有不同大小的情況。舉例來說，被指派到相對高速處理核的樣本子集與相對低速處理核所關聯的或者被指派到相對低速處理核的樣本子集相比可以被提供有更大數目的樣本。與將樣本104劃分為各種樣本子集114、116、118。相反，聚類106可以被整體再現，以供可用核108、110、112中的每ー個處理。具體地說，如圖所示，聚類106可以在可用核108、110、112中的每ー個處被整體再現為聚類再現120。因此，如下面提供的更為詳細的例子中所述，可以針對相應的樣本子集114、116、118並且結合聚類再現120運 行在各個核108、110、112處的(或者與各個核108、110、112關聯的)並行化整合操作器(operator) 122、124、126。具體地說，舉例來說，可以使用並行化整合操作器122，將示範性子集114中的全部樣本分別與全部聚類再現120相比較或者以其它方式相對於全部聚類再現120進行考慮。類似地，可以使用並行化整合操作器124，將樣本子集116中的全部樣本分別與全部聚類再現120進行比較。類似地，類似注釋適用於相對於聚類再現120的樣本子集118以及並行化整合操作器126。通過這樣的方式，可以發現，總體上，可以以利用高等級的非常高效的並行化的方式來將全部樣本104分別與聚類106中的每ー個進行比較。結果，系統100的操作者或者其它用戶可以快速得到期望的結果。舉例來說，如下面所提供的更為詳細的例子中那樣，系統100的操作者可能接下來能夠以期望方式快速定義並且形成聚類106，以便由此之後以其它傳統方式來使用聚類106。在圖I的特定例子中，聚類管理器102示出為包括屬性選擇器128。如上所述，樣本104可以分別與針對正在討論的樣本定義的或者以其它方式與正在討論的樣本相關的ー個或多個屬性關聯。眾所周知，並且如這裡詳細描述的那樣，這些屬性的數目和類型以及其可能值或者值的範圍，可以依賴於系統100的使用場景而變化很大。在系統100的一個給定實施方式中，可以出現可用屬性的僅ー個子集或者一部分可能被期望用於相應計算中。另夕卜，或者可替換地，可以出現某些屬性應當被重視或者被區別對待(例如，視為較重要或較不重要)。因此，屬性選擇器128可以被配置為使系統100的用戶能夠以期望方式選擇可用樣本屬性和/或描述可用樣本屬性的特徵。舉例來說，儘管在圖I的例子中未具體示出，但是可以為系統100的用戶提供合適的圖形用戶界面，其中，如應當認識到的那樣，這樣的圖形用戶界面的形式和格式將依賴於系統100的特定使用場景。聚類選擇器130可以被配置為使系統100的用戶能夠定義聚類106的期望本質或者以其它方式描述聚類106的期望本質的特性。舉例來說，例如，依賴於正在使用的相關聚類算法或者其它因素，聚類選擇器130可以使系統100的用戶能夠定義將要計算的聚類106的數目。另外，或者可替換地，聚類選擇器130可以使系統100的用戶能夠進ー步描述聚類106的特性。舉例來說，用戶可以定義聚類106的最大大小，或者聚類106相互之間的相對大小，或者聚類106的任意其它特徵或者特性。與屬性選擇器128 —祥，可以由聚類選擇器130提供合適的圖形用戶界面，以供系統100的用戶在執行剛剛提到的聚類106的並行化時使用。舉例來說，如圖I中所示，聚類106可以包括M個聚類，在圖I中示出為第一聚類106(1)以及第M聚類106 (M)。然後，在該例子中，可以認為聚類選擇器130使系統100的用戶能夠定義參數M，以使得如所描述的那樣，可以將全部M個聚類複製為在可用核108、110、112處的聚類再現120。樣本劃分器132可以被配置為執行將樣本104劃分為樣本子集114、116、118。如上所述，樣本劃分器132可以通過將樣本104劃分為一定數目的樣本子集——該數目等於可用核的任意數目——來執行，其中樣本子集中的每ー個可以彼此大小近似相等。然而，如上所述，樣本劃分器132還可以與圖形用戶界面或者可以使系統100的用戶能夠以更加定 制化的方式配置樣本子集的其它輸入技術相關聯。舉例來說，樣本子集114、116、118可以大小不同。在其它例子中，可以基於樣本子集的指定參數屬性來定義及劃分樣本子集，而非通過樣本104的簡單分割來定義和劃分。聚類再現器134可以被配置為在核108、110、112中的每ー個處將聚類106再現為聚類再現120。相關再現技木本身是公知的，因此這裡不再進一步詳細描述。合併器136可以被配置為整合、同步、聚合(aggregate)或者以其它方式合併來自核108、110、112的處理結果。舉例來說，合併器136可以被配置為合併作為聚類管理器102的較大操作集的部分的中間處理結果以及合併最終結果集。在並行處理的場景中這樣的合併操作本身是公知的，並且可以包括，舉例來說，以來自每個相關的處理核的結果填充公共資料庫或者其它存儲器，和/或執行每個相關處理核的關聯處理(具體來說，執行可以僅在中央處理器處執行的數據的處理，這樣的處理的例子是公知的和/或將在下面詳細提供)。舉例來說，在圖I的例子中，並行化整合操作器138可以被配置為執行上面針對操作器122、124、126所述的多種類型的操作。一般來說，例如，如前所述，這樣的整合操作可以包括將樣本104 (或者其子集)與聚類106中的每ー個単獨比較。下面的例子討論了相似性比較以及相關處理，作為這樣的整合操作的ー個例子。然而，將認識到，也可以由聚類管理器102執行其它類型的整合操作以及相關處理。雖然如此，但是在圖I的特定例子中，為了說明起見，並行化整合操作器138可以包括比較器140。比較器140可以被配置為例如，用於將樣本104(或者其子集)分別地與聚類106中的每ー個進行比較。基於這些比較的結果，樣本指派器或者樣本重新指派器142可以被配置為將樣本中的每ー個與聚類106中給定的ー個關聯。隨後，中心選擇器144可以被配置為分析如此形成的聚類以及所包含的樣本，以便由此確定新的或者更新的中心或者與每個聚類關聯的其它度量。隨後，比較器140可以通過重複將單個樣本與新定義的聚類中的每ー個進行比較來以迭代方式繼續，以使得樣本重新指派器142可以因此根據需要針對當前的聚類定義重新指派樣本。該迭代過程可以繼續直到例如聚類到達所定義的穩定程度(例如，根據在新迭代中被重新指派的樣本數目或者百分比小於一定的閾值來定義的，和/或基於這些迭代到達某ー閾值的預定義次數定義的)。如上所述，在圖I的系統100的特定示範性實施方式中，比較器140可以使用相似性比較器140a來執行所述比較，所述相似性比較器140被配置為比較每個單個樣本(例如，樣本子集的每個單個樣本)與聚類106中的每ー個的相似程度。這些相似性測量本身是公知的，並且對於本領域技術人員來說應當是清楚的，因此除了對於理解圖I的系統100的操作是必要的或者有幫助的內容之外不對其詳細描述。然而，一般說來，會認識到，可以針對樣本104的各種屬性(或者其子集)來執行這些相似性測量。例如，如上所述，屬性選擇器128可以被配置為使系統100的用戶能夠定義樣本104的屬性(和/或其特徵或值)，以使得相似性比較器140A可以由此被配置為基於所定義的屬性(或者其特徵或值)來執行每個單個樣本與聚類106中的每ー個之間的相似性測量。在許多情況下，如下面詳細描述的那樣(例如，針對圖2)，可以出現樣本104中的每ー個與相對較大數目的屬性關聯，這些屬性被定義或者指定用幹與聚類106中的每ー個的相似性比較中。因此，可能期望在較大的並行處理相對於聚類106的樣本本身的場景內，但是針對正在討論的屬性，使用並行處理。換句話說，例如，以與樣本劃分器132可以被配置為將樣本104劃分為樣本子集114、116、118幾乎ー樣的方式,屬性劃分器140b可以被配置為劃分或者以其它方式分割或者指定所選擇的屬性。因此，會認識到，通過已經被指定 用於相似性比較的樣本的屬性子集的並行處理的使用，可以加速相似性比較器140a的相似性比較。正如所述，下面將例如參考圖2提供對於在單個樣本和聚類106之間的相似性比較的場景中使用樣本屬性的這種並行處理的示範性技木。在圖I的例子中，聚類管理器102、樣本104和聚類106被示出為通過使用至少ー個計算裝置146——其可以包括或者合併至少一個處理器146a以及計算機可讀存儲介質146b——來實現。在此上下文中，一般會認識到，圖I示出系統100的特徵和功能可以通過使用利用計算機可讀存儲介質146b存儲並且由至少ー個處理器146a運行的指令或者其它代碼來識別。具體地說，例如，圖I示出單個計算裝置146 ;然而，會認識到，至少ー個計算裝置146可以表示多個計算裝置，其中每個計算裝置都可以使用也許如這裡所述並行運行的兩個或更多處理器。舉例來說，在一些不範性實施方式中，至少一個處理器146a可以由一個或多個核108、110、112中的ー個或多個表示，而在其它示範性實施方式中，至少ー個計算裝置146可以表示與伺服器或者容納核108、110、112的其它計算機通信的中央計算機。因此，儘管聚類管理器102及其組件被示出為包括在至少ー個計算裝置146中或者結合至少ー個計算裝置146運行，但是會認識到，可以使用多個不同的計算裝置——例如，ー個或多個核108、110、112來運行聚類管理器102中的部分或者全部。也就是說，舉例來說，在一些實施方式中，聚類管理器102的部分可以在第一計算裝置以及關聯的處理器上運行，而聚類管理器102的其它部分可以使用ー個或多個單獨的計算設備/處理器來運行。舉例來說，計算裝置146可以表示中央計算裝置，該中央計算裝置由系統100的用戶訪問並且運行聚類管理器102的組件，諸如像屬性選擇器128、聚類選擇器110、樣本劃分器132、聚類再現器134和合併器136。同時，如上所述並且如可以從圖I的例示會認識到的那樣，並行化整合操作器138可以被實例化為相應核108、110、112中的每ー個處的並行化整合操作器122、124、126和/或作為相應核108、110、112中的每ー個處的並行化整合操作器122、124、126以其它方式運行。在其它實施例中，會認識到，至少ー個計算裝置146可以表示在其中執行這裡所描述的並行處理的核中的ー個。系統100的架構上的這些變化或者其它結構對本領域技術人員來說是清楚的，並且因此在這裡沒有更詳細地進行描述。而且，許多其它變化也是可能的並且應當是清楚的。舉例來說，可以使用或許在通過網絡彼此通信的不同計算裝置上運行的兩個或更多組件來運行聚類管理器102的任意單個組件。反之，可以使用單個組件運行聚類管理器102的兩個或更多組件。通過舉例在這裡描述了許多其它實施方式，或者許多其它實施方式本來也是明顯的。圖2是圖I的系統100的更詳細的實施方式的框圖。具體地說，如上所述(例如，針對屬性劃分器140b)，圖2示出了這樣的示範性實施方式其中，聚類管理器102以另外並行處理樣本子集的屬性子集來補充樣本104的子集的並行處理。具體地說，在圖I的例子中，核108、110、112被示出並且大致上描述為表示可以被配置為彼此並行處理的幾乎任意類型、數量的多個核或者可以被配置為彼此並行處理的多個核的幾乎任意組合。在更具體的圖2的例子中，伺服器202、204、206被示出為各自包括 至少兩個處理核。換句話說，如圖所示，伺服器202、204、206表示多核伺服器。在示出的該具體例子中，如圖所示，伺服器202包括核208、210，而伺服器204包括核212、214，且伺服器206包括核216、218。因此，在操作中，聚類管理器102可以被配置為將樣本104劃分為樣本子集220、222和224，然後它們可以被分別指派給伺服器202、204、206，如圖所示。舉例來說，樣本劃分器132可以被配置為以上面針對圖I所描述的方式將樣本104劃分為樣本子集220、222、224。對於此點，會認識到，上面針對圖I描述的聚類管理器102的許多特徵和功能可以在圖2的場景中類似地執行。舉例來說，屬性選擇器128可以接收對與將用於聚類生成過程中的樣本104中的每ー個相關聯的各種屬性的選擇，而聚類選擇器130和聚類再現器134可以也被配置為執行它們的相應功能(例如，儘管在圖2的例子中未具體示出，但是選擇聚類106的數目和/或特徵，並且複製全部聚類106以便將其與伺服器202、204、206關聯)。類似注釋應用於針對在圖2的場景中在執行對應功能時使用合併器136和並行化整合操作器138時合併器136和並行化整合操作器138的操作。因此，將認識到，聚類管理器102的在圖2中的功能與其在圖I中的功能是相似的，因此在這裡不再詳細重複了。至於樣本子集220 (要理解類似的注釋適用於樣本子集222和樣本子集224)，可以存在樣本子集220的每個樣本被相對於被複製以與伺服器202相關聯並且由伺服器202使用的聚類106中的每ー個都進行比較(例如，樣本子集220的每個樣本將具有一個經判定的相似程度)。換句話說，如這裡詳細描述的那樣，可以將樣本子集220中的第一樣本相對於聚類106中的每ー個都進行比較，以得到其與聚類106中的每ー個的相似性。隨後，樣本子集220中的第二樣本可以類似地與聚類106中的每ー個都進行比較，直到樣本子集220的全部樣本都被如此進行了比較為止。在圖2的示範性實施方式中，假定樣本104各自與相對較大數目的關聯屬性相關聯，並且假定已經選擇了相對較大數目的這些可用屬性用於剛剛提到的相似性比較。於是，在圖2的例子中，這樣的一個相對較大的屬性池可以被劃分為相應的屬性子集，例如，與伺服器202的核208相關聯的屬性子集226以及與伺服器202的核210相關聯的屬性子集228。具體地說，例如，屬性劃分器140b可以被配置為將待使用的屬性集劃分為期望數目的子集，例如，與位於用於處理與正在討論的屬性關聯的相應樣本的相應多核伺服器處的可用核的數目相應的數目。隨後，會認識到，基於關聯屬性的比較可以彼此並行進行，以使得可以以更快且更及時的方式完成整體相似性比較。而且，如上所述並且如圖2的例子所示，類似注釋適用於伺服器204、206。具體來說，如圖所示，與樣本子集222關聯的屬性可以被劃分為屬性子集230和232，用於使用伺服器204的各個核212、214對其的並行處理。類似注釋適用於分別與伺服器206的核216、218關聯的屬性子集234、236。圖3是示出圖I的系統100和圖2的系統200的示範性操作的流程圖300。在圖3的例子中，操作302-312被示為單獨的、順序的操作。然而，將認識到，在其它示範性實施方式中，可以以部分或者完全重疊或並行的方式實現兩個或更多操作302、312。而且，操作302-312可以以不同於圖示的次序執行，包括例如，以嵌套的、循環 的或者迭代的方式。另夕卜，還可以包括未在圖3的例子中具體示出的附加操作或者替換操作，和/或可以省去ー個或多個操作或者其部分。在圖3的例子中，可以確定存儲在資料庫中的具有關聯屬性的多個樣本(302)。舉例來說，屬性選擇器128可以被配置為接收對與樣本104相關聯地存儲的指定屬性的選擇。可以確定多個樣本聚類(304)。舉例來說，聚類選擇器110可以被配置為標識、特徵化、參數化和/或以其它方式標識或者確定聚類106。多個樣本聚類可以在多個處理核中的每ー個處被再現(306)。舉例來說，聚類再現器134可以被配置為在核108、110、112中的每ー個處(或者，在圖2的例子中，在伺服器202,204,206中的每ー個處)再現相對於相關樣本104定義或者標識的全部聚類106。多個樣本可以被劃分為數目與多個處理核的數目相應的樣本子集(308)。舉例來說，樣本劃分器132可以被配置為將樣本104劃分為樣本子集114、116、118(或者，在圖2的例子中，劃分為樣本子集220、222、224)。該數目的樣本子集中的每ー個都可以與多個處理核中的相應ー個處理核相關聯(310)。舉例來說，樣本劃分器132可以被配置為複製或者以其它方式提供樣本104的樣本子集(例如，圖I的樣本子集114、116、118，或者圖2的樣本子集220、222、224)。舉例來說，樣本劃分器132可以被配置為將樣本子集中的每ー個複製到與所述多個處理核中的相應ー個處理核(例如，圖I的核108、110、112，或者圖2的伺服器202、204、206)相關聯的存儲器，所述存儲器例如可以由相應處理核讀取。基於在多個處理核中的每個相應核處的每個樣本子集中的每個樣本的關聯屬性，執行所述每個樣本相對於在相應處理核處再現的多個樣本聚類中的每個樣本聚類的比較(312)。舉例來說，並行化整合操作器138 (例如，或者其實例122、124、126)可以被配置為執行這樣的比較。舉例來說，並行化整合操作器122可以被配置為基於樣本子集114的每個樣本的屬性，將樣本子集114的每個樣本與核108所關聯的再現聚類120中的每ー個相比較。當然，類似注釋適用於並行化整合操作器124、126以及各個樣本子集116、118。在這裡描述的具體例子中，所述比較可以包括子集樣本中的每ー個與在處理核中的每ー個處再現的多個聚類中的每ー個之間的相似性比較。舉例來說，與特定樣本子集中的特定樣本相關聯的屬性可以被用於執行與多個再現聚類中的每ー個的這種相似性比較，如這裡詳細描述的那樣。具體地說，例如，如上相對於圖2所述，將用於這種相似性比較的、相對較大數目的這些樣本屬性可以被進一步劃分為樣本屬性子集，以供隨後在這種相似性比較的場景中的另外的並行化處理中使用。會認識到，可以如上針對圖I和圖2所述的那樣來執行這樣的並行處理的附加方面或者替換方面，或者這樣的並行處理的附加方面或者替換方面可以以清楚的其它方式運行。舉例來說，在這樣的並行處理完成時或者在其中間步驟完成時，可以進行適當的合併操作，以便組合或者以其它方式合併該並行處理(或者其中間操作的)的結果。舉例來說，合併器136可以被配置為組合與給定子集樣本相關聯的屬性子集226、228的並行處理，以便完成該子集樣本與給定樣本聚類的相似性比較。類似地，合併器136可以被配置為合併在圖I的場景中與樣本子集114、116、118中的每ー個關聯的比較結果，或者合併在圖2的場景中的樣本子集220、222、224的比較結果。當然，可以根據給定示範性實施方式的特定場景，包括更多附加或者替換操作。下 面圖4、圖5A和圖5B將提供k均值算法的的例子。具體地說，圖4和圖5A、圖5B提供了在實現k均值算法(k-means algorithm)的場景中圖I-圖3的系統和操作的實施方式的例子。如上所述，並且眾所周知，k均值算法是ー種分析方法被設計為將「N」個樣本(例如，樣本104)分割為「k」個聚類(例如，聚類106)，以使得「 N」個樣本中的每ー個都屬於具有最近均值的第k個聚類。因為k均值算法本身是具有許多已知實現領域的公知算法，除了可能對理解這裡描述的系統和操作的特徵和功能是必要的或者有幫助的內容之外，k均值算法本身和許多實現領域的例子這裡都不詳細提供。雖然如此，但是為了說明和示範起見，圖4示出包含k均值算法的完整運行的操作402-412。在圖4和圖5A、圖5B的場景中並且如上所述，參考具體例子或者例子集合，其中「 N」個樣本104可以包括提供能源和相關服務的公用事業公司的客戶的大量(例如，3百萬)客戶簡檔。在這樣的例子中，客戶簡檔中的每ー個都可以具有已定義數目的屬性(例如，300個屬性)。舉例來說，如在這樣的場景中公知的那樣，這樣的屬性可以包括，例如，家庭收入或者與對應客戶簡檔關聯的財務特性、能源使用歷史、住所特性(例如，關聯的客戶是住套房(house)還是公寓(apartment))或者可能與客戶關聯的以及可能與按時且有利地向其遞送公共設施相關的任意其它特性或者屬性。而且，還是如上所述，在圖I和圖2的系統中，以及一般而言在k均值算法中，對於用戶來說可以選擇以及以其它方式描述將要形成的一定數目的k聚類的特性。為了所提供的例子起見，假定k均值算法的示範性實施方式將使用與3百萬個客戶簡檔中的每ー個關聯的300個屬性的對應值，將該3百萬客戶簡檔聚類為100個聚類。因此，在圖4的例子中，操作可以ー開始以隨機選擇k個聚類中心開始(402)。也就是說，正如所述的那樣，用戶可能想要數目為k的聚類，其等於例如100個聚類。在這裡所描述的k均值算法的場景中，每個這樣聚類可以相對於其中心來定義，「N」個樣本中的每ー個都與該中心來比較，以得到其相似度。也就是說，如k均值算法中所已知的，並且如下所述，應當形成理想的或者期望的k = 100個聚類的最終集合，以使得全部N = 3百萬個樣本被指派給這樣的聚類其中心在所有中心中與正在討論的樣本最相似。因此，在該場景中，並且如一般在k均值算法實施方式的場景中公知的那樣，術語「中心」或者「聚類中心」應當理解為指代代表性的屬性或者定義的屬性，或者屬性的集合或者組合，這些屬性可以用於描述聚類的特性，以將聚類相互區分。舉例來說，在一個簡單例子中，3百萬客戶簡檔的300個屬性中的一個可以包括對應客戶的地理位置(例如，使用位置的郵政編碼或者經/緯度表示)。在這樣的例子中，可以存在這些位置屬性被指定為100個聚類的定義的基礎，以使得3百萬個地理位置中的100個可以用於定義該聚類(也即，用於定義聚類中心)。在這樣的例子中，使用如下所述的方法，3百萬客戶中的每ー個都將與對應聚類和聚類中心相關聯，該聚類中心在所有聚類中相對於正在討論的特定客戶來說具有最接近的地理位置。通過這樣的方式，全部3百萬客戶可以被指派給對應的、地理上定義的聚類。 當然，在其它更為詳細的例子中，可以相對於屬性集合或者組合定義聚類中心。舉例來說，可以歸ー化屬性的值，例如，通過給300個屬性中的每ー個賦予0到I之間的屬性值，以使得3百萬客戶中的每ー個都具有針對300個屬性中的每ー個的0到I之間的對應屬性值。在這樣的例子中，可以選擇期望的屬性集合或者組合，並且可以使用所選擇的屬性的歸ー化值來計算100個聚類的中心的對應集合。再有，這樣的技木本身是公知的，因此除了對於理解圖4和圖5A、5B的例子是必要的或者有幫助的內容之外，在這裡不更為詳細地進行描述。如上所述，在圖4的例子中，操作402因此表示對所選擇的k個聚類中心的初始的、最佳猜測的(best guess)或者隨機的選擇，僅僅作為開始圖4的算法的迭代的手段。舉例來說，在上面描述的簡化的基於地理的聚類中，操作402可以包括隨機從3百萬客戶中選擇100個，並且使用對應的100個地理位置作為聚類中心的初始集合。在上面所述的其它例子中，操作402可以包括隨機選擇100個客戶，然後分析相關的、關聯歸一化屬性值以計算對應的100個中心。—旦正如上所述已經選擇了聚類中心的初始集合，就可以計算N= 3百萬個樣本中的每ー個與k = 100個聚類中心之間的相似性(404)。舉例來說，如關於上面圖I-圖3的描述應當清楚的那樣，操作404的計算一般應當需要3百萬乘300再乘100次計算(假定將使用全部300個屬性)。雖然如此，但是使用上面相對於圖I-圖3描述的特徵和功能，可以以有助於快速且及時執行這樣的計算方式來並行化這樣的計算。具體地說，如上相對於圖I所述，可以將N = 3百萬個樣本劃分為數目為S的樣本子集，該數目S等於可用伺服器或者處理核的數目。然後，如上所述，可以針對S個伺服器/核中的每ー個再現全部k= 100個聚類中心。然後，如上所述，可以針對S個伺服器/核中的每ー個再現全部k= 100個聚類中心。如可以看到的那樣，這樣的再現可以是實際且直接明了的，假定期望的聚類中心的數目k比待分組的樣本的數目N小，因此k個聚類中心的複製不會產生相對可觀的開銷。儘管沒有相對於圖I具體討論，但是可以存在可以使用描述相對於對應聚類中心中的每ー個的相關屬性(或者其集合或者組合)的特性的相似性表格，進行將在如此劃分的樣本子集中的每ー個樣本子集中的每個樣本與對應聚類中心中的每ー個之間執行的相似性測量，從而可以確定它們之間的相對相似度。這樣的相似性表格本身及其使用是公知的。然而，在圖I-圖4的例子中，並且如下面將相對於圖5A和圖5B更為詳細地描述的那樣，這樣的相似性表格可以被類似地分割為S個部分，並且與相同伺服器或者處理核相關聯地存儲。換句話說，如這裡所述，N = 3百萬個樣本可以被劃分為數目為S的樣本子集，S=可用伺服器/核，並且對應的相似性表格可以類似地被劃分為數目為S的相似性表格子集，S=可用伺服器/核。圖5A和圖5B用圖示出將結合操作404執行的計算的本質，以及如這裡所述這些計算可以被並行化的方式。具體地說，如圖所示，N = 3百萬個樣本被示為樣本502、504. 506，並且被示為分別與對應聚類中心508,510. 512相比較。因此，圖5A概念性地示出上面所述的將針對N = 3百萬個樣本執行相對於k = 100個聚類的所述類型的相似性計算或者其它整合操作的資源密集的本質(resource-intensive nature)。同吋，圖5B概念性地示出可以使用這裡所描述的技術並行化操作404的資源密集的整合操作的方式。如上所述，參照圖5B描述的技術可以例如使用具有多個伺服器的群和/或使用包括多個核的單個伺服器來實現。因此，在所提供的示例中，可以認識到，對服務 器/核或多個伺服器/多個核的引用應當被理解為指代這些選擇中的其中之一或者它們ニ者，以供實現。具體地說，如圖所示，由伺服器514、516...51 8示出數目為S或C的可用伺服器/核。如圖所示並且所描述的那樣，N = 3百萬個樣本可以被劃分為對應於並且被指派給可用伺服器/核514、516. . . 518中的每ー個的樣本子集。具體地說，如圖所示，樣本(I N/S)或(I N/C)(在圖5B中示出為樣本502. . . 520)可以被指派給第一伺服器/核514。類似地，對應數目的樣本以及第ニ樣本子集(在圖5B中以樣本522表示)將被指派給第二伺服器/核516，等等，直到最後的伺服器/核518，最後的伺服器/核518將接收最後的樣本子集，其包括第N(l-(1/S))或N(l-(1/C))樣本524到最後的樣本506。從以上內容，可以認識到，在下面的內容中，為了簡潔並且僅僅為了註解，一般使用標號「 S」自己，但是無論如何標號「 S」要被理解為指代多個伺服器中的一個或者在單個伺服器上運行的多個核中的ー個。如圖5B所示，伺服器/核514、516. . . 51 8中的每ー個也將接收全部k個聚類中心508. . . 512，或者已經向伺服器/核514、516. . . 518中的每ー個指派了全部k個聚類中心508. . . 512。而且，如圖所示以及如上所述，也可以將針對給定樣本子集的樣本的任意相似性表格項和/或樣本-聚類映射複製或者存儲到伺服器/核514、516. . . 518中的對應ー個中。舉例來說,如圖所示,接收樣本502. . . 520的伺服器/核514將類似地接收針對樣本子集(也即，N個樣本中的第一到第N/S樣本)中的相應樣本的相應相似性表格項以及樣本-聚類映射。同時，並且類似地，伺服器/核518將接收針對對應於相關樣本子集(也即，第N(l-(1/S)...第N樣本)的樣本的相似性表格項和樣本-聚類映射。儘管未具體不出，但是可以認識到，可以針對樣本子集中的每ー個和關聯伺服器/核執行相關相似性表格項和樣本-聚類映射的類似的關聯和指派。因此，可以認識到，可以在S個伺服器/核上並行化操作404，否則操作404會昂貴，並且此後彼此獨立地執行。具體地說，可以在相關樣本子集中的每個樣本與聚類中心中的每ー個之間都進行相似性測量和比較。在該上下文中，如上所述，這樣的相似性比較可以包括或者基幹與在這裡描述的例子中為定義相似性而選擇的M = 300個屬性相關聯的計算。舉例來說，相對於圖5B，可以認識到，樣本502可以與300個屬性的對應值關聯，並且可以針對這300個屬性類似地定義中心508. . . 512。此後，可以ー開始將第一樣本502與第一中心508相比較，以便確定與其的相對相似性。
舉例來說，可以使用已知的歐式距離計算這樣的相似性，如下面的公式I的例子所示d = Im (X廠 X/)2 公式 I舉例來說，對於表不為「樣本A」的第一樣本502以及對於表不為「樣本B」的第一中心508來說，可以根據公式2來計算公式I的歐式距離d 樣本A= [X1, X2, , xM]樣本B= [x/ , x2』， ，xM』 ]d(A，B) = y(ろ-A1 Y + (A2 -A2 )' + …+ (xM -Xm )2.公式 2其中，如所示，對於樣本A、B中的每ー個來說M個屬性被示為X1. . . Xmo 因此，在這樣的例子中，可以依次計算該歐式距離，作為對於第一樣本502與聚類508. . . 512中的姆ー個的相對相似性的相似性量度(measurement),此後對於指派給第一伺服器/核514的樣本子集中的每個剩餘樣本，直到並且包括相關樣本子集的最後ー個這樣的樣本，也即，第N/S樣本520，進行這樣的計算。類似注釋將適用於在剩餘伺服器/核516…518處執行的計算。而且，如上所述，例如，相對於屬性劃分器140b，可以以類似於針對N= 3百萬個樣本整體的相似性計算的並行化的方式，進ー步並行化剛剛提到的相似性計算。具體地說，如上所述，可以存在伺服器/核514、516. ..518可以表示圖2的多核伺服器202、204、206。然後，300個屬性可以被劃分為相應的屬性子集，用於在與每個這樣的多核伺服器相關聯的多個核處對其的並行化處理。在ー個具體例子中，參考圖2，可以存在樣本子集220將包括3百萬客戶簡檔中的一百萬個客戶簡檔，而核208將與包括300個屬性中的150個屬性的屬性子集226相關聯，第二核210將包括屬性子集228中的其餘150個屬性。通過這樣的方式，還可以在一定數目的可用屬性上進ー步並行化公式1-2的相似性計算，以便更進ー步促進快速和及時的相似性計算。一旦已經計算出每個樣本子集中的每ー樣本與每個聚類中心之間的相似性量度，就可以基於該相似性量度在k個聚類中心內以及在k個聚類中心之間重新指派樣本(406)。舉例來說，相對於圖5B的第一伺服器/核514，如上所述，可以計算樣本502. . . 520中的每ー個與中心508. . . 512中的每ー個之間的相似性量度。因此，舉例來說，第一樣本502將具有最接近聚類中心508. . . 512中之一的相似性量度，並且因此將被指派給該聚類中心。可以針對指派給伺服器/核514的樣本子集中的其餘樣本，直到並且包括N/S樣本520，進行類似指派，從而，在操作406的結束時，全部樣本502. . . 520都已經指派給核中心508. . . 512中的ー個。當然，類似注釋適用於將伺服器/核516處的樣本子集中的樣本重新指派成伺服器/核518處的樣本子集524. . . 506的樣本。因此，可以明確地看到，在圖4和圖5B的例子中，以並行化的方式將全部N = 3百萬個樣本與k = 100個聚類中心中的每ー個都進行了比較，因此這是以高效方式進行計算。在操作406之後，可以做出穩定性確定(408)。舉例來說，在一個簡單例子中，可以簡單地基於圖4的流程圖400的迭代的次數來確定k = 100個聚類中心的聚類結果的穩定性。也就是說，例如，在假定其穩定性之後可以定義迭代的最大次數。另外，或者可替換地，可以基於其它衡量標準(metric)來判定穩定性。舉例來說，穩定性可以被確定為在操作406期間被重新指派給k = 100個聚類中心的樣本的數目。也就是說，如在k均值算法的傳統實施方式中已知的那樣，一旦在流程圖400的一次迭代的操作406期間在聚類之間重新指派了最小數目的樣本，就可以進一歩假定迭代將對k = 100個聚類的樣本指派產生微小的影響，和/或事實上N =3百萬個樣本中的大多數或者全部被指派給最相似的聚類中心。在至少部分地基於被重新指派的樣本的數目來判定穩定性的情況下，可能需要例如使用合併器136合併來自可用服務/核的數據。也就是說，參考作為示例的圖I的例子，可能出現單個樣本被重新指派到在核108、110、112中的每ー個處的新的中心。因此，合併器136可能合併來自核108、110、112的數據，以確定已發生總共三次重新指派。因此，如果確定了期望的穩定程度(408)，那麼流程圖400的算法就可以完成 (410)。否則(408)，可能需要或者期望計算正在討論的k = 100個聚類中的更新的聚類中心(412)。也就是說，如上所述，例如，相對於操作402，流程圖400的算法可以ー開始以隨機選擇k個聚類中心開始。舉例來說，在上述所給定的簡化例子中，聚類中心是基於客戶的地理位置來定義的，那麼操作402就可以ー開始隨機地選擇關聯地理位置中的100個客戶。然而，因為這樣的選擇是隨機的，所以可能存在如此選擇的聚類中心是非代表性的或者要不然的話就是非期望的。舉例來說，可能存在所有100個地理位置都位於彼此非常接近的位置。因此，正如所述的那樣，操作412可以被設計為計算新的、經更新的聚類中心——其可以更能代表相關樣本(例如，客戶)的期望特性或者屬性的實際的、期望的分布。換句話說，可以確定新的、更新的聚類中心，其使得可能最小化N= 3百萬個樣本中的每ー個與至少ー個相應聚類中心之間的距離。在k均值算法的傳統實施方式中，可以通過計算每個樣本與其當前或者(如果適用的話)新指派的聚類中心之間的總距離來執行操作412。然後，可以確定每個聚類中所有樣本的均值或者平均數，並且每個這樣的計算出的均值在之後都可以用作k = 100個聚類中心的新的聚類中心。在圖4的實施方式中，可以在每個伺服器/核處並行計算樣本中的每ー個與它們被新指派到的(如果已經發生了重新指派)聚類的當前中心之間的總距離。隨後，可以集中執行新中心的實際計算，並且該算法可以接下來進行操作404。換句話說，如已知並且如圖4中所示，相似性計算之後可以如上所述針對操作404繼續進行，直到達到穩定(408)，並且流程圖400的算法完成(410)。下面提供的偽碼部分1-3示出了根據圖4的流程圖400的示範性實施方式。具體地說，如下所示，偽碼I示出了用於計算公式I和2的歐式距離的示範性函數，而偽碼2示出了使用一定數目的核C並行計算距離(例如，相似性)的例子。最後偽碼3示出了圖4的K均值算法的實施方式，其可以包括偽碼部分I和2的計算。偽碼II. FUNCTION Euclidean_Distance(Vector x_vec, Vector y_vec)2. BEGIN
3. for i:=0 to size (x_vec) do4. distance+ = (x_vec [i]-y_vec [i]) "25. end for6. distance := sqrt (distance)7. return distance8. END偽碼2I. % C the number of cores 2. FUNCTION Euclidean—Distance (Vector x_vec, Vector y_vec)3. BEGIN4. N = size (x_vec)5. Vector distance = new Vector[C]6. On Core I 7.for i = 0 to INT (N/C) do8.distance[l]+= (x_vec[i]-y_vec[i]) "29.end for10. On Core 2 11.for i = INT (N/C) to 2*INT(N/C)do12.distance [2]+ = (x_vec [i]-y_vec [i]) "213.end for14.......15. On Core C 16.for i := INT (N(l_l/C)) to N do17.distance [C_l] + = (x_vec [i]-y_vec [i]) "218.end for19. result := sqrt (sum(distance))20. return resultEND偽碼3I. FUNCTION K—Means—Parallel2. % K the number of cluster3. % nSamples the number of samples4. % nDimensions the number of dimensions5. % [nSamples, nDimensions] := size (inputData)6. % nServers the number of servers7.8. % Set up the maximum number of iterations9.MAX—ITER: = 10010.
11. Matrix center = new Matrix[K][nDimensions]12. center = random select K samples13.14. % Set up storage for the cluster id of samples15. Vector cluster—id : = new Vector[nSamples]16. Vector old—cluster—id : = new Vector[nSamples]17. old—cluster—id := ones (nSamples) 18.19. % Set up storage for the cluster result20. Matrix cluster—result := new Matrix [K][]21.22. while cluster—id ! = old—cluster—id && iter く MAX—ITER do23. Copy the new centers to S servers24. old—cluster—id : = cluster—id25. On server I 26.% Set up storage for the similarity between samples on thisserver and centers27.Matrix similarity_on_Server_l = new Matrix [num—SampIes_on_Server_l][K]28.29. Matrix sum—on—Server—I := new Matrix [K] [nDimensions]30.% Compute similarity between the samples on this server andcenters31. for i = 0 to num_Samples_on_Server_l do32.for j = 0 to K do33.similarity—on—Server—I [i] [j] : = Euclidean—Distance (Samples—on—Serverl [i]，center—copy—I [j])34.35.end for36.end for37.38.% Find out the cluster id (with minimum distance) for eachsample39.for i = 0 to num—Samples—on—Server—I do40.id := min_index (similarity_on_Server_l)41.cluster—id[i] := id42.cluster—result [id]. pushback [i]43. end for44.
45.% For each cluster，compute the sum of the corresponding sampleson this server46.for i = 0 to num_Samples_on_Server_l do47.if Samples_on_ServerI [i]. cluster_id = = m then48.sum—on—Server—I [m]+ = Samples—on—Serverl [i]49.end if50.end for51.52.On server 2 53.% Set up storage for the similarity between samples on thisserver and centers54.Matrix similarity_on_Server_2 = new Matrix [num—SampIes_on_Server—2][K]55.56.Matrix sum_on_Server_2 = new Matrix [K] [nDimensions]57.% Compute similarity between the samples on this server andcenters58.for i : = 0 to num—Samples—on—Server—2 do 59.for j = 0 to K do60.similarity—on—Server—2 [i] [j] : = Euclidean—Distance (Sampl es_on_Server2 [i]，center_copy_2 [ j])61.end for62.end for63.64.for i : = 0 to num—Samples—on—Server—2 do65.id := min_index (similarity_on_Server_2)66.cluster—id [i+num—Sample—on—Server I] := id67.cluster—result [id] pushback [i+num—Sample_on_ServerI]68.end for69.70.for i : = 0 to num—Samples—on—Server—2 do71.if Samples_on_Server2 [i]. cluster_id = = m then72.sum—on—Server—2 [m] + = Samples—on—Server2 [i]73.end if74.end for75.......76.On server S 77.% Set up storage for the similarity between samples on thisserver and centers
78.Matrix similarity_on_Server_S = new Matrix [num—SampIes_on_Server—S][K]79.80.Matrix sum_on_Server_S = new Matrix [K] [nDimensions]81.% Compute similarity between the samples on this server andcenters82.for i : = 0 to num—Samples on—Server—S do83.for j = 0 to K do84.similarity—on—Server—S [i] [j] : = Euclidean—Distance ( Sampl es_on_ServerS [i]，center_copy_S [ j])85.end for86.end for87.88.for i : = 0 to num—Samples—on_Server_S do89.id := min_index (similarity_on_Server_S)90.cluster—id[i+nSamples-num—Samples—on—Server—S] = id91.cluster—result [id] pushback [i+nSamples-num—Samples—on—Server—S]92.end for93.94.for i : = 0 to num—Samples—on—Server—S do95.if Samples_on_ServerS[i]. cluster_id = = m then96.sum—on—Server—S [m] + = Samples—on—ServerS [i]97.end if98.end for99.100.% Update the centers101.Matrix sum = new Matirx [K] [nDimensions]102.for i = 0 to K do103.sum+ = sum—on—Server—i104.end for105.for i = 0 to K do106.center [i] : = sum[i]/size (cluster—result [i])107.end for108.109. end while110. return cluster—result111. END因此，圖1-5B的特徵和功能提供使用這裡描述的並行處理技術將樣本快速、高效且及時分組到期望數目的聚類。當然，會認識到，提供的例子僅為了圖示的目的，而不意在以某種方式進行限制。舉例來說，會認識到，可以在幾乎任意如下場景中利用這裡描述的技術，在所述場景中希望針對相對較大數據集和相對小得多的數據集來實現這裡所述的類型的整合操作。如所述的那樣，在這樣的場景中，相對較小的數據集的全部都可以被複製到多個可用核中的每ー個中，並且較大數據集可以細分為數目對應於可用核的數目的子集。之後，可以進行並行化處理，從而當合併運行的整合操作時，保證在兩個數據集的所有組合上的計算結果都被包括在內。因此，在這種整合操作先前局限於傳統的串行處理的這樣的場景和背景中，可以獲得並行處理的好處。這裡描述的各種技術的實現方式可以被實施在數字電子電路中，或者實施在計算機硬體、固件、軟體，或者它們的組合中。實現方式可以實施為電腦程式產品，即有形地具體實施在信息載體中的電腦程式，信息載體例如在機器可讀存儲設備中或者在傳播的信號中，以供數據處理裝置執行或者控制數據處理裝置的操作，所述數據處理裝置例如可編
程處理裝置、計算機或多個計算機。電腦程式，諸如上面描述的電腦程式，可以用任何形式的程式語言編寫，包括彙編語言或解釋語言，並且，它可以被以任何形式部署，包括作為獨立的程序或者作為模塊、組件、子程序或其他適於在計算環境中使用的単元。電腦程式可以被部署為在ー個計算機上執行或在位於ー個地點或跨過多個地點分布並被通信網絡互連起來的多個計算機上執行。方法步驟可以被ー個或多個可編程處理器執行，所述可編程處理器執行電腦程式，以便通過對輸入數據操作和產生輸出來執行功能。方法步驟還可以被專用邏輯電路執行，或者裝置可以被實施為專用邏輯電路，所述專用邏輯電路例如FPGA(現場可編程門陣列)或ASIC (專用集成電路)。作為例子，適於執行電腦程式的處理器包括通用和專用微處理器，以及任何類型的數字計算機的任意一個或多個處理器。一般來說，處理器將從只讀存儲器或隨機存取存儲器接收指令和數據，或者從兩者都接收指令和數據。計算機的元件可以包括至少ー個用於執行指令的處理器，和用於存儲指令和數據的ー個或多個存儲器設備。一般來說，計算機還可以包括，或者被可操作地連接，以從ー個或多個用於存儲數據的海量儲存設備接收數據，或把數據傳送到海量儲存設備，或者二者皆有，所述海量儲存設備例如磁碟、磁光碟或光碟。適於具體實施電腦程式指令和數據的信息載體包括所有形式的非易失性存儲器，作為例子，包括半導體存儲器器件，例如EPR0M、EEPROM和快閃記憶體設備、磁碟，例如內置硬碟或可移動磁碟、磁光碟和⑶-ROM以及DVD-ROM盤。處理器和存儲器可以以專用邏輯電路補充，或者被包含在專用邏輯電路中。為了提供和用戶的交互，實現方式可以在具有顯示設備和鍵盤以及定點設備的計算機上實施，顯示設備例如陰極射線管(CRT)或液晶顯示器(LCD)監視器，用於向用戶顯示信息，鍵盤和指示設備例如滑鼠或軌跡球，用戶利用它們可以提供到計算機的輸入。其他種類的設備也可以被用來提供和用戶的交互；例如，提供給用戶的反饋可以是任何形式的感覺反饋，例如視覺反饋、聽覺反饋或觸覺反饋，並且，可以以任何形式接收來自用戶的輸入，包括聲音、語音或觸覺輸入。實現方式可以被在包括後端組件或包括中間件組件或包括前端組件的計算系統中實施，或者在這些後端、中間件、前端組件的任意組合中實施，後端組件例如數據伺服器，中間件組件例如應用伺服器，前端組件例如具有圖形用戶界面，或Web瀏覽器的客戶端計算機，通過圖形用戶界面或Web瀏覽器，用戶可以和實現方式進行交互。可以利用數字數據通信的任何形式或介質互連組件，數字數據通信介質例如通信網絡。通信網絡的例子包括區域網(LAN)和廣域網(WAN)，例如網際網路。雖然如這裡所描述的那樣已經示出了所描述的實現方式的某些特徵，但是本領域普通技術人員現在應當想到很多修改、替換、變化或等同物。因此應當理解，所附權利要求旨在覆蓋落入實施例的實質精神內的所有這樣的 修改和變化。
權利要求
1.ー種包括記錄在計算機可讀介質上的指令的計算機系統，該系統包括 聚類選擇器，其被配置為確定多個樣本聚類，以及在多個處理核中的每ー個處再現所述多個樣本聚類； 樣本劃分器，其被配置為將存儲在資料庫中的具有關聯屬性的多個樣本劃分為數目對應於所述多個處理核的數目的樣本子集，並且還被配置為將所述數目的樣本子集中的每ー個與所述多個處理核中的對應ー個相關聯；以及 整合操作器，其被配置為基於所述多個處理核中的每個對應核處的每個樣本子集中的每個樣本的關聯屬性，執行所述每個樣本相對於在所述對應處理核處再現的多個樣本聚類中的每ー個的比較。
2.如權利要求I所述的系統，其中，所述聚類選擇器被配置為通過圖形用戶界面(GUI)從用戶接收多個樣本聚類的數目。
3.如權利要求I所述的系統，包括合併器，其被配置為合併所述在多個處理核中的每一個處執行的比較的比較結果，以便由此以所述多個樣本來填充所述樣本聚類。
4.如權利要求I所述的系統,其中,樣本子集的數目等於所述多個處理核的數目，並且其中，每個樣本子集包括相等數目的樣本。
5.如權利要求I所述的系統，還包括屬性劃分器，其被配置為將與每個樣本關聯的屬性劃分為屬性子集，以便在執行所述比較期間對其進行並行處理。
6.如權利要求I所述的系統，其中，所述比較包括在多個處理核中的每ー個處執行的、每個樣本子集中的每個樣本與每個聚類的中心之間的相似性比較。
7.如權利要求6所述的系統，其中，使用包括在每個聚類中的樣本的平均屬性值來確定每個聚類的中心。
8.如權利要求6所述的系統，其中，所述整合操作器被配置為基於所述比較將樣本從第一聚類重新指派到第二聚類。
9.如權利要求8所述的系統，包括合併器，其被配置為合併所述比較的比較結果以及被配置為根據需要使用經合併的比較結果來更新每個聚類的每個中心的值。
10.如權利要求9所述的系統，其中，所述合併器被配置為基於被重新指派的樣本的數目來確定每個聚類內樣本的穩定性。
11.一種計算機實現方法，包括 確定存儲在資料庫中的具有關聯屬性的多個樣本； 確定多個樣本聚類； 在多個處理核中的每ー個處再現所述多個樣本聚類； 將所述多個樣本劃分為數目與所述多個處理核的數目相對應的樣本子集； 將所述數目的樣本子集中的每ー個與所述多個處理核中的對應ー個相關聯；以及 基於在所述多個處理核的每個對應核處的每個樣本子集中的每個樣本的關聯屬性，執行所述每個樣本相對於在對應處理核處再現的多個樣本聚類中的每ー個的比較。
12.如權利要求11所述的方法，還包括合併所述在多個處理核中的每ー個處執行的比較的比較結果，以便由此以所述多個樣本來填充所述樣本聚類。
13.如權利要求11所述的方法，執行所述比較還包括將與每個樣本相關聯的屬性劃分為屬性子集，以便在執行所述比較期間對其進行並行處理。
14.如權利要求11所述的方法，其中，執行所述比較進ー步包括在多個處理核中的每一個處執行每個樣本子集中的每個樣本與每個聚類的中心之間的相似性比較。
15.一種電腦程式產品，該電腦程式產品被有形地具體實施在計算機可讀介質上並且包括指令，所述指令當被運行時被配置為執行如下步驟 確定存儲在資料庫中的具有關聯屬性的多個樣本； 確定多個樣本聚類； 在多個處理核中的每ー個處再現所述多個樣本聚類； 將所述多個樣本劃分為數目與所述多個處理核的數目相對應的樣本子集； 將所述數目的樣本子集中的每ー個與所述多個處理核中的對應ー個相關聯；以及 基於在所述多個處理核的每個對應核處的每個樣本子集中的每個樣本的關聯屬性，執行所述每個樣本相對於在對應處理核處再現的多個樣本聚類中的每ー個的比較。
16.如權利要求15所述的電腦程式產品，其中，所述指令當被運行時被配置為合併所述在多個處理核中的每ー個處執行的比較的比較結果，以便由此以所述多個樣本來填充所述樣本聚類。
17.如權利要求15所述的電腦程式產品，其中，所述指令當被運行時被配置為將與每個樣本關聯的屬性劃分為屬性子集，以便在執行所述比較期間對其進行並行處理。
18.如權利要求15所述的電腦程式產品，其中，所述比較包括在多個處理核中的每一個處執行的、每個樣本子集中的每個樣本與每個聚類的中心之間的相似性比較。
19.如權利要求15所述的電腦程式產品，其中，所述指令當被運行時被配置為基於所述比較將樣本從第一聚類重新指派到第二聚類。
20.如權利要求19所述的電腦程式產品，其中，所述指令當被運行時被配置為基於所述被重新指派的樣本的數目確定每個聚類內的樣本的穩定性。
全文摘要
本發明提供大規模數據聚類分析的並行化處理的方法和系統。聚類選擇器可以確定多個樣本聚類，以及可以在多個處理核中的每一個處再現所述多個樣本聚類。樣本劃分器可以將存儲在資料庫中的具有關聯屬性的多個樣本劃分為數目相應於所述多個處理核的數目的樣本子集，並且可以將所述數目的樣本子集中的每一個與所述多個處理核中的對應一個關聯。整合操作器可以基於所述多個處理核中的每個對應核處的每個樣本子集的每個樣本的關聯屬性，執行所述每個樣本相對於在所述對應處理核處再現的多個樣本聚類中的每一個的比較。
文檔編號G06F17/30GK102855259SQ20111018388
公開日2013年1月2日 申請日期2011年6月30日 優先權日2011年6月30日
發明者黎文憲, 孫谷飛 申請人:Sap股份公司