1. 距離的量度

1) 距離

?距離的定義是一個(gè)寬泛的概念：只要滿足非負(fù)、自反、三角不等式就可以稱之為距離。其中非負(fù)是指任意兩個(gè)相異點(diǎn)的距離為正；自反是Dis(y,x)=Dis(x,y)；三角不等式是Dis(x,z)<=Dis(x,y)+Dis(y,z)

2) 馬氏距離（閔可夫斯基距離）

?其中d是維數(shù)，p是階數(shù)，也稱為p范數(shù)。
?當(dāng)p=1時(shí)，是曼哈頓距離
?當(dāng)p=2時(shí)，是歐氏距離
?當(dāng)p→∞時(shí)，是切比雪夫距離
?當(dāng)p=0時(shí)，是海明距離

3) 歐氏距離

?兩點(diǎn)間的直線距離（一般用兩條豎線||w||代表w的2范數(shù)）代入公式：

4) 曼哈頓距離（城市街區(qū)距離）

?各坐標(biāo)數(shù)值差的和，就像汽車只能行駛在橫平豎直的街道上，代入公式：

5) 切比雪夫距離

?各坐標(biāo)數(shù)值差的最大值，當(dāng)馬氏距離的p→∞時(shí)，最終的結(jié)果取決于距離最大的維度上的距離：
Dis∞=maxj|xj-yj|
?在二維的情況下：c=max(a,b)

6) 海明距離

?L0范數(shù)并不是一個(gè)真正的范數(shù)，它主要被用來度量向量中非零元素的個(gè)數(shù)。

7) 總結(jié)

?圖片從上到下依次顯示a與b點(diǎn)的三種距離：歐氏距離（藍(lán)色），切比雪夫距離（紅色），曼哈頓距離（綠色）

2. 范數(shù)

?范數(shù)是一種強(qiáng)化了的距離概念，根據(jù)馬氏距離的公式，把x,y兩點(diǎn)間的距離看作一個(gè)向量z

?||z||p是向量z的p范數(shù)，也記作Lp范數(shù)。
?范數(shù)包括向量范數(shù)和矩陣范數(shù)，向量范數(shù)表征向量空間中向量的大小，矩陣范數(shù)表征矩陣引起變化的大小。上面我們看到的就是L0, L1, L2, L∞范數(shù)的計(jì)算方法。
?機(jī)器學(xué)習(xí)中常使用范數(shù)防止過擬合，它可以計(jì)量模型的大?。◤?fù)雜度），作為懲罰項(xiàng)加入公式，通過迭代計(jì)算，在誤差和復(fù)雜度之間制衡，如公式：

?其中x是自變量，y是結(jié)果，w是參數(shù)，通過f(x;w)預(yù)測y’，L(y,y’)求真實(shí)值與預(yù)測值的誤差，Ω是懲罰項(xiàng)，λ是懲罰項(xiàng)的系數(shù)。目標(biāo)是求誤差最小時(shí)參數(shù)w的取值。
和上一次SVM篇中講到的一樣，這也是在條件Ω下求誤差L極小值的問題，還是拉格朗日乘子法，用系數(shù)λ把兩式連在一起，變?yōu)楹唵蔚那髽O值問題。

3. KNN（K近鄰）算法

1) K近鄰

?存在一個(gè)樣本數(shù)據(jù)集合（訓(xùn)練集），并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽，輸入沒有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對應(yīng)的特征相比較，然后提取樣本集中特征最相似的前K個(gè)數(shù)據(jù)的分類標(biāo)簽。
算法參考Ｋ個(gè)距離最近的訓(xùn)練樣例，并整合多個(gè)目標(biāo)值，對于分類問題，最簡單的方法是投票法，也可以預(yù)測各個(gè)類別的概率分布，對于回歸問題，可取均值，或按距離加權(quán)等。
?簡言之，K近鄰就是根據(jù)距離實(shí)例最近的范例來判定新實(shí)例的類別或估值。
?K近鄰可處理分類和回歸問題。它需要記憶全部訓(xùn)練樣本，空間復(fù)雜度高，計(jì)算復(fù)雜度高，優(yōu)點(diǎn)是對異常值不敏感，精度高，但當(dāng)樣本少噪聲大時(shí)也會過擬合。
?對于Ｋ值的選擇，一般情況下，起初隨著Ｋ增加，分類器的性能會快速提升，但K大到某一點(diǎn)時(shí)，性能又會下降，因此需要謹(jǐn)慎選擇的Ｋ值，也有一些自動計(jì)算K值的方法，后面說。

