[發明專利]大規模文本數據的外部聚類方法及系統

無效

• 申請號: 200810012141.X
• 申請日: 2008-07-04
• 公開（公告）號: CN101308496A
• 公開（公告）日: 2008-11-19
• 發明（設計）人: 季鐸;蔡東風;張桂平;尹寶生;苗雪雷;周俏麗;白羽
• 申請（專利權）人: 沈陽格微軟件有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 沈陽世紀藍海專利事務所
• 代理人: 譚琦

技術領域：

本發明涉及信息技術領域中一種利用外部存儲器進行大規模文本數據聚類的方法及實現，基于檢索技術的外部文檔聚類方法，克服現有方法在處理問題規模和時間上的不足的大規模文本數據的外部聚類方法及系統。

背景技術：

近10年，以信息為基礎的組織或知識型企業煥發勃勃生機，創造和傳播知識已經成為檢驗企業核心能力的關鍵要素，知識的創造和應用能力成為不折不扣的企業核心競爭力的強力支撐。知識除儲存于員工的大腦中外，還根植于企業長期積累的各種文檔，以及其他應用系統的數據當中。如何在企業龐雜的信息數據中挖掘出知識，則首先需要將數據歸類分析，本發明則是其中一種歸類方法——聚類。聚類是按照事物的某些屬性、特征把事物聚集成類，使得類間的相似性最小，類內的相似性盡量大。由于聚類是一種無指導的學習方法，無需耗費大量的人力、物力，因此文本的自動聚類技術已成為最有效的突破信息處理的最主要手段。例如，基于聚類技術的搜索引擎，通過聚類技術可以對每個用戶的檢索結果進行歸類，當用戶檢索“軟件”時，可以將結果歸類為“病毒”、“辦公”等類別，這樣用戶可以更系統地掌握、分析檢索結果。

聚類能夠消耗大量存儲器和處理器資源，因為每個數據必須和其它數據逐一比較，以便識別數據間的類別關系。然而隨著數據的不斷積累，處理數據的規模成為了現有的聚類系統的最主要問題。參考文獻中有涉及一些處理規模較大的方法，如CURE和CURD，CURE是一種自底向上的層次聚類算法，首先將輸入的每個點作為一個聚類，然后合并相似的聚類，直到聚類的個數為k時為止。在CURE中指出，基于中心點的方法和所有的點的距離計算方法都不適合非球形或任意形狀的聚類，因此CURE采用了折衷的方法，即用固定數目的點表示一個聚類，從而提高了算法挖掘任意形狀的聚類的能力。CURE算法的時間復雜性為O(n*n)(低維數據)和O(n*n*logn)(高維數據)，算法在處理大量數據時必須基于抽樣、劃分等技術。CURD算法受CURE算法的啟發，不同的是采用了密度的方法屏蔽異常數據(噪音)對算法的影響，具有和K-MEANS算法相同的時間復雜性，效率較高。

由此可以看到現有的方法，只是在通過一種縮減的手段，利用少數的特點來代替大規模數據。但往往為了保證系統的性能，其選擇的代表點不能過少，因此從本質上上述方法還是沒有解決由于處理規模的空間復雜度而造成的不可計算問題。因此研制一種大規模文本數據的外部聚類方法及系統是國內外急需解決的新課題。

發明內容：

本發明的目的是提供一種新的利用外存進行聚類方法，在確保空間復雜度較低的前提下，利用最少的內、外存交互，實現一個處理數據規模大，執行效率高的聚類方法，對海量的雜亂的非結構化數據，進行有用資源正確提取，標明屬性，抽象特征，區分類別，使資源重新有序化，并實現跨來源、跨類別的廣泛關聯的大規模文本數據的外部聚類方法及系統。