模式識別中的近鄰性測度

崔榮一

（延邊大學(xué)工學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 智能信息處理研究室，吉林 延吉133002）

模式識別中的近鄰性測度

崔榮一

（延邊大學(xué)工學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 智能信息處理研究室，吉林 延吉133002）

模式之間的相異性或相似性的定量描述是模式識別領(lǐng)域中的基本問題之一．本文在論述和討論近鄰性的本質(zhì)和數(shù)學(xué)定義的基礎(chǔ)上，綜述和歸納了模式識別中采用的典型近鄰性測度方法及其應(yīng)用領(lǐng)域，闡明了近鄰性與模式屬性之間的關(guān)系以及在近鄰性的度量中模式本身的特性與先驗(yàn)知識所起的重要作用．

模式識別；測度；度量；近鄰性

0 引言

近鄰性（proximity）是刻畫事物間的差異或相似程度的量，差異程度可用距離來描述，而相似程度可用相似度來描述．近鄰性的定量描述是模式識別中分類與聚類的基礎(chǔ)，是所有以對象之間在某些特征上的相近程度為依據(jù)的信息處理問題中最為基本的問題．差異和相似性是從不同角度描述事物之間相近程度的量，二者之間存在對立關(guān)系：差異越大（?。?，相似性就越小（大），反之亦然．因此在很多的定性討論中“近鄰性”以廣義的“相似性”來替代，而在本文中將嚴(yán)格區(qū)別相異性（dissimilarity）與相似性（similarity），并把二者統(tǒng)稱為近鄰性．

在機(jī)器學(xué)習(xí)、模式識別、數(shù)據(jù)挖掘等理論、方法和技術(shù)的研究中出現(xiàn)了大量的近鄰性描述方法［1］，其中離不開距離、近鄰性、相似度等詞匯．然而，很多情況下工程應(yīng)用中的近鄰性測度和度量并不一定都符合嚴(yán)格的數(shù)學(xué)定義，因而造成近鄰性概念和使用方法上的混亂．本文以嚴(yán)格的數(shù)學(xué)定義為基礎(chǔ)，首先介紹模式識別問題中常用的基本近鄰性測度函數(shù)及其相關(guān)性質(zhì)，分析不同方法的特點(diǎn)與適用問題；之后探討近鄰性與屬性之間存在的內(nèi)在關(guān)系以及先驗(yàn)知識在近鄰性測度中的重要地位和相關(guān)的機(jī)器學(xué)習(xí)方法．

1 近鄰性的本質(zhì)

近鄰性是事物及其存在形式與變化方式之間所擁有的共性，這種共性是系統(tǒng)的一個(gè)基本特征，是人們認(rèn)知機(jī)制中的重要元素．系統(tǒng)科學(xué)認(rèn)為這種共性體現(xiàn)在系統(tǒng)的結(jié)構(gòu)和功能、存在方式和演化過程，是一種有差異的共性（等同是近鄰的特例），是系統(tǒng)同一性的一種表現(xiàn)［2］．不同領(lǐng)域中的近鄰性具有同樣的特性，如語言學(xué)中相似詞語具有語義上的公共要素，代數(shù)學(xué)中相似矩陣具有相同的本征值，幾何學(xué)中相似圖形的對應(yīng)邊之間存在相同的比例關(guān)系，等等．學(xué)科內(nèi)部、學(xué)科之間也存在相似性，因此，以已發(fā)現(xiàn)的科學(xué)規(guī)律為原型可以通過類比推理揭示新的科學(xué)規(guī)律；也可以從已有學(xué)科建立起另一學(xué)科，如認(rèn)知科學(xué)就是在人腦的信息加工與計(jì)算機(jī)的數(shù)據(jù)處理之間的相似性基礎(chǔ)上建立起來的［3］．

近鄰性與概念密切相關(guān)，其計(jì)算可以決定概念的發(fā)現(xiàn)［4］．從對象與概念之間的關(guān)系上看，存在2種近鄰性：一是對象與概念之間的近鄰性，可用Zadeh的模糊隸屬度來表示［5］；二是在某概念下對象之間的近鄰性，就是在特定概念下樣本之間的近鄰性．

概念的本質(zhì)特征本身可以看作是相似性，因此在特定概念及其相關(guān)屬性確定的前提下，合理定義近鄰性的問題就是由相關(guān)特征提取本質(zhì)屬性的過程，一般屬于監(jiān)督學(xué)習(xí)（supervised learning）問題．但如果概念事先未知而只有給定的屬性，那么近鄰性對于概念的提取具有重要作用，這也是機(jī)器學(xué)習(xí)和模式識別的根本任務(wù)．

模式識別是以分類為基本目標(biāo)的學(xué)科．分類（clasification）是以模式在特征空間中的近鄰性為依據(jù)的，而聚類分析（clustering analysis）就是利用近鄰性從有限數(shù)據(jù)中發(fā)現(xiàn)概念的技術(shù)和方法．機(jī)器學(xué)習(xí)從數(shù)據(jù)中提取任務(wù)相關(guān)的概念，其基本前提就是同屬于1個(gè)概念的樣例之間彼此相近．不同的近鄰性測度隱含著對數(shù)據(jù)樣本觀察角度的不同，而這些角度都取決于函數(shù)自身的性質(zhì)及其所表達(dá)的形狀，傾向于發(fā)現(xiàn)適合于特定觀察角度的不同形狀的類結(jié)構(gòu)［6］．