2) 步驟

i. 計(jì)算歐氏距離
ii. 按距離排序
iii. 選取距離最小的k個(gè)點(diǎn)
iv. 確定k點(diǎn)中各分類的出現(xiàn)概率
v. 返回出現(xiàn)概率最高的分類

3) 例程

i. 功能
根據(jù)訓(xùn)練集中的四個(gè)實(shí)例，對新數(shù)據(jù)[1.2, 1.3]分類
ii. 代碼

# -*- coding: utf-8 -*-

from numpy import *
import operator

def classify(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet #求inX與訓(xùn)練集各個(gè)實(shí)例的差
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5 # 求歐式距離
    sortedDistIndicies = distances.argsort() # 取排序的索引，用于排label
    classCount={}
    for i in range(k):
        voteILabel = labels[sortedDistIndicies[i]]
        classCount[voteILabel]=classCount.get(voteILabel,0)+1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0] # 取最多的分類

group = array([[1,1.1],[1,1],[0,0],[0,0.1]]) # 訓(xùn)練集
labels = ['A','A','B','B'] #　訓(xùn)練集分類
print classify([1.2,1.3], group, labels, 3) # 對數(shù)據(jù)點(diǎn)[0,0]分類

iii. 分析
?例程中沒有調(diào)庫，直接用python實(shí)現(xiàn)了KNN，主要為了解原理，實(shí)際操作中一般使用sklearn庫中的sklearn.neighbors.NearestNeighbors類。

4. K-means聚類算法

1) K-means：

?K-means（K均值）聚類，其中k是用戶指定的要?jiǎng)?chuàng)建的簇的數(shù)目，算法以k個(gè)隨機(jī)質(zhì)心開始，計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離，每個(gè)點(diǎn)會被分配到距其最近的簇質(zhì)心，然后基于新分配到的簇的點(diǎn)更新質(zhì)心，以上過程重復(fù)數(shù)次，直到質(zhì)心不再改變。
?該算法能保證收斂到一個(gè)駐點(diǎn)，但不能保證能得到全局最優(yōu)解，受初始質(zhì)心影響大?？刹捎靡恍﹥?yōu)化方法，比如先將所有點(diǎn)作為一個(gè)簇，然后使用k-均值(k=2)進(jìn)行劃分，下一次迭代時(shí)，選擇有最大誤差的簇進(jìn)行劃分，重復(fù)到劃分為k個(gè)簇為止。
?該算法在數(shù)據(jù)多的時(shí)候，計(jì)算量大，需要采取一些優(yōu)化方法，比如一開始計(jì)算時(shí)只取部分?jǐn)?shù)據(jù)。
聚類方法常用于無監(jiān)督學(xué)習(xí)，給無標(biāo)簽的數(shù)據(jù)分類；根據(jù)質(zhì)心的原理也可實(shí)現(xiàn)有監(jiān)督學(xué)習(xí)中的分類和回歸。

2) 評價(jià)聚類

聚類常用于無監(jiān)督學(xué)習(xí)，那么如何評價(jià)聚類的好壞呢？這里使用了散度。
?散度（divergence）可用于表征空間各點(diǎn)矢量場發(fā)散的強(qiáng)弱程度，給定數(shù)據(jù)矩陣X，散度矩陣定義為：

?其中μ是均值，散度可以理解為各點(diǎn)相對于均值的發(fā)散程度。
?當(dāng)數(shù)據(jù)集D被劃分為多個(gè)簇D1,D2…Dk時(shí)，μj為簇Dj的均值，Sj為簇Dj的散度矩陣，B為將D中各點(diǎn)替換為相應(yīng)簇均值uj后的散度矩陣。

