機(jī)器學(xué)習(xí)相似量

目錄相似性度量主要相似度度量算法度量學(xué)習(xí)部分算法實(shí)踐機(jī)器學(xué)習(xí)相似度概述流形學(xué)習(xí)當(dāng)前第1頁\共有36頁\編于星期五\2點(diǎn)相似性度量機(jī)器學(xué)習(xí)相似度概述當(dāng)前第2頁\共有36頁\編于星期五\2點(diǎn)相似度度量

機(jī)器學(xué)習(xí)的目的就是讓機(jī)器具有類似于人類的學(xué)習(xí)、認(rèn)識、理解事物的能力。計(jì)算機(jī)對大量的數(shù)據(jù)記錄進(jìn)行歸納和總結(jié)，發(fā)現(xiàn)數(shù)據(jù)中潛在的規(guī)律，給人們的生活帶來便利。

對數(shù)據(jù)記錄和總結(jié)中常用到聚類算法。聚類算法就是按照對象間的相似性進(jìn)行分組，因此如何描述對象間相似性是聚類的重要問題。相似度度量機(jī)器學(xué)習(xí)相似度概述當(dāng)前第3頁\共有36頁\編于星期五\2點(diǎn)相似度度量

刻畫數(shù)據(jù)樣本點(diǎn)之間的親疏遠(yuǎn)近程度主要有以下兩類函數(shù)：

（1）相似系數(shù)函數(shù)：兩個(gè)樣本點(diǎn)愈相似，則相似系數(shù)值愈接近1；樣本點(diǎn)愈不相似，則相似系數(shù)值愈接近0。這樣就可以使用相似系數(shù)值來刻畫樣本點(diǎn)性質(zhì)的相似性。

（2）距離函數(shù)：可以把每個(gè)樣本點(diǎn)看作高維空間中的一個(gè)點(diǎn)，進(jìn)而使用某種距離來表示樣本點(diǎn)之間的相似性，距離較近的樣本點(diǎn)性質(zhì)較相似，距離較遠(yuǎn)的樣本點(diǎn)則差異較大。相似度度量機(jī)器學(xué)習(xí)相似度概述當(dāng)前第4頁\共有36頁\編于星期五\2點(diǎn)主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第5頁\共有36頁\編于星期五\2點(diǎn)主要相似度算法歐氏距離標(biāo)準(zhǔn)化歐氏距離閔可夫斯基距離曼哈頓距離切比雪夫距離馬氏距離漢明距離夾角余弦杰卡德距離&杰卡德相似系數(shù)主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第6頁\共有36頁\編于星期五\2點(diǎn)歐式距離歐氏距離（Euclideandistance）也稱歐幾里得距離，它是一個(gè)通常采用的距離定義，它是在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離。也可以用表示成向量運(yùn)算的形式：主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第7頁\共有36頁\編于星期五\2點(diǎn)標(biāo)準(zhǔn)歐式距離由于特征向量的各分量的量綱不一致(比如說身高和體重)，通常需要先對各分量進(jìn)行標(biāo)準(zhǔn)化，使其與單位無關(guān)。假設(shè)樣本集X的均值(mean)為m，標(biāo)準(zhǔn)差(standarddeviation)為s，那么X的“標(biāo)準(zhǔn)化變量”表示為：（160cm，60kg）（170cm，50kg）標(biāo)準(zhǔn)化后的值=

(標(biāo)準(zhǔn)化前的值

－分量的均值)/分量的標(biāo)準(zhǔn)差主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第8頁\共有36頁\編于星期五\2點(diǎn)加權(quán)歐式距離加權(quán)歐式距離：在距離計(jì)算時(shí)，考慮各項(xiàng)具有不同的權(quán)重。公式如下：主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第9頁\共有36頁\編于星期五\2點(diǎn)曼哈頓距離

曼哈頓距離，也稱為城市街區(qū)距離，是一種使用在幾何度量空間的幾何學(xué)用語，用以標(biāo)明兩個(gè)點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距總和：X(2,4),Y(1,6)dist(X,Y)=|2-1|+|4-6|=3主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第10頁\共有36頁\編于星期五\2點(diǎn)閔可夫斯基距離

