一種基于流形距離的迭代優(yōu)化聚類(lèi)算法

王　娜　杜海峰　王孫安

聚類(lèi)，即無(wú)監(jiān)督分類(lèi)，是一種重要的數(shù)據(jù)分析方法，已經(jīng)被廣泛應(yīng)用于信息檢索、數(shù)據(jù)挖掘和模式識(shí)別等領(lǐng)域，在現(xiàn)有的聚類(lèi)方法中，基于目標(biāo)函數(shù)的聚類(lèi)算法把聚類(lèi)問(wèn)題歸結(jié)為一個(gè)優(yōu)化問(wèn)題，具有深厚的泛函基礎(chǔ)，是聚類(lèi)算法研究的重要分支之一，而樣本之間的相似度度量以及待優(yōu)化的準(zhǔn)則函數(shù)設(shè)計(jì)就成為此類(lèi)算法研究的核心問(wèn)題，通常，樣本之間的相似度度量就是樣本之間的距離，最簡(jiǎn)單的相似度度量是歐氏距離，它對(duì)空間分布為球形或超球體的數(shù)據(jù)具有很好的性能，但對(duì)于空間分布復(fù)雜的流形結(jié)構(gòu)的數(shù)據(jù)效果很差，因此為此類(lèi)數(shù)據(jù)設(shè)計(jì)更加合理的相似度度量是非常必要的工作，準(zhǔn)則函數(shù)的設(shè)計(jì)力圖反映聚類(lèi)目標(biāo)，即把樣本分為多個(gè)類(lèi)，同類(lèi)中的樣本具有較高的相似度，不同類(lèi)中的樣本差別較大，簡(jiǎn)單且應(yīng)用廣泛的準(zhǔn)則函數(shù)是誤差平方和準(zhǔn)則、相關(guān)的最小方差準(zhǔn)則和散布準(zhǔn)則，雖然這些準(zhǔn)則在很多問(wèn)題中都體現(xiàn)出很強(qiáng)的實(shí)用性，但對(duì)于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)(密集類(lèi)被稀疏類(lèi)包圍或互相絞纏在一起的線(xiàn)條式的幾個(gè)類(lèi))依然無(wú)法正確聚類(lèi)。