?無論是否劃分，整體的散度S不變，它由各個(gè)簇內(nèi)部的散度Sj和各均值相對于整體的散度B組成的。
我們聚簇的目標(biāo)是增大B，減少各個(gè)Sj，就是讓簇內(nèi)部的點(diǎn)離均值更近，各簇間的距離更遠(yuǎn)。該公式（求散度矩陣的跡）可以作為評價(jià)聚類質(zhì)量的量度。

3) 例程：

i. 功能
用sklearn提供的KMeans類實(shí)現(xiàn)聚類功能，并畫圖
ii. 代碼

# -*- coding: utf-8 -*-  

import numpy as np  
import matplotlib.pyplot as plt  
  
from sklearn.cluster import KMeans  
from sklearn.datasets import make_blobs  
  
plt.figure()  
random_state = 170  
X,y = make_blobs(n_samples=200,random_state=random_state)  # 使用sklearn提供的數(shù)據(jù)
y_pred = KMeans(n_clusters=3,random_state=random_state).fit_predict(X)  
plt.scatter(X[:,0],X[:,1],c=y_pred)  
plt.show()

5. 使用注意事項(xiàng)

?基于距離的算法實(shí)際應(yīng)用中，需要做一些預(yù)處理，以便達(dá)到更好的效果：
?屬性多時(shí)，最好先降維，以免無意義數(shù)據(jù)淹沒有意義數(shù)據(jù)。
?使用之前最好做直方圖分析，查看樣本的密集區(qū)域。
?使用之前需要對各個(gè)屬性做標(biāo)準(zhǔn)化，以免值大的屬性有更大權(quán)重。
?使用之前最好根據(jù)經(jīng)驗(yàn)對各屬性分配不同的權(quán)重。
?對于無法直接分開的數(shù)據(jù)，可以考慮使用核函數(shù)轉(zhuǎn)換后再計(jì)算距離。

6. 算法之間的關(guān)系

?線性回歸，logistic回歸，支持向量機(jī)，KNN，K-Means都屬于基于距離的模型。下面以分類問題為例，看看它們之間的關(guān)系。
?假設(shè)我們有一個(gè)訓(xùn)練數(shù)據(jù)集(xi,yi)，需要預(yù)測數(shù)據(jù)a屬于哪個(gè)分類，在對數(shù)據(jù)毫無先驗(yàn)知識的情況下：
我們可能會找一個(gè)和a最相近的x，然后把a(bǔ)預(yù)測成x對應(yīng)的分類y，這就是最近鄰；
?如果覺得一個(gè)x不保險(xiǎn)（萬一它是噪聲數(shù)據(jù)呢），找離它最近的k個(gè)點(diǎn)x，看看它們對應(yīng)的y屬性大多數(shù)屬于哪個(gè)分類y，這就是k近鄰；

?如果我們估計(jì)這些數(shù)據(jù)可以被分成一簇一簇（左圖），而不是混在一起的，那我們可以用K-Means先把它分成幾簇，看a屬性哪一簇，然后按簇預(yù)測，這樣只保存簇心點(diǎn)及該簇對應(yīng)的分類即可，可以簡化數(shù)據(jù)存儲和計(jì)算量；
?如果不同的簇剛好對應(yīng)不同的分類，也就是說不同分類在空間上是分離的，那么計(jì)算兩個(gè)簇的質(zhì)心（中圖），連接兩個(gè)質(zhì)心（灰線），在連線中間做垂線（黑色），把兩類分開，就是logistic回歸/線性回歸，這樣就不需要保存實(shí)例，而保存直線參數(shù)即可分類；
?如果計(jì)算直線的時(shí)候，考慮到直線到兩類的邊界（右圖），就是SVM支持向量機(jī)，它保存邊界上的實(shí)例和直線的參數(shù)，以提供更多的信息。
?簇還可以和決策樹結(jié)合，按照距離把相近的簇合二為一；如果考慮到數(shù)據(jù)在歐氏空間中的概率分布，還可以在概率模型和幾何模型之建立聯(lián)系……