（計(jì)算機(jī)軟件與理論專業(yè)論文）半監(jiān)督學(xué)習(xí)方法及其應(yīng)用研究.pdf

摘要 摘要 隨著計(jì)算機(jī)技術(shù)的發(fā)展，人類收集數(shù)據(jù)、存儲(chǔ)數(shù)據(jù)的能力得到了極大的提高，無(wú)論 是科學(xué)研究還是社會(huì)生活，各個(gè)領(lǐng)域中都積累了大量的數(shù)據(jù)，對(duì)這些數(shù)據(jù)進(jìn)行分析以發(fā) 掘數(shù)據(jù)中蘊(yùn)含的有用信息，幾乎成為所有領(lǐng)域的共同需求。傳統(tǒng)的機(jī)器學(xué)習(xí)方法大多只 考慮有標(biāo)記數(shù)據(jù)( 1 a b e l e dd a t a ) 或者未標(biāo)記數(shù)據(jù)( u n l a b e l e dd a t a ) ，但是在很多真實(shí)問(wèn)題 中往往是二者并存的。半監(jiān)督學(xué)習(xí)( s e m i s u p e r v i s e dl e a r n i n g ) 由此應(yīng)運(yùn)而生。 半監(jiān)督學(xué)習(xí)是模式識(shí)別和機(jī)器學(xué)習(xí)中重要研究領(lǐng)域之一，一直為國(guó)際機(jī)器學(xué)習(xí)界關(guān) 注，其在分類( c l a s s i f i c a t i o n ) 和聚類( c l u s t e r i n g ) 中得到了廣泛的應(yīng)用，本文主要針對(duì) 半監(jiān)督聚類進(jìn)行研究和分析。 本文首先對(duì)于半監(jiān)督聚類領(lǐng)域的國(guó)內(nèi)外研究情況進(jìn)行回顧，然后通過(guò)對(duì)無(wú)監(jiān)督聚類 和監(jiān)督學(xué)習(xí)理論知識(shí)的介紹，得出半監(jiān)督聚類為何會(huì)得到廣泛關(guān)注，同時(shí)給出半監(jiān)督聚 類常用的思路和算法。最后本文詳細(xì)介紹了我們?cè)谶@方面研究開(kāi)展的一系列工作： ( 1 ) 我們提出了改進(jìn)微分進(jìn)化算法的半監(jiān)督模糊聚類，在結(jié)合傳統(tǒng)f c m 和進(jìn)化 算法的基礎(chǔ)上，參考粒子群算法慣性權(quán)重思想，引入慣性加權(quán)系數(shù)。算法前期可以維持 個(gè)體的多樣性，后期能夠加快算法的收斂速度，有效地提高了算法的性能。遙感圖像數(shù) 據(jù)等實(shí)驗(yàn)結(jié)果證明了算法的有效性。 ( 2 ) 我們提出了基于改進(jìn)的成對(duì)約束的半監(jiān)督聚類算法，首先對(duì)原先少量約束對(duì) 信息進(jìn)行調(diào)整，增加約束對(duì)量。在此基礎(chǔ)上利用監(jiān)督信息對(duì)原始數(shù)據(jù)進(jìn)行降維，利用閉 包中心代替閉包集，最后在基于成對(duì)約束的k 均值算法上進(jìn)行聚類。該算法解決了成對(duì) 約束的違反問(wèn)題，同時(shí)提高了聚類的性能。在u c i 數(shù)據(jù)集的實(shí)驗(yàn)中可以證明這種方法的 可行性。 關(guān)鍵詞：半監(jiān)督聚類，模糊c 均值，k 均值算法，成對(duì)約束，進(jìn)化算法，閉包 a b s t r a c t a b s t r a c t w i 廿lt h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , t h ea b i l i t yo fd a t ac o l l e c t i o na n ds t o r a g e h a sb e e ni m p r o v e dg r e a t e l y n o to n l yi ns c i e n c er e s e a r c h ，b u ta l s oi nd a i l yl i f ep l e n t yo fd a t a h a sb e e ng a i n e d h o wt oa n a l y s et h e s ed a t ag o ta n dm i n et h eu s e f u li n f o r m a t i o nh i d d e ni nt h e d a t a ，w h i c hi sac r i t i c a lr e q u i r e m e n ti ne v e r yf i e l d i nt h et r a d i t i o n a lm a c h i n el e a r n i n g ，j u s tt h e u n l a b e l e dd a t ao rt h el a b e l e dd a t aw e r ec o n s i d e r e d b o t ho ft h e ma r ee x i s t i n gi nm a n y i n s t a n c e s ，h o wt ou s et h ec o m b i n e di n f o r m a t i o n s ，t h e ns e m i - s u p e r v i s e dl e a r n i n gi sp r o p o s e d s e m i s u p e r v i s e dl e a r n i n gi s o n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d si n p a t t e r n r e c o g n i t i o na n dm a c h i n el e a r n i n g i ti sw i d e l ya p p l i e di nc l a s s i f i c a t i o na n dc l u s t e r i n g i nt h i s p a p e ro n l ys e m i - s u p e r v i s e dc l u s t e r i n gi sm e n t i o n e d i nt h i sp a p e r , f i r s t l y , t h es t u d ys t a t u so ns e m i s u p e r v i s e dc l u s t e r i n gi sr e v i e w e d s e c o n d l y , w ei n t r o d u c et h et h e o r yo ft h en o n - s u p e r v i s e dc l u s t e r i n ga n ds u p e r v i s e dc l u s t e r i n g ，a n dg e t t h er e a s o n sw h ys e m i - s u p e r v i s e dl e a r n i n gi sw i d e l ya t t e n d e d w ea l s oi n t r o d u c et h eg e n e r a l m e t h o da n da l g o r i t h mi ns e m i - s u p e r v i s e dc l u s t e r i n g l a s t l y , w ep r e s e n tw h a tw eh a v ed o n e a b o u ts e m i - s u p e r v i s e dc l u s t e r i n gw h i c hc a nb eg e n e r a l i z e dt w ot h i n g s ( 1 ) w ep r o p o s eam o d i f i e dd i f f e r e n t i a le v o l u t i o na l g o r i t h mf o rs e m i - s u p e r v i s e df u z z y c l u s t e r i n g o nt h eb a s e so ft r a d i t i o n a lf c ma l g o r i t h ma n de v o l u t i o n a r ya l g o r i t h m , w ei n t r o d u c e i n e r t i a - w e i g h t e dc o e f f i c i e n tb yc o n s i d e r i n gi n e r t i a - w e i g h t e di d e ao fp a r t i c l es w a r ma l g o r i t h m ， w h i c hk e e p sd i v e r s i t yo fi n d i v i d u a la te a r l ys t a g e sa n dq u i c k e n sc o n v e r g e n ts p e e da tl a t e r s t a g e s ，a n da tt h es a m et i m ei m p r o v e st h ep e r f o r m a n c eo ft h ea l g o r i t h m e x p e r i m e n t a lr e s u l t s f o rr e m o t es e n s i n gd a t ai n d i c a t et h ee f f i c i e n c y ( 2 ) w ep r o p o s eas e m i - s u p e r v i s e dc l u s t e r i n ga l g o r i t h mb a s e do nm o d i f i e dp a i r w i s e c o n s t r a i n t s w ea d j u s tt h eo l df e wp a i r w i s ec o n s t r a i n t st og e tm o r ei n f o r m a t i o na tf i r s t ，t h e n u t i l i z en e ws u p e r v i s i o nt oi n t e g r a t ed i m e n s i o n a lr e d u c t i o n w eu s ep a i r w i s ec o n s t r a i n t s k - m e a n sa l g o r i t h mt oc l u s t e ri nt h es u b s e ti nw h i c ht h ec l o s u r e sa r ec h a n g e db yc l o s u r e s c e n t e r t h i sn e wa l g o r i t h ms o l v e st h ep r o b l e mo fv i o l a t i n gp a i r w i s ec o n s t r a i n t s ，a l s oi m p r o v e s t h ep e r f o r m a n c eo fc l u s t e r i n g t h ef e a s i b i l i t yi sp r o v e do nu c id a t a b a s e k e y w o r d s ：s e m i - s u p e r v i s e dc l u s t e r i n g ，f u z z ycm e a n ，k - m e a n sa l g o r i t h m ，p a i r w i s e c o n s t r a i n t s ，e v o l u t i o na l g o r i t h m ，c l o s u r e i i 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是芬人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取 得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文 中不包含其他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果，也不包含本人為獲得江南 大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過(guò)的材料。與我一同工作的同志 對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意。 簽 名- 殛拯蘭遮 日 期：理之星：纓 關(guān)于論文使用授權(quán)的說(shuō)明 本學(xué)位論文作者完全了解江南大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定： 江南大學(xué)有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允 許論文被查閱和借閱，可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù) 進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文， 并且本人電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。 保密的學(xué)位論文在解密后也遵守此規(guī)定。 簽 名：盜拯! 送導(dǎo)師簽名：壅塑盔 日 期：7 的少孑筍 第章引言 第一章引言 1 1 半監(jiān)督聚類研究現(xiàn)狀 數(shù)據(jù)庫(kù)技術(shù)的發(fā)展使保存在計(jì)算機(jī)上的數(shù)據(jù)以驚人的速度增長(zhǎng)，面對(duì)迅速膨脹的超 級(jí)數(shù)據(jù)庫(kù)時(shí)，人們卻無(wú)從著手去理解數(shù)據(jù)中包含的信息，更難以獲得有價(jià)值的信息。如 何從海量的數(shù)據(jù)中提取有用的和有價(jià)值的信息即知識(shí)成為信息研究的瓶頸【1 1 。數(shù)據(jù)挖掘 就是因?yàn)檫@些問(wèn)題應(yīng)運(yùn)而生發(fā)展起來(lái)的數(shù)據(jù)處理技術(shù)。數(shù)據(jù)挖掘在2 0 世紀(jì)9 0 年代以美 國(guó)信息工程領(lǐng)域?yàn)榇淼难芯繉＜易隽舜罅康膰L試與研究，并對(duì)數(shù)據(jù)挖掘做了詳細(xì)的論 述。 數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取人們感興趣的信息和知識(shí)，這些往往是隱含的、有用 的、尚未發(fā)現(xiàn)的，它是一種綜合應(yīng)用統(tǒng)計(jì)分析、數(shù)據(jù)庫(kù)和智能語(yǔ)言等來(lái)分析龐大數(shù)據(jù)資 料的智能化技術(shù)1 2 | 。這個(gè)定義包括好幾層含義： ( 1 ) 數(shù)據(jù)源必須是真實(shí)的、大量的、含噪音的； ( 2 ) 發(fā)現(xiàn)的必須是用戶感興趣的知識(shí)； ( 3 )發(fā)現(xiàn)的知識(shí)要可接受、可理解、可運(yùn)用，最好能用自然語(yǔ)言表達(dá)發(fā)現(xiàn)； ( 4 )并不是要求是放之四海皆準(zhǔn)的知識(shí)，所有發(fā)現(xiàn)的知識(shí)都是相對(duì)的，是有特定 前提和約束條件、面向特定領(lǐng)域。 目前，數(shù)據(jù)挖掘已經(jīng)引起了人們的廣泛關(guān)注，成為國(guó)內(nèi)外數(shù)據(jù)庫(kù)和信息決策領(lǐng)域的 最前沿研究方向。 聚類分析是依據(jù)樣本間關(guān)聯(lián)的度量標(biāo)準(zhǔn)將其自動(dòng)分成幾個(gè)群組，且使同一群組內(nèi)的 樣本相似，而屬于不同群組的樣本相異的一組方法。一個(gè)聚類分析的系統(tǒng)輸入是一組樣 本和一個(gè)度量?jī)蓚€(gè)樣本間相似度( 或相異度) 的標(biāo)準(zhǔn)。聚類分析的輸出是數(shù)據(jù)集的幾個(gè) 組( 類) ，這些組構(gòu)成一個(gè)分區(qū)或個(gè)分區(qū)結(jié)構(gòu)。聚類過(guò)程通常是沒(méi)有教師指導(dǎo)的，是 無(wú)監(jiān)督過(guò)程。 基于目標(biāo)函數(shù)的聚類方法已成為聚類分析的主流【3 1 。一方面可將其轉(zhuǎn)化為優(yōu)化問(wèn)題 易于與經(jīng)典數(shù)學(xué)的非線性規(guī)劃領(lǐng)域聯(lián)系起來(lái)，用現(xiàn)代數(shù)學(xué)方法來(lái)求解；另方面求解過(guò) 程易于計(jì)算機(jī)實(shí)現(xiàn)。各種聚類方法得到了廣泛的應(yīng)用。如圖像處理、模式識(shí)別以及模糊 推理等。 在很多實(shí)際應(yīng)用中，在得到數(shù)據(jù)同時(shí)，可能得到一些先驗(yàn)知識(shí)。在傳統(tǒng)的聚類分析 過(guò)程中，算法對(duì)樣本進(jìn)行聚類并未考慮先驗(yàn)知識(shí)。 半監(jiān)督學(xué)習(xí)是近年來(lái)機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)研究熱點(diǎn)。在實(shí)際應(yīng)用中，獲取大量無(wú)標(biāo) 江南大學(xué)碩士學(xué)位論文 簽樣本是非常容易的，而獲取有標(biāo)簽的樣本需要付出大量時(shí)間和精力，代價(jià)昂貴。傳統(tǒng) 的無(wú)監(jiān)督學(xué)習(xí)只考慮無(wú)標(biāo)簽樣本，而監(jiān)督學(xué)習(xí)只利用少量的有標(biāo)簽樣本學(xué)習(xí)。半監(jiān)督學(xué) 習(xí)的優(yōu)越性則體現(xiàn)在綜合利用有標(biāo)簽和無(wú)標(biāo)簽樣本進(jìn)行學(xué)習(xí)【4 1 。 半監(jiān)督學(xué)習(xí)一般分為兩大類：半監(jiān)督分類和半監(jiān)督聚類。前者利用有標(biāo)簽數(shù)據(jù)輔佐 分類過(guò)程，以達(dá)到更好的分類效果；后者利用無(wú)標(biāo)簽數(shù)據(jù)使算法達(dá)到更好的分類效果。 本文針對(duì)半監(jiān)督聚類進(jìn)行研究。 1 9 8 5 年，p e d r y c z 5 】在研究模糊聚類算法時(shí)就已提出半監(jiān)督聚類的思想，把“半監(jiān)督 稱為“部分監(jiān)督 ( p a r t i a ls u p e r v i s i o n ) 。然而一直到最近幾年，伴隨著大規(guī)模實(shí)際問(wèn)題的 出現(xiàn)，人們才重新認(rèn)識(shí)到半監(jiān)督聚類的價(jià)值。許多傳統(tǒng)的聚類算法陸續(xù)被推廣到相應(yīng)的 “半監(jiān)督 版本。 現(xiàn)有的半監(jiān)督聚類算法大致可分為3 類。第1 類是基于約束的半監(jiān)督聚類算法 ( c o n s 仃m n t b a s e ds e m i - s u p e r v i s e dc l u s t e r i n gm e t h o d ，簡(jiǎn)稱c b s s c ) 。這類算法一般使用 m u s t 1 i n k 和c a n n o t - l i n k 成對(duì)約束來(lái)引導(dǎo)聚類過(guò)程。其中又可以分為如下幾類： ( 1 ) 在原始目標(biāo)函數(shù)中增加一個(gè)包含樣本標(biāo)記信息或者其他約束的監(jiān)督項(xiàng)【6 】； ( 2 ) 在聚類過(guò)程中分配類標(biāo)記時(shí)施加強(qiáng)制約束【7 】； ( 3 ) 利用有標(biāo)記樣本或者其他約束來(lái)生成一個(gè)初始聚類【8 】【9 1 。 第2 類是基于距離的半監(jiān)督聚類算法( d i s t a n c e b a s e ds e m i s u p e r v i s e dc l u s t e r i n g m e t h o d ，簡(jiǎn)稱d b s s c ) ，這類算法利用成對(duì)約束來(lái)學(xué)習(xí)距離度量，從而改變各樣本之間 的距離，使其有利于聚類。其可分為如下幾類： ( 1 ) 基于期望最大化方法( e m ) 的s t r i n g e d i t 度量【1 0 1 ； ( 2 ) 基于最短路徑算法的歐式度量【l l 】； ( 3 ) 基于凸最優(yōu)化的馬氏度量【1 2 】【1 3 】。 第3 類是集成了約束與距離的半監(jiān)督聚類算法( c o n s t r a i n ta n dd i s t a n c eb a s e d s e m i s u p e r v i s e dc l u s t e r i n gm e t h o d ，簡(jiǎn)稱c d b s s c ) ，它將兩種方法進(jìn)行了統(tǒng)一。如文獻(xiàn)【1 4 【1 5 】 就是典型的混合方法。 在半監(jiān)督聚類中，一般利用監(jiān)督信息指導(dǎo)聚類過(guò)程，通常監(jiān)督信息有如下兩種形式： 帶類標(biāo)簽的樣本數(shù)據(jù)和成對(duì)約束信息。相對(duì)來(lái)說(shuō)獲得成對(duì)約束信息要更容易，而且?guī)ь?標(biāo)簽的樣本可以轉(zhuǎn)換為成對(duì)約束。 半監(jiān)督聚類已經(jīng)被廣泛的運(yùn)用到網(wǎng)頁(yè)檢索和文本分類、基于生物特征的身份識(shí)別、 圖像檢索和視頻檢索，醫(yī)學(xué)數(shù)據(jù)等一系列活動(dòng)中。在研究人員的不斷努力下，半監(jiān)督聚 類在理論和實(shí)際研究應(yīng)用中都獲得了長(zhǎng)足的發(fā)展。 2 第一章引言 目前半監(jiān)督聚類的研究正在繼續(xù)從廣度和深度上不斷進(jìn)行擴(kuò)展【1 6 l 。不斷有各種傳統(tǒng) 的或新提出的半監(jiān)督聚類的改進(jìn)算法出現(xiàn)，同時(shí)也有新的數(shù)學(xué)方法不斷的引進(jìn)半監(jiān)督聚 類中。半監(jiān)督聚類探討的對(duì)象已經(jīng)由簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)擴(kuò)展到流形結(jié)構(gòu)，半監(jiān)督數(shù)據(jù)和圖 模型的關(guān)系等。換而言之，半監(jiān)督聚類已經(jīng)和當(dāng)前機(jī)器學(xué)習(xí)研究的熱點(diǎn)和重點(diǎn)問(wèn)題緊密 聯(lián)系在一起了。 半監(jiān)督聚類的理論在未來(lái)一段時(shí)間內(nèi)仍將是機(jī)器學(xué)習(xí)研究的重點(diǎn)和熱點(diǎn)。這些研究 對(duì)于我們理解機(jī)器學(xué)習(xí)的機(jī)理以及人機(jī)交互都具有重要的理論意義。 1 2 研究意義和目標(biāo) 半監(jiān)督聚類融合了無(wú)監(jiān)督和有監(jiān)督聚類的各自優(yōu)點(diǎn)，通過(guò)較小的代價(jià)，如利用成對(duì) 約束信息指導(dǎo)聚類，使獲得更好的聚類效果。半監(jiān)督聚類勢(shì)必成為聚類研究的熱點(diǎn)，新 的理論會(huì)不斷涌現(xiàn)出來(lái)，將科技成果轉(zhuǎn)化到實(shí)際生產(chǎn)中，降低生產(chǎn)投資成本，提高經(jīng)濟(jì) 效益。 在半監(jiān)督聚類中，一些已經(jīng)提出的算法已經(jīng)取得了不錯(cuò)的分類效果。我們的目標(biāo)是 對(duì)算法進(jìn)行改進(jìn)，不降低分類效果，同時(shí)可以提高算法的運(yùn)行速度。在改進(jìn)微分進(jìn)化算 法的半監(jiān)督模糊聚類中，參照傳統(tǒng)f c m 和進(jìn)化算法，添加粒子群慣性權(quán)重思想。算法前 期不影響種群的多樣性，而在后期加快了收斂速度。很好的達(dá)到了上述目的。在半監(jiān)督 聚類中，怎樣才能更好的利用監(jiān)督信息，在這方面的研究人員各抒己見(jiàn)，出現(xiàn)了大量的 方法，都獲得了不錯(cuò)的效果。我們?cè)谇叭搜芯康某晒希紫壤眉s束對(duì)之間隱含的關(guān) 系，擴(kuò)大約束對(duì)數(shù)量，再利用擴(kuò)大的監(jiān)督信息對(duì)原始樣本進(jìn)行投影，最后利用基于成對(duì) 約束的k m e a n s 算法去聚類，實(shí)驗(yàn)結(jié)果表明可以提高聚類性能。 1 3 論文章節(jié)安排 本文共分為5 章，章節(jié)安排如下： 第一章為引言部分，首先介紹了數(shù)據(jù)挖掘的概念，然后講述了聚類分析與數(shù)據(jù)挖掘 的關(guān)系，最后提出半監(jiān)督聚類，并給出了常用半監(jiān)督聚類研究思路和方法。 第二章首先介紹了聚類的分類和度量方法，并相應(yīng)的進(jìn)行了簡(jiǎn)單的介紹。接著我們 給出了半監(jiān)督聚類的一些典型算法，最后對(duì)半監(jiān)督聚類算法最近的研究成果作簡(jiǎn)單的回 顧。 第三章首先介紹了模糊集的一些基本知識(shí)，并給出了模糊c 均值算法的一般步驟， 然后給出了進(jìn)化算法的基本原理和實(shí)現(xiàn)步驟。在兩者的基礎(chǔ)之上我們提出了改進(jìn)微分進(jìn) 化算法的半監(jiān)督模糊聚類，并對(duì)該算法進(jìn)行詳細(xì)的介紹，最后在遙感圖像等數(shù)據(jù)集進(jìn)行 實(shí)驗(yàn)，進(jìn)行詳細(xì)的分析。 第四章首先介紹一種如何通過(guò)成對(duì)約束內(nèi)部之間的關(guān)系擴(kuò)大成對(duì)約束量，然后利用 監(jiān)督信息進(jìn)行降維。在不違反成對(duì)約束的基礎(chǔ)上提出一種改進(jìn)的半監(jiān)督聚類算法。在 u c i 數(shù)據(jù)集中進(jìn)行驗(yàn)證算法的可行性。 3 江南大學(xué)碩士學(xué)位論文 第五章為全文的總結(jié)，對(duì)研究中存在的問(wèn)題和不足加以說(shuō)明，對(duì)本文所取得的成果 進(jìn)行了分析，并對(duì)進(jìn)一步的研究做了展望。 4 第二章半監(jiān)督聚類算法分析 第二章半監(jiān)督聚類算法分析 在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)，半監(jiān)督聚類這個(gè)研究課題已經(jīng)引起了研究人員的廣 泛的關(guān)注，半監(jiān)督聚類的目的在于利用先驗(yàn)知識(shí)對(duì)樣本獲得一個(gè)更好的分類。半監(jiān)督聚 類優(yōu)越性在于融合了無(wú)監(jiān)督聚類和有監(jiān)督分類兩者的優(yōu)點(diǎn)。所以在介紹半監(jiān)督聚類之前 我們先簡(jiǎn)單回顧一下聚類知識(shí)，同時(shí)介紹幾種常用聚類算法。 2 1 聚類分類以及常用度量方法 2 1 1 聚類的類別 在這里我們給出e v e r i t t 1 7 l 在1 9 7 4 年關(guān)于聚類所下的定義：一個(gè)類簇內(nèi)的實(shí)體是相 似的，不同的類簇的實(shí)體是不相似的；一個(gè)類簇是測(cè)試空間中點(diǎn)的會(huì)聚，同一類簇的任 意兩個(gè)點(diǎn)間的距離小于不同類簇的任意兩個(gè)點(diǎn)間的距離；類簇可以描述為一個(gè)包含密度 相對(duì)高的點(diǎn)集的多維空間中的連通區(qū)域，它們借助包含密度相對(duì)較低的點(diǎn)集的區(qū)域與其 他區(qū)域( 類簇) 相分離。 事實(shí)上，聚類是一個(gè)無(wú)監(jiān)督的分類，它沒(méi)有任何先驗(yàn)知識(shí)可用。聚類分析的輸入可 以用一組有序數(shù)對(duì)( x ，s ) 或( x ，d ) 表示，這里x 表示一組樣本，s 和d 分別是度量樣本 間相識(shí)度或相異度( 距離) 的標(biāo)準(zhǔn)。聚類系統(tǒng)的輸出是一個(gè)分區(qū)a = g 1 ，g 2 ，g ，其 中，q ( 七= 1 ，) 是x 的子集，如下所示： g 1ug 2u u g r = x ( 2 1 ) qn g = ，i s ， ( 2 2 ) a 中成員g 1 ，g 2 ，g 叫做類，每一個(gè)類都是通過(guò)一些特征描述的。在基于搜索的 聚類中，聚類分析的結(jié)果是類( x 中的單獨(dú)的點(diǎn)集) 和它的特征或描述。 在圖2 1 中，我們將給出不同類型聚類算法的分類。聚類算法可分為層次方法與劃 分方法兩大類。所謂層次聚類是指產(chǎn)生一個(gè)嵌套的簇集。在層次體系中，每一層都有一 些分開(kāi)的簇。在最底層，每一個(gè)元組都組成一個(gè)單獨(dú)的簇。在最高層，所有的元組都屬 于同一簇集。在層次聚類中，不必輸入簇的數(shù)目。所謂劃分聚類是指利用算法構(gòu)造一個(gè) 簇集，其中簇的數(shù)目由用戶指定或系統(tǒng)指定。傳統(tǒng)的聚類算法為了滿足內(nèi)存要求，一般 都是針對(duì)數(shù)值型的小型數(shù)據(jù)庫(kù)設(shè)計(jì)的。為了滿足內(nèi)存約束，這些針對(duì)大型數(shù)據(jù)庫(kù)設(shè)計(jì)的 算法要么采取對(duì)數(shù)據(jù)進(jìn)行抽樣，要么利用數(shù)據(jù)機(jī)構(gòu)來(lái)壓縮或修剪數(shù)據(jù)庫(kù)?；谑欠癞a(chǎn)生 重疊或非重疊的簇，可得到不同的聚類算法。但即使只考慮非重疊的簇，也有可能將一 個(gè)元組放置到不同的簇中。非重疊聚簇類算法可分為外部的和內(nèi)部的。外部算法使用元 組的標(biāo)簽來(lái)輔助分類過(guò)程。事實(shí)上，這些算法就是傳統(tǒng)的有指導(dǎo)學(xué)習(xí)分類算法，使用這 些算法要用到特殊的輸入訓(xùn)練集。內(nèi)部算法不需要任何先驗(yàn)信息，而只取決于包含元組 之間距離的鄰接矩陣。 江南大學(xué)碩士學(xué)位論文 圖2 - 1 聚類算法的分類 f i g 2 - 1t y p e so fc l u s t e r i n ga l g o r i t h m 層次聚類算法實(shí)際上是產(chǎn)生嵌套的聚集，根據(jù)產(chǎn)生聚集的方式不同，可以分為凝聚 算法和分裂算法。 凝聚算法在初始時(shí)，每一個(gè)成員都組成一個(gè)單獨(dú)的簇，在以后的迭代過(guò)程中，再把 那些相互鄰近的簇合并成一個(gè)簇，直到所有的成員組成一個(gè)簇為止。不同的層次算法在 每一層合并簇的方式也不同。算法2 1 給出了一個(gè)典型的凝聚聚類算法。 算法2 1 輸入： d = ，f 2 ，厶) ，成員集合 彳 表示成員之間距離的鄰接矩陣 輸出： d e i i 以有序三元組形式表示的譜系圖 凝聚算法： d = 0 ： k = 刀： k = ，饑) ) ； d e = d ，k ，k ) ) ；在初始譜系圖中，每一個(gè)成員均為一個(gè)單獨(dú)的簇。 r e p e a t o l d k = k ； d = d + 1 ； a d = v e r t e xa d j a c e n c ym a t r i xf o rg r a p h w i t ht h r e s h o l dd i s t a n c eo fd ； ( 七，k ) = n e w c l u s t e r s ( d d ，d ) ； i fo l d k kt h e n d e = d e u ( d ，k ，k ) ；新簇集加入譜系圖中 u n t i lk = 1 6 第二章半監(jiān)督聚類算法分析 算法2 1 調(diào)用一個(gè)稱為n e w c l u s t e r s 的過(guò)程來(lái)決定如何從前一個(gè)層次的簇合并產(chǎn)生 下一個(gè)層次的簇。不同類型的凝聚算法具有不同的n e w c l u s t e r s 過(guò)程。n e w c l u s t e r s 過(guò)程 可能之合并了兩個(gè)簇，也可能合并了多個(gè)簇。當(dāng)幾個(gè)簇之間具有相等的距離是，不同的 算法會(huì)采用不同的合并策略。另外，計(jì)算簇之間距離的方式也可能發(fā)生變化。 分裂聚類在初始使所有元組都屬于同一個(gè)簇，然后將上層的簇重復(fù)分裂為兩個(gè)下層 簇，直到每一個(gè)元組都組成一個(gè)單獨(dú)的簇為止。其主要思想是將那些成員之間不是非常 緊密的簇進(jìn)行分裂。 劃分聚類或非層次在一步中就產(chǎn)生所有的簇，而不需要幾個(gè)步驟。雖然在各種算法 中，可以在算法內(nèi)部產(chǎn)生幾個(gè)不同的簇集，但劃分聚類的結(jié)果只產(chǎn)生一個(gè)簇集。由于僅 有一個(gè)簇集作為輸出，所有用戶必須輸入期望得到的簇的數(shù)目k 。另外還需要度量函數(shù) 或準(zhǔn)則函數(shù)來(lái)判定所給出的解的優(yōu)劣程度。在準(zhǔn)則函數(shù)意義下，具有最優(yōu)值的解作為最 終的聚類結(jié)果。常用的度量是平方誤差度量，它表示簇中每一點(diǎn)到簇的質(zhì)心的距離平方 的和： 量 如( q ，f 。，) 2 ( 2 3 ) m = l e k m 還有一些相關(guān)的度量方法我們將在后面一一講解。 基于劃分算法的聚類常用的算法有最小生成樹(shù)、平方誤差聚類算法、k 均值聚類、 最近鄰算法、p a m 算法、結(jié)合能量算法、基于遺傳算法的聚類、基于神經(jīng)網(wǎng)絡(luò)的聚類 等，限于篇幅就不一一介紹了。 前面提到的都是一些傳統(tǒng)的聚類技術(shù)。當(dāng)在動(dòng)態(tài)數(shù)據(jù)庫(kù)上進(jìn)行聚類時(shí)，這些算法可 能并不合適。首先這些技術(shù)都假設(shè)要有足夠的主存( 因?yàn)榇蠖鄶?shù)算法的復(fù)雜性都是 o ( n 2 ) ) ，用于存儲(chǔ)要聚類的數(shù)據(jù)及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。由于大型數(shù)據(jù)庫(kù)包含了成千上萬(wàn)個(gè) 元組( 或更多) ，因此這些假設(shè)是不現(xiàn)實(shí)的，另外，在算法的多次迭代中，不斷地進(jìn)行 i o 操作也要付出很大的代價(jià)。但由于主存的限制，這些算法都不能擴(kuò)展到大型數(shù)據(jù)庫(kù) 上去。另一個(gè)問(wèn)題是有些聚類技術(shù)還假設(shè)所有數(shù)據(jù)是一次提供的。對(duì)于動(dòng)態(tài)數(shù)據(jù)庫(kù)而言， 這個(gè)假設(shè)也不是現(xiàn)實(shí)的。b i r c h 算法、d b s c a n 算法以及c u r e 算法很好解決了上述 問(wèn)題。這里我們將詳述討論b i r c h 算澍2 1 。 b i r c h 是一個(gè)綜合的層次聚類方法。它引入兩個(gè)概念：聚類特征( c f ) 和聚類特 征樹(shù)( c f 樹(shù)) ，它們用于概括聚類描述，這些結(jié)構(gòu)輔助聚類方法在大型數(shù)據(jù)庫(kù)中取得較 高的速度和伸縮性。 ( 1 ) 聚類特征c f 一個(gè)聚類特征c f 是一個(gè)三元組，給出對(duì)象子聚類信息的匯總描述。假設(shè)某個(gè)子聚 類中有個(gè)d 維的點(diǎn)或?qū)ο?q 。則該子聚類的聚類特征c f 定義如下： c f = ( ，l s ，s s ) ( 2 4 ) 7 江南大學(xué)碩士學(xué)位論文 其中n 是子類中點(diǎn)的個(gè)數(shù)，l s 是個(gè)點(diǎn)的線性和( 即q ) ，嬲是數(shù)據(jù)點(diǎn)的平方 i - i ， 和( y d 2 ) 。 一 i = l ( 2 ) c f 樹(shù) 一棵c f 樹(shù)存儲(chǔ)了層層疊疊聚類的聚類特征，它是一個(gè)有兩個(gè)參數(shù)的高度平衡樹(shù)： 分支因子b 和閾值工，分支因子定義了每個(gè)非葉節(jié)點(diǎn)孩子的最大數(shù)目，而閾值參數(shù)給出 了存儲(chǔ)在樹(shù)的葉子節(jié)點(diǎn)中聚類的最大直徑，這兩個(gè)參數(shù)會(huì)直接影響結(jié)果樹(shù)大小。 定義2 1 在一個(gè)有刀個(gè)節(jié)點(diǎn)的聚類中，這刀個(gè)節(jié)點(diǎn)分別為d 1 ，0 2 ，q ，則該 聚類的直徑d 定義為： ih l ( q q ) 2 肚i 坐n 殺礦 il 刀一1 ) d 代表一個(gè)聚類中每一對(duì)節(jié)點(diǎn)之間的平均距離。 每個(gè)非葉子節(jié)點(diǎn)形式為：【c f , ，幽f 磁】，其中扛1 , 2 ，b ，c h i t d ，是一個(gè)指向它的第i 個(gè)子節(jié)點(diǎn)的指針，而c f , 是該子節(jié)點(diǎn)所代表的子聚類的c f 條目。因此，一個(gè)非葉子節(jié) 點(diǎn)代表一個(gè)由它個(gè)條目所代表的所代表子聚類組成的聚類。另外，為了限制葉子節(jié)點(diǎn)的 大小，設(shè)置一個(gè)閾值三，確保每個(gè)葉子節(jié)點(diǎn)最多含有三個(gè)條目，每一個(gè)葉子節(jié)點(diǎn)條目的 形式為 c f , 】，f - 1 , 2 ，l ，c f , 是它的第i 個(gè)子聚類的c f 。與此同時(shí)，為了提高查詢速 度，每一個(gè)葉節(jié)點(diǎn)均設(shè)置兩個(gè)指針，p r e v 和n e x t ，用于連接所有的葉節(jié)點(diǎn)。一個(gè)葉節(jié)點(diǎn) 也代表一個(gè)由它的各條目所代表的子聚類組成的聚類。圖2 2 表示了一個(gè)c f 樹(shù)的最后 兩層示意描述。 c fl + c f 2 + c f 3c f 4 + c f 5 c f 3 目c f 4 邙5 e 二 c f lc f 2 圖2 - 2c f 樹(shù)結(jié)構(gòu) f i g 2 - 2s t r u c t u r eo fc ft r e e 最后第二層 后第一層 b i r c h 算法包括以下兩個(gè)階段： 第一階段：掃描數(shù)據(jù)庫(kù)，建立一個(gè)初始存放內(nèi)存的c f 樹(shù)，它可以被認(rèn)為是數(shù)據(jù)的 多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)。 8 第二章半監(jiān)督聚類算法分析 第二階段：采用某個(gè)聚類算法對(duì)c f 樹(shù)的葉節(jié)點(diǎn)進(jìn)行聚類。 在第一階段中c f 樹(shù)是根據(jù)不斷插入的對(duì)象而動(dòng)態(tài)建立的，因此，b i r c h 算法是一 種增式聚類方法，一個(gè)對(duì)象被插入到與它最近的葉子節(jié)點(diǎn)中。若一個(gè)葉節(jié)點(diǎn)的子聚類直 徑在插入一個(gè)新對(duì)象后大于閾值工，那么該葉子節(jié)點(diǎn)和其他葉子節(jié)點(diǎn)就要進(jìn)行分解，而 在插入一個(gè)新對(duì)象后，有關(guān)它的信息將向著樹(shù)根傳遞。通過(guò)修改閾值可以改變c f 樹(shù) 的大小。如果存放c f 樹(shù)所需要的內(nèi)存大于現(xiàn)有的內(nèi)存，那么指定較小的閾值三并重建 c f 樹(shù)，并通過(guò)重新將舊樹(shù)的葉條目插入到新的c f 樹(shù)中，重建更小的c f 樹(shù)，在所有的 舊葉條目重新插入后，數(shù)據(jù)掃描( 插入到新樹(shù)) 從中斷電得到恢復(fù)。這樣重建樹(shù)的過(guò)程 不需要重讀所有對(duì)象。這一點(diǎn)與構(gòu)造礦樹(shù)時(shí)的插入與分解過(guò)程相類似。 在b i r c h 算法的第二階段，可利用任何聚類算法發(fā)，一般使用劃分聚類方法，對(duì) 第一階段所獲得的c f 樹(shù)進(jìn)行聚類分析。 b i r c h 算法努力在現(xiàn)有資源條件下產(chǎn)生最好的聚類。面對(duì)有限的內(nèi)存，一個(gè)重要 的憂慮就是如何使得i o 時(shí)間最小。b i r c h 算法利用多階段處理方式? 掃描一遍數(shù)據(jù)集 獲得一個(gè)基本理想的聚類，再次掃描一遍數(shù)據(jù)集以幫助改善聚類的質(zhì)量。由此可見(jiàn)， b i r c h 算法的時(shí)間復(fù)雜度為d ( 刀) ，其中行是待聚類的對(duì)象數(shù)。 有關(guān)的實(shí)驗(yàn)結(jié)果表明，就數(shù)據(jù)對(duì)象的聚類的質(zhì)量而言，b i r c h 算法表現(xiàn)出線性可 擴(kuò)展性。然而由于大小的限制，c f 樹(shù)中的每個(gè)節(jié)點(diǎn)僅能容納有限的入口，因此一個(gè)c f 樹(shù)節(jié)點(diǎn)并不總是能對(duì)應(yīng)用戶認(rèn)為的一個(gè)自然聚類。此外如果聚類不是球狀，則會(huì)由于 b i r c h 算法是利用直徑來(lái)控制一個(gè)聚類直徑，從而導(dǎo)致算法的性能變差。 在以下的章節(jié)里，我們還會(huì)挑選一些算法進(jìn)行介紹。 2 1 2 相似性和距離度量以及異常點(diǎn) 在樣本空間x 的聚類算法中，用一個(gè)數(shù)據(jù)向量表示一個(gè)樣本x ( 或特征向量) 。大 多數(shù)待聚類的數(shù)據(jù)樣本實(shí)用有限元的向量形式，沒(méi)有必要區(qū)別對(duì)象或者說(shuō)樣本x j 以及相 應(yīng)的向量。因此，我們假定每一個(gè)樣本x i x ，扛l ，挖都用向量t = x i l 以2 ， 來(lái) 表示，聊的值表示樣本的維數(shù)( 特征) ，刀是一個(gè)聚類過(guò)程的樣本空間x 中的樣本數(shù)。 相似度是定義一個(gè)聚類的基礎(chǔ)，所以同一特征空間中的兩個(gè)模式的相似度的度量標(biāo) 準(zhǔn)對(duì)大多數(shù)聚類算法都是必不可少的。因?yàn)橐粋€(gè)聚類分析過(guò)程的質(zhì)量取決于對(duì)度量標(biāo)準(zhǔn) 的選擇，所以必須仔細(xì)選取度量的標(biāo)準(zhǔn)。一般地，不是計(jì)算兩個(gè)樣本間的相似度，而是 用特征空間中的距離作為度量標(biāo)準(zhǔn)來(lái)計(jì)算兩個(gè)樣本間的相異度。對(duì)于某個(gè)樣本空間來(lái) 說(shuō)，距離的度量標(biāo)準(zhǔn)是度量的( m e t r i c ) 或是半度量的( q u a s i m e t r i c ) ，以便用來(lái)量化樣 本的相異度【l j 。 聚類中的“相異度 這個(gè)詞意味著當(dāng)x 和x 是兩個(gè)相似樣本時(shí)，s ( x ，x ) 的取值是很 大的，當(dāng)x 和x 不相似時(shí)，s ( x ，x ) 的取值是很小的。而且，相似度的度量標(biāo)準(zhǔn)s 具有自 反性： s ( x ，x ) = s ( x ，x ) ，v x ，x x ( 2 5 ) 對(duì)于大多數(shù)聚類方法，相似度的度量標(biāo)準(zhǔn)可以標(biāo)準(zhǔn)化為： 9 江南大學(xué)碩士學(xué)位論文 0 s ( x ，x ) 1 ，v x ，x x ( 2 6 ) 通常，使用相異度的度量而不是相似度的度量作為標(biāo)準(zhǔn)。相異度的度量標(biāo)準(zhǔn)用 d ( x ，x ) ，v x ，x x 來(lái)表示。通常稱相異度為距離。當(dāng)x 和x 相似時(shí)，距離d ( x ，x ) 很小， 如果x 和x 不相似，d ( x ，x ) 就很大。不失一般性，我們規(guī)定： d ( x ，x ) o ，v x ，x 。x ( 2 7 ) 距離的度量標(biāo)準(zhǔn)也具有對(duì)稱性： d ( x ，x 。) = d ( x ，x ) ，v x ，x 。x ( 2 8 ) 如果這是一個(gè)距離度量標(biāo)準(zhǔn)( m e t r i cd i s t a n c em e a s u r e ) 。那么需滿足下面的三角不等 式： d ( x ，x 。) d ( x ，x 。) + d ( x ，x ”) ，v x ，x ，x 。x ( 2 9 ) 最著名的距離度量標(biāo)準(zhǔn)是m 維特征空間的歐式距離： a 2 c x , ，_ ) = ( ( 一啄) 2 ) u 2 ( 2 1 0 ) k = l 另外一種經(jīng)常用的距離度量標(biāo)準(zhǔn)是厶距離或城邊距離( c i t yb l o c k ) ： 盔( 而，o ) = e i x , , - x , i ( 2 1 1 ) k = l 最后，明考斯基距離是包括歐式距離和城區(qū)距離的特例 a , c x , ，巧) = ( ( 一靠) ，) ， ( 2 1 2 ) k = l 一般地，根據(jù)樣本之間的一個(gè)距離度量標(biāo)準(zhǔn)，可以確定類( 樣本集) 間的距離度量 標(biāo)準(zhǔn)，這些度量標(biāo)準(zhǔn)對(duì)評(píng)價(jià)一個(gè)聚類過(guò)程的質(zhì)量是必不可少的。因此，它們也是聚類算 法的一個(gè)組成部分，廣泛應(yīng)用于類g 和c ，的距離度量標(biāo)準(zhǔn)是： ( 1 ) 瓏i n ( e ，c j ) = m i np i p j i其中易g 和p q ( 2 1 3 ) ( 2 ) 見(jiàn)。冊(cè)( q ，q ) = h m l其中m ，和研j 是c i 和q 的質(zhì)心 ( 2 1 4 ) ( 3 ) ( c ，q ) = 1 ( 吩) b 一所i 其中只c f 和p q ，且吩和乃是類c f 和 c 。間的樣本數(shù) ( 2 1 5 ) ( 4 ) d i 嗽( g ，q ) = m a x l p ，一p l 其中p i e 和p ，q ( 2 1 6 ) 在聚類過(guò)程中，通常會(huì)遇到異常點(diǎn)問(wèn)題。所謂的異常點(diǎn)是指數(shù)據(jù)集中與其他的點(diǎn)顯 著不同的樣本點(diǎn)。異常點(diǎn)可能說(shuō)明數(shù)據(jù)中存在錯(cuò)誤，異常點(diǎn)也可能是一些正確的數(shù)據(jù)值， 知不是這些數(shù)值與其他數(shù)據(jù)相比，非常不同。 當(dāng)存在異常點(diǎn)時(shí)，許多聚類技術(shù)的效果都不理想，為了保證聚類效果，聚類算法可 以發(fā)現(xiàn)并剔除異常點(diǎn)。但在實(shí)際剔除異常點(diǎn)時(shí)一定要謹(jǐn)慎。例如數(shù)據(jù)挖掘問(wèn)題是水災(zāi)預(yù) 報(bào)。與正常水位值相比，非常高的水位值很少發(fā)生，因此可視為異常點(diǎn)。但如果剔除異 常點(diǎn)，則數(shù)據(jù)挖掘算法就不能有效地預(yù)報(bào)水災(zāi)，這是因?yàn)榉从乘疄?zāi)即將發(fā)生的數(shù)據(jù)已經(jīng) 被剔除了。 1 0 第二章半監(jiān)督聚類算法分析 異常點(diǎn)檢測(cè)或異常點(diǎn)挖掘是指在數(shù)據(jù)集中標(biāo)示出異常點(diǎn)的過(guò)程。發(fā)現(xiàn)異常點(diǎn)后，利 用聚類或者其他數(shù)據(jù)挖掘算法可以剔除它們或者按不同方式處理。許多異常點(diǎn)檢測(cè)是基 于統(tǒng)計(jì)技術(shù)的。通常假設(shè)數(shù)據(jù)集服從一個(gè)已知分布，然后通過(guò)總所周知的不一致檢測(cè)來(lái) 檢測(cè)出異常點(diǎn)。但是由于現(xiàn)實(shí)世界數(shù)據(jù)集不一定服從簡(jiǎn)單的數(shù)據(jù)分布，所以這種方法對(duì) 于真實(shí)數(shù)據(jù)是不適用的。另外，大多數(shù)統(tǒng)計(jì)檢驗(yàn)都假設(shè)使用單屬性數(shù)值，而現(xiàn)實(shí)世界數(shù) 據(jù)集中的數(shù)據(jù)都是多屬性的。采用基于距離測(cè)度的檢測(cè)技術(shù)可能是一條可行的途徑。 2 2 支持向量機(jī)簡(jiǎn)介 聚類是一種無(wú)教師的過(guò)程，即無(wú)監(jiān)督的方法。在這里我們將介紹有監(jiān)督的方法。我 們這里主要討論的是支持向量機(jī)( s u p p o r tv e c t o rm a c h i n e ，即s v m ) 。 s v m 由v a p n i k 首先提出的，是一種通用的前饋神經(jīng)網(wǎng)絡(luò)，可用于解決模式分類和 非線性映射問(wèn)題【1 礓1 8 】。從線性可分模式分類角度看，支持向量機(jī)的主要思想是建立一個(gè) 最優(yōu)決策超平面，使得該平面兩側(cè)平面最近的兩類樣本之間的距離最大化，從而對(duì)分類 問(wèn)題提供良好的泛化能力。對(duì)于非線性可分模式分類問(wèn)題，可將復(fù)雜的模式分類問(wèn)題非 線性地投射到高維特征空間可能是線性可分的，因此只要變化是非線性的且特征空間的 維數(shù)足夠高，則原始模式空間能變換為一個(gè)新的高維特征空間，是的在特征空間中模式 以較高的概率為線性可分的。此時(shí)，應(yīng)用支持向量機(jī)算法在特征空間建立超平面，即可 解決非線性可分的模式識(shí)別問(wèn)題。支持向量機(jī)是基于統(tǒng)計(jì)學(xué)習(xí)理論的原理性方法。 考慮p 個(gè)線性可分樣本 ( x 1 ，d 1 ) ，( 彳27 d 2 ) ，( x pd 尸) ，對(duì)于任一輸入樣本x p ，其 期望輸出為d p = l ，分別代表兩類的類別標(biāo)示。用于分類的超平面方程為 w r x + b = 0 ( 2 1 7 ) 式中，x 為輸入向量，礦為權(quán)值向量，b 為偏置，相當(dāng)于負(fù)閾值，則有 j 形7 x p + b 0 ，當(dāng)d ，= + 1， 1 渺r x p + 6 o ，當(dāng)d j p = 一1 j 叫 由公式( 2 1 7 ) 定義的超平面與最近的樣本點(diǎn)之間的間隔稱為分離邊緣，用p 表示。 支持向量機(jī)的目標(biāo)是找到一個(gè)分離邊緣最大的超平面，即最優(yōu)超平面。圖2 3 給出了二 維平面中最優(yōu)超平面的示意圖?？梢钥闯觯笥页矫婺軌蛱峁﹥深愔g最大可能的分 離，因此確定最優(yōu)超平面的權(quán)值礬和偏置b 0 應(yīng)是唯一的。公式( 2 1 7 ) 定義的一簇超平 面中，最優(yōu)平面的方程應(yīng)該為 形r + 6 0 = 0 ( 2 1 9 ) 江南大學(xué)碩士學(xué)位論文 - - 一- 一 最優(yōu)超平面 l s p a c e 。f p 。沁。e ；n p 懂。x w x + 6 = 。 圖2 - 3 最優(yōu)分類超平面 f i g 2 - 3t h em a x i m i z eh y p e r p l a n e 由解析集合知識(shí)可得樣本空間任一點(diǎn)到最優(yōu)超平面的距離為 r ：w o r x + b o。 慨4 從而有判別函數(shù) g ( x ) = 1 l w o l l = w d x + b o 給出從x 到最優(yōu)超平面的距離的一種代數(shù)度量。 將判別函數(shù)進(jìn)行歸一化，使所有樣本都滿足 ( 2 2 0 ) ( 2 2 1 ) w w o r r x l ，p p + b o f 1 耋! ：= + 1 p ：1 ，2 ，p( 2 2 2 ) i 矽了x 尸+ b o 1 ， 當(dāng)d p ：一1 一1 二，k 厶z z j 則對(duì)于離最優(yōu)超平面最近的特殊樣本彳滿足i g ( x ) 卜l ，稱為支持向量。由于支持 向量最靠近分類決策面，是最難分的數(shù)據(jù)點(diǎn)，因此這些向量在支持向量機(jī)的運(yùn)行中起著 d p ( r v r x ，+ 6 ) 1 p = 1 ，2 ，p( 2 2 3 ) 廠2 甜= 磊1 = 一 泣 p 2 2 y 2 麗 2 2 5 ) 1 2 第二章半監(jiān)督聚類算法分析 上式表明，分離邊緣最大化等價(jià)于使權(quán)值向量- 一- ， ，一0 w i i 最小化。因此，滿足公式 ( 2 2 5 ) 的條件且使0 矽0 最小的分類超平面就是最優(yōu)超平面。 根據(jù)上面的討論，建立最優(yōu)分類面的問(wèn)題可以表示成如下的約束優(yōu)化問(wèn)題，即對(duì)于 給定的訓(xùn)練樣本p ( x 1 ，d 1 ) ，( x 2d 2 ) ，( z pd 尸) ) ，找到權(quán)值向量w 和閾值丁的最優(yōu)值。 使其在公式( 2 2 3 ) 的約束下，最小化代價(jià)函數(shù) ( 形) = 寺0 8 2 = 去形r w ( 2 2 6 ) 這個(gè)代價(jià)函數(shù)是礦的凸函數(shù)，且關(guān)于緲的約束條件是線性的，因此可以用l a g r a n g e 系數(shù)方法解決約束最優(yōu)化問(wèn)題。引入l a g r a n g e 函數(shù)如下： l ( w ，b , a ) = 去形7 w 一a p 【d p ( 形r x p + 6 ) 一1 】 ( 2 2 7 ) 式中a 。0 ，p = 1 , 2 ，p 稱為l a g r a n g e 系數(shù)。式( 2 2 7 ) 中第一項(xiàng)為代價(jià)函數(shù)，第二項(xiàng) 非負(fù)，因此最小化西( 形) 就轉(zhuǎn)化為求l a g r a n g e 函數(shù)的最小值。觀察l a g r a n g e 函數(shù)可以看 出，欲使函數(shù)值最小化，應(yīng)該第一項(xiàng)( 形) 較小，第二項(xiàng)較大。為了使第一項(xiàng)最小化， 將( 2 2 7 ) 對(duì)形和b 求偏導(dǎo)，并使結(jié)果為0 。 i 絲( 蘭! 型：0 a 肜 ( 2 2 8 ) l o l ( w , b , a ) ：0 利用公式( 2 2 7 ) 和公式( 2 2 8 ) ，經(jīng)過(guò)整理可導(dǎo)出最優(yōu)化條件1 ： p w = a 。d p x p j 一， p = l 同時(shí)可以得出最優(yōu)化條件2 ： p d p = o ( 2 2 9 ) ( 2 3 0 ) 為了使第二項(xiàng)最大化，將式( 2 2 7 ) 展開(kāi)如下： 1ppp 三( 礦，6 ，口) = 去矽r w 一a p d p w7 x p 一6 a p d p + ( 2 3 1 ) j p = lp = lp = 1 根據(jù)式( 2 3 0 ) ，上式中第三項(xiàng)為0 ，根據(jù)式( 2 2 9 ) 可將上式最終表示為 ppp w