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

無效

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

1、一種大規模文本數據的外部聚類方法及系統，其特征在于：方法的主要步驟包括：對輸入文本集的預處理，生成文本集的倒排索引和特征向量；采用檢索技術檢索每一文檔的候選關系集合；利用關系計算方法對有候選關系的文檔進行關系計算；排序輸出大于一定閾值的計算結果；聚類算法再依照排序結果，反復迭代合并具有第一直接關系的文本對，最終達到對文本集合的聚類輸出。

2、根據權利要求1所述的大規模文本數據的外部聚類方法設計的聚類系統，包括一候選分析器、關系生成器、關系選取和聚類部件，其特征在于：聚類的基本過程，首先每個樣本點都作為一個簇，通過檢索技術為每個樣本挑選出候選的具有聯系的候選點集合，而后利用關系生成器計算樣本與候選關系樣本間的關系，并按遞增/遞減順序輸出到外部存儲空間，然后在關系選取和聚類部件的控制下在外部存儲中反復地對樣本關系文件進行刪除合并，直到關系文件為空。

3、根據權利要求1所述的大規模文本數據的外部聚類方法及系統，其特征在于：基于文本檢索技術的樣本關系候選計算方法，該方法通過對描述數據的特征建立倒排索引，然后對于每一樣本都檢索出與其有共同特征的樣本作為候選樣本集合；聚類是一種消耗大量存儲器和處理器資源的方法，因為每個樣本必須和其它樣本進行逐一比較，以便識別出樣本間的類別關系；利用高效的倒排檢索技術可以最大程度地減少樣本關系計算中所占用的存儲器和處理器資源；這種過濾的過程可被稱為篩選，一些傳統聚類方法都有利用篩選，但是本發明中基于檢索技術的篩選尤其有效。

4、根據權利要求1和3所述的大規模文本數據的外部聚類方法及系統，其特征在于：當所有樣本計算出候選關系序列后，便需要計算樣本與樣本間的關系，這里稱之為距離或相似度；這個距離或相似度的值可以衡量兩個樣本的相似程度，是諸衡量兩個具有一定數量的特征和權值的數據的相似程度的方法或組合；各樣本間的距離或相似度通過一定閾值加以控制，如果距離/相似度低于/高于所對應的閾值，則這個關系則被按升序或降序保存到關系文件中；這種按順序保存的樣本關系可以減小其后的聚類中合并和選取的復雜度，減小磁盤交互帶來的時間開銷。

5、根據權利要求1和3所述的大規模文本數據的外部聚類方法及系統，其特征在于：通過排序的關系文件進行外部聚類的方法，該方法每次從存儲于外存的關系文件依次合并具有最先關系的樣本，而后在合并的基礎對現有關系進行裁剪；當關系文件為空時聚類過程結束，并將合并樣本集合作為結果進行輸出。