對文檔進行聚類的方法和裝置製造方法
2023-05-24 13:42:51 1
對文檔進行聚類的方法和裝置製造方法
【專利摘要】本發明提供一種對文檔進行聚類的方法和裝置。該方法包括：步驟A、對文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標；步驟B、將多個文檔坐標聚為兩個簇並分別獲取每個簇在多維空間中的幾何中心；步驟C、分別計算每個簇的平均半徑，並在平均半徑滿足預設條件時，將兩個簇中的文檔坐標對應的文檔聚為一個不可分裂的類，在平均半徑不滿足預設條件時，將兩個簇分別對應為兩個可分裂的類，其中，平均半徑為簇中所有文檔坐標到幾何中心的距離的平均值；步驟D、在每個可分裂的類中，再次執行步驟B和步驟C；以及步驟E、當每篇文檔都屬於不可分裂的類時，終止聚類。通過本發明，提高了對文檔進行聚類的準確性和智能性。
【專利說明】對文檔進行聚類的方法和裝置
【技術領域】
[0001]本發明涉及網際網路領域，特別涉及一種對文檔進行聚類的方法和裝置。
【背景技術】
[0002]在互連網信息急劇增加的環境下，如何有效準確的得到所需的信息成為亟待解決的技術問題。其中，如何對網絡文檔進行聚類以得到多種文檔類別尤為關鍵。
[0003]現有技術中對文檔進行聚類的方法智能性較低，需要依靠人工的參與，即預先人工輸入聚類數值，確定將文檔聚為幾類後，才能開始聚類，例如，人工輸入將文檔聚為3類或4類。當人工輸入的聚類數值不準時，聚類效果會受到很大影響，進一步地，當文檔數量為海量時，人工無法給出一個聚類數值，聚類操作難以進行。
【發明內容】
[0004]本發明實施例提供一種對文檔進行聚類的方法和裝置，避免了人工參與，提高了對文檔進行聚類的準確性和智能性。
[0005]本發明為了實現上述目的提供一種對文檔進行聚類的方法，包括:步驟A、對文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標；步驟B、將多個文檔坐標聚為兩個簇並分別獲取每個簇在多維空間中的幾何中心；步驟C、分別計算每個簇的平均半徑，並在平均半徑滿足預設條件時，將兩個簇中的文檔坐標對應的文檔聚為一個不可分裂的類，在平均半徑不滿足預設條件時，將兩個簇分別對應為兩個可分裂的類，其中，平均半徑為簇中所有文檔坐標到幾何中心的距離的平均值；步驟D、在每個可分裂的類中，再次執行步驟B和步驟C ；以及步驟E、當每篇文檔都屬於不可分裂的類時，終止聚類。
[0006]在一個實施例中，步驟B包括:步驟F、根據文檔坐標的距離將多個文檔坐標聚為兩個簇中。
[0007]在一個實施例中，步驟F包括:步驟G、等概率選取兩個文檔坐標；步驟H、分別計算每個未選取的文檔坐標與選取的兩個文檔坐標的距離，並將未選取的文檔坐標與距其距離短的選取的文檔坐標聚為同一個簇。
[0008]在另一個實施例中，步驟F包括:步驟G、隨機選取一個文檔坐標；步驟H、將在選取的文檔坐標預設距離內的多個文檔坐標聚為一個簇，將不在選取的文檔坐標預設距離內的多個文檔坐標聚為一個簇。
[0009]在一個實施例中，在步驟B與步驟C之間，還包括:步驟1、將每個文檔坐標與兩個幾何中心進行比較，並將其與兩個幾何中心中距其距離短的幾何中心聚為一個新一代的簇；步驟J、獲取每個新一代的簇在多維空間中的幾何中心，當相鄰兩代的簇的幾何中心的距離差值不滿足預設的閾值時，重複步驟I，當相鄰兩代的簇的幾何中心的距離差值滿足預設的閾值時，執行步驟C。
[0010]在一個實施例中，預設條件包括:兩個簇的平均半徑之和不小於兩個幾何中心之間的距離。
[0011]本發明為了實現上述目的還提供一種對文檔進行聚類的裝置，包括:獲取模塊，用於對所述文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標；第一分類模塊，用於將多個所述文檔坐標聚為兩個簇並分別獲取每個簇在所述多維空間中的幾何中心；處理模塊，用於分別計算所述每個簇的平均半徑，並在所述平均半徑滿足預設條件時，將所述兩個簇中的所述文檔坐標對應的文檔聚為一個不可分裂的類，在所述平均半徑不滿足預設條件時，將所述兩個簇分別對應為兩個可分裂的類，其中，所述平均半徑為所述簇中所有文檔坐標到所述幾何中心的距離的平均值；第一調用模塊，用於在所述每個可分裂的類中，再次調用所述第一分類模塊和所述處理模塊對所述可分裂的類中的文檔坐標進行操作；以及終止模塊，用於當每篇文檔都屬於不可分裂的類時，終止聚類。
[0012]在一個實施例中，第一分類模塊根據文檔坐標的距離將多個文檔坐標聚為兩個簇中。
[0013]在一個實施例中，第一分類模塊包括:選取子模塊，用於等概率選取兩個文檔坐標；分類子模塊，用於分別計算每個未選取的文檔坐標與選取的兩個文檔坐標的距離，並將未選取的文檔坐標與距其距離短的選取的文檔坐標聚為同一個簇。
[0014]在另一個實施例中，第一分類模塊包括:選取子模塊，用於隨機選取一個文檔坐標；分類子模塊，用於將在選取的文檔坐標預設距離內的多個文檔坐標聚為一個簇，將不在選取的文檔坐標預設距離內的多個文檔坐標聚為一個簇。
[0015]在一個實施例中，上述裝置還包括:第二分類模塊，用於將每個文檔坐標與兩個幾何中心進行比較，並將其與兩個幾何中心中距其距離短的幾何中心聚為一個新一代的簇；第二調用模塊，用於獲取每個新一代的簇在多維空間中的幾何中心，當相鄰兩代的簇的幾何中心的距離差值不滿足預設的閾值時，調用第二分類模塊，當相鄰兩代的簇的幾何中心的距離差值滿足預設的閾值時，調用處理模塊。
[0016]在一個實施例中，預設條件包括:兩個簇的平均半徑之和不小於兩個幾何中心之間的距離。
[0017]本發明既能準確地對文檔進行聚類，也避免了人工參與，提高了對文檔進行聚類的準確性和智能性。
【專利附圖】
【附圖說明】
[0018]此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，並不構成對本發明的限定。在附圖中:
[0019]圖1是根據本發明實施例的對文檔進行聚類的方法的流程圖；
[0020]圖2是根據本發明優選實施例的對文檔進行聚類的方法的流程圖；
[0021]圖3是根據本發明實施例的等概率選取2個文檔坐標的示意圖；
[0022]圖4A是根據本發明實施例的預設條件判斷標準一的示意圖；
[0023]圖4B是根據本發明實施例的預設條件判斷標準二的示意圖；
[0024]圖5是根據本發明實施例的對文檔進行聚類的裝置的結構框圖；
[0025]圖6是根據本發明優選實施例的對文檔進行聚類的裝置的結構框圖；
[0026]圖7是根據本發明的另一優選實施例的對文檔進行聚類的裝置的結構框圖。【具體實施方式】
[0027]為使本發明的目的、技術方案和優點更加清楚明白，下面結合附圖對本發明實施例作進一步詳細說明。在此，本發明的示意性實施例及其說明用於解釋本發明，但並不作為對本發明的限定。
[0028]現在將參考附圖進一步詳細描述本發明。本發明可以許多不同的形式來實現，不應該被理解為僅限於此處所闡述的實施例。這些實施例只作為示例提供，以便為本領域技術人員提供對本發明的完全理解。
[0029]圖1是根據本發明實施例的對文檔進行聚類的方法的流程圖。如圖1所示，包括步驟102至步驟110。
[0030]在步驟102中，對獲取到的多篇文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標。
[0031]在步驟104中，將多個文檔坐標聚為兩個簇並分別獲取每個簇在多維空間中的幾何中心。
[0032]在步驟106中，分別計算每個簇的平均半徑，並根據平均半徑，將每個簇中的文檔坐標聚為兩個可分裂的類或一個不可分裂的類。具體地，在平均半徑滿足預設條件時，將兩個簇中的文檔坐標對應的文檔聚為一個不可分裂的類，在平均半徑不滿足預設條件時，將兩個簇分別對應為兩個可分裂的類，其中，平均半徑為簇中所有文檔坐標到幾何中心的距離的平均值。
[0033]聚類條件可以根據具體情況進行設置，例如預設條件為兩個簇的平均半徑之和不小於兩個幾何中心之間的距離。
[0034]在步驟108中，在可分裂的類中，再次執行步驟104和步驟106。
[0035]在步驟110中，當每篇文檔都屬於不可分裂的類時，終止聚類。
[0036]在本實施例中，先將所有的文檔對應的文檔坐標聚成兩個簇，再在每一類中通過文檔坐標的距離判斷文檔內容的緊密度，並判斷每個簇是否需要繼續分裂，從而自動根據文檔內容對文檔進行聚類，該方法既能準確地對文檔進行聚類，也避免了人工參與，提高了對文檔進行聚類的準確性和智能性。
[0037]圖2是根據本發明優選實施例的對文檔進行聚類的方法的流程圖。如圖2所示，包括步驟202至步驟220。
[0038]步驟202，分別對多篇文檔進行分詞。
[0039]分詞過程可以基於詞庫的正向最大匹配，非詞庫中的連續出現的英文數字混排字符也會作分詞處理。具體步驟可包括:
[0040]獲取詞庫，詞庫中包括常用的詞彙，例如各常用的動詞和名詞。
[0041]將網頁文檔中的文字與詞庫匹配以進行分詞。
[0042]步驟204，分別對分詞後的各文檔進行矢量化。
[0043]矢量化後的文檔對應一個文檔向量，該文檔向量同時也表示多維空間中的一個文檔坐標。
[0044]首先獲取在步驟202中分出的所有去重後的詞語，生成列表。以3篇文檔為例，文檔I中包括a、b、c和d四個詞語，文檔2中包括b、a、e和f四個詞語，文檔3包括c、b、a、e和d五個詞語,去重後生成的列表為a、b、C、d、e和f。
[0045]然後可以根據列表中的詞語的詞頻值等詞語特性進行矢量化。例如，a的詞頻值為xl，b的詞頻值為x2，c的詞頻值為x3，d的詞頻值為x4，e的詞頻值為x5，f的詞頻值為x6，則列表矢量化的結果為(xl，x2，x3, x4, x5, x6),由於列表矢量化的結果是6維的，因此將各文檔按照列表的順序進行矢量化後，各文檔矢量化後分別對應6維空間中的一個文檔坐標，文檔I對應的文檔坐標為(xl，x2, x3, x4，0，0)，文檔2對應的文檔坐標為(xl，x2,
0,0, x5, x6)，文檔 3 對應的文檔坐標為(xl，x2, x3, x4, x5，0)。
[0046]步驟206，根據文檔坐標的距離將多個文檔坐標分到兩個簇中。
[0047]在本實施例的一種具體實現方式中，可以先等概率選取2個文檔坐標，使得η個文檔坐標中，每個文檔坐標被選取的概率為2/η。
[0048]等概率選取2個文檔坐標的具體過程如下:
[0049]首先，將η個文檔坐標中的前2個文檔坐標存放在預設位置中。
[0050]隨即，當出現第3個文檔坐標時，由於總共有3個文檔坐標，而預設位置僅能存放2個文檔坐標，因此第3個文檔坐標有2/3的概率被選擇存放到預設位置，當第3個文檔坐標被選擇時，該文檔坐標隨機替換已存放在預設位置的前2個文檔坐標中的一個。同理，當出現第4個文檔坐標時，由於總共有4個文檔坐標，而預設位置僅能存放2個文檔坐標，因此第4個文檔坐標有2/4的概率被選擇，當第4個文檔坐標被選擇時，該文檔坐標隨機替換在預設位置已存放的一個文檔坐標，以此類推。由於預設位置每次最多僅有I個文檔坐標發生替換，因此每個文檔坐標被選取的概率是相等的。
[0051]因此，η個文檔坐標遍歷完畢後，預設位置的2個文檔坐標就是等概率隨機選取的，概率為2/η。優於隨機從η個文檔坐標中選取2個文檔坐標。因為隨機坐標選取中，第一次選取一個文檔坐標的概率是1/η，第二次選取一個文檔坐標的概率是I/ (η-1)，後被選取的文檔坐標被選取的概率大於先被選取的文檔坐標。
[0052]圖3是根據本發明實施例的等概率選取2個文檔坐標的流程圖。如圖3所示，包括以下步驟302至步驟312。
[0053]步驟302，將η個文檔坐標的前2個放入預設位置。
[0054]步驟304，獲取隨機數i (2 < i < n)，令初始i=3。
[0055]其中，η為文檔坐標的個數。本實施例因為前2個文檔坐標已經放入預設位置，因此初始值i從第3個文檔坐標開始，計算從多個文檔坐標中選取2個文檔坐標的概率。
[0056]步驟306，從i個文檔坐標中選2個放入預設位置，每個文檔坐標概率2/i。
[0057]步驟308，判斷i〈n，如果是，執行步驟310 ;如果否，執行步驟312。
[0058]在本步驟中，判斷是否已經遍歷了所有的文檔坐標。
[0059]步驟310，令i=i+l，並執行步驟306。
[0060]如果沒有遍歷所有的文檔坐標，則繼續計算增加一個文檔坐標時選取2個文檔坐標的概率。由於每次計算相比上一次計算，僅增加一個文檔坐標，因此，預設位置最多只出現一個文檔坐標的替換，每個文檔坐標被替換的概率是相等的。
[0061]步驟312，得到從η個文檔坐標中選2個放入預設位置的概率2/η，流程結束。
[0062]當i=n時，預設位置存放的2個文檔坐標即為等概率選出的，概率均為2/η。
[0063]在選取2個文檔坐標後，計算未被選取的文檔坐標分別和這兩個選取的文檔坐標的歐幾裡德距離或餘弦距離；本實施例以歐幾裡德距離為例:假設未被選取的文檔坐標z3和兩個選取的文檔坐標zl及z2的距離分別為1 |z3-zl| 1與1 |z3-z2| |，將z3與距其距離短的文檔坐標zl或z2聚為同一個簇，以相同的步驟將其他未被選取的坐標文檔聚到某一個簇中。
[0064]通過等概率選取，避免了後出現的文檔坐標被選取的概率較高的情況。
[0065]在本實施例的另一種具體實現方式中，可以先隨機選取一個文檔坐標，然後根據經驗值將該文檔坐標預設距離內的文檔坐標聚為同一個簇，再將所有其他的文檔坐標聚為同一個簇。該實現方式的計算量小，聚類效果介於隨機選取兩個文檔坐標和等概率選取兩個文檔坐標之間。
[0066]步驟208，確定每個簇的幾何中心。
[0067]在本步驟中，分別計算每個簇中文檔坐標均值，假設文檔坐標的維度為M,則，一個簇的幾何中心c=(2xl/nl, Σχ2/η1, Σχ3/η1,..., ΣχΜ/nl),其中，nl為該簇包含的文檔坐標的個數。
[0068]步驟210，根據幾何中心重新將所有文檔坐標聚為兩個簇。
[0069]分別計算所有的文檔坐標和這兩個幾何中心的距離，並根據步驟206的方法將所有文檔坐標聚為兩個簇。
[0070]步驟212，確定每個簇的新一代的幾何中心。
[0071]步驟214，計算新一代的幾何中心和上一代幾何中心的距離，當該距離滿足預設的閾值內時，執行步驟216 ;否則，再次執行步驟210至步驟212。例如，閾值為5個單位，當該距離為3個單位時,則滿足該閾值,執行步驟216,但該距離為10個單位時,不滿足該閾值，返回至步驟210。最終分別獲取兩個簇中確定的幾何中心Cl和c2。
[0072]步驟216，分別計算每個簇的平均半徑。
[0073]—個簇的平均半徑r=Σ (c-z1)/nl,其中，c為最後該簇確定的幾何中心，z1為簇中的文檔坐標,1為1到nl之間任一整數，nl為該簇包含的文檔坐標的個數。通過本步驟，可以分別測得兩個簇的半徑rl和r2。
[0074]步驟218，判斷兩個簇的平均半徑是否滿足預設條件，並據此對上述兩個簇進行聚類。在本實施例的一個實現方式中，該預設條件為兩個簇的平均半徑之和(rl+r2)不小於兩個幾何中心的距離1 |cl-c2| 1的大小。當(rl+r2)≥| |cl-c2| |時，將兩個簇中的文檔坐標對應的文檔分別聚為兩個可分裂的類；1(rl+r2)〈| cl-c2 |時，將兩個簇中的文檔坐標對應的文檔聚為一個不可分裂的類。
[0075]對每個可分裂的類，再次執行步驟206至步驟218。
[0076]圖4是根據本發明實施例的預設條件判斷標準示意圖，在計算出兩個簇的平均半徑rl、r2和兩個幾何中心的距離1 |cl-c2| |後，可以通過示意圖直觀的判斷兩個簇的緊密度。分別生成以cl為圓心，r1為半徑的圓,和以c2為圓心，r2為半徑的圓，如圖4A所示的判斷標準一，當兩個圓相交時，表示(rl+r2)〈| |cl-c2| |，說明兩個簇中的文檔坐標對應的文檔緊密度高，有交叉的內容，因此這兩個簇中的文檔坐標對應的文檔應該聚為同一類；如圖4B所示的判斷標準二，當兩個圓相離或相切時,表示(rl+r2)≥| |cl-c2| 1,說明兩個簇中的文檔坐標對應的文檔緊密度不高，內容相對獨立，因此這兩個簇中的文檔坐標對應的文檔應該分別聚為同一類，對這兩個類中的文檔，應該再次執行本實施例的上述步驟，判斷是否能夠繼續細分。
[0077]步驟220，當所有的文檔都屬於某一不可分裂的類中時，終止聚類。
[0078]通過本實施例，可以通過文檔在多維空間中的文檔坐標之間的距離判斷文檔之間內容的緊密程度，從而自動進行聚類。進一步地，還可以根據聚類最終結果獲知多篇文檔被聚為幾類，如若在採用其他聚類方法時，該聚類數目可以作為參考。
[0079]本實施例還提供了一種對文檔進行聚類的裝置，該裝置的各模塊和子模塊分別對應於本實施例中的對文檔進行聚類的方法的各步驟。
[0080]圖5是根據本發明實施例的對文檔進行聚類的裝置500的結構框圖。如圖5所示，該裝置包括獲取模塊502、第一分類模塊504、處理模塊506、第一調用模塊508和終止模塊510。
[0081]獲取模塊502用於對文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標。
[0082]第一分類模塊504用於將多個文檔坐標聚為兩個簇並分別獲取每個簇在多維空間中的幾何中心。
[0083]處理模塊506用於分別計算每個簇的平均半徑，並在平均半徑滿足預設條件時，將兩個簇中的文檔坐標對應的文檔聚為一個不可分裂的類，在平均半徑不滿足預設條件時，將兩個簇分別對應為兩個可分裂的類，其中，平均半徑為簇中所有文檔坐標到幾何中心的距離的平均值。
[0084]第一調用模塊508用於在每個可分裂的類中，再次調用第一分類模塊504和處理模塊506對上述可分裂的類中的文檔坐標進行操作。
[0085]終止模塊510用於當每篇文檔都屬於不可分裂的類時，終止聚類。
[0086]圖6是根據本發明優選實施例的對文檔進行聚類的裝置600的結構框圖。如圖6所不，第一分類模塊504中包括選取子模塊602和分類子模塊604。
[0087]在一個實施例中，選取子模塊602用於等概率選取兩個文檔坐標。分類子模塊604用於分別計算每個未選取的文檔坐標與選取的兩個文檔坐標的距離，並將未選取的文檔坐標與距其距離短的選取的文檔坐標聚為同一個簇。
[0088]在另一個實施例中，選取子模塊602用於隨機選取一個文檔坐標。分類子模塊604用於將在選取的文檔坐標預設距離內的多個文檔坐標聚為一個簇，將不在選取的文檔坐標預設距離內的多個文檔坐標聚為一個簇。
[0089]圖7是根據本發明的另一優選實施例的對文檔進行聚類的裝置700的結構框圖。如圖7所示，本裝置還包括第二分類模塊702和第二調用模塊704。
[0090]第二分類模塊702用於將每個文檔坐標與兩個幾何中心進行比較，並將其與兩個幾何中心中距其距離短的幾何中心聚為一個新一代的簇。
[0091]第二調用模塊704用於獲取每個新一代的簇在多維空間中的幾何中心，當相鄰兩代的簇的幾何中心的距離差值滿足預設的閾值時，調用第二分類模塊702，當相鄰兩代的簇的幾何中心的距離差值不滿足預設的閾值時，調用處理模塊506。
[0092]本實施例相比於現有技術，能夠快速確定聚類數值，準確完成聚類操作。
[0093]本領域技術人員還可以進一步意識到，結合本文中所公開的實施例描述的各示例的單元及算法步驟，能夠以電子硬體、計算機軟體或者二者的結合來實現，為了清楚地說明硬體和軟體的可互換性，在上述說明中已經按照功能一般性地描述了各示例的組成及步驟。這些功能究竟以硬體還是軟體方式來執行，取決於技術方案的特定應用和設計約束條件。本領域技術人員可以對每個特定的應用來使用不同方法來實現所描述的功能，但是這種實現不應認為超出本發明的範圍。
[0094]結合本文中所公開的實施例描述的方法或算法的步驟可以用硬體、處理器執行的軟體模塊，或者二者的結合來實施。軟體模塊可以置於隨機存儲器(RAM)、內存、只讀存儲器(ROM)、電可編程ROM、電可擦除可編程ROM、寄存器、硬碟、可移動磁碟、CD-ROM、或【技術領域】內所公知的任意其它形式的存儲介質中。
[0095]以上的【具體實施方式】，對本發明的目的、技術方案和有益效果進行了進一步詳細說明，所應理解的是，以上僅為本發明的【具體實施方式】而已，並不用於限定本發明的保護範圍，凡在本發明的精神和原則之內，所做的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
【權利要求】
1.一種對文檔進行聚類的方法，其特徵在於，包括: 步驟A、對所述文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標； 步驟B、將多個所述文檔坐標聚為兩個簇並分別獲取每個簇在所述多維空間中的幾何中心； 步驟C、分別計算所述每個簇的平均半徑，並在所述平均半徑滿足預設條件時，將所述兩個簇中的所述文檔坐標對應的文檔聚為一個不可分裂的類，在所述平均半徑不滿足預設條件時，將所述兩個簇分別對應為兩個可分裂的類，其中，所述平均半徑為所述簇中所有文檔坐標到所述幾何中心的距離的平均值； 步驟D、在所述每個可分裂的類中，再次執行所述步驟B和所述步驟C ；以及 步驟E、當每篇文檔都屬於不可分裂的類時，終止聚類。
2.根據權利要求1所述的方法，其特徵在於，步驟B包括: 步驟F、根據所述文檔坐標的距離將多個所述文檔坐標聚為兩個簇中。
3.根據權利要求2所述的方法，其特徵在於，步驟F包括: 步驟G、等概率選取兩個所述文檔坐標； 步驟H、分別計算每個未選取的所述文檔坐標與選取的所述兩個所述文檔坐標的距離，並將未選取的所述文檔坐標與距其距離短的選取的所述文檔坐標聚為同一個簇。
4.根據權利要求2所述的方法，其特徵在於，步驟F包括: 步驟G、隨機選取一個所述文檔坐標； 步驟H、將在選取的所述文檔坐標預設距離內的多個所述文檔坐標聚為一個簇，將不在選取的所述文檔坐標預設距離內的多個所述文檔坐標聚為一個簇。
5.根據權利要求1所述的方法，其特徵在於，在步驟B與步驟C之間，還包括: 步驟1、將每個所述文檔坐標與所述兩個幾何中心進行比較，並將其與所述兩個幾何中心中距其距離短的幾何中心聚為一個新一代的簇； 步驟J、獲取每個所述新一代的簇在所述多維空間中的幾何中心，當相鄰兩代的簇的幾何中心的距離差值不滿足預設的閾值時，重複步驟J，當相鄰兩代的簇的幾何中心的距離差值滿足預設的閾值時，執行步驟C。
6.根據權利要求1所述的方法，其特徵在於，所述預設條件包括: 兩個簇的平均半徑之和不小於兩個所述幾何中心之間的距離。
7.一種對文檔進行聚類的裝置，其特徵在於，包括: 獲取模塊，用於對所述文檔分別進行矢量化，其中，每篇文檔在矢量化後對應多維空間中的一個文檔坐標； 第一分類模塊，用於將多個所述文檔坐標聚為兩個簇並分別獲取每個簇在所述多維空間中的幾何中心； 處理模塊，用於分別計算所述每個簇的平均半徑，並在所述平均半徑滿足預設條件時，將所述兩個簇中的所述文檔坐標對應的文檔聚為一個不可分裂的類，在所述平均半徑不滿足預設條件時，將所述兩個簇分別對應為兩個可分裂的類，其中，所述平均半徑為所述簇中所有文檔坐標到所述幾何中心的距離的平均值； 第一調用模塊，用於在所述每個可分裂的類中，再次調用所述第一分類模塊和所述處理模塊對所述可分裂的類中的文檔坐標進行操作；以及 終止模塊，用於當每篇文檔都屬於不可分裂的類時，終止聚類。
8.根據權利要求7所述的裝置，其特徵在於，所述第一分類模塊根據所述文檔坐標的距離將多個所述文檔坐標聚為兩個簇中。
9.根據權利要求8所述的裝置，其特徵在於，所述第一分類模塊包括: 選取子模塊，用於等概率選取兩個所述文檔坐標； 分類子模塊，用於分別計算每個未選取的所述文檔坐標與選取的所述兩個所述文檔坐標的距離，並將未選取的所述文檔坐標與距其距離短的選取的所述文檔坐標聚為同一個簇。
10.根據權利要求8所述的裝置，其特徵在於，所述第一分類模塊包括: 選取子模塊，用於隨機選取一個所述文檔坐標； 分類子模塊，用於將在選取的所述文檔坐標預設距離內的多個所述文檔坐標聚為一個簇，將不在選取的所述文檔坐標預設距離內的多個所述文檔坐標聚為一個簇。
11.根據權利要求7所述的裝置，其特徵在於，所述裝置還包括: 第二分類模塊，用於將每個所述文檔坐標與所述兩個幾何中心進行比較，並將其與所述兩個幾何中心中距其距離短的幾何中心聚為一個新一代的簇； 第二調用模塊，用於獲取每個所述新一代的簇在所述多維空間中的幾何中心，當相鄰兩代的簇的幾何中心的距離差值不滿足預設的閾值時，調用所述第二分類模塊，當相鄰兩代的簇的幾何中心的距離差值滿足預設的閾值時，調用所述處理模塊。
12.根據權利要求7所述的裝置，其特徵在於，所述預設條件包括: 兩個簇的平均半徑之和不小於兩個所述幾何中心之間的距離。
【文檔編號】G06F17/30GK103455534SQ201310157114
【公開日】2013年12月18日 申請日期:2013年4月30日 優先權日:2013年4月30日
【發明者】黃平春 申請人:北界創想（北京）軟體有限公司