[發(fā)明專利]基于增量成員選擇和改進共協(xié)矩陣的聚類融合方法

在審

• 申請?zhí)枺?/td>: 201610877582.0
• 申請日: 2016-10-08
• 公開（公告）號: CN106650772A
• 公開（公告）日: 2017-05-10
• 發(fā)明（設計）人: 馬廷淮;吳秀格;薛羽;曹杰
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 江蘇愛信律師事務所32241
• 代理人: 唐小紅

技術領域

本發(fā)明屬于數(shù)據(jù)挖掘領域，具體涉及的是一種利用對聚類融合的成員進行增量選擇和對共協(xié)矩陣進行改進的聚類融合方法。

背景技術

數(shù)據(jù)聚類作為一種了解數(shù)據(jù)集結構的有用工具，已經被廣泛應用于各種領域，如生物學、模式識別、物理學和推薦系統(tǒng)等。聚類的目標是把數(shù)據(jù)劃分到簇，使得同一個簇內的對象更相似，不同簇內的對象不相似。盡管關于聚類的研究(海沫.大數(shù)據(jù)聚類算法綜述[J].計算機科學,2016(s1))中有許多聚類算法，但是每個聚類算法都有優(yōu)點和缺點，故而并不是每個算法都能適用于所有數(shù)據(jù)集。

近年來，聚類融合作為一個十分重要的數(shù)據(jù)分析工具，已經克服了上述缺陷。聚類融合的主要目標是合并不同聚類算法的聚類結果，生成一個更準確的共識聚類結果。聚類融合的精度優(yōu)先于獨立的聚類算法。現(xiàn)有研究表明，要得到較優(yōu)的聚類融合結果，必須同時考慮聚類成員的質量和聚類成員之間的差異性(李丹丹.基于權重設計的聚類融合算法研究及應用[D].遼寧工程技術大學,2009)。聚類融合綜合利用了多種聚類算法對數(shù)據(jù)進行聚類，避免了使用單一聚類算法的缺點。

聚類融合的核心思想是將由不同聚類算法得到的多個聚類結果進行合并，使最終融合后的結果在最大程度上共享所有單個聚類結果對數(shù)據(jù)集的聚類信息，且優(yōu)于單個聚類算法的結果(秦鋒,陳奇明,程澤凱.聚類融合算法研究[J].計算機技術與發(fā)展,2010,20(07):106-108)。聚類融合的定義為：合并多個對一組對象進行劃分的不同結果，且不使用對象原有的特征。聚類融合方法由兩部分組成：聚類成員生成和共識函數(shù)設計。假設原始數(shù)據(jù)集X有n個樣本X＝{x₁,x₂,…x_n}，首先由單個或多個聚類算法對數(shù)據(jù)集X進行M次有差異的劃分，得到M組聚類結果P＝{P₁,P₂,…P_M}，即M個聚類融合成員，其中P_m(m＝1,2,…M)為第m次聚類得到的聚類結果，每個聚類融合成員P_m中都有k_m個簇。最后，設計一個共識函數(shù)Γ對M個聚類成員進行集成得到一個最終的劃分P^*(劉雄.基于k-means的改進聚類融合算法的研究與應用[D].中南大學,2011)。

發(fā)明內容

本發(fā)明綜合考慮平方誤差和、局部成本函數(shù)、融合成員之間的相似度等因素，增量選擇聚類融合成員(侯娟.聚類融合算法及其應用研究[D].中南大學,2010)，篩除對最終聚類結果貢獻相對較少的聚類融合成員。利用選中的聚類融合成員，根據(jù)成員劃分之間的關系，考慮兩個數(shù)據(jù)點同時出現(xiàn)在一個簇的概率和該簇的穩(wěn)定性，構造改進的共協(xié)矩陣(李丹丹,褚麗麗.加權共協(xié)矩陣聚類融合研究[J].科技和產業(yè),2010,10(1):89-91)。根據(jù)共協(xié)矩陣構造加權圖，應用歸一化割算法(王洋洋,劉柏嵩,劉薇.基于歸一化割的主題劃分算法研究[J].寧波大學學報(理工版),2013(4):40-44)對加權圖進行分割得到最終聚類結果。

本發(fā)明所要解決的技術問題是基于增量成員選擇和改進共協(xié)矩陣的聚類融合方法。通過綜合平方誤差和、局部成本函數(shù)、聚類融合成員之間的相似度等因素，增量選擇融合成員，篩除對最終聚類結果貢獻相對較少的融合成員。利用選中的融合成員，根據(jù)成員劃分之間的關系，考慮兩個數(shù)據(jù)點同時出現(xiàn)在一個簇的概率和該簇的穩(wěn)定性，構造改進的共協(xié)矩陣。根據(jù)共協(xié)矩陣構造加權圖，應用歸一化割算法對加權圖進行分割得到最終聚類結果。本發(fā)明能夠有效減少原來聚類融合算法的工作量，篩除對于最終聚類結果影響較小的融合成員，同時提高聚類融合的準確度和精度。

本發(fā)明的技術方案如下：

基于增量成員選擇和改進共協(xié)矩陣的聚類融合方法，包括以下步驟：

步驟1)，用K-means算法對數(shù)據(jù)集X進行M次有差異的聚類，最終得到M個有差異的劃分P₁,P₂,…P_M，組成聚類融合成員集合Old＝{P₁,P₂,…P_M}。