閔可夫斯基距離（閔氏距離）不是一種距離，而是一組距離的定義。閔氏距離是歐氏距離的推廣，是對多個(gè)距離度量公式的概括性的表述。公式如下：其中p是一個(gè)變參數(shù)。當(dāng)p=1時(shí)，就是曼哈頓距離；當(dāng)p=2時(shí)，就是歐氏距離；當(dāng)p→∞時(shí)，就是切比雪夫距離。根據(jù)變參數(shù)的不同，閔氏距離可以表示一類的距離主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第11頁\共有36頁\編于星期五\2點(diǎn)切比雪夫距離

切比雪夫距離是由一致范數(shù)（或稱為上確界范數(shù)）所衍生的度量，也是超凸度量的一種。在數(shù)學(xué)中，切比雪夫距離(L∞度量)是向量空間中的一種度量，二個(gè)點(diǎn)之間的距離定義是其各坐標(biāo)數(shù)值差的最大值。X(2,4),Y(1,6)dist(X,Y)=max{|2-1|,|4-6|}=2主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第12頁\共有36頁\編于星期五\2點(diǎn)馬氏距離

表示數(shù)據(jù)的協(xié)方差距離。它是一種有效的計(jì)算兩個(gè)未知樣本集的相似度的方法。與歐式距離不同的是它考慮到各種特性之間的聯(lián)系（例如：一條關(guān)于身高的信息會帶來一條關(guān)于體重的信息，因?yàn)閮烧呤怯嘘P(guān)聯(lián)的）并且是尺度無關(guān)的)，即獨(dú)立于測量尺度。C為X,Y的協(xié)方差矩陣，如果協(xié)方差矩陣為單位矩陣,那么馬氏距離就簡化為歐式距離,如果協(xié)方差矩陣為對角陣,則其也可稱為正規(guī)化的歐氏距離。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第13頁\共有36頁\編于星期五\2點(diǎn)漢明距離

兩個(gè)等長字符串s1與s2之間的漢明距離定義為將其中一個(gè)變?yōu)榱硗庖粋€(gè)所需要作的最小替換次數(shù)。例如字符串“1111”與“1001”之間的漢明距離為2。漢明距離就是表示X,Y取值不同的分量數(shù)目。只適用分量只取-1或1的情況。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第14頁\共有36頁\編于星期五\2點(diǎn)杰卡德相似系數(shù)&杰卡德距離

卡德距離：是與杰卡德相似系數(shù)相反的概念，杰卡德距離用兩個(gè)集合中不同元素占所有元素的比例來衡量兩個(gè)集合的區(qū)分度。杰卡德距離可用如下公式表示：杰卡德相似系數(shù)：兩個(gè)集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個(gè)集合的杰卡德相似系數(shù)，用符號J(A,B)表示。杰卡德相似系數(shù)是衡量兩個(gè)集合的相似度一種指標(biāo)。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第15頁\共有36頁\編于星期五\2點(diǎn)杰卡德相似系數(shù)&杰卡德距離例如，A（0,1,1,0）和B（1,0,1,1）。我們將樣本看成一個(gè)集合，1表示集合包含該元素，0表示集合不包含該元素。p：樣本A與B都是1的維度的個(gè)數(shù)q：樣本A是1而B是0的維度的個(gè)數(shù)r：樣本A是0而B是1的維度的個(gè)數(shù)s：樣本A與B都是0的維度的個(gè)數(shù)那么樣本A與B的杰卡德相似系數(shù)可以表示為：此處分母之所以不加s的原因在于：對于杰卡德相似系數(shù)或杰卡德距離來說，它處理的都是非對稱二元變量。非對稱的意思是指狀態(tài)的兩個(gè)輸出不是同等重要的。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第16頁\共有36頁\編于星期五\2點(diǎn)余弦相似度

余弦相似度用向量空間中兩個(gè)向量夾角的余弦值作為衡量兩個(gè)個(gè)體間差異的大小。相比距離度量，余弦相似度更加注重兩個(gè)向量在方向上的差異，而非距離或長度上。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第17頁\共有36頁\編于星期五\2點(diǎn)調(diào)整余弦相似度