2 近鄰性的數(shù)學(xué)定義

近鄰性描述事物及其存在和變化方式之間有差異的共性，其度量方法的基礎(chǔ)是相異性測度和相似性測度，而距離和相似度是對相異性測度和相似性測度進(jìn)行進(jìn)一步限定而得出的函數(shù)．測度和度量是具有嚴(yán)格定義的數(shù)學(xué)概念，簡單地說，測度是定義在集合子集上的實(shí)函數(shù)，而度量是評估集合中2個(gè)元素之間的差異或相似性的實(shí)函數(shù)．在近鄰性程度的描述中，度量建立在測度之上．下面給出向量空間中點(diǎn)間的距離和相似度概念的基本定義和相關(guān)定理，這是構(gòu)造更復(fù)雜的距離與相似度的基礎(chǔ)．

定義1（相異性測度）［7－8］對向量集合X和實(shí)數(shù)集R，若函數(shù)d（d∶X×X→R）滿足：①?d0∈R s．t－∞ ＜d0≤d（x，y）＜＋∞，?x，y∈X（下界存在性）；②d（x，x）＝d0，?x∈X（自反性）；③d（x，y）＝d（y，x），?x，y∈X（對稱性）；則稱d為X上的1個(gè)相異性測度（dissimilarity measure，DM）．

條件①規(guī)定了相異性測度存在一個(gè)確定的下界（存在“最近”的概念），條件②意味著任何向量與自身是最相近的，條件③規(guī)定了向量之間的相異性是2個(gè)向量之間相對而對等的概念．

定義2（距離）［7－8］如果向量集合X上的相異性測度d滿足：④當(dāng)且僅當(dāng)x＝y(tǒng)時(shí)，d（x，y）＝d0（同一性）；⑤d（x，z）≤d（x，y）＋d（y，z），?x，y，z∈X（三角不等式）；則稱d為相異性度量 （metric DM），又稱距離函數(shù)，簡稱距離（distance）．

作為距離函數(shù)的特性，條件④規(guī)定最近的2個(gè)向量必然是同一向量，反之亦然；條件⑤規(guī)定兩點(diǎn)間直線距離最短．兩點(diǎn)間的距離描述了它們所代表的模式之間的相異程度（dissimilarity level）．由條件③—⑤可以導(dǎo)出距離函數(shù)的以下性質(zhì)：

性質(zhì)1（距離的非負(fù)性） 相異性度量是非負(fù)函數(shù)，即d0≥0．

定義3（超度量）［8－9］如果把距離函數(shù)d滿足的條件⑤替換為更強(qiáng)的條件：d（x，z）≤max［d（x，y），d（y，z）］，?x，y，z∈X（強(qiáng)三角不等式），則函數(shù)d稱為超度量 （ultrametric）．

例如，離散度量

定義4（相似性測度）［7－8］對向量集合X和實(shí)數(shù)集R，若函數(shù)s∶X×X→R滿足：⑥?s0∈R s．t－∞ ＜s（x，y）≤s0＜＋∞，?x，y∈X（上界存在性）；⑦s（x，x）＝s0，?x∈X（自反性）；⑧s（x，y）＝s（y，x），?x，y∈X（對稱性）；則稱s為X上的1個(gè)相似性測度 （similarity measure，SM）．

條件⑥規(guī)定了相似性測度存在1個(gè)確定的上界（存在“最相似”的概念），條件⑦意味著所有向量與自身是最相似的，條件⑧規(guī)定了向量之間的相似性是2個(gè)向量之間相對而對等的概念．

定義5（相似度）［7－8］如果向量集合X上的相似性測度s滿足：⑨ 當(dāng)且僅當(dāng)x＝y(tǒng)時(shí)，s（x，y）＝s0（同一性）；⑩s（x，y）s（y，z）≤ ［s（x，y）＋s（y，z）］s（x，z），?x，y，z∈X（倒三角不等式）；則稱s為相似性度量 （metric SM），簡稱相似度（similarity）．

上述條件⑨表示最相似的2個(gè)向量必然是同一向量，反之亦然；而條件⑩稱為倒三角不等式是因?yàn)椋寒?dāng)相似度s（x，y）＞0，?x，y∈X，且相異性與相似性的對立關(guān)系表現(xiàn)為反比關(guān)系時(shí)（相似度和距離并非一定存在反比關(guān)系），條件⑩等價(jià)于這與距離條件

⑤極其相似，只是測度值取了倒數(shù)．由條件⑧—⑩可證明相似度的以下2個(gè)性質(zhì)：

性質(zhì)1（相似度的保號性） 相似度一定是非負(fù)的：

或一定是非正的：

性質(zhì)2（相似性的相容性） 非負(fù)相似度（式（1））中不存在與2個(gè)完全不相似（相似度為0）向量都相似（相似度大于0）的向量．

在模式識別的很多應(yīng)用中取d0＝0（向量到自身的距離定義為0），相似度常采用式（1），且s0＝1（歸一化）［8］；然而一般情況下d0可能是其他正數(shù)，s0也可以取其他正數(shù)或負(fù)數(shù)（若采用式（2））．

