用改進(jìn)的rpcl算法提取聚類的最佳數(shù)目

1、上海大學(xué)學(xué)報上海大學(xué)學(xué)報JOURNALOFSHANGHAIUNIVERSITY1999年第5卷第5期Vol.5No.51999用改進(jìn)的用改進(jìn)的RPCLRPCL算法提取聚類的最佳數(shù)目算法提取聚類的最佳數(shù)目李昕鄭宇江芳澤摘要摘要:對于傳統(tǒng)的K平均算法來說如何選擇適當(dāng)類的數(shù)目是一個難以解決的問題.有人提出了次勝者受罰的競爭學(xué)習(xí)(rivalpenalizedcompetitivelearning:RPCL)算法試圖來解決這一問題.但是當(dāng)數(shù)據(jù)類有

2、重疊以及輸入矢量含有非獨(dú)立項時RPCL算法的性能不能令人滿意.本文提出了一種結(jié)合全協(xié)方差矩陣的RPCL算法并逐步刪除那些只包含少量訓(xùn)練數(shù)據(jù)的類.這種算法我們稱之為改進(jìn)的RPCL算法.我們用改進(jìn)的RPCL算法來確定高斯混合分布類的數(shù)目并將其與原來的RPCL進(jìn)行比較.實驗證明改進(jìn)的RPCL算法比原來的RPCL算法能夠更好地表征類.關(guān)鍵詞關(guān)鍵詞:聚類RPCL算法競爭學(xué)習(xí)中圖分類號中圖分類號:TN:TN912.34912.34文獻(xiàn)標(biāo)識碼文獻(xiàn)標(biāo)識

3、碼:A:AAnImprovedRPCLAlgithmfClusteringLIXinJIANGFangze(SchoolofAutomationShanghaiUniversityShanghai200072China)ZHENGYu(DepartmentofComputerShanghaiMaritimeUniversityShanghai200135China)Abstract:inganappropriatenumberofclu

4、stersisaproblemintheclassicalKmeansalgithm.Therivalpenalizedcompetitivelearning(RPCL)algithmisdesignedtosolvethisproblem.Butitsperfmanceisnotsatisfactywhenthedatahaveoverlappedclusterstheinputvectscontaindependentcompone

5、nts.ThispaperaddressesthisproblembyincpatingfullcovariancematricesintotheiginalRPCLalgithm.TheresultingalgithmreferredtoastheimprovedRPCLalgithmprogressivelyeliminatestheunitswhoseclusterscontainonlyasmallptionofthetrain

6、ingdata.TheimprovedalgithmisappliedtodeterminethenumberofclustersofaGaussianmixturedistribution.TheresultsshowthatthecovariancematricesintheimprovedRPCLalgithmhaveabetterrepresentationoftheclustersthanthoseoftheiginalRPC

7、Lalgithm.Keywds:clusteringRPCLalgithmcompetitionlearning聚類是將多維空間內(nèi)的數(shù)據(jù)集合分成多個有意義的子群或類的過程.它在很多領(lǐng)域都有著非常重要的應(yīng)用尤其是在語音、圖像識別等方面.多年來人們提出過許多種聚類的方法［1］其中最著名的是K平均法它在每次迭代過程中將(2)這里0≤αc(t)αr(t)≤1分別是競爭獲勝單元和次勝單元的學(xué)習(xí)率.第四步:t值加1如果tτ時將單元i刪除由所剩下單元

8、組成的權(quán)值矢量作為類的中心.這樣通過RPCL算法可以自動地確定一個適當(dāng)類的數(shù)目.但是當(dāng)類互相重疊時它的性能會很快下降這是因為在這種情況下算法對競爭獲勝單元和次勝單元的學(xué)習(xí)率非常敏感.而當(dāng)輸入矢量包含非獨(dú)立項時問題會更嚴(yán)重.我們認(rèn)為之所以出現(xiàn)這種情況是因為用歐氏距離作為RPCL算法中的距離量度并非好的選擇.我們提出用一組協(xié)方差矩陣Σjkj=1來作為距離量度這樣式(2)中的歐氏距離就被馬氏距離(Mahalanobisdistance:(xω

9、j)TΣ1j(xωj)所代替.需要指出的是當(dāng)Σjkj=1是單位矩陣時改進(jìn)的RPCL算法就簡化為原來的RPCL算法.改進(jìn)的RPCL算法開始時要在競爭學(xué)習(xí)網(wǎng)絡(luò)中選擇一個大的單元數(shù)目這個數(shù)目應(yīng)該大于輸入數(shù)據(jù)集中預(yù)計的類的數(shù)目.每次迭代之后我們要測定每個類中包含的樣本數(shù)然后將只含有少量樣本的單元刪除.這是因為這些單元中包含的樣本數(shù)太少不能可靠地估計出協(xié)方差矩陣.我們稱之為“冗余單元”.改進(jìn)的RPCL算法的步驟如下:第一步:設(shè)定類的中心數(shù)目初始值

10、這個值應(yīng)大于數(shù)據(jù)集中的可能類的數(shù)目.用K鄰近算法初始化矩陣Σjkj=1同時設(shè)定刪除冗余單元的閾值ζ.將計數(shù)器p值設(shè)為零.第二步:設(shè)計數(shù)器t=0從數(shù)據(jù)集中隨機(jī)選取樣本x.從i=1…k使(3)這里c表示獲勝單元r表示次勝單元γi值的計算與RPCL算法相同.(b)按式(2)修改權(quán)值ωj.(c)t值加1如果tT則轉(zhuǎn)第二步(a)否則轉(zhuǎn)第三步.第三步:對每一個樣本找出它最近的中心然后將它分配到相關(guān)的類中.第四步:對每一個類測定它包含的樣本數(shù).如果該