[核函數在劃分聚類中的應用與實現] 聚類分析的基本原理

來源:好詞好句 發布時間:2019-07-22 05:00:58 點擊:

  摘要:聚類是數據挖掘的一種重要方法,核函數是能夠将低維不可分的數據映射到高維空間進行線性可分時能夠降低數據處理難度的重要手段。介紹了聚類算法和核函數的特點。通過引入基于核函數的相似性測度,對k-平均聚類算法和圍繞中心點的劃分(PAM)算法在Matlab上做了改進和實現。
  關鍵詞:核函數;劃分聚類;k-折交叉驗證;PAM(圍繞中心點的劃分);主成分分析
  中圖分類号:TP18 文獻标識碼:A 文章編号:1009-3044(2013)27-6185-04
  随着智能化的到來,機器學習技術得到廣泛的重視。當前,數據挖掘技術的發展,以及社會應用對雲計算、大數據等的要求也越來越高。分類、關聯規則、聚類、時間序列與序列模式、Web挖掘、空間挖掘技術等得到了較快發展。作為一種基于統計學習理論的支持向量機(SVM)成為了數據挖掘的一種比較重要且有特色的方法,在分類、聚類方面有着很重要的意義。支持向量機使用結構風險最小化原則代替經驗風險最小化原則,采用将低維空間映射到高維空間,在非線性、小樣本、二分類、高維模式應用環境中具有一些明顯的優勢。
  支持向量機目前在二分類問題中得到了深入的研究,在多類分類問題的求解上也提出了很多解決辦法。聚類作為數據挖掘的另一個重要領域,則相對于分類而言,研究的較少。文獻[6]對将支持向量機的思想應用于聚類做了簡單的介紹,并且提出了采用主成分分析(PCA)進行特征提取的一種線性降維的簡單算法。
  支持向量機具有的明顯優勢,有一個很重要的原因,就是采用了核函數(但核函數不一定隻用在SVM上)。該文根據核函數在支持向量機上進行有效分類的啟發,将核函數思想應用到劃分聚類上,在Matlab環境下進行了應用與實現。
  1 核函數
  核函數對支持向量機的分類性能有影響。核函數的形式的選取,參數的選擇,都是核函數的應用必須考慮的問題。
  核函數具有以下優點:
  2)采用核函數可以處理高維數據。這是因為采用核函數後,輸入空間的維數對核函數的矩陣沒有影響。這樣就避免了所謂的“維數災難”,并且計算量得到了減小。
  3)核函數對于支持向量機是至關重要的,但核函數的思想絕不僅僅隻用于支持向量機處理上。實際上,隻要一個應用,在建立模型後存在内積形式,都可以采用K(x,x’)去替換,這樣就有可能改進目标算法。這樣,核函數思想就可以與聚類算法相結合,在聚類的預處理步驟上,能夠設計出各種基于核函數的子算法,更重要的是這兩部分的設計可以獨立開展,根據不同的應用環境進行篩選,找出合适的算法。
  4)核函數有多種形式,相同的核函數的參數也會不同。有些應用,适合采用某一種核函數,而有些應用可能要采用另一種核函數。
  核函數應用中,Mercer定理具有很重要的意義。Mercer定理指出:要證明K是一個核函數,不必去尋找Φ變換函數,隻需要在數據訓練集上求出各個内積Kij,然後隻要判斷一下矩陣K是不是半正定矩陣就可以了。滿足Mercer條件的函數就能作為核函數。
  2 聚類
  2.1 聚類簡介
  聚類和分類一樣,是數據挖掘的一項重要功能。分類是一種有監督的學習。而聚類與分類不同,聚類中要劃分的組(簇)事先是不确定的,而是由數據決定的,因此聚類是一種無監督的學習。聚類分析又稱群分析,它是研究(樣品或指标)分類問題的一種統計分析方法。聚類具有重要的意義和普遍的價值。在日常生活中,經常有“物以類聚,人以群分”的說法,聚類能夠很好地刻畫數據的屬性以及群體行為特征。聚類的目标就是将數據采用某種算法,根據數據本身的屬性,劃分成若幹組(簇),分組的依據是在同一個組(簇)中的數據之間具有較高的相似度,在不同的組(簇)中具有很低的相似度。
  目前,數據挖掘技術以及大數據技術面對的是巨大的、複雜的、異構的數據集,聚類分析算法面臨很大的挑戰。一個好的聚類分析算法應該考慮以下一些方面:
  1) 可伸縮性:聚類算法在小數據集和大數據集上均能得出有效的結論;
  2) 能夠處理各種數據類型的屬性,并且能夠處理高維、稀疏數據;
  3) 能夠根據數據本身的特征,找出任意形狀的組(簇),而不是僅僅發現類球類的簇;
  4) 對專業領域知識依賴性低;聚類的結果應該是易于理解、便于應用;
  5)數據集輸入的順序對聚類的結果影響較小;
  6) 能夠對噪聲進行處理;能夠根據實際應用的約束條件進行聚類。
  2.2 距離與相似度的度量
  從聚類的概念上可以看出,數據元素之間的相似度是聚類分析中很重要的因素。如何來定義數據對象之間的相似度,對聚類分析的質量有決定作用。相似度在通常情況下可以用距離d(xi,xj)來衡量,當xi與xj相似時,d(xi,xj)值較小;而當xi與xj不相似時,d(xi,xj)較大。
  常用的度量标準有:
  1)兩個數據對象之間的距離函數(相似性測度)
  對于具有連續特征的數據集空間,常用的距離函數有明科夫斯基距離、二次型距離、餘弦距離等;對于二元類型的數據集,可以采用簡單匹配系數(SMC)、Jaccard系數和Rao系數進行描述。
  2) 簇間距離(不相似性測度)
  描述兩個簇間的距離,可以有以下一些方法:
  采用兩個簇中相距最遠的兩個數據之間的距離來表示簇間距離(最遠距離法);
  采用兩個簇中相距最近的兩個數據之間的距離來表示簇間距離(最近距離法);
  采用兩個簇中的中心點的距離作為簇間距離,簇的中心可以用該簇所有元素的算術平均表示(簇中心點法);
  采用兩個簇中任意的兩個數據對象之間的距離表示簇間距離(簇平均法);   除了以上四種方法外,還可以采用離差平方和來描述簇間距離。
  2.3 聚類的類型
  聚類的類型按照不同的标準,有不同的分法。這裡根據聚類分析算法的設計思路,将聚類分成以下5種類型。
  1)劃分聚類
  這是最基本的聚類方法,劃分思想比較接近日常生活。若給定l個數據(可以是多維),将這l個數據劃分成k類,k   5)重複3,計算每個數據到簇中心的餘弦相似測度,并聚類到與該數據最相似的簇中去;
  6)重複4,計算每個簇中所有點的相似測度平均值,并将這個平均值作為新的簇中心
  7)輸出聚類的結果k個簇
  3.2.2核函數在圍繞中心點劃分(PAM)算法上的應用
  PAM算法選用簇中位置最靠近中心的數據作為中心點,然後把l個對象劃分成k個簇。可以最初随機選取k個對象作為中心點,反複用非中心點數據來代替中心點,這樣找出更加合理的中心點。從PAM的執行過程中可以看出,PAM算法在替換中心點時,計算代價非常高。PAM算法克服了k-平均聚類對噪聲數據和孤立點數據的敏感性,但在處理大數據集上,由于替換中心點的複雜性,失去了k-平均聚類對處理大數據集的相對高效與可伸縮性。
  究其原因,PAM算法中在用非中心點替換中心點時,在計算代價上的組合情況較多。因此,采用基于餘弦相似測度的核函數應用,在傳統PAM算法的兩點之間距離的計算上,采用核函數進行,可能會對效率有所提高。
  對于PAM算法,算法的步驟基本不需要改變,主要将算法中的用非中心點代替中心點試探時,在計算代價和總代價時,改為采用餘弦相似測度來進行度量。
  3.3采用核函數的兩個劃分聚類算法性能
  算法的實現采用了 Matlab 7.1,數據集采用了用Matlab 7.1随機産生的100個5維空間的數據myData,并進行了一些手工調整。在聚類時,采用了标準的k-平均聚類、标準的PAM聚類,以及采用了改進的核函數聚類的k-平均聚類和PAM聚類算法。核函數采用了RBF核函數、多項式核函數以及Sigmoid核函數。
  4 結束語
  将核函數的思想應用到劃分聚類中,對k-平均聚類算法和PAM算法在距離的計算上改為采用了基于核函數的餘弦相似測度的計算,從效果上看,在k-平均聚類算法性能的提高上要優于PAM算法。這是因為PAM對數據量較大的數據集效率下降的較快。下一步的工作,準備将核函數的思想應用到另外兩種能夠處理較大數據集的劃分聚類算法CLARA算法和CLARANS中去。
  參考文獻:
  [1] 奉國和.SVM分類核函數及參數選擇比較[J].計算機工程與應用,2011,47(3):123-128.
  [2] 許敏.核向量機算法研究及應用[J].無錫職業技術學院學報,2012,11(4):73-76.
  [3] 李天恩,何桢.基于改進的核化聚類判别分析的故障識别[J].管理工程學報,2012,26(3):34-41.
  [4] 孫軍,黎琪,李和睿.支持向量機遙感圖像幾何校正中的不同核算法的比較[J].四川兵工學報,2012,33(8):76-80.
  [5] 鄭波.基于Gauss核函數的SVM故障診斷技術研究[J].中國民航飛行學院學報,2012,23(3):49-51.
  [6] 鄧乃揚,田英傑.支持向量機-理論、算法與拓展[M].北京:科學出版社,2009:81-111
  [7] 毛國君,段立娟.數據挖掘原理與算法[M].北京:清華大學出版社,2005:156-181
  [8] 陳森平,陳啟買,吳志傑.基于核函數的層次聚類算法[J].暨南大學學報,2011,32(1):31-35.
  [9] 張倩,楊耀權.基于支持向量機核函數的研究[J].電力科學與工程,2012,28(5):42-45.
  [10] 胡婷,王勇,陶曉玲.基于核函數的SOM網絡流量分類方法[J].計算機工程與設計,2011,32(4):1195-1198.

推薦訪問:資訊 資訊 資訊
上一篇:[審視别人的放大鏡等] 拿望遠鏡看别人 拿放大鏡看自己
下一篇:最後一頁

Copyright @ 2013 - 2018 韓美範文網- 精品教育範文網 All Rights Reserved

韓美範文網- 精品教育範文網 版權所有 湘ICP備11019447号-73

http://m.juhua866857.cn|http://wap.juhua866857.cn|http://www.juhua866857.cn||http://juhua866857.cn