余弦相似度更多的是從方向上區(qū)分差異，而對絕對的數(shù)值不敏感，因此沒法衡量每個(gè)維度上數(shù)值的差異。需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個(gè)均值。用戶對內(nèi)容評分，按5分制，X和Y兩個(gè)用戶對兩個(gè)內(nèi)容的評分分別為（1,2）和（4,5），使用余弦相似度得到的結(jié)果是0.98，兩者極為相似。但從評分上看X似乎不喜歡兩個(gè)這個(gè)內(nèi)容，而Y則比較喜歡。比如X和Y的評分均值都是3，那么調(diào)整后為(-2,-1)和(1,2)，再用余弦相似度計(jì)算，得到-0.8，相似度為負(fù)值并且差異不小，但顯然更加符合現(xiàn)實(shí)。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第18頁\共有36頁\編于星期五\2點(diǎn)皮爾森相似度|調(diào)整余弦相似度|<=|皮爾森相似度|主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第19頁\共有36頁\編于星期五\2點(diǎn)斯皮爾曼相關(guān)

斯皮爾曼相關(guān)性可以理解為是排列后（Rank）用戶喜好值之間的Pearson相關(guān)度。皮爾曼相關(guān)度的計(jì)算舍棄了一些重要信息，即真實(shí)的評分值。但它保留了用戶喜好值的本質(zhì)特性——排序（ordering），它是建立在排序（或等級，Rank）的基礎(chǔ)上計(jì)算的。主要相似度算法機(jī)器學(xué)習(xí)相似度概述當(dāng)前第20頁\共有36頁\編于星期五\2點(diǎn)度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第21頁\共有36頁\編于星期五\2點(diǎn)度量學(xué)習(xí)

現(xiàn)有的大部分算法對圖像進(jìn)行特征提取后化為向量的表達(dá)形式，其本質(zhì)是把每一幅用于訓(xùn)練的圖像通過某種映射到歐氏空間的一個(gè)點(diǎn)，并利用歐氏空間的良好性質(zhì)在其中進(jìn)行學(xué)習(xí)器的訓(xùn)練。但定義圖像特征之間的歐氏距離未必能很好反映出樣本之間的相似。通過訓(xùn)練樣本尋找一種能夠合理描述當(dāng)前樣本相似度的距離度量，能夠大大提高學(xué)習(xí)器的性能。

度量學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)重要分支，通過有標(biāo)記樣本或結(jié)合未標(biāo)記樣本，尋找一個(gè)能夠在給定指標(biāo)下最恰當(dāng)刻畫樣本相似度的距離矩陣或距離函數(shù)。

度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第22頁\共有36頁\編于星期五\2點(diǎn)度量學(xué)習(xí)度量學(xué)習(xí)包括監(jiān)督度量學(xué)習(xí)和半監(jiān)督度量學(xué)習(xí)。

監(jiān)督度量學(xué)習(xí)主要是利用標(biāo)注樣本學(xué)習(xí)一個(gè)反映樣本語義關(guān)系的度量函數(shù)，使語義上相近的樣本之間距離較近，反之則較遠(yuǎn)。

半監(jiān)督度量學(xué)習(xí)則是利用了標(biāo)注樣本，也利用了未標(biāo)注樣本。

度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第23頁\共有36頁\編于星期五\2點(diǎn)監(jiān)督度量學(xué)習(xí)

利用攜帶標(biāo)注信息的訓(xùn)練數(shù)據(jù)進(jìn)行距離度量學(xué)習(xí)，能更好的降低“語義鴻溝”的影響。