距離和相似度是相互對立的，一般的基于空間距離d的相似度計(jì)算框架被認(rèn)為是［4］：s＝F（d），其中函數(shù)F（x）是x的非負(fù)遞減函數(shù)，且0≤F（x）≤1，F(xiàn)（0）＝1．從距離與相似度的基本定義出發(fā)可以證明以下結(jié)論成立（通過驗(yàn)證定義所要求的條件①—⑩來證明，而關(guān)鍵是驗(yàn)證條件⑤和⑩）：

定理1（距離與相似度的反比轉(zhuǎn)換） 若s為集合X上的相似度，且滿足s（x，y）＞0，?x，y∈X，則d＝a/s（a＞0）是X上的距離；若d為集合X上的距離，且滿足d（x，y）＞0，?x，y∈X，則s＝a/d（a＞0）是X上的相似度．

定理2（相異性與相似性的逆差轉(zhuǎn)換） 若s為集合X上的相似性測度，則d＝s0－s是X上的相異性測度；若d為集合X上的相異性測度，則s＝dmax－d（dmax＝maxx，y∈Xd（x，y））是X上的相似性測度．

通過對距離和相似度的適當(dāng)函數(shù)變換可以導(dǎo)出新的距離和相似度函數(shù)．

定理3（距離和相似度的膨脹平移） 若d為集合X上的距離，則kd＋a（?a≥0，k＞0）仍是X上的距離；若s為集合X上的相似度，滿足s（x，y）≥0，?x，y∈X，則ks＋a（?a≥0，k＞0）仍是X上的相似度．

定理4（距離和相似度的函數(shù)變換） 若單調(diào)遞增連續(xù)函數(shù)f∶R＋→R＋滿足f（x）＋f（y）≥f（x＋y），?x，y∈R＋，而d為X上的距離，測度值下界為d0≥0，則f（d）仍為X上的距離；若單調(diào)遞減連續(xù)函數(shù)g∶R＋→R＋滿足g（x）＋g（y）≥g（1/（1/x＋1/y）），?x，y∈R＋，而s為X上的相似度，滿足s（u，v）＞0，?u，v∈X，則g（s）仍為X上的相似度．

以點(diǎn)間的近鄰性測度與度量為基礎(chǔ)，可進(jìn)一步定義點(diǎn)與集合、集合與集合之間的近鄰性．在近鄰性度量的很多應(yīng)用中，定義中的條件不一定全部滿足，但就特定的應(yīng)用目的而言仍具有有效的使用價(jià)值．如果只有三角不等式不成立則稱為半度量（semi－metric）［8］．

3 基本的近鄰性測度

在近鄰性測度表述過程中，1個(gè)模式將會(huì)有3種表示方式：1）實(shí)向量空間中的特征向量x∈X?Rn，n表示向量維數(shù)，xk表示向量x的第k個(gè)分量；2）屬性集合表示屬性集合的元素個(gè)數(shù)；3）屬性向量x∈｛0，1｝n，各維分量值為1或0，分別表示該模式中特定屬性出現(xiàn)與否．對2個(gè)二值向量x，y∈｛0，1｝n，其各分量中0和1組合出現(xiàn)的可能性及其數(shù)量如表1所示．例如，b表示向量x和y同一維分量對（xk，yk）?。?，0）的數(shù)目．

表1 二值向量對的各維取值組合可能性表

3．1 相異性測度

在聚類分析等領(lǐng)域，Minkowski距離在刻畫模式相異度的過程中起重要的作用［10］．歐氏距離與現(xiàn)實(shí)空間距離概念一致而且常用于計(jì)算模式之間的空間位置差異；Manhattan距離是從1個(gè)點(diǎn)沿各坐標(biāo)軸方向行進(jìn)到達(dá)另1點(diǎn)的距離，在數(shù)字圖像中2個(gè)像素之間的4鄰接通路的長度就是這2個(gè)像素點(diǎn)間的Manhattan距離［11］；Chebyshev距離是從1個(gè)點(diǎn)沿各坐標(biāo)軸方向或45°方向到達(dá)另1點(diǎn)的距離，在數(shù)字圖像中2個(gè)像素之間的8鄰接通路的長度就是這2個(gè)像素點(diǎn)間的Chebyshev距離［11］．

證明Minkowski距離為相異性度量的關(guān)鍵是證明定義2中的條件⑤，即Minkowski不等式：距離具有平移不變性，但只有p＝2時(shí)（即歐氏距離）才具有旋轉(zhuǎn)不變性［9］．值得注意的是，Minkowski距離具有量綱，因此一定要采用相同量綱的變量．如果變量的量綱不同，測量值變化范圍相差懸殊時(shí)，具有很大差異的屬性將主導(dǎo)距離度量．因此首先要進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化處理，然后再計(jì)算距離．Minkowski距離存在2個(gè)方面的問題：一是認(rèn)為各分量的量綱（scale）因素均等；二是認(rèn)為各分量的分布均等．實(shí)踐中應(yīng)盡可能地避免變量的多重相關(guān)性（multi－collinearity），因?yàn)槎嘀叵嚓P(guān)性所造成的信息重疊，會(huì)片面強(qiáng)調(diào)某些屬性的重要性．該性質(zhì)對于最近鄰規(guī)則算法的重要性表現(xiàn)在：最近鄰算法的有效性會(huì)受到各維特征所選擇的單位的影響，往往是單位選擇較小的特征在歐氏距離的計(jì)算中起著較重要的作用，而單位較大的特征之間的差異在距離計(jì)算中往往被掩蓋掉．為了解決這一問題，在分類之前可以分別對每個(gè)特征進(jìn)行尺度變換，使得特征的尺度均衡化．具體實(shí)現(xiàn)時(shí)可以選擇變換系數(shù)：其中max（xk）和min（xk）分別表示所有訓(xùn)練樣本中第k維特征的最大值和最小值．

