1、13計算機技術(shù)Xxx xxxxxxxx目錄相似性度量主要相似度度量算法度量學習部分算法實踐機器學習機器學習相似度概述相似度概述流形學習機器學習相似度概述機器學習相似度概述相似度度量相似度度量機器學習的目的就是讓機器具有類似于人類的學習、認識、理解事物的能力。計算機對大量的數(shù)據(jù)記錄進行歸納和總結(jié)，發(fā)現(xiàn)數(shù)據(jù)中潛在的規(guī)律，給人們的生活帶來便利。對數(shù)據(jù)記錄和總結(jié)中常用到聚類算法。聚類算法就是按照對象間的相似性進行分組，因此如何描述對象間相似性是聚類的重要問題。相似度度量相似度度量機器學習相似度概述機器學習相似度概述相似度度量相似度度量刻畫數(shù)據(jù)樣本點之間的親疏遠近程度主要有以下兩類函數(shù)：（1）相似系數(shù)函

2、數(shù)：兩個樣本點愈相似，則相似系數(shù)值愈接近1；樣本點愈不相似，則相似系數(shù)值愈接近0。這樣就可以使用相似系數(shù)值來刻畫樣本點性質(zhì)的相似性。 （2）距離函數(shù)：可以把每個樣本點看作高維空間中的一個點，進而使用某種距離來表示樣本點之間的相似性，距離較近的樣本點性質(zhì)較相似，距離較遠的樣本點則差異較大。相似度度量相似度度量機器學習相似度概述機器學習相似度概述機器學習相似度概述機器學習相似度概述主要相似度算法主要相似度算法歐氏距離 標準化歐氏距離閔可夫斯基距離 曼哈頓距離切比雪夫距離 馬氏距離漢明距離 夾角余弦杰卡德距離 & 杰卡德相似系數(shù)主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述

3、歐式距離歐式距離歐氏距離（ Euclidean distance）也稱歐幾里得距離，它是一個通常采用的距離定義，它是在m維空間中兩個點之間的真實距離。也可以用表示成向量運算的形式：主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述標準歐式距離標準歐式距離由于特征向量的各分量的量綱不一致(比如說身高和體重)，通常需要先對各分量進行標準化，使其與單位無關(guān)。假設(shè)樣本集X的均值(mean)為m，標準差(standard deviation)為s，那么X的“標準化變量”表示為：（160cm，60kg）（170cm，50kg）標準化后的值 = ( 標準化前的值 分量的均值 ) /分量的標準差

4、主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述加權(quán)歐式距離加權(quán)歐式距離加權(quán)歐式距離：在距離計算時，考慮各項具有不同的權(quán)重。公式如下：主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述曼哈頓距離曼哈頓距離曼哈頓距離，也稱為城市街區(qū)距離，是一種使用在幾何度量空間的幾何學用語，用以標明兩個點在標準坐標系上的絕對軸距總和：X(2,4),Y(1,6)dist(X,Y)=|2-1|+|4-6|=3主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述閔可夫斯基距離閔可夫斯基距離閔可夫斯基距離（閔氏距離）不是一種距離，而是一組距離的定義。閔氏距離是歐氏距離的推廣，是

5、對多個距離度量公式的概括性的表述。公式如下：其中p是一個變參數(shù)。當p=1時，就是曼哈頓距離；當p=2時，就是歐氏距離；當p時，就是切比雪夫距離。根據(jù)變參數(shù)的不同，閔氏距離可以表示一類的距離主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述切比雪夫距離切比雪夫距離切比雪夫距離是由一致范數(shù)（或稱為上確界范數(shù)）所衍生的度量，也是超凸度量的一種。在數(shù)學中，切比雪夫距離(L度量)是向量空間中的一種度量，二個點之間的距離定義是其各坐標數(shù)值差的最大值。X(2,4),Y(1,6)dist(X,Y)=max|2-1|,|4-6|=2主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述馬

6、氏距離馬氏距離表示數(shù)據(jù)的協(xié)方差距離。它是一種有效的計算兩個未知樣本集的相似度的方法。與歐式距離不同的是它考慮到各種特性之間的聯(lián)系（例如：一條關(guān)于身高的信息會帶來一條關(guān)于體重的信息，因為兩者是有關(guān)聯(lián)的）并且是尺度無關(guān)的)，即獨立于測量尺度。C為X,Y的協(xié)方差矩陣，如果協(xié)方差矩陣為單位矩陣,那么馬氏距離就簡化為歐式距離,如果協(xié)方差矩陣為對角陣,則其也可稱為正規(guī)化的歐氏距離。主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述漢明距離漢明距離兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變?yōu)榱硗庖粋€所需要作的最小替換次數(shù)。例如字符串“1111”與“1001”之間的漢明距離為2。漢

7、明距離就是表示X,Y取值不同的分量數(shù)目。只適用分量只取-1或1的情況。主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述杰卡德相似系數(shù)杰卡德相似系數(shù) & & 杰卡德距離杰卡德距離卡德距離：是與杰卡德相似系數(shù)相反的概念，杰卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區(qū)分度。杰卡德距離可用如下公式表示：杰卡德相似系數(shù)： 兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的杰卡德相似系數(shù)，用符號J(A,B)表示。杰卡德相似系數(shù)是衡量兩個集合的相似度一種指標。主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述杰卡德相似系數(shù)杰卡德

