[發明專利]基于質心中間帶的K-MEANS聚類方法及系統

在審

• 申請號: 202010730251.0
• 申請日: 2020-07-27
• 公開（公告）號: CN111881975A
• 公開（公告）日: 2020-11-03
• 發明（設計）人: 周書田;薛雁;于海洋
• 申請（專利權）人: 青島網信信息科技有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 青島發思特專利商標代理有限公司 37212
• 代理人: 鞏同海;江鵬飛

本發明涉及一種基于質心中間帶的K?MEANS聚類方法及系統，屬于數據挖掘聚類分析技術領域。本發明包括如下步驟：S1:質心中間帶的提出：質心中間帶是指沿質心左右搖擺的地方設置一個中間帶，即此中間帶與各個質心間的距離差小于設定的閾值，該閾值設定為最小識別閾值Y；S2:最小識別閾值Y的選取；S3:最小距離的兩個分類的選取；S4：輸出方差的確定值。本發明在質心間的左右搖擺的地方設置一個質心中間帶，即此點與各個質心間的距離差小于設定的閾值，在此區域的點進行隨機歸類。該基于質心中間帶的K?MEANS聚類方法的好處在于能夠減少過擬合提高泛化，屬于對此算法一種新的K?MEANS算法改進。

技術領域

本發明涉及一種基于質心中間帶的K-MEANS聚類方法及系統，屬于數據挖掘聚類分析技術領域。

背景技術

聚類分析是研究分類問題的一種統計分析方法也是數據挖掘的一個重要方法。K-MEANS算法是一種基于劃分的聚類算法。目前的K-Means的主要缺點有：1)K值的選取不好把握；2)對于不是凸的數據集比較難收斂；3)如果各隱含類別的數據不平衡，比如各隱含類別的數據量嚴重失衡，或者各隱含類別的方差不同，則聚類效果不佳；4)采用迭代方法，得到的結果只是局部最優；5)對噪音和異常點比較的敏感。

發明內容

針對現有技術存在的上述缺陷，本發明提出了一種基于質心中間帶的K-MEANS聚類方法及系統。

本發明所述的基于質心中間帶的K-MEANS聚類方法及系統，包括如下步驟：

S1:質心中間帶的提出：質心中間帶是指沿質心左右搖擺的地方設置一個中間帶，即此中間帶與各個質心間的距離差小于設定的閾值，該閾值設定為最小識別閾值Y；

S2:最小識別閾值Y的選取，包括如下情形：

情況一：憑借對于數據的理解之上而給出固定的經驗，即先驗經驗；

情況二：根據算法迭代次數在一定范圍內遞增或遞減；

情況三：預設偏向某幾個分類，即偏好聚類；

S3:最小距離的兩個分類的選取，包括如下小步：

S31：輸入是樣本集D＝{x₁,x₂,...x_m},聚類的簇樹k,最大迭代次數N,輸出是簇劃分C＝{C₁,C₂,...Ck}；

S32：從樣本集D中隨機選擇k個樣本作為初始的k個質心：{μ₁,μ₂,...,μ_k}；

S33：將簇劃分C初始化為對于i＝1,2...m,計算樣本x_i和各個質心向量μ_j(j＝1,2,...k)的距離：

S34：選取最小距離的兩個分類，如果x_i與這兩個分類的距離差小于最小識別閾值Y，則隨機選取其中一個分類，將x_i標記為對應的類別λ_i；

S35：更新Cλ_i＝Cλ_i∪{x_i}，對于j＝1,2,...,k,對C_j中所有的樣本點重新計算新的質心：

如果所有的k個質心向量都沒有發生變化，則輸出簇劃分C＝{C₁,C₂,...C_k}；

S4：輸出方差的確定值，包括如下情況：

情況一：在質心中間帶點進行隨機歸類，隨機產生一個隨機數作為替代值，確定最小距離兩個樣本的方差；