上述度量函數(shù)的定義中把特征向量的各維屬性同等看待，為了表現(xiàn)不同屬性的重要性差異，可以在度量函數(shù)的定義中為向量的各維指定不同權(quán)值，所得距離稱為加權(quán)距離．加權(quán)Minkowski距離定義為：其中wk為第k個(gè)特征屬性的權(quán)值，刻畫該屬性的重要程度．式（3）實(shí)際上就是一種權(quán)值．

當(dāng)p不是1和∞時(shí)，Minkowski距離的計(jì)算代價(jià)是較大的．從解決問題和降低計(jì)算復(fù)雜度的需要出發(fā)，可以用其他距離函數(shù)逼近歐氏距離，如Chaudhuri等［12］提出了歐氏距離的1種逼近：dCha（x，y）．這種逼近避免了歐氏距離計(jì)算中的平方和開方運(yùn)算．上述距離也可用屬性集合與屬性向量表示，如歐氏距離的屬性集合與屬性向量分別表示為其中b，c的意義見表1．克服Minkowski距離依賴于量綱的1種改進(jìn)距離就是Mahalanobis距離．

如果協(xié)方差矩陣為對角陣，則稱為正規(guī)化的Mahalanobis距離：其中σk是樣本第k維特征的標(biāo)準(zhǔn)差．這是把不同因素（如身高和體重）統(tǒng)一標(biāo)準(zhǔn)化處理的1種方法．

3）Canberra（Lance－Williams）距離這是1個(gè)無量綱的距離函數(shù)，但不能克服分量間的相關(guān)性．該距離的特點(diǎn)是向量間每個(gè)屬性的差異利用這2個(gè)向量該屬性之和進(jìn)行規(guī)范化，每1項(xiàng)在［0，1］內(nèi)取值：當(dāng)2個(gè)向量的某一屬性值相等時(shí)，相應(yīng)的距離項(xiàng)為0；當(dāng)2個(gè)向量某一屬性值同號時(shí)，相應(yīng)的距離項(xiàng)介于0和1之間；而一旦2個(gè)向量某一屬性值異號時(shí)，相應(yīng)的距離項(xiàng)變?yōu)?；距離值最終取值于［0，n］．該距離常用于圖像特征差異的分析等應(yīng)用中［16］．

對二值向量x，y∈｛0，1｝n來說，Hamming距離就是二者的異或運(yùn)算結(jié)果中1出現(xiàn)的個(gè)數(shù)，也等于向量間的Manhattan距離容易證明，二值離散空間中向量間的歐氏距離就是這2個(gè)向量之間Hamming距離的平方根1｝n為屬性向量，則有Hamming距離的另一有意義的表述：其中b和c的含義見表1．用屬性集合表示模式時(shí)，2個(gè)模式A和B之間的Hamming距離就是2個(gè)集合中相異元素的個(gè)數(shù)：

Hamming距離在信息論、通信、計(jì)算機(jī)技術(shù)等領(lǐng)域的應(yīng)用非常廣泛［17］．在編碼過程中為了檢測e個(gè)錯(cuò)誤，需要1個(gè)Hamming距離為e＋1的編碼方案，而為了糾正f個(gè)錯(cuò)誤，需要1個(gè)距離為2f＋1的編碼方案．在聚類分析的應(yīng)用中，Hamming距離仍是簡潔有效的相異性度量［18］，在本文相似度計(jì)算等其他領(lǐng)域，Hamming距離也得到了廣泛的應(yīng)用［19］．

5）Tanimoto距離．用屬性集合表示模式時(shí)，模式A和B之間的Tanomoto距離定義為屬性向量x，y∈｛0，1｝n之間的Tanimoto距離定義為其中a，b，c的含義見表1．Tanimoto距離的意義為：2個(gè)向量所代表的模式非共享屬性個(gè)數(shù)占共同擁有屬性個(gè)數(shù)的比例，即2個(gè)模式組成結(jié)構(gòu)的差異．

Tanimoto距離符合相異性度量的全部要求［20］，取值于［0，1］：當(dāng)2個(gè)集合互不相交（具有完全不同屬性）時(shí)取最大值，當(dāng)2個(gè)集合相等（具有完全相同屬性）時(shí)取最小值．Tanimoto距離廣泛用于分類學(xué)和刻畫結(jié)構(gòu)之間的差異［21－22］，也可以用于表示文檔數(shù)據(jù)的差異．

3．2 相似性測度

