（應(yīng)用數(shù)學(xué)專業(yè)論文）支持向量機(jī)與k均值聚類融合算法研究.pdf

摘要 內(nèi)容摘要：本文在介紹了支持向量機(jī)和k 一均值聚類算法的基本理論 的基礎(chǔ)上，對支持向量機(jī)和k 均值聚類算法的融合算法進(jìn)行了研 究，詳細(xì)介紹了改進(jìn)算法的理論知識，并通過實(shí)驗驗證了算法的有 效性。 支持向量機(jī)是在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展出來的一種新的、非 常有效的機(jī)器學(xué)習(xí)方法，它集優(yōu)化、核、最佳推廣能力等特點(diǎn)于一 身，較好地解決了以往困擾很多學(xué)習(xí)方法的小樣本、非線性、過學(xué) 習(xí)、高維數(shù)、局部極小點(diǎn)等實(shí)際問題。盡管支持向量機(jī)有著其它機(jī) 器學(xué)習(xí)方法無法比擬的優(yōu)勢，但也有其自身局限性。針對其對噪聲 和野點(diǎn)敏感的問題，我們提出了基于模糊隸屬度的支持向量機(jī)去噪 方法，在線性規(guī)劃下的一類分類支持向量機(jī)中引入模糊隸屬度，剔 除樣本中的噪聲和野點(diǎn)，并在多種數(shù)據(jù)集上驗證了算法的有效性。 k 一均值算法是解決聚類問題的一種簡潔、快速的經(jīng)典算法。如 果樣本是密集的，并且類與類之間是線性可分的，它的效果最好： 但是如果類與類之間是線性不可分的，它的聚類效果就很不理想。 針對這個問題，我們提出了基于支持向量機(jī)的k 一均值聚類算法， 將一類分類支持向量機(jī)引入k 一均值聚類算法之中。文中在人工數(shù) 據(jù)集( d e l t as e t ) 和u c i 數(shù)據(jù)集( i r i sd a t a ) 上分別進(jìn)行了實(shí)驗，實(shí)驗證 明，此算法與其它算法相比，聚類精度明顯提高。而且線性規(guī)劃下 的支持向量機(jī)比引用二次規(guī)劃下的支持向量機(jī)，不僅提高了聚類精 度，而且極大的降低了算法的復(fù)雜性。 關(guān)鍵詞：支持向量機(jī)；一類分類；線性規(guī)劃；隸屬度；k 均值 i a b s t r a c t c o n t e n t ：i nt h i sp a p e r ，w er e s e a r c hf u s i o na l g o r i t h m so fs u p p o r tv e c - t o rm a c h i n ea n dk m e a n sc l u s t e r i n ga l g o r i t h m ，o nt h eb a s i so ft h e f o u n d a t i o n a lt h e o r i e so fs u p p o r tv e c t o rm a c h i n ea n dk - m e a n sc l u s - t e r i n ga l g o r i t h m ，i n t r o d u c et h et h e o r e t i c a lk n o w l e d g eo fi m p r o v i n g a l g o r i t h m sc a r e f u l l y , a n dv e r i f yt h ee f f e c t i v e n e s so ft h ea l g o r i t h m sb y e x p e r i m e n t s u p p o r tv e c t o rm a c h i n e ( s v m ) i san e wa n dv e r ye f f e c t i v em e t h o d o fm a c h i n el e a r n i n gd e v e l o p e do ns t a t i s t i c a ll e a r n i n gt h e o r y , w h i c h c o n c l u d e so p t i m i z a t i o n ，k e r n e la n dt h ea b i l i t yo ft h eb e s tp r o m o t i n g a n ds oo n i ts o l v e sm a n yp r a c t i c a lp r o b l e m sw h i c ht r o u b l e dm a n y l e a r n i n gm e t h o d si nt h ep a s t ，s u c h 嬲s m a l ls a m p l e ，n o n - l i n e a r ，o v e r - s t u d y , h i g h - d i m e n s i o na n dl o c a lm i n i m u mp o i n t c o m p a r e dw i t ht h e o t h e rm a c h i n el e a r n i n gm e t h o d s ，t h es u p p o r tv e c t o rm a c h i n eh a si n - c o m p a r a b l ea d v a n t a g e si nm a n ya s p e c t s ，b u ti ta l s oh a si t so w nl i m - i t a t i o u s f o rt h es e n s i t i v ep r o b l e mt on o i s e sa n do u t l i e r s ，w eh a v e p r o p o s e daa p p r o a c ho fr e m o v i n gn o i s e sa n do u t l i e r sf o rs v mb a s e d o nf u z z ym e m b e r s h i pw h i c ha d d sf u z z ym e m b e r s h i pi no n e - c l a s ss v m u n d e rl i n e a rp r o g r a m m i n g ，a n dv e r i f yt h ee f f e c t i v e n e s so ft h ea l g o r i t h m i na v a r i e t yo fd a t as e t s k m e a n sc l u s t e r i n ga l g o r i t h mi sas i m p l e ，f a s ta n dc l a s s i c a la l g o - r i t h mt os o l v et h ep r o b l e mo fc l u s t e r i n g i ft h es a m p l e sa r ei n t e n s i v e 支持向量機(jī)與k 均值聚類融合算法研究 a n dl i n e a ra m o n gt h ec a t e g o r i e s ，i ti st h eb e s tm e t h o d ，b u ti ft h e ya r e n o n - l i n e a r ，t h ec l u s t e r i n ge f f e c ti s n tp e r f e c t a g m n s tt h i sp r o b l e m ， w eh a v ep r o p o s e dk m e a n sc l u s t e r i n ga l g o r i t h mb a s e do ns v m ，w h i c h a d d so n c l a s ss v mi nk m e a n sc l u s t e r i n ga l g o r i t h m i nt h i sp a p e r w e c o n d u c t se x p e r i m e n t sr e s p e c t i v e l yo nas y n t h e t i cd a t as e t ( d e l t as e t ) a n dau c id a t as e t ( i r i sd a t a ) ，t h e yp r o v et h a ti t sc l u s t e r i n ga c c u r a c y i m p r o v e do b v i o u s l yc o m p a r e dw i t ho t h e ra l g o r i t h m s c o m p a r e dw i t h s v mu n d e rq u a d r a t i cp r o g r a m m i n g ，s v mu n d e rl i n e a rp r o g r a m m i n g d o e s n to n l yi m p r o v et h ea c c u r a c yo fc l u s t e r i n g ，b u ta l s or e d u c et h e c o m p l e x i t yo ft h ea l g o r i t h mg r e a t l y k e yw o r d s ：s v m ；o n e - c l a s s ；l i n e a rp r o g r a m m i n g ；m e m b e m h i p ；k - 1 1 1 學(xué)位論文獨(dú)創(chuàng)性聲明 本人承諾：所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下所取得的研究成果論文中除特別 加以標(biāo)注和致謝的地方外，不包含其他人和其他機(jī)構(gòu)已經(jīng)撰寫或發(fā)表過的研究成果，其他同 志的研究成果對本人的啟示和所提供的幫助，均已在論文中做出了明確的聲明并表示謝意 學(xué)位論文作者簽名： e t 期：鑼口9 嗽o 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解遼寧師范大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，及學(xué)校有權(quán) 保留并向國家有關(guān)部門或機(jī)構(gòu)送交復(fù)印件和磁盤，允許論文被查閱和借閱本人授權(quán)遼寧師 范大學(xué)，可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印 或其他復(fù)制手段保存、匯編學(xué)位論文保密的論文在解密后使用本授權(quán)書 學(xué)位論文作者簽名：張 指導(dǎo)教師簽名：乏川氣屜 日 期：枷p 縱。 支持向量機(jī)與k 一均值聚類融合算法研究 支持向量機(jī)與k 一均值聚類融合算法研究 1 緒論 1 1論文研究的背景及意義 由于數(shù)據(jù)庫技術(shù)引發(fā)了海量數(shù)據(jù)，人們想用數(shù)據(jù)管理系統(tǒng)存儲數(shù)據(jù)，用 機(jī)器學(xué)習(xí)的方法分析數(shù)據(jù)、挖掘海量數(shù)據(jù)背后的知識，由此數(shù)據(jù)挖掘( d a t a m i n i n g ) 產(chǎn)生了。概括的講數(shù)據(jù)挖掘的任務(wù)是從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取人 們感興趣的、事先未知的、有用的或潛在有用的信息1 1 1 。 支持向量機(jī)( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 1 是數(shù)據(jù)挖掘中的一項新技 術(shù)，是借助于最優(yōu)化方法解決機(jī)器學(xué)習(xí)問題的新工具。它最初于2 0 世紀(jì)9 0 年代 中期由v a p n i k 提出，近年來在其理論研究和算法實(shí)現(xiàn)方面都取得了突破性進(jìn) 展，開始成為克服“維數(shù)災(zāi)難”和“過學(xué)習(xí)”等傳統(tǒng)困難的有力手段。其理論 基礎(chǔ)是專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的統(tǒng)計學(xué)習(xí)理論1 2 ，3 】。該理論采用結(jié) 構(gòu)風(fēng)險最小化原則，在最小化樣本點(diǎn)誤差的同時，縮小模型復(fù)雜度，即減小模 型泛化誤差的上界，從而提高模型的泛化能力。 支持向量機(jī)使用最大間隔因子來控制學(xué)習(xí)機(jī)器的訓(xùn)練過程，使其只選擇 具有最大分類間隔的分類超平面，又叫最優(yōu)超平面f 在不可分情況下，又引入 松弛因子來控制經(jīng)驗風(fēng)險) ，從而使其在滿足分類要求的情況下，又具有最高 的推廣能力。尋找最優(yōu)超平面的過程最終轉(zhuǎn)化為二次型優(yōu)化問題( q u a d r a t i c p r o g r a m m i n g ，q p ) ，從理論上說，得到的是全局最優(yōu)解。在處理非線性分類 問題上，與傳統(tǒng)的學(xué)習(xí)機(jī)器不同的是支持向量機(jī)是將輸入空間映射到高維的特 征空間，仍然使用大間隔因子在高維特征空間中尋找最大間隔超平面。事實(shí) 上，高維特征空間中的超平面對應(yīng)著輸入空間中的非線性分類面。實(shí)際中，支 持向量機(jī)的優(yōu)化過程并沒有真正在高維特征空間中進(jìn)行，而是通過一些具有特 殊性質(zhì)的核函數(shù)【4 - - 1 0 ，將高維特征空間中的內(nèi)積運(yùn)算轉(zhuǎn)化為原始空間中核函數(shù) 的運(yùn)算，從而巧妙地避免了在高維特征空間中處理問題的困難。為了進(jìn)一步降 低算法的復(fù)雜性，一些基于線性規(guī)劃的支持向量機(jī)算法被提出，實(shí)驗表明線性 規(guī)劃支持向量機(jī)在保持較好的推廣能力的前提下，算法復(fù)雜度大大降低。 盡管支持向量機(jī)在很多方面都有著其它機(jī)器學(xué)習(xí)方法無法比擬的優(yōu)勢，但 任何方法都不是萬能的，它也有著自身的局限性。針對傳統(tǒng)支持向量機(jī)對于噪 支持向量機(jī)與k 均值聚類融合算法研究 聲和野點(diǎn)敏感的問題，本文對傳統(tǒng)支持向量機(jī)進(jìn)行了改進(jìn)，引入模糊隸屬度， 剔除樣本中存在的噪聲或野值樣本，而且，在確定樣本的隸屬度時，不僅要考 慮樣本所在類中心之問的距離，還考慮了類中樣本之問的緊密度。 聚類是數(shù)據(jù)挖掘中的一種重要技術(shù)，是分析數(shù)據(jù)并從中發(fā)現(xiàn)有用信息的一 種有效手段?；凇拔镆灶惥邸钡臉闼厮枷?，它將數(shù)據(jù)對象分組成為若干個類 或簇，使得在同一個類中的對象之間具有較高的相似度，而不同類中的對象差 別很大，通過聚類，人們能夠識別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式以 及數(shù)據(jù)屬性之間有趣的相互關(guān)系。聚類分析在客戶分類、基因識別、w 、唧文 本分類、空間數(shù)據(jù)處理、衛(wèi)星照片分析、醫(yī)療圖象自動檢測等領(lǐng)域有著廣泛的 應(yīng)用，而其本身的研究也是一個蓬勃發(fā)展的領(lǐng)域，數(shù)據(jù)挖掘、統(tǒng)計學(xué)、機(jī)器學(xué) 習(xí)、空間數(shù)據(jù)庫技術(shù)、生物學(xué)和市場學(xué)的發(fā)展推動著聚類分析研究的進(jìn)展，使 它己成為數(shù)據(jù)挖掘研究中的一個非?；钴S的研究課題。與其它數(shù)據(jù)挖掘方法不 同，在進(jìn)行聚類分析前用戶一般并不知道數(shù)據(jù)集的特征。因此，從某種角度 看，聚類分析是一種無監(jiān)督的學(xué)習(xí)過程，是基于觀察的學(xué)習(xí)而不是基于實(shí)例的 學(xué)習(xí)。作為統(tǒng)計的一個分支，聚類分析己經(jīng)被廣泛地研究了許多年，主要集中 在基于距離的聚類分析?；趉 一均值，k 一中心點(diǎn)和其它一些方法的聚類分析工 具己經(jīng)被加入到許多統(tǒng)計分析軟件包或系統(tǒng)中，如s p l u s ，s p s s ，以及s a s 。 k - 均值屬于聚類分析中一種基本的劃分方法，常采用誤差平方和準(zhǔn)則函數(shù) 作為聚類準(zhǔn)則。主要優(yōu)點(diǎn)是算法簡單、快速而且能有效地處理大數(shù)據(jù)集。然而 這種算法依賴于初始值的選擇以及數(shù)據(jù)的輸入順序。此外，由于運(yùn)用誤差平方 和準(zhǔn)則函數(shù)測度聚類效果，如果各類的形狀和大小差別很大，則不能達(dá)到一個 好的聚類效果。 因此，本文針對k 一均值聚類算法中存在的問題也進(jìn)行了改進(jìn)，其中結(jié)合了 支持向量機(jī)一類分類算法，提高了算法的泛化能力，并采用線性規(guī)劃算法，不 僅聚類精度有所提高，而且極大的降低了算法的復(fù)雜性，并具有一定的實(shí)際應(yīng) 用價值。 1 2 本文的研究內(nèi)容及組織結(jié)構(gòu) 1 2 1 研究內(nèi)容 本文闡述了數(shù)據(jù)挖掘中支持向量機(jī)和k 一均值聚類算法的主要理論。在此基 礎(chǔ)上，著重對支持向量機(jī)和k 一均值算法進(jìn)行了改進(jìn)，對兩種算法的融合算法進(jìn) 2 支持向量機(jī)與k 均值聚類融合算法研究 行了研究。 針對支持向量機(jī)對噪聲和野點(diǎn)敏感的問題，我們提出了基于模糊隸屬度的 支持向量機(jī)去噪方法，在線性規(guī)劃下的一類分類支持向量機(jī)中引入模糊隸屬度 剔除噪聲和野點(diǎn)，并在多種數(shù)據(jù)集上進(jìn)行實(shí)驗，通過實(shí)驗驗證了算法的有效 性。 在傳統(tǒng)的k 均值聚類方法中，引入了線性規(guī)劃下的支持向量機(jī)，提出了一 個改進(jìn)的k 一均值聚類算法，即基于支持向量機(jī)的k 一均值聚類算法。應(yīng)用基于 支持向量機(jī)的k 均值聚類算法分別在人工數(shù)據(jù)集( d e l t as e t ) 和u c i 數(shù)據(jù)集( i r i s d a t a ) 上進(jìn)行實(shí)驗，結(jié)果表明此算法對線性不可分的數(shù)據(jù)聚類精度更高，泛化能 力強(qiáng)，且節(jié)省了大量的時間。 1 2 2 組織結(jié)構(gòu) 本論文共分四章，具體組織結(jié)構(gòu)如下： 第一章是緒論，介紹了本論文研究的背景及意義。第二章詳細(xì)介紹了支持 向量機(jī)算法的基礎(chǔ)理論，由二次規(guī)劃下的一類分類支持向量機(jī)算法推導(dǎo)出了線 性規(guī)劃下的一類分類支持向量機(jī)算法，并且提出了基于模糊隸屬度的支持向量 機(jī)去噪方法，介紹了算法的主要理論、實(shí)現(xiàn)步驟以及通過實(shí)驗驗證了算法的可 行性和有效性。第三章主要介紹了聚類方法中的k - 均值聚類算法的基礎(chǔ)理論， 闡述了k 一均值方法的優(yōu)缺點(diǎn)，并且針對k 一均值中存在的問題，闡述了現(xiàn)存的各 種解決方法。在此基礎(chǔ)上，提出了一種基于支持向量機(jī)的k 一均值聚類方法，其 中介紹了這種算法的主要思想和實(shí)現(xiàn)步驟，并通過實(shí)驗證明了算法的有效性。 第四章是對全文的總結(jié)與展望。 3 支持向量機(jī)與k 一均值聚類融合算法研究 2 支持向量機(jī)理論 2 1基于二次規(guī)劃的支持向量機(jī)分類 支持向量機(jī)【i i 】是統(tǒng)計學(xué)習(xí)理論中最實(shí)用的部分，其核心思想是將結(jié)構(gòu)風(fēng)險 最小化原則引入其中。 支持向量機(jī)是從線性可分情況下的最優(yōu)分類超平面發(fā)展而來的，其本質(zhì)是 在訓(xùn)練樣本中找出構(gòu)造最優(yōu)分類超平面的支持向量。在數(shù)學(xué)上歸結(jié)為一個求解 具有不等式約束條件的二次規(guī)劃問題。 假定訓(xùn)練樣本集( 玩，璣) ，i = 1 ，z ，由二類組成，如果奶形屬于第一 類，則標(biāo)記為正慨= 1 ) ；如果x i 艫屬于第二類，則標(biāo)記為負(fù)( 璣= 一1 ) 。學(xué) 習(xí)的目標(biāo)是構(gòu)造一個決策函數(shù)，將測試數(shù)據(jù)盡可能正確的分類。針對訓(xùn)練樣本 集為線性或非線性兩種情況進(jìn)行討論。 2 1 1 線性可分 如果存在分類超平面 z ) + b = 0( 2 1 ) 使得： ( 鼢) + b 1 ，y i = 1 ( u 甄) + b 一1 ，y i = 一1 ，i = 1 ，2 ，j( 2 2 ) 則稱訓(xùn)練集是線性可分的，其中z ) 表示向量u 形與z 形的內(nèi)積。上述 兩式中的z 艫，b 形都進(jìn)行了規(guī)范化，使每類樣本集中與分類超平面距離 最近的數(shù)據(jù)點(diǎn)滿足( 2 2 ) 的等式要求。對于式( 2 2 ) ，可寫成如下形式 犰( ( u 黽) + b ) 1 ，i = 1 ，2 ，z( 2 3 ) 由統(tǒng)計學(xué)習(xí)理論知，如果訓(xùn)練樣本集沒有被超平面錯誤分開，并且距離超 平面最近的樣本數(shù)據(jù)與超平面之間的距離最大，則該超平面為最優(yōu)超平面，由 此得到的決策函數(shù) ，( z ) = s 夕禮( ( c d z ) + b )( 2 4 ) 4 支持向量機(jī)與k 一均值聚類融合算法研究 其推廣能力最優(yōu)，其中s 妒( ) 為符號函數(shù)。最優(yōu)超平面的求解需要最大化南， 即最小化 i iu1 1 2 。歸結(jié)為如下的二次規(guī)劃問題 m i n 扣u1 1 2 約束為 鼽( ( u 也) + b ) 1 ，i = 1 ，2 ，l 我們采用l a g r a n g e 優(yōu)化方法。為此必須找到l a 口a n g e 函數(shù) 三( u ，6 ，口) = 釧u1 1 2 一q t ( 弘( ( “，餓) + 6 ) 一1 ) 的鞍點(diǎn)。式中q t 0 為l a g r a n g e 乘子。 函數(shù)( 2 7 ) 式中的最小值必須滿足條件 掣：u 一壹姚戤o釓 一蘆。一?！?。 丁o l ( w , b , a ) = 壹舭= oa u白挪1 。 將式( 2 8 ) 代入式( 2 7 ) 并考慮式( 2 9 ) ，我們得到 ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) q ( n ) = 啦一吉q a j y t y j ( x i 巧) ( 2 1 0 ) i = 1 。i j - - 1 這里，我們已經(jīng)將符號從三( u ，b ，o ) 改成q ( q ) ，以反映出最后的轉(zhuǎn)換。 q ( q ) 的表達(dá)式( 2 1 0 ) 稱之為l a g r a n g e 對偶目標(biāo)函數(shù)，在約束條件： 0 ，i = 1 ，2 ，j 5 ( 2 1 1 ) ( 2 1 2 ) 甄吼 犰 ；：l i | u 到得此由 0 = 璣 q 。甜 o = 璣 q 。洶 支持向量機(jī)與k 一均值聚類融合算法研究 下對啦求解函數(shù)q ( q ) 的最大值，所得到的解啦只有一部分( 通常是少部分) 不為 零，對應(yīng)的樣本就是支持向量。 應(yīng)該注意的是最優(yōu)化問題的目標(biāo)函數(shù) ) = i - - - - 1q t 一去薈啪砒吲 j = l 與向量z 的維數(shù)無關(guān)，但是與兩個向量的內(nèi)積有關(guān)。這一事實(shí)將允許我們隨后在 高維空間( 甚至在無限維f 拘h i l b e r t 空問) 中構(gòu)造分類超平面。 2 1 2 線性不可分 1 核方法 為了解決線性不可分問題，我們采用一個非線性變換西0 ) 把輸入變量z 影射 到一個高維特征空間日，然后在這一特征空間( 可能為無限大的) 中構(gòu)造一個最 優(yōu)分類超平面，并得到分類器的決策函數(shù)。因此，在非線性情況，分類超平面 為 ( u 圣( z ) ) + b = 0( 2 1 3 ) 決策函數(shù)為 f ( x ) = s 夕禮( ( u 西( z ) ) + 6 )( 2 1 4 ) 由式( 2 1 0 ) , - p a 看出，對于在特征空間日中構(gòu)造最優(yōu)分類超平面，我們并不 需要以顯式來表示特征空間。我們僅僅需要計算特征空間中的向量之間的內(nèi) 積。 假定，我們將輸入向量z 冊映射到一個h i l b e r t 空間，即 圣1 ( z ) ，圣2 ( z ) ，圣。( z ) 根據(jù)h i l b e r t s c h m i d t 理論，h i l b e r t 空間中的內(nèi)積有一個等價表達(dá)式： ( 1 ，九2 ) = q h i ( x 1 ) 吃( z 2 ) 甘k ( x l ，z 2 ) ，o l i 0 ( 2 1 5 ) i = 1 式口p k ( z l ，z 2 ) 為滿足m e r c e r 定理的對稱函數(shù)，稱之為核函數(shù)。目前常用的核函 數(shù)有1 0 多種，其中流行的核函數(shù)是： d 次多項式： k ( x ，甄) = ( 1 + x 乜) d( 2 1 6 ) 高斯徑向基函數(shù)：g ( x ，戤) = e x p ( 一i iz 一瓤1 1 2 盯2 )( 2 1 7 ) 6 支持向量機(jī)與k 一均值聚類融合算法研究 神經(jīng)網(wǎng)絡(luò)核函數(shù)：k ( x ，戤) = t a n h1 ( z 覷) + 忱( 2 1 8 ) 核方法的基本思想是：橢h m e r c e r 條件的任何核函數(shù)k ( z ，既) ，存在 個特征空間( 圣1 ( z ) ，圣2 ( z ) ，垂。( z ) ，) ，在這一空間中這個核函數(shù)生成內(nèi)積。 也就是說式( 2 1 5 ) 的左端絕對一致的收斂于函數(shù)k ( x ，x i ) ，即 k ( x ，x i ) = ：a l h t ( x ) h t ( x i )( 2 1 9 ) 1 = 1 由此可見，樣本空間的內(nèi)積運(yùn)算已替換成核，事實(shí)上，運(yùn)算是在樣本空間進(jìn)行 的，而不是在高維特征空間進(jìn)行的，這就是核技巧的思想。 核方法的優(yōu)點(diǎn)：由于輸入空間的核函數(shù)實(shí)際上是特征空間內(nèi)積的等價。因 此，在實(shí)際計算中，我們不必關(guān)心非線性映射圣( z ) 的具體形式，只需要選定核 函數(shù)g ( x ，兢) 就行。核函數(shù)比較簡單，而映射函數(shù)可能很復(fù)雜，而且維數(shù)很高。 因此，引入核方法才能克服“維數(shù)災(zāi)難”問題。 2 算法實(shí)現(xiàn) 根據(jù)核方法思想，對于非線性分類，首先采用一個非線性映射圣( z ) 把數(shù)據(jù) 影射到一個高維特征空間，然后在高維特征空間中進(jìn)行線性分類，映回到原空 間后就成了輸入空間中的非線性分類。為了避免高維空間中的復(fù)雜計算，支持 向量機(jī)采用一個核函數(shù)k ( x ，y ) 代替高維空間中的內(nèi)積運(yùn)算( 圣( z ) 圣( 矽) ) 。 另外，考慮到可能存在一些樣本不能被分離超平面正確分類，采用松弛變 量解決這個問題，于是優(yōu)化問題為： 1 。 r a u ，6 i ，n 互l 約束為 璣( ( u 圣( 黽) ) + b ) 1 一已，i = 1 ，2 ，z 已0 ，i = 1 ，2 ，z 其中，c 為一正常數(shù)。式( 2 2 0 ) 中第一項使樣本到超平面的距離盡量大， 高泛化能力；第二項則使分類誤差盡量小。 引入拉格朗日函數(shù) l ：互1 怕臚+ c 壺已一壹叫洲u 州硝) + 6 ) 一1 + 已) 一壹m 已 其中，q t ，m 0 ，i = 1 ，f 7 ( 2 2 0 )& 。洶 c+ 2 叫鋤限 塒 勉 勉 廄 勉 q 炯 5 支持向量機(jī)與k 一均值聚類融合算法研究 函數(shù)l 的極值應(yīng)滿足條件 o 伽l = o , 旦l = 。，瓦0 0b l = 。 伽 一 1 弛一 。 于是得到 u = y i a t 圣( ) ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) c q 一已= 0 ，i = 1 ，f ( 2 2 7 ) 將( 2 2 5 ) 一( 2 2 7 ) 代入式( 2 2 3 ) 中，得到優(yōu)化問題的對偶形式為： f 1l m a x 啦一吉a i a j y i y j k ( x t , 巧) ( 2 2 8 ) i = li = 1j = l 約束為 ，q t 犰= 0 ( 2 2 9 ) i = l 0 q c ，i = 1 ，f ( 2 3 0 ) 一般情況下，該優(yōu)化問題解的特點(diǎn)是大部分啦將為零，其中不為零的q ；所 對應(yīng)的樣本為支持向量( s u p p o r tv e c t o r ，s v ) 。 根據(jù)k k t 條件，在鞍點(diǎn)有 a t ( 璣( ( u 圣( 戤) ) + b ) 一l + 已) = 0 ，i = 1 ，z ( 2 3 1 ) ( c 一口i ) & = 0 ，i = 1 ，f( 2 3 2 ) 于是可得b 的計算式如下： l 璣( a j y j k ( x j ，毛) + 6 ) 一1 = o ，q ( o ，c ) ( 2 3 3 ) j = l 因此，可以通過任意一個支持向量求出6 的值。為了穩(wěn)定起見，也可以用所 有的支持向量求出6 的值，然后取平均。 最后得到?jīng)Q策函數(shù)為： 8 ( 2 3 4 ) o l i 璣 口 ，洶 6+zzk 璣 q ，謝 n 9 s = z ，j 支持向量機(jī)與k 一均值聚類融合算法研究 2 1 3 一類分類 設(shè)定一個正類樣本點(diǎn)集為【祝，i = 1 ，z ) ，瓤r d 用一個非線性映射將樣 本點(diǎn)映射到高維特征空間。一類支持向量機(jī)( 1 s v m ) 的目的就是要在高維空間 中找一個超平面，使之以盡可能大的距離p 將盡可能多的樣本從原點(diǎn)分離開，即 估計一個函數(shù)f ( x ) = p 圣( z ) ) 當(dāng)一個樣本z 滿足厶( z ) p 時，它被確定為屬于 該類。為了獲得“，和p 的值，并根據(jù)結(jié)構(gòu)風(fēng)險最小化原則，將問題歸結(jié)為下面的 優(yōu)化： ( 2 3 5 ) ( u 垂( 兢) ) p 一毛，& 0 ，i = l ，f( 2 3 6 ) 其中，；i iu1 1 2 為規(guī)劃項，參數(shù)c 對誤差項和規(guī)劃項做出折中。將優(yōu)化問題化為 對偶形式： m i n 專啦k ( 雙，) ( 2 3 7 ) 。i = lj = l 約束為 0 q t c ，i = 1 ，z( 2 3 8 ) 解出口值后，可得決策函數(shù)： 決策超平面為： ( 2 3 9 ) ( 2 4 0 ) ( 2 4 1 ) 2 2基于線性規(guī)劃的支持向量機(jī)分類 支持向量機(jī)中參數(shù)的數(shù)量在分類情況下等于訓(xùn)練樣本的個數(shù)，在回歸情況 下是訓(xùn)練樣本個數(shù)的二倍。當(dāng)數(shù)據(jù)量很大時，其計算的時間和空間復(fù)雜度均很 大。若能將支持向量機(jī)算法歸結(jié)為線性規(guī)劃來求解無疑會大大減少計算量，于 是一些線性規(guī)劃下的支持向量機(jī)方法被提出。最初的支持向量機(jī)分類算法是通 9 已 。僦 c+ p 一 釅 u 1 2 洫差| 為束約 l = 口 ；斟 zzkq 。洶 = z ，j p l l 圣zk口 。洶 支持向量機(jī)與k - 均值聚類融合算法研究 過最大化分類間隔得到的，而其中的距離度量采用的是由l 2 范數(shù)導(dǎo)出的歐氏距 離。若用l 1 和l 范數(shù)代替其中的l 2 范數(shù)將得到基于線性規(guī)劃的支持向量機(jī)算 法。線性規(guī)劃的支持向量機(jī)算法仍然具有很好的性能，而且計算復(fù)雜度大大減 少。 若優(yōu)化問題( 2 3 5 ) d p 的規(guī)劃項采用l o 。范數(shù)，并且核函數(shù)取高斯核函數(shù)，可 以得到其等價的線性優(yōu)化問題： 。 l m i n - p + c 已 i = 1 ( 2 4 2 ) 約束為 ( u 圣( z i ) ) p 一& ，& 0 ，i = 1 ，j( 2 4 3 ) 0ui l l = 1( 2 4 4 ) z 可以直接采用核展開式eo q k ( z j ，兢) 代替優(yōu)化i h - i 題( 2 4 2 ) c p 的不等式約束 項p 圣( 戤) ) ，于是可得到下面的線性規(guī)劃形式： f r a i n - p + c 矗 ( 2 4 5 ) = 1 約束為 a j k ( x ，) p 一劬= 1 ，z ( 2 4 6 ) j = l f o l i = 1 ( 2 4 7 ) i = 1 啦，& 0 ，i = 1 ，z ( 2 4 8 ) 解這個線性規(guī)劃可以獲得q 和p 的值，于是得到一個決策函數(shù)： z ，( z ) = 啦k ( x i ，z ) ( 2 4 9 ) i = 1 根據(jù)優(yōu)化問題的意義，對于大部分訓(xùn)練樣本將滿足， ) p ，參數(shù)c 的意義 就是控制滿足條件廠( z ) p 的樣本數(shù)量，較大的參數(shù)c 值將使所有的樣本滿足條 件。得到的決策超平面為： f q t k ( x 艫) = p ( 2 5 0 ) i = 1 1 0 支持向量機(jī)與k 一均值聚類融合算法研究 該決策超平面映回到原空間后，就成為包含訓(xùn)練樣本的緊致區(qū)域。對于區(qū)域內(nèi) 的任意樣本z ，滿足，( z ) p ，而對于區(qū)域外的任意樣本y 將滿足，( ) p 。實(shí)際 應(yīng)用中，核函數(shù)中的參數(shù)盯2 的取值越小，獲得原空間中包含訓(xùn)練樣本的區(qū)域越 緊致，這就說明參數(shù)o r 2 將決定分類的精度。 2 3基于模糊隸屬度的支持向量機(jī)去噪方法 盡管在很多方面支持向量機(jī)都具有其它學(xué)習(xí)方法無法比擬的優(yōu)勢，但是它 不是萬能的，也有其自身的局限性，例如對噪聲或野值反應(yīng)靈敏，從而使其容 噪性差，因此，提高支持向量機(jī)的抗噪性成為了一個值得研究的課題。 由于支持向量機(jī)在構(gòu)造最優(yōu)分類超平面時，所有的樣本所起的作用相同， 這樣，當(dāng)樣本中含有一定的噪聲或野值樣本時，考慮這些噪聲或野值樣本所產(chǎn) 生的分類面往往不是真正的最優(yōu)分類超平面。針對這種情況，l i n 等學(xué)者提出 了模糊支持向量機(jī)( f u z z ys u p p o r tv e c t o rm a c h i n e ，f s v m ) a 2 - x s ，對不同樣本 采用不同的權(quán)重系數(shù)，使得在構(gòu)造目標(biāo)函數(shù)時，對噪聲或野值賦予較小的權(quán) 值，以削弱其影響。在f s v m 中，必須能夠客觀準(zhǔn)確地反映系統(tǒng)中樣本存在的 不確定性。一般的f s v m 都是基于樣本到類中心之間的距離來度量其隸屬度的 大小，然而，在依據(jù)樣本到類中心之間距離的角度確定樣本的隸屬度時，有時 并不能將噪聲或野值樣本從有效的樣本中區(qū)分出來，導(dǎo)致將噪聲或野值樣本與 有效樣本賦予相同的隸屬度。針對這個問題，文獻(xiàn) 1 6 】中提出了一種基于樣本之 間緊密度的模糊支持向量機(jī)方法，在確定樣本的隸屬度時，不僅要考慮樣本所 在類中心之間的距離，還要考慮類中樣本之間的緊密度。 支持向量機(jī)的本質(zhì)是在訓(xùn)練樣本中找出構(gòu)造最優(yōu)分類超平面的支持向量， 而樣本中存在的噪聲或野值樣本常常在分類面附近，從而影響了支持向量對構(gòu) 造分類面的作用，本章提出的方法就是利用模糊隸屬度剔除樣本中存在的噪聲 或野值樣本，在構(gòu)造最優(yōu)分類超平面時，不考慮權(quán)重系數(shù)小的噪聲或野值樣 本。在確定隸屬度的訓(xùn)練中，采用的是線性規(guī)劃一類分類方法，實(shí)驗證明了本 文提出的方法在提高s v m 的抗噪能力方面的有效性，而且在處理大量數(shù)據(jù)時， 線性規(guī)劃要比二次規(guī)劃節(jié)省很多時間。 2 3 1 構(gòu)造隸屬度函數(shù) 在確定樣本的隸屬度時，不儀要考慮樣本與所在類中心的距離，還要考慮 1 1 支持向量機(jī)與k 一均值聚類融合算法研究 樣本之間的緊密度。樣本之間的緊密度可以通過樣本遠(yuǎn)離原點(diǎn)的程度來度量。 所以，樣本的隸屬度要根據(jù)樣本遠(yuǎn)離原點(diǎn)的最大距離p 來確定。對分布在區(qū)域 內(nèi)、外的樣本，分別采用兩種不同的計算方式計算各自的隸屬度。隸屬度計算 公式為： l l0 6 宰i p ( 鼢) ： l 卜水l + 0 以) ) ，( 覷) p ( 2 5 1 ) ，( 甄) p 其中p 為樣本離原點(diǎn)的最大距離，( 忍) 為樣本x t 的決策函數(shù)，其計算式為 f f ( x j ) = a i k ( x i ，巧) ，j = 1 ，f ( 2 5 2 ) i = 1 由( 2 5 1 ) 定義的隸屬度p ( 兢) 可以看出：樣本離原點(diǎn)越遠(yuǎn)，則該樣本屬于該 類的隸屬度就越大，同時也考慮了樣本位于類內(nèi)位置的影響，位于類區(qū)域內(nèi)的 樣本隸屬度都大于0 5 ；而位于類區(qū)域外的樣本隸屬度都小于0 5 ，由于噪聲和 野值樣本一般都位于類區(qū)域外，所以其隸屬度都小于o 5 。由此，設(shè)置一個小 于0 5 的閥值就可以將噪聲和野值樣本從樣本集中剔除，留下的都是對構(gòu)建最優(yōu) 分類超平面有益的樣本。 2 3 2實(shí)現(xiàn)步驟 1 分別對正、負(fù)類樣本進(jìn)行線性規(guī)劃下的一類分類，由此分別產(chǎn)生正、負(fù) 決策面a i k ( z i ，x ) = n ，2 ，及決策函數(shù) ，2 ( z ) = e 毗k ( 貌，z ) ； 2 由p 1 ，2 和 ，2 ( z ) 確定各個樣本的隸屬度p ( z ) ； 3 設(shè)定閥值入，將p ( z ) 入的噪聲樣本從原樣本中剔除，從而產(chǎn)生新樣本 集； 4 采用去噪后的樣本訓(xùn)練支持向量機(jī)。 2 3 3 實(shí)驗分析 本實(shí)驗先采用了4 0 0 個隨機(jī)產(chǎn)生的兩類二維樣本，2 0 0 個正類樣本和2 0 0 個 負(fù)類樣本，并分別在正、負(fù)類樣本中隨機(jī)加入了1 0 的噪聲作為訓(xùn)練樣本， 如圖2 1 所示。采用2 2 0 個測試樣本，在測試樣本中同樣也隨機(jī)加入了1 0 的 噪聲。分別采用傳統(tǒng)支持向量機(jī)和本文提出的基于模糊技術(shù)去噪聲的方法 1 2 垂、 、一、 一，壟f 卜一h h 支持向量機(jī)與k 均值聚類融合算法研究 圖2 1 ：帶噪聲樣本 進(jìn)行實(shí)驗，c 和口分別取1 2 和3 0 ，a = 0 3 ，傳統(tǒng)的支持向量機(jī)樣本正確識別率 為8 3 6 4 ，本文的方法樣本正確識別率為8 7 7 3 。又采用相似隨機(jī)樣本，但只 在分類面附近加入噪聲，分別用兩種方法訓(xùn)練，c 和伊分別取3 0 和5 0 ，a = 0 3 ， 傳統(tǒng)的支持向量機(jī)正確識別率分別為7 9 2 ，本文的方法正確識別率為8 4 5 1 。 分別采用b a n a n a ，h e a r t ，b r e a s t c a n c e r 數(shù)據(jù)進(jìn)行實(shí)驗，在原始數(shù)據(jù)中分別 加入1 0 的噪聲，再用上述兩種方法分別進(jìn)行實(shí)驗。實(shí)驗結(jié)果顯示，樣本的正 確識別率均有所提高，實(shí)驗結(jié)果如表2 1 所示。而對不加噪聲的樣本用兩種方法 分別進(jìn)行實(shí)驗，結(jié)果并沒有太大差異。 表2 1 本文方法與s v m 方法的正確識別率之比較 方法 b a n a n ah e a r tb r e a s t c a n c e r s v m8 4 6 8 8 0 0 0 7 7 1 本章方法 8 6 2 9 8 5 0 1 7 9 5 2 對于不同的數(shù)據(jù)，閥值入要采用不同的值，一般情況取0 3 a 0 4 。通過 1 3 支持向量機(jī)與k 均值聚類融合算法研究 訓(xùn)練調(diào)整a 值，a 值太大會把正常樣本點(diǎn)去掉，入值太小對噪聲起不到作用。實(shí) 驗證明，去除含有“異?！毙畔⒌脑肼晿颖緦?gòu)建最優(yōu)分類超平面是有益的， 本文提出的方法在提高支持向量機(jī)的抗噪能力方面效果非常明顯，應(yīng)用也非常 廣泛。 2 3 4實(shí)驗總結(jié) 傳統(tǒng)的支持向量機(jī)在處理無噪聲的樣本時，學(xué)習(xí)能力和泛化能力都非常 強(qiáng)，但當(dāng)樣本中存在噪聲或野值樣本時，噪聲或野值樣本影響了支持向量對構(gòu) 造分類面的作用，使產(chǎn)生的分類面偏離了最優(yōu)分類超平面。本文運(yùn)用模糊隸屬 度去除樣本中存在的噪聲或野值樣本，減小其對分類面的影響。在確定隸屬度 時，不僅考慮樣本與所在類的距離，而且還考慮了樣本之間的緊密度，對不同 的樣本采用不同的公式計算其隸屬度。再者，應(yīng)用線性規(guī)劃大大節(jié)省了計算時 間。通過對比實(shí)驗，證明本文提出的方法與傳統(tǒng)的支持向量機(jī)相比，樣本的正 確識別率更高，改善了支持向量機(jī)對噪聲敏感的問題，增強(qiáng)了支持向量機(jī)的抗 噪能力。 1 4 支持向量機(jī)與k 一均值聚類融合算法研究 3k 均值聚類算法 3 1劃分聚類算法概述 劃分聚類也叫分割聚類。給定一個含有t t 個對象或元組的數(shù)據(jù)庫，一個劃分 方法，通過優(yōu)化一個評價函數(shù)構(gòu)建數(shù)據(jù)的k 個劃分，每個劃分表示一個聚類，并 且k t t 。也就是說，它將數(shù)據(jù)劃分為k 個組，同時滿足如下的要求： 1 每個組至少包括一個對象； 2 每個對象必須屬于且只屬于一個組。 但是在某些模糊劃分技術(shù)中第二個要求可以放寬。一個好的劃分準(zhǔn)則是：在 同一個類中對象之間盡可能“接近或相關(guān)，而不同類中的對象之間盡可能 “遠(yuǎn)離”或不同。 為了達(dá)到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。實(shí)際 上，絕大多數(shù)應(yīng)用采用了以下兩個比較流行的啟發(fā)式方法：1 k 均值算法，在 該算法中，每個簇用其中對象的平均值來表示。2 k 一中心點(diǎn)算法，在該算法 中，每個簇用接近聚類中心的一個對象來表示。這些啟發(fā)式聚類方法對在中小 規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用。為了對大規(guī)模的數(shù)據(jù)集進(jìn)行聚類，以及處 理復(fù)雜形狀的聚類，基于劃分的方法需要進(jìn)一步地擴(kuò)展。 劃分算法典型地采用兩階段反復(fù)循環(huán)過程：1 指定聚類，即指定一個數(shù)據(jù) 對象到某一個聚類，使得它與這個聚類中心的距離比它與其它聚類中心的距離 要近；2 修改聚類中心。算法的結(jié)束條件是不再有數(shù)據(jù)被重新分配?？梢赃x 擇一個反映聚類效果的目標(biāo)函數(shù)，當(dāng)函數(shù)達(dá)到最優(yōu)解時滿足終止標(biāo)準(zhǔn)。這一 類算法中，有的算法在對每一個數(shù)據(jù)對象的每一次指定后就修改一次聚類中 心( 如s o m 方法) ，有的算法當(dāng)對所有的數(shù)據(jù)對象都指定完后才修改一次聚類中 心( 如k 一均值，l b g 方法) ，所以對這一類方法來說，存在兩個基本問題，即： 如何計算距離和如何修改聚類中心。在計算距離時，對數(shù)值屬性主要的方法是 采用明考夫斯基距離中的歐氏距離，而對符號屬性則可以采用海明距離。 在數(shù)據(jù)規(guī)模比較小以及數(shù)據(jù)對象維數(shù)較低的情況下，傳統(tǒng)的劃分聚類算法 可以將數(shù)據(jù)全部讀入到內(nèi)存進(jìn)行計算，而隨著數(shù)據(jù)量地增加，需要和磁盤進(jìn)行 多次數(shù)據(jù)交換，花費(fèi)大量的i o 時間；又由于劃分聚類算法通常需要大量的距 離計算( 數(shù)據(jù)對象之間以及它們與聚類中心之間的) ，從而導(dǎo)致運(yùn)行時問開銷較 大，效率較低。這直接限制了它們在一些相關(guān)領(lǐng)域中的實(shí)用性。如何對以驚人 1 5 支持向量機(jī)與k 一均值聚類融合算法研究 速度增長的數(shù)據(jù)量進(jìn)行聚類，如何提高算法的執(zhí)行效率以及可擴(kuò)展性就成為了 許多算法需要解決的問題1 1 7 】。 3 2聚類分析中數(shù)據(jù)類型 數(shù)據(jù)分析中的數(shù)據(jù)類型主要有兩類。假設(shè)對一個數(shù)據(jù)集進(jìn)行聚類分析，該 數(shù)據(jù)集包含n 個對象，這些對象可以是人、樹木、文件等等?；趦?nèi)存的聚類算 法通常采用以下兩種數(shù)據(jù)結(jié)構(gòu)1 1 8 ： 1 數(shù)據(jù)矩陣 數(shù)據(jù)矩陣是一個對象一一屬性結(jié)構(gòu)，它其實(shí)是一張關(guān)系表，每列代表對象 的一個屬性，每行表示一個數(shù)據(jù)對象。具有m 個屬性的n 個對象( 例如：樹木對 象可以利用m 個屬性來描述，屬性如：高度、種類等) 可以表示為一個幾x 仇矩 陣來表示： a l t o a n m ( 3 1 ) 2 差異矩陣 差異矩陣存儲n 個對象兩兩之間的相異性。它是一個對象一一對象結(jié)構(gòu)，其 表現(xiàn)形式是一個nx n f f r 矩陣，其中的每一個元素d ( t 歹) 表示對象i 和對象歹之間的 墊_ ：。卜 2 ， 通常情況下，d ( i ，歹) 是一個非負(fù)數(shù)，當(dāng)對象i 和對象j 彼此“接近”時， 該數(shù)據(jù)就越接近0 值：該數(shù)據(jù)值越大，就表示對象i 和對象7 越不相似。由于 有d ( i ，j ) = d ( j ，i ) ，且d ( i ，i ) = 0 ，因此，此矩陣可表示成下三角行列式的形式。 通常，數(shù)據(jù)矩陣又可稱為雙模式( t w o - m o d e ) 矩陣，差異矩陣則又可稱為單 模式( o n e - m o d e ) 矩陣。因為數(shù)據(jù)矩陣的行和列分別表示不同的實(shí)體，而差異矩 陣的行和列則表示的是同一實(shí)體。許多聚類算法都是基于差異矩陣進(jìn)行聚類分 1 6 一 一 l ，1 m ； o 磊& m o m 邢m ，。一 示表r r如 。 度異相 支持向量機(jī)與k 一均值聚類融合算法研究 析的。如果數(shù)據(jù)是以數(shù)據(jù)矩陣的形式給出的，就要先將其轉(zhuǎn)換為差異矩陣，才 能利用聚類算法對其進(jìn)行處理。 3 3聚類分析中相似度度量方法 1 區(qū)間標(biāo)度變量 區(qū)問標(biāo)度變量是一個粗略線性標(biāo)度的連續(xù)變量。典型的例子包括重量和高 度，經(jīng)度和緯度，以及大氣溫度。 選用的度量單位將直接影響聚類分析的結(jié)果。一般而言，選用的單位越 小，變量可能的值域就越大，這樣對聚類結(jié)果的影響就越大。因此為了避免聚 類結(jié)果對單位選擇的依賴，數(shù)據(jù)應(yīng)當(dāng)標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化處理后，對象間的相異度 是基于距離來計算的。最常用的距離度量方法是歐氏距離，它的定義為： d ( x i ，協(xié)) = 、ix i l 一協(xié)11 2 + lx i 2 一y i 21 2 + + ix i l y j m1 2 ( 3 3 ) 這里戤= ( x i l ，x i 2 ，x i 竹) 的劬= ( 協(xié)1 ，y j 2 ，協(xié)n ) 和是兩個仇維的數(shù)據(jù)對象。 在使用歐氏距離時要特別注意樣本諸測量值的選取，應(yīng)是能有效反映類別屬性 的特征。 另外，兩個著名的度量方法是曼哈頓距離： d ( 戤，協(xié)) = x i l 一協(xié)1i + ix i 2 一協(xié)2i + + i 兢1 一協(xié)mi( 3 4 ) 明考夫斯基距離： d ( x i , 協(xié)) = 舡孓i 再瓦i 萬i 可而 ( 3 5 ) 從明考夫斯基距離可以看出：當(dāng)口= 1 時，它表示曼哈頓距離，當(dāng)q = 2 時， 它表示歐氏距離。 2