8、相似系數(shù) & & 杰卡德距離杰卡德距離例如，A（0,1,1,0）和B（1,0,1,1）。我們將樣本看成一個集合，1表示集合包含該元素，0表示集合不包含該元素。p：樣本A與B都是1的維度的個數(shù)q：樣本A是1而B是0的維度的個數(shù)r：樣本A是0而B是1的維度的個數(shù)s：樣本A與B都是0的維度的個數(shù)那么樣本A與B的杰卡德相似系數(shù)可以表示為：此處分母之所以不加s的原因在于：對于杰卡德相似系數(shù)或杰卡德距離來說，它處理的都是非對稱二元變量。非對稱的意思是指狀態(tài)的兩個輸出不是同等重要的。主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述余弦相似度余弦相似度余弦相似度用向量空間中兩個

9、向量夾角的余弦值作為衡量兩個個體間差異的大小。相比距離度量，余弦相似度更加注重兩個向量在方向上的差異，而非距離或長度上。主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述調(diào)整余弦相似度調(diào)整余弦相似度余弦相似度更多的是從方向上區(qū)分差異，而對絕對的數(shù)值不敏感，因此沒法衡量每個維度上數(shù)值的差異。需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個均值。用戶對內(nèi)容評分，按5分制，X和Y兩個用戶對兩個內(nèi)容的評分分別為（1,2）和（4,5），使用余弦相似度得到的結(jié)果是0.98，兩者極為相似。但從評分上看X似乎不喜歡兩個這個內(nèi)容，而Y則比較喜歡。比如X和Y的評分均值都是3

10、，那么調(diào)整后為(-2,-1)和(1,2)，再用余弦相似度計算，得到-0.8，相似度為負值并且差異不小，但顯然更加符合現(xiàn)實。主要相似度算法主要相似度算法機器學習相似度概述機器學習相似度概述皮爾森相似度皮爾森相似度|調(diào)整余弦相似度|X生成的,其中 ，于是流形學習的任務(wù)就是通過觀測數(shù)據(jù)把未知映射f和隱變量Y重建出來。由于mn,故該問題是一個病態(tài)問題,不存在唯一解,因此研究人員提出了各種各樣的流形學習算法,它們試圖通過添加某些特定約束用以恢復(fù)流形的內(nèi)在結(jié)構(gòu)。流形學習流形學習機器學習相似度概述機器學習相似度概述流形學習流形學習總體來說,流形學習的興起來源于2000年在科學雜志上的兩篇關(guān)于流形學習的文章“

11、其中一篇提出了一個叫ISOMAP的方法,該方法把傳統(tǒng)的MDS算法擴展到非線性流形上,通過對中心化的測地線距離矩陣進行特征值分解來保持流形上的整體拓撲結(jié)構(gòu)。而另一篇文章提出廠局部線性嵌入(Local Linear Embedding (LLE)算法,該算法假設(shè)高維數(shù)據(jù)和低維數(shù)據(jù)的局部拓撲結(jié)構(gòu)關(guān)系保持不變,即鄰域關(guān)系不變,然后刊用這種關(guān)系從高維數(shù)據(jù)重構(gòu)出低維的流形嵌入。流形學習流形學習機器學習相似度概述機器學習相似度概述PCAPCA該方法認為特征的方差越大提供的信息量越多，特征的方差越小提供的信息量越少。PCA 通過原分量的線性組合構(gòu)造方差大、含信息量多的若干主分量，從而降低數(shù)據(jù)的維數(shù)。流形學習流

12、形學習機器學習相似度概述機器學習相似度概述H. HotellingAnalys is of a complex of statistical variables into principal componentsJ. Journal ofEducational Psychology, 1933, 24: 417-441. MDSMDS其中（a）為真實數(shù)據(jù)集的流形結(jié)構(gòu)圖，（b）為從（a）隨機采樣 2000 個點后的數(shù)據(jù)分布圖，（c）、（d）和（e）為經(jīng)三次不同采樣后，采樣點經(jīng) MDS 算法降到二維空間后分布圖?？梢钥闯?，（c）圖在一定程度上保持了數(shù)據(jù)的連續(xù)性，但并沒有發(fā)現(xiàn)嵌入在數(shù)據(jù)的本質(zhì)，改變了

13、采樣點的拓撲結(jié)構(gòu)；（d）和（e）圖的效果更差，不同樣本點均發(fā)生了不同程度的重疊，嚴重改變了采樣點的結(jié)構(gòu)。流形學習流形學習機器學習相似度概述機器學習相似度概述C. K. I. WilliamsOn a connection between kernel PCA and metric multidimens ional scalingJ.Machine Learning, 2002, 46(1-3): 11-19. ISOMAPISOMAP其中（a）為真實數(shù)據(jù)集的流形結(jié)構(gòu)圖，（b）為從。流形學習流形學習機器學習相似度概述機器學習相似度概述J. B. Tenenbaum, V. D. Silva,

14、J. LangfordA global geometric framework for nonlinear dimensionalityreductionJ. Science, 2000, 290(5500): 2319-2323 流形學習流形學習 Laplacian Eigenmap(LE)就是其中的一種,該算法首先構(gòu)造一個鄰域關(guān)系圖,然后對該圖的拉普拉斯矩陣進行特征值分解來得到流形的低維表示,這樣的分解保持了數(shù)據(jù)的局部關(guān)系，注意到在LE中,我們要估計流形上的Laplacian算子。Hessian Eigenmap(HLLE) 該算法通過估計流形上的Heosian算子,然后對該算子進行特征值

15、分解來保持流形的局部拓撲性。SDE算法：為了得到一個等距嵌入，用半正定規(guī)劃的方法估計流形上的點對間的角度和距離,從而學習圖像數(shù)據(jù)中的流形。流形學習流形學習機器學習相似度概述機器學習相似度概述（1） Mikhail Belkin and parthaNiyogi。Lapacian eigenmaps and spectral techniquesFor embedding and clusteringA.In NlPS,Pages 585一591/2001(2)David L.Donoho and Carrie Grimes.Hessian eigenmaps:New locallyl inear mbedding teclulique