以下給出的相似性函數(shù)都是相似性測度，但不是相似性度量，因?yàn)樗鼈儾粷M足相似性度量的條件⑩．根據(jù)定理1和2，相似性與相異性測度是可以相互轉(zhuǎn)換的，對任何1個(gè)相似性測度s，都可以構(gòu)造相應(yīng)的相異性測度d．以下相似性測度通常采用定理2轉(zhuǎn)換為相異性測度，然而所得到的相異性測度不一定是相異性度量．

3）Tanimoto測 度 （Tanimoto系 數(shù)，Jaccard系 數(shù)當(dāng)模式類X中的向量歸一化為長度為a＞0的等長向量時(shí)，該測度可改寫為：sTan（x，y）測度是余弦測度的推廣，顯然具有旋轉(zhuǎn)不變性，其取值范圍是［－1/3，＋1］，在x＝－y時(shí)達(dá)到最小值，在x＝y(tǒng)時(shí)達(dá)到最大值，而當(dāng)2個(gè)向量正交時(shí)測度值為0．

用屬性集合表示模式時(shí)，模式A和B之間的Tanomoto測度定義為：值域?yàn)椋?，1］．屬性向量x，y∈ ｛0，1｝n之間的Tanimoto測度定義為：

值域也是［0，1］．由此可見，Tanimoto測度是共享屬性個(gè)數(shù)占共擁屬性個(gè)數(shù)的比例．Tanimoto測度常用于計(jì)算樣本集之間或模式結(jié)構(gòu)之間的相似度［26］，也可以用來計(jì)算字符串之間的相似性、對象集合之間的匹配度等測度．在聚類算法研究中，Tanimoto測度應(yīng)用于聚類有效性假設(shè)檢驗(yàn)的外部準(zhǔn)則中［7］．

取值范圍皆為［0，1］．Dice測度與Tonimoto測度都用于計(jì)算模式或?qū)ο蠹现g的相似程度，但不完全相同，主要區(qū)別是：①由Tanimoto測度構(gòu)造的Tanimoto相異性測度是距離函數(shù)，但按構(gòu)造的Dice相異性測度不是1個(gè)度量．②比較（5）和（6）式可知，這2個(gè)測度對非共享屬性（不相交集合元素）個(gè)數(shù)的權(quán)重不同，Tanimoto測度考慮總體屬性個(gè)數(shù)時(shí)對共享和非共享屬性均等看待，而Dice測度則降低非共享屬性個(gè)數(shù)的作用（僅考慮半數(shù)）；因此，在共享屬性個(gè)數(shù)相同的情況下，Tanimoto測度值往往比Dice測度值小，是較為悲觀的評估．

除此之外，在具體應(yīng)用中還可以定義很多不同的相似性測度，如文獻(xiàn)［27］為研究流式細(xì)胞計(jì)數(shù)數(shù)據(jù)的實(shí)時(shí)自適應(yīng)聚類問題，采用了相似性測度

3．3 動(dòng)態(tài)相似性測度

在語音識別、生物信息學(xué)、信息檢索、機(jī)器翻譯、辭典編撰和方言學(xué)等領(lǐng)域，需要度量字符串之間的相似性．因?yàn)樽址L度不固定，無法用前述的近鄰性測度去衡量字符串之間的差異或相似性．這種情況下，可以使用動(dòng)態(tài)近鄰性測度，典型的描述方法是采用Levenshtein距離（編輯距離）．

在文本信息檢索、剽竊抄襲檢測等領(lǐng)域文本近鄰性的度量是基礎(chǔ)性問題［29］，而編輯距離是自然語言文本近鄰性度量中的重要方法，文本字符串的距離越大，說明它們的差異越大．編輯距離通常用于句子的快速模糊匹配領(lǐng)域，但其規(guī)定的編輯操作不夠靈活，也沒有考慮語句的同義替換．編輯距離的計(jì)算需要通過特定的算法實(shí)現(xiàn)［6，8，30］，動(dòng)態(tài)規(guī)劃是常采用的方法．基于編輯距離可以定義字符串之間的Levenstein相似度

3．4 半度量和超度量

定理3和定理4表明距離函數(shù)的特定函數(shù)變換仍然是距離函數(shù)，但并不是所有形式的函數(shù)變換都可以得到新的度量，即使這種變換會(huì)帶來應(yīng)用中的好處．例如：歐氏距離是距離函數(shù)，然而歐氏距離的平方卻不是．半度量不滿足三角不等式，因此兩點(diǎn)之間直線半度量距離不一定最短（見圖1）．因此，半度量距離（準(zhǔn)確地說是“相異性半度量”）在反映相異性程度的意義上有使用價(jià)值（距離越大差異越大），但距離之間的運(yùn)算結(jié)果不一定會(huì)提供有意義的結(jié)果（半度量距離的部分之和并不等于整體）．

平方歐氏距離dsEqcru（x，y）＝ （x－y）T（x－y）就是1個(gè)半度量距離．該距離可提供兩點(diǎn)間空間距離的長短大小的信息，因不必進(jìn)行開方運(yùn)算可降低計(jì)算復(fù)雜度．使用中可以通過比較平方歐氏距離來判定2個(gè)長度的大小，然而不能通過2個(gè)平方歐氏距離之和計(jì)算2個(gè)線段的長度之和．

