改進(jìn)的KFCM聚類(lèi)算法及其在分治SVM中的應(yīng)用.pdf

1、傳統(tǒng)的聚類(lèi)分析主要是基于歐幾里得空間作為特征空間來(lái)進(jìn)行。其中基于劃分的聚類(lèi)算法（例如Crisp clustering和Fuzzy clustering）能夠處理線性可分的數(shù)據(jù)，但對(duì)于線性不可分的數(shù)據(jù)分類(lèi)效果較差。針對(duì)這類(lèi)問(wèn)題，核函數(shù)將其映射到高維的特征空間中，在這一空間中數(shù)據(jù)樣本變得線性可分。基于核的聚類(lèi)分析一直是國(guó)內(nèi)外研究的熱點(diǎn)，它在圖像處理、文本聚類(lèi)、嫌疑犯排查、客戶細(xì)分等領(lǐng)域得到了廣泛運(yùn)用，有很好的應(yīng)用價(jià)值。
　　本文系統(tǒng)介

2、紹了基于劃分的聚類(lèi)分析中的幾個(gè)經(jīng)典算法，關(guān)鍵介紹了迭代公式的計(jì)算、核函數(shù)、隸屬度矩陣。并使用UCI數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)仿真比較它們的聚類(lèi)效果。結(jié)果顯示基于核函數(shù)的算法較其它算法有更好的聚類(lèi)效果，模糊聚類(lèi)比硬聚類(lèi)有更好的聚類(lèi)效果。進(jìn)而提出了新的基于DCA算法和核模糊k均值聚類(lèi)(Kernel Fuzzy k-means,KFCM)的算法：DCA-KFCM和DCA-KFCM2算法，這兩種算法的是比較新穎的聚類(lèi)方法。
　　但隨著社會(huì)的發(fā)

3、展，現(xiàn)實(shí)生活中的數(shù)據(jù)呈現(xiàn)出由少到多，由簡(jiǎn)單到復(fù)雜，由低維到高維的趨勢(shì)。造成核矩陣的計(jì)算時(shí)間的加長(zhǎng)和存儲(chǔ)空間的不足。本文針對(duì)這一不足提出了近似KFCM算法，該算法過(guò)程中不需要計(jì)算整個(gè)核矩陣，而是僅僅計(jì)算核矩陣的對(duì)角線元素和被選出的數(shù)據(jù)樣本所對(duì)應(yīng)的行，大大降低了計(jì)算復(fù)雜度。實(shí)驗(yàn)證明，近似KFCM算法能夠有效處理大數(shù)據(jù)樣本。
　　為了驗(yàn)證近似KFCM的效果，本文將其應(yīng)用到分治SVM中，稱(chēng)為近似分治SVM算法。近似分治SVM比起現(xiàn)有的算法

4、有更快地收斂速度，而且在更少的時(shí)間內(nèi)獲得比其它算法更精確的解。近似分治SVM首先將整個(gè)問(wèn)題分成若干可以被獨(dú)立解決的子問(wèn)題。在理論上可以證明近似KFCM算法可以使得子問(wèn)題與全局問(wèn)題間差異最小化，且由子問(wèn)題所確定的支持向量與全局問(wèn)題的支持向量相似。然而，在整個(gè)數(shù)據(jù)集上運(yùn)行近似KFCM問(wèn)題有些耗時(shí)，運(yùn)用兩步近似KFCM方法找到有效劃分。在“治”這一步中，子問(wèn)題的解可以“拼”成全局問(wèn)題的初始解，在后面的分析中可以得出，其能快速地收斂到全局最優(yōu)解