[發明專利]基于中心法的自適應文本聚類算法

有效

• 申請號: 201410014995.7
• 申請日: 2014-01-14
• 公開（公告）號: CN103699695B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 歐陽繼紅;周曉堂;李熙銘;馬超;王旭
• 申請（專利權）人: 吉林大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 長春市四環專利事務所(普通合伙)22103
• 代理人: 郭耀輝

技術領域

本發明屬于信息檢索領域，尤其涉及一種基于中心法并自適應確定聚類個數的文本聚類算法。

背景技術

文本聚類算法是機器學習、信息檢索等領域中一類主要的文本數據挖掘方法，是解決互聯網文本信息過載的主要途徑之一。其目的是按照“物以類聚”的原則組織互聯網文本集合，以得到一系列有意義的文本子集。其中，每個文本子集內的文本之間最大程度地相似，而不同文本子集的文本之間最大程度地不同。良好的文本聚類算法能夠將同話題同種類的文本聚集成一個有意義的文本子集，可以幫助互聯網用戶從海量文本信息中更容易地找到其最感興趣的內容。研究和運用文本聚類算法對于完成文本數據挖掘任務具有重要的理論價值和現實意義。

目前，已提出了多種文本聚類算法，大體分為如下三類：層次聚類算法、分割聚類算法和概率模型聚類算法。層次聚類算法通常以自頂向下或者自底向上的方式將文本集合組織成一個層次結構；分割聚類算法則按照某種選定標準將文本集合直接分割成幾個聚簇，聚簇的數目通常是預先設定的；而概率模型聚類算法通過概率主題模型來解決文本聚類問題。

其中，分割聚類算法因其具有容易理解、實現簡單的優點而被廣泛研究和使用。分割聚類算法的基本原理和過程是：首先，根據某一選定標準將數據集分割為k份，每份代表一個聚簇。分割產生的聚簇具備兩個特點：1）每個聚簇至少包含一個數據，2）每個數據只屬于一個聚簇。然后，通過反復的迭代過程對初次產生的劃分進行逐步調整。最后，當選定標準達到最優或者迭代收斂條件滿足時算法終止。

從上述算法過程可以看出：分割聚類在算法運行之前需要人工預先指定聚簇個數k，這是其主要問題之一。另外，根據前人研究：分割聚類算法在數據集包含較多類別時算法表現較差。綜上，分割聚類算法存在兩個主要問題：1）在算法運行之前需要人工預先指定聚簇個數；2）在數據集包含較多類別時算法表現較差。

發明內容

針對分割聚類算法在算法運行之前需要人工預先指定聚簇個數以及在數據集包含較多類別時算法表現較差這兩個問題，本發明的目的是提供一種在算法運行之前不需人工預先指定聚類個數（即根據數據集和算法運行情況自適應確定聚類個數）并且在數據集包含較多類別時算法表現較好的分割聚類算法。本發明方法：首先將文本數據集隨機分割成大小相同并且較小的一組聚簇；然后根據文本和各聚簇中心的相似度通過迭代過程對聚簇進行調整、對數據集進行重組；最后當終止條件達到時迭代過程終止，可以獲得更準確的聚類結果。

本發明提供了一種基于中心法并自適應確定聚簇個數的文本聚類算法，所述方法包括如下步驟：

步驟1：初始化算法相關參數

首先，初始化聚簇的“類—特征—中心”(CFC:Class-Feature-Centroid)向量計算參數：b和log函數的底數。其次，設置算法運行控制參數，包括：隨機聚類過程時的初始聚簇大小參數Im，重啟頻率參數Fm和重啟范圍Rm。最后，設置算法終止條件參數：最大迭代次數和收斂準確率。

步驟2：分割數據集

隨機將數據集分割為大小為Im的一組聚簇，并計算每個聚簇的CFC向量。

步驟3：重組數據集

根據每個文本和不同聚簇的CFC向量的相似度重新組織每個文本，以得到新的一組聚簇，重組過程包含兩種處理情況：

（1）非重啟迭代重組：將每個文本分配到和其最相似的CFC向量所屬的聚簇中。

（2）重啟迭代重組：將每個文本分配到和其第2到第Rm相似區間中的某一CFC向量所屬的聚簇中。

步驟4：重新計算各聚簇的CFC向量

在將所有文本重組之后，重新計算每個非空聚簇的CFC向量。

步驟5：判定算法是否終止

算法有兩個終止條件：最大迭代次數和收斂準確率。如果兩個終止條件有一個滿足，則算法終止。否則，算法繼續進行，轉到步驟3。

附圖說明

圖1基于中心法的自適應文本聚類算法流程示意圖。

圖2四個子數據集上本方法與其他4個方法的F值比較圖。

圖3四個子數據集上本方法與其他4個方法的純度比較圖。

圖4四個子數據集上本方法與其他4個方法的信息熵比較圖。

圖5參數Im和F值的關系圖。

圖6參數Fm和F值的關系圖。

圖7參數Rm和F值的關系圖。

圖8重啟和非重啟情況下的F值比較圖。

圖9重啟和非重啟情況下的純度比較圖。

圖10重啟和非重啟情況下的信息熵比較圖。

具體實施方式