基于合并的層次聚類中如果把合并2個(gè)模式所需要的最短步數(shù)定義為這2個(gè)模式之間的距離，可得到超距離度量．因?yàn)轭愔g的距離的排序能夠得到嚴(yán)格保持，所以基于超度量的聚類準(zhǔn)則不易導(dǎo)致局部最?。?］．

圖1 3個(gè)向量之差的歐氏范數(shù)的關(guān)系

3．5 模糊相似性測度

考慮實(shí)向量x，y，它們的分量xk，yk∈ ［0，1］（i＝1，2，…，n），這些分量的值表示擁有第k個(gè)屬性的可能程度．如果x擁有（或不擁有）第k個(gè)屬性的可能性越大，則xk接近于1（或0）；如果xk接近于1/2，則x是否擁有第k個(gè)屬性的不確定性最大．這種向量稱為模糊向量，其分量是模糊邏輯中的隸屬度［5］．2個(gè)實(shí)值變量xk，yk∈［0，1］的模糊相似性測度可定義為sFuz（xk，yk）＝max［min（1－xk，1－yk），min（xk，yk）］，該測度值取值于［0，1］．基于變量之間的相似性測度，可以定義2個(gè)向量x，y之間的通用相似性測度［7該測度值取值于［0，n1/q］，若2個(gè)向量所有對應(yīng)維分量值中1個(gè)為0（1）時(shí)另1個(gè)為1（0），即2個(gè)向量的屬性組清晰而相斥，則該函數(shù)值為0；當(dāng)2個(gè)向量所有對應(yīng)維分量值彼此相等且皆為0或1，即屬性組清晰而一致，則該函數(shù)值為n1/q．同一向量間的相似性測度值滿足的每個(gè)分量為1/2時(shí)達(dá)到最小值，x的每個(gè)分量為0或1時(shí)達(dá)到最大值．由此可知，該函數(shù)不滿足測度定義中的自反性條件，因此嚴(yán)格來說不是測度．

從上述定義可以得出如下結(jié)論：①模糊向量是模糊概念的一種表示，向量間的相似程度不僅取決于相互間的相近程度，同時(shí)還取決于向量表示概念的清晰程度，即使是相同的向量，如果不是對概念的清晰表示，相似程度不會(huì)達(dá)到最大；②當(dāng)2個(gè)向量都是對概念的清晰表示時(shí)，二者之間的相似程度可以達(dá)到0（最小）或1（最大）；③同一向量間的模糊相似性測度不會(huì)低于最大值的1/2，即向量與自身相似的程度至少要達(dá)到50%．

3．6 相似性融合

如何將相似性進(jìn)行有效融合是相似性研究面臨的重要難題［4］．當(dāng)2個(gè)樣例同時(shí)具有連續(xù)屬性和離散屬性，甚至某些屬性缺失時(shí)，需要將2個(gè)不同近鄰性計(jì)算融合，常用方法是Gower模型［31］：sGow（i，j）其中sk（i，j）是第i個(gè)樣本和第j個(gè)樣本在第k個(gè)屬性上的相似性；wijk是屬性權(quán)值，通常的取法是當(dāng)?shù)趉個(gè)屬性缺失時(shí)為0，否則為1．

4 近鄰性與屬性

丑小鴨定律說明，世界上所有事物之間的近鄰性都是一樣的，丑小鴨與天鵝之間的差別與2只天鵝之間的差別一樣大［32］．因此，不存在“純客觀”的分類準(zhǔn)則，人們進(jìn)行分類所依據(jù)的一切準(zhǔn)則都是主觀的，而選擇什么準(zhǔn)則進(jìn)行分類則純屬主觀評價(jià)問題，是一個(gè)涉及到價(jià)值觀的問題．分類準(zhǔn)則的不同源于分類目的的不同，因而選擇特征時(shí)所持的價(jià)值觀也不同［33］．而分類準(zhǔn)則直接依賴于近鄰性的度量方法，這意味著屬性選擇的不同，或者對不同屬性所賦予的重要性不同，近鄰性度量的結(jié)果也會(huì)不同．例如，以體長為特征時(shí)馬和牛比起馬和小汽車更相近，但以奔跑速度為特征時(shí)馬和小汽車更相近．

在許多模式識別問題中，特征向量的各分量常常代表不同的物理量（如顏色和長度），不具有可比性．“如何處理各分量代表不同物理意義的向量”，這一問題沒有可通用的方法來解決．在實(shí)踐中，選擇1個(gè)相似函數(shù)或?qū)?shù)據(jù)進(jìn)行某種規(guī)格化，就意味著設(shè)計(jì)者引入了額外的信息用來賦予這種操作以明確的物理意義［9］．

對數(shù)據(jù)進(jìn)行規(guī)格化處理是使數(shù)據(jù)處理對坐標(biāo)系變換具有不變性的一種方法．這種方法的出發(fā)點(diǎn)是防止某些特征僅僅因?yàn)槠鋽?shù)值過大而主導(dǎo)距離的度量．然而，如果數(shù)據(jù)的波動(dòng)是因?yàn)榇嬖诙鄠€(gè)類，那么這種規(guī)格化反而會(huì)導(dǎo)致不真實(shí)的數(shù)據(jù)分布結(jié)構(gòu)［9］．因此，對問題本身的深入分析總是模式識別的首要任務(wù)和解決問題的根本基礎(chǔ)．

