[發明專利]一種基于免疫克隆灰狼優化算法的K-Means文本分類方法

有效

• 申請號: 202010122596.8
• 申請日: 2020-02-27
• 公開（公告）號: CN111368891B
• 公開（公告）日: 2023-06-13
• 發明（設計）人: 邱少明;張斌;杜秀麗;呂亞娜
• 申請（專利權）人: 大連大學
• 主分類號: G06F18/23213
• 分類號: G06F18/23213;G06F16/35;G06F40/289;G06F40/216
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 姜威威;李洪福

本發明公開了一種基于免疫克隆灰狼優化算法的K?Means文本聚類方法，屬于數據挖掘領域，該方法包括對文本數據進行數據預處理，采用余弦角度為相似性度量，分別計算預處理后的文本數據向量中的每一個數據對象到每一個初始灰狼個體的初始聚類中心點間的距離，再計算下一個灰狼個體的數據分配結果，直到灰狼種群中所有的灰狼個體都計算完畢，得到N種初步文本聚類結果，從適應度值降序排列的灰狼種群個體中，選擇前m個形成灰狼個體組成精英種群；根據Xsubgt;α/subgt;聚類中心得到最終的文本數據聚類結果；該方法可以克服傳統K?Means算法容易陷入局部最優，對初始聚類中心的過度依賴的局限性，極大的提高了文本數據劃分的準確性。

技術領域

本發明涉及數據挖掘領域，尤其涉及一種基于免疫克隆灰狼優化算法的K-Means文本分類方法。

背景技術

隨著科技進步和存儲成本的降低，人們傾向于用電子媒介存儲文本文件與信息。目前，絕大多數的信息的表現形式為文本形式，如何在大量的文本中提取用戶感謝興趣的、潛在有用的信息是需要解決的問題。文本挖掘是對文本信息進行數據挖掘的過程，隨著文本數據的增長，文本挖掘成為數據挖掘領域中的一個重要研究方向，而文本聚類是文本挖掘方法中重要的信息挖掘方法。

文本聚類主要是依據著名的聚類假設：同類的文檔相似度較大，而不同類的文檔相似度較小。作為一種無監督的機器學習方法，聚類由于不需要訓練過程，以及不需要預先對文檔手工標注類別，因此具有一定的靈活性和較高的自動化處理能力，已經成為對文本信息進行有效地組織、摘要和導航的重要手段。

而現如今用于文本聚類的方法一般分為5類：(1)基于劃分的文本聚類方法；(2)基于密度的文本聚類方法；(3)基于網格的文本聚類方法(4)基于層次的文本聚類方法；(5)基于模型的文本聚類

本發明所用到的文本聚類方法：K-Means算法，就是基于劃分的文本聚類方法：給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，KN。而且這K個分組滿足下列條件：(1)每一個分組至少包含一個數據紀錄；(2)每一個數據紀錄屬于且僅屬于一個分組(注意：這個要求在某些模糊聚類算法中可以放寬)；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的記錄越遠越好。如K-Means算法，K-MEDOIDS算法、CLARANS算法等；

Kmeans算法是一種典型的基于劃分的聚類算法，該聚類算法的基本思想是在聚類開始時根據用戶預設的類簇數目k隨機地在所有文本集當中選擇k個對象，將這些對象作為k個初始類簇的平均值或者中心，對于文本集中剩余的每個對象，根據對象到每一個類簇中心的歐幾里得距離，劃分到最近的類簇中；全部分配完之后，重新計算每個類簇的平均值或者中心，再計算每篇文本距離這些新的類簇平均值或中心的距離，將文本重新歸入目前最近的類簇中；不斷重復這個過程，直到所有的樣本都不能再重新分配為止。

但是K-Mean算法也存在著一些缺點：(1)對初始聚類中心的選取比較敏感，往往得不到全局最優解，得到的多是次優解；(2)關于算法需要預先設定的k值，限定了聚類結果中話題的個數，這在非給定語料的應用中并不可行；(3)該算法容易受到異常點的干擾而造成結果的嚴重偏差。因此多采用運用元啟發算法：如引力搜索算法、模擬退火算法、粒子群算法、遺傳算法，憑借其優秀的尋優能力以及收斂速度來克服K-Means算法的局限性，灰狼優化算法(Grey?Wolf?Optimizer，GWO)較上述提及的元啟發算法有更好的全局尋優能力，部分研究人員采用灰狼優化算法去克服K-Means算法的缺點：Kumar?V等開發了一種基于GWO算法的聚類算法，與傳統K-Means算法相比，提高了聚類性能；Zhang等提出了一種具有Powell局部優化的GWO聚類算法；楊紅光等提出了一種結合灰狼優化和K-Means的混合聚類算法，以解決K-Means算法對初始中心選擇敏感和全局搜索能力不足的缺點；劉佳銘同樣將GWO算法與K-Means算法結合以改善K-Means算法對初始聚類中心位置敏感的問題。