[發(fā)明專利]一種基于二分模塊度的模糊聚類評(píng)價(jià)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910205966.1
• 申請(qǐng)日: 2019-03-19
• 公開(kāi)（公告）號(hào): CN110097072B
• 公開(kāi)（公告）日: 2022-10-04
• 發(fā)明（設(shè)計(jì)）人: 劉永利;韓光偉;郭倩倩;陳敬麗;楊合超
• 申請(qǐng)（專利權(quán)）人: 河南理工大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明提出了一種基于二分模塊度的模糊聚類評(píng)價(jià)方法，將類內(nèi)緊致性、類間分離性與二分模塊度融合在一起，用于確定模糊C均值聚類算法的最優(yōu)分類結(jié)果。該指標(biāo)結(jié)合類內(nèi)緊致性與類間分離性，增強(qiáng)了指標(biāo)的魯棒性，且能夠準(zhǔn)確檢測(cè)最佳類簇?cái)?shù)目，提高了評(píng)估聚類結(jié)果的準(zhǔn)確率。

技術(shù)領(lǐng)域

本發(fā)明涉及一種聚類評(píng)價(jià)方法，具體地，涉及一種基于二分模塊度的模糊聚類評(píng)價(jià)方法，屬于數(shù)據(jù)挖掘領(lǐng)域。

背景技術(shù)

作為數(shù)據(jù)挖掘的關(guān)鍵技術(shù)之一，聚類能夠?qū)⒁唤M樣本劃分為多個(gè)簇，使得同簇內(nèi)元素之間的相似度盡可能高，而不同簇元素之間的相似度盡可能低。

以FCM(Fuzzy C Means)算法為代表的模糊聚類將隸屬度的取值模糊化，允許一個(gè)樣本以不同概率隸屬于多個(gè)簇，更符合人們對(duì)樣本分布規(guī)律的認(rèn)知，因此模糊聚類研究歷久彌新。迄今為止，為數(shù)眾多的模糊聚類算法在準(zhǔn)確率、效率、魯棒性等方面不斷取得進(jìn)步，有效促進(jìn)了數(shù)據(jù)挖掘研究的發(fā)展；與此同時(shí)，用以評(píng)估模糊聚類質(zhì)量或性能的有效性指標(biāo)在算法研究中不可或缺，其重要性日益凸顯。

迄今為止，關(guān)于聚類有效性指標(biāo)的研究成果較為豐富。廣泛使用的一些有效性指標(biāo)如PC、PE和MPC等過(guò)于依賴于FCM算法產(chǎn)生的隸屬度，且由于FCM算法本身對(duì)噪聲點(diǎn)和離群值較為敏感，因此旨在增強(qiáng)魯棒性的有效性指標(biāo)相繼被提出，但在準(zhǔn)確率方面還有待提高。

發(fā)明內(nèi)容

為解決現(xiàn)有技術(shù)中存在的問(wèn)題，本發(fā)明提出了一種基于二分模塊度的模糊聚類評(píng)價(jià)方法，具體地，該方法包括以下步驟：

(1)將FCM算法在給定數(shù)據(jù)集上運(yùn)行，得到第i個(gè)數(shù)據(jù)點(diǎn)對(duì)第c個(gè)簇的隸屬度u_ci，i＝1,2…,N，c＝1,2…C，N為樣本個(gè)數(shù)，C為簇?cái)?shù)；

(2)計(jì)算類內(nèi)緊致性，對(duì)每個(gè)數(shù)據(jù)點(diǎn)，計(jì)算其對(duì)所有簇隸屬度的平方和比較所有數(shù)據(jù)點(diǎn)的結(jié)果，得到最大值u_max；對(duì)每個(gè)數(shù)據(jù)點(diǎn)，計(jì)算所有數(shù)據(jù)點(diǎn)對(duì)所有簇隸屬度的平方和與最大值的比值；

(3)計(jì)算類間分離性，對(duì)每個(gè)數(shù)據(jù)點(diǎn)和其屬于兩個(gè)不同簇的隸屬度，設(shè)置閾值T_o排除噪聲點(diǎn)和簇邊界上的離群值；運(yùn)行FCM算法獲得模糊隸屬度矩陣，計(jì)算所有數(shù)據(jù)點(diǎn)對(duì)所有簇的分離度之和；

(4)計(jì)算二分模塊度，利用FCM算法得到的C個(gè)聚類中心和原始數(shù)據(jù)點(diǎn)構(gòu)建一個(gè)加權(quán)二分網(wǎng)絡(luò)，模糊隸屬度u_ci表示其加權(quán)邊的權(quán)值；

(5)在劃分系數(shù)PC(Partition Coefficient)的基礎(chǔ)上，比較N個(gè)樣本屬于各個(gè)簇的隸屬度平方之和得出其最大值u_max，再計(jì)算與u_max的比值得類內(nèi)緊致性，根據(jù)屬于不同模糊簇的隸屬度u_ci與閾值T_o的關(guān)系計(jì)算任意兩個(gè)簇之間的類間分離性，將二者與二分模塊度進(jìn)行適當(dāng)?shù)募訙p運(yùn)算，得到新指標(biāo)，且新指標(biāo)的值越大，表示聚類結(jié)果越好。

尤其在步驟(2)中，類內(nèi)緊致性為u_ci表示第i個(gè)數(shù)據(jù)點(diǎn)對(duì)第c個(gè)簇的隸屬度，N和C分別代表數(shù)據(jù)點(diǎn)和聚類結(jié)果簇的個(gè)數(shù)。

進(jìn)一步地，在步驟(3)中，類間分離性為a和b分別代表兩個(gè)不同的簇，用于排除噪聲點(diǎn)和簇邊界上的離群值。

進(jìn)一步地，在步驟(4)中，應(yīng)用于二分網(wǎng)絡(luò)中的二分模塊度為和分別表示兩個(gè)不同方向V^X→V^Y和V^Y→V^X上連接V_l和V_p兩種類型頂點(diǎn)的所有邊數(shù)，和分別表示和的行和。

進(jìn)一步地，在步驟(5)中，新的模糊聚類評(píng)價(jià)方法的目標(biāo)函數(shù)為：CSBM＝(C-1)^1/C×(NC-SEP+Q_B)/2。