5 結(jié)論

模式識別中典型的和常用的基本近鄰性測度及其應(yīng)用見表2．由于篇幅所限，本文不可能介紹全部近鄰性測度函數(shù)，而有些未涉及到的函數(shù)也是很重要的，如2個(gè)概率分布P（x）和Q（x）之間的差異性測度——Kullback－Leibler距離（相對熵，信息偏差該函數(shù)在信息論中具有重要地位［17］，同時(shí)也應(yīng)用于說話人檢索等領(lǐng)域［34］．另外，在聚類分析中，為了把1個(gè)模式對象歸類為某一類別以及為了合并最相似的2個(gè)類，需要計(jì)算模式對象與類別（模式對象的集合）之間的近鄰性和2個(gè)集合之間的近鄰性測度．集合之間的近鄰性測度問題還出現(xiàn)在諸如圖像相似性的計(jì)算等過程中［7，15］，其中典型的有Hausdorff距離．

表2 近鄰性測度與應(yīng)用

本文所介紹的相似性測度都不是相似性度量，而且關(guān)于相似度（similarity）在一些文獻(xiàn)中并未要求倒三角不等式．大多數(shù)情況下，相似性的描述是通過相似系數(shù)（similarity coefficient）來實(shí)現(xiàn)的［35］，而相似系數(shù)sij定義的核心是［36］∶－1≤sij≤1，sij≤sii＝1，sij＝sji．關(guān)于距離和相似系數(shù)的完整的討論與專門應(yīng)用可參見文獻(xiàn)［28］．

與相似性測度相比，距離函數(shù)更注重解釋對象之間的差異；從描述對象的屬性角度來說，距離函數(shù)能更有效地表征2個(gè)對象共同缺少的屬性．對于連續(xù)變量，迄今歐氏距離仍為應(yīng)用最廣泛的1種方法．然而，近鄰性測度函數(shù)并不是脫離人的主觀世界而存在的客體，其構(gòu)造形式隱含了人們解決特定問題的目的性，某一測度函數(shù)僅適應(yīng)于解決特定的1類問題．如何利用分類信息或者類別的其他先驗(yàn)信息來研究近鄰性是有監(jiān)督的近鄰性研究．通過訓(xùn)練數(shù)據(jù)集學(xué)習(xí)1個(gè)能夠很好地反映樣本空間特性的距離函數(shù)作為目標(biāo)的機(jī)器學(xué)習(xí)方法稱為度量學(xué)習(xí)［37］．

在近鄰性研究領(lǐng)域當(dāng)前人們關(guān)注的主要問題為［4］：①如何將先驗(yàn)知識引入到相似性計(jì)算中；②如何構(gòu)建完善的相似性融合模型；③如何選擇相似性模型中的參數(shù)．

模式識別的研究對象是客觀的，而認(rèn)識客觀對象及其存在與演化方式是人的事情，近鄰性的計(jì)算方法是人們對客觀世界的認(rèn)識過程，與認(rèn)識問題與解決問題的目的性緊密相關(guān)．相異/相似性作為主體對客體的1種認(rèn)定手段，始終要在特定目標(biāo)約束下揭示客體及其存在與演變的真實(shí)規(guī)律，模式本身的特性和對它的先驗(yàn)知識必須體現(xiàn)在近鄰性測度中．

［1］ Cha S H．Comprehensive survey on distance/similarity measure between probability density functions［J］．International Journal of Mathematical Models and Methoeds in Applied Sciences，2007，1（4）：300－307．

［2］ 魏宏森，曾國屏．系統(tǒng)論：系統(tǒng)科學(xué)哲學(xué)［M］．北京：清華大學(xué)出版社，1995：276．

［3］ 史忠植．智能科學(xué)［M］．北京：清華大學(xué)出版社，2006：315．

［4］ 于劍．概念、相似性與聚類分析［C］//周志華，楊強(qiáng)．機(jī)器學(xué)習(xí)及其應(yīng)用2011［M］．北京：清華大學(xué)出版社，2011：136－146．

［5］ Zadeh L A．Fuzzy sets［J］．Information and Control，1965，8（3）：338－353．

［6］ Pedrycz W．Clustering and fuzzy clustering［C］//Pedrycz W．Knowledge－based clustering：from data to information granules［M］．John Wiley ＆Sons，2005．

［7］ Theodoridis S，Koutroumbas K．Pattern recognition［M］．4th ed．Elsevier，2009：602－625．

［8］ Xu R，Wunsch II D C．Clustering［M］．John Wiley ＆Sons，2009：15－30．

［9］ Duda R O．Pattern classification［M］．2nd ed．John Wiley ＆Sons，2001．

［10］ de Amorim R C，Mirkin B．Minkowski metric，feature weighting and anomalous cluster initializing in K－Means clustering［J］．Pattern Recognition，2012，45（3）：1061－1075．

［11］ Gonzalez R C，Woods R E．Digital image processing［M］．2nd ed．USA：Prentice－Hall，2002．

［12］ Chaudhuri D，Murthy C A，Chaudhuri B B．A modified metric to compute distance［J］．Pattern Recognition，1992，25（7）：667－677．

［13］ 張賢達(dá)．矩陣分析與應(yīng)用［M］．北京：清華大學(xué)出版社，2004：225－227．

［14］ Xiang S，Nie F，Zhang C S．Learning a mahalanobis distance metric for data clustering a classification［J］．Pattern Recognition，2008，41（12）：3600－3612．

［15］ Wang L，Zhang Y，F(xiàn)eng J．On the euclidean eistance of images［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（8）：1334－1339．

［16］ Kokare M，Biswas P K，Chatterji B N．Texture image retrieval using rotated wavelet filters［J］．Pattern Recognition Letters，2007，28（10）：1240－1249．

［17］ Cover T M，Thomas J A．Elements of information theory［M］．John Wiley ＆Sons，1991：209－212．

［18］ 李彬，汪天飛，劉才銘，等．基于相對Hamming距離的Web聚類算法［J］．計(jì)算機(jī)應(yīng)用，2011，31（5）：1387－1390．

［19］ 張煥炯，王國勝，鐘義信．基于漢明距離的文本相似度計(jì)算［J］．計(jì)算機(jī)工程與應(yīng)用，2001，37（19）：21－22．

［20］ Lipkus A H．A proof of the triangle inequality for the tanimoto distance［J］．Journal of Mathematical Chemistry，1999，26（1－3）：263－265．

［21］ Tanimoto T．An elementary mathematical theory of classification and prediction［M］．New York：International Business Machines Co．，1958．

［22］ Jarvis R A，Patrick E A．Clustering using a similarity measure based on shared near neighbors［J］．IEEE Transactions on Computers，1973，C－22（11）：1025－1034．

［23］ Ricardo B Y，Berthier R N．Modern information retrieval［M］．New York：ACM Press，1999：26－29．

［24］ Tan P N，Steinbach M，Kumar V．Introduction to data mining［M］．Addison－Wesley，2005：500．

［25］ Eisen M B，Spellman P T，Brown P O，et al．Cluster analysis and display of genome－wide expression patterns［C］．Proc Natl Acad Sci USA，1998，95：14863－14868．

［26］ 湯燕彬，許榕生．基于Tanimoto系數(shù)的JPEG碎片數(shù)據(jù)識別方法［J］．計(jì)算機(jī)應(yīng)用與軟件，2011，28（9）：80－81；92．

［27］ Fu L，Yang M，Braylan R，et al．Real－time adaptive clustering of flow cytometric data［J］．Pattern Recognition，

1993，26（2）：365－373．

［28］ Deza E，Deza M M．Dictionary of distances［M］．Elsevier，2006．

［29］ 鄧愛萍，徐國梁，肖奔．程序源代碼剽竊檢測串匹配算法的研究［J］．計(jì)算機(jī)工程與科學(xué)，2008，30（3）：62－68．

［30］ 鄒旭楷．漢字/字符串編輯距離和編輯路徑的有效求解技術(shù)［J］．計(jì)算機(jī)研究與發(fā)展，1996，33（8）：574－580．

［31］ Gower J C．A general coefficient of similarity and some of its properties［J］．Biometrics，1971，27（4）：857－871．

［32］ Watanabe S．Knowing and guessing：a quantitative study of inference and information［M］．New York：Wiley，1969：376－377．

［33］ 趙南元．認(rèn)知科學(xué)揭秘：認(rèn)識科學(xué)與廣義進(jìn)化論［M］．2版．北京：清華大學(xué)出版社，2002：8－9．

［34］ 韓紀(jì)慶，鄭鐵然，鄭貴濱．音頻檢索理論與技術(shù)［M］．北京：科學(xué)出版社，2011：194－195．

［35］ Sesli1 M，Yegenoglu E D．Comparison of similarity coefficients used for cluster analysis based on RAPD markers in wild olives［J］．Genetics and Molecular Research，2010，9（4）：2248－2253．

［36］ Tomas M S，Alsina C，Rubio－Martinez J．Pseudometrics from three－positive semidefinite similarities［J］．Fuzzy Sets and Systems，2006，157（17）：2347－2355．

［37］ Yang L，Jin R．Distance metric learning：a comprehensive survey［EB/OL］．Michigan：Michigan State University，2006．http：//www．cse．msu．edu/～rongjin/semisupervised/dist－metric－survey．pdf．

Proximity measures in pattern recognition

CUI Rong－yi
（Intelligent Information Processing Lab．，Dept．of Computer Science ＆Technology，College of Engineering，Yanbian University，Yanji 133002，China）

The quantitative description of dissimilarity and similarity between patterns is a basic problem in pattern recognition．On the basis of exposition and discussion on the essence and mathematical definition of proximity，the typical proximity measures and their applications are summarized．Furthermore，the relation between proximity and attributes of pattern，and the important roles of the features of patterns and a priori knowledge are pointed out．

pattern recognition；measure；metric；proximity

TP391．4

A

1004－4353（2012）03－0236－11

20120712

崔榮一（1962—），男，博士，教授，研究方向?yàn)槟Ｊ阶R別、智能計(jì)算．