監(jiān)督的距離度量學(xué)習(xí)的主要思想是，利用標(biāo)注數(shù)據(jù)學(xué)習(xí)一個(gè)度量矩陣，對樣本進(jìn)行映射變換，使得在變換后的度量空間中，同類樣本之間的距離變小，異類樣本之間的距離變大，或使得相似的樣本距離變小，不相似的樣本距離變大?？梢酝ㄟ^設(shè)定不同的標(biāo)注信息，使得距離度量結(jié)果符合不同的相似度評判標(biāo)準(zhǔn)，因此度量方式的選擇更加自由。度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第24頁\共有36頁\編于星期五\2點(diǎn)監(jiān)督度量學(xué)習(xí)（1）基于凸規(guī)劃的全局距離度量學(xué)習(xí)方法：該方法學(xué)習(xí)一個(gè)度量矩陣，使非相似樣本間距離的平方和最大，同時(shí)使相似樣本間距離的平方和小于一定值。（2）近鄰成分分析：以概率的方式定義點(diǎn)的軟鄰域，然后通過最大化訓(xùn)練樣本的留一法分類錯(cuò)誤率學(xué)習(xí)距離度量矩陣。該方法在訓(xùn)練度量矩陣的同時(shí)，保持了相鄰數(shù)據(jù)點(diǎn)之間關(guān)系，但不一定能全局最優(yōu)。（3）區(qū)分性成分分析：通過學(xué)習(xí)一種最優(yōu)的數(shù)據(jù)轉(zhuǎn)換使不同“團(tuán)簇”間的方差和最大，所有“團(tuán)簇”內(nèi)的方差和最小。度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述(1)E.P.Xing,A.Y.Ng,M.I.Jordan,S.Russell．DistanceMetricLearningwithApplicationtoClusteringwithSide-information[J].AdvancesinNeuralInformationProcessingSystems,2002,15:505-512.(2)J.Goldberger,S.Roweis,G.Hinton,R.Salakhutdinov．Neighbourhoodcomponentsanalysis[A].InAdvancesinNeuralInformationProcessingSystems[C].Washington,MITPress,2004:13-18.(3)S.C.H.Hoi,W.Liu,M.R.Lyu,W.Y.Ma．Learningdistancemetricswithcontextualconstraintsforimageretrieval[A].Proceedingsofthe2006IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition[C].Vienna,Austria,2006:2072-2078.

當(dāng)前第25頁\共有36頁\編于星期五\2點(diǎn)監(jiān)督度量學(xué)習(xí)（4）基于信息論的距離度量學(xué)習(xí)方法：在滿足約束信息的同時(shí)，使學(xué)習(xí)到的度量矩陣M和根據(jù)某種先驗(yàn)知識給出的度量矩陣M0之間的KL散度最小。（5）最大邊界近鄰分類：分類方法是將樣本的K最近鄰保持在同一類別中，同時(shí)使異類樣本之間的邊界最大。其損失函數(shù)的第一項(xiàng)是懲罰輸入樣本和其最近鄰間的距離，第二項(xiàng)是懲罰異類樣本間較小的距離。度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述(4)J.V.Jason.Davis,B.Kulis,P.Jain,etal．Information-theoreticmetriclearning[A].InProceedingsoftheInternationalConferenceonMachineLearning[C].Florida,USA,2007:209-216.(5)K.Q.Weinberger,J.Blitzer,L.K.Saul．Distancemetriclearningforlargemarginnearestneighborclassi?cation[J].JournalofMachineLearningResearch,2009(10):207-244.(6)呂秀清，圖像度量學(xué)習(xí)技術(shù)[D]，2013當(dāng)前第26頁\共有36頁\編于星期五\2點(diǎn)半監(jiān)督度量學(xué)習(xí)

監(jiān)督度量學(xué)習(xí)只利用了有限的標(biāo)注數(shù)據(jù)，且常會遇到訓(xùn)練數(shù)據(jù)不足的問題，而實(shí)際中卻有大量未標(biāo)注的數(shù)據(jù)存在。半監(jiān)督度量學(xué)習(xí)通過對未標(biāo)注數(shù)據(jù)加以利用，以獲得更準(zhǔn)確的模型。（1）07年，一種基于核的半監(jiān)督距離度量學(xué)習(xí)方法（2）09年，通過保留類似于LLE局部線性嵌嵌入）的局部關(guān)系學(xué)習(xí)距離度量（3）Laplacian正則化距離度量學(xué)習(xí)（LRML），將樣本點(diǎn)的近鄰看作相似點(diǎn)，聯(lián)合已有標(biāo)注數(shù)據(jù)學(xué)習(xí)距離度量。度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述(1)D.Yeung,H.Chang．Akernelapproachforsemi-supervisedmetriclearning[J].IEEETransactionsonNeuralNet-works,2007,18(1):141–149.(2)M.Baghshah,S.Shouraki．Semi-supervisedmetriclearningusingpairwiseconstraints[A].Proceedingsofthe21stinternationaljontconferenceonArtificalintelligence[C].Pasadena,California,US,2009:1217–1222.(3)S.C.H.Hoil,W.Liu,S.F.Chang．Semi-superviseddistancemetriclearningforcollaborativeimageretrievalandclustering[J].ACMTransactionsonMultimediaComputing,CommunicationsandApplications,2010,6(3):1-18.

當(dāng)前第27頁\共有36頁\編于星期五\2點(diǎn)度量學(xué)習(xí)

近年來，距離度量學(xué)習(xí)已成為智能信息處理方面的一個(gè)研究熱點(diǎn)，研究表明，距離度量學(xué)習(xí)能夠大大提升了圖像分類、圖像匹配、及圖像檢索等工作的性能。度量學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第28頁\共有36頁\編于星期五\2點(diǎn)流形學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第29頁\共有36頁\編于星期五\2點(diǎn)流形學(xué)習(xí)

作為機(jī)器學(xué)習(xí)研究的熱點(diǎn)問題之一,流形學(xué)習(xí)是要從高維數(shù)據(jù)集中發(fā)現(xiàn)內(nèi)在的低維流形,并基于低維流形來實(shí)現(xiàn)隨后的各種機(jī)器學(xué)習(xí)任務(wù),如模式識別,聚類分析等。

與歐氏空間不同,流形學(xué)習(xí)主要處理的是非歐空間里的模式識別和維數(shù)約簡等問題。

從宇宙空間看地球,如果不借助外界力量的話,我們只能局限于地球的表面活動(dòng),而且地球上兩點(diǎn)的距離并不單純是它們對應(yīng)的直線的跟離,而是它們的測地線即離"可以證明,我們生活的地球是一個(gè)嵌入在3維歐式空間中的維流形,也就是說,地球表面點(diǎn)的位置可由兩個(gè)變量來控制。

流形學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第30頁\共有36頁\編于星期五\2點(diǎn)流形學(xué)習(xí)

從定義我們可以看出,流形就是局部歐式的拓?fù)淇臻g,歐式空間的性質(zhì)只在鄰域內(nèi)有效。值得指出的是,當(dāng)鄰域定義為整個(gè)歐氏空間時(shí),歐氏空間本身也可以視為流形。所以，流形學(xué)習(xí)并非是一種特殊學(xué)習(xí)方法，而是基于歐氏度量學(xué)習(xí)的一種推廣,具有更強(qiáng)的一般性。流形學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第31頁\共有36頁\編于星期五\2點(diǎn)流形學(xué)習(xí)

從定義我們可以看出,流形就是局部歐式的拓?fù)淇臻g,歐式空間的性質(zhì)只在鄰域內(nèi)有效。值得指出的是,當(dāng)鄰域定義為整個(gè)歐氏空間時(shí),歐氏空間本身也可以視為流形。所以，流形學(xué)習(xí)并非是一種特殊學(xué)習(xí)方法，而是基于歐氏度量學(xué)習(xí)的一種推廣,具有更強(qiáng)的一般性。流形學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第32頁\共有36頁\編于星期五\2點(diǎn)流形學(xué)習(xí)

我們假設(shè)這些觀測數(shù)據(jù)是由一些隱變量Y通過一個(gè)映射f：Y->X生成的,其中，于是流形學(xué)習(xí)的任務(wù)就是通過觀測數(shù)據(jù)把未知映射f和隱變量Y重建出來。由于m<n,故該問題是一個(gè)病態(tài)問題,不存在唯一解,因此研究人員提出了各種各樣的流形學(xué)習(xí)算法,它們試圖通過添加某些特定約束用以恢復(fù)流形的內(nèi)在結(jié)構(gòu)。流形學(xué)習(xí)機(jī)器學(xué)習(xí)相似度概述當(dāng)前第33頁\共有36頁\編于星期五\2點(diǎn)流形學(xué)習(xí)

總體來說,流形學(xué)習(xí)的興起來源于2000年在《科學(xué)》雜志上的兩篇關(guān)于流形學(xué)習(xí)的文章“其中一篇提出了一個(gè)叫ISOMAP的方法,該方法把傳統(tǒng)的MDS算法擴(kuò)展到非線性流形上,