4.2 機器學習 —— KNN & K-Means

這是一篇李航老師《統(tǒng)計學習方法（第二版）》中KNN和K-Means部分的閱讀筆記蛉谜，文中用到了一些書中的表述和自己的理解缭乘。

1. KNN（k 近鄰算法）

1）是什么

??這是一個分類算法，輸入是實例的特征向量宴霸，輸出為實例的類別僧家。首先，我們有一個訓練集赂鲤，它是有標注的；對于一個新輸入的實例贰拿，我們在訓練數(shù)據(jù)集中找到與該實例最近的k個實例蛤袒，然后在這k個實例中進行多數(shù)表決熄云，最終確定新實例的類別膨更。

2）為什么

??k 近鄰算法的三個基本要素是：

k 值選擇，若k值較小缴允，則只有與輸入實例較近的訓練實例對預測結(jié)果起作用荚守，訓練的近似誤差會減小，但是由于模型對噪音數(shù)據(jù)的包容性更低练般，估計誤差會增大矗漾，更容易發(fā)生過擬合；反之薄料，若k較大敞贡，模型就會使用較大的鄰域進行預測，這樣就削弱了個別錯誤數(shù)據(jù)的干擾摄职，因此估計誤差會更小一些誊役，但同時較遠的實例也會對預測起作用，因此近似誤差會增大谷市。
距離度量蛔垢，如歐氏距離
分類決策規(guī)則，一般使用多數(shù)表決

誤分類率

3）怎么做

??其實通過上面的描述也可知迫悠，當數(shù)據(jù)量非常大的時候鹏漆，主要的時間消耗是 k 近鄰搜索，仍然使用線性搜索的方式的話创泄，時間開銷太大艺玲。為了提高 k 近鄰搜索的效率，可以考慮使用特殊的結(jié)構(gòu)存儲訓練數(shù)據(jù)鞠抑，以減少計算距離的次數(shù)饭聚，下面介紹 kd 樹（kd tree）方法。
??kd 樹是一種對 m 維空間中的實例點進行存儲以方便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)碍拆。kd 樹是一個二叉樹若治，表示對 m 維空間的一個劃分（partition）慨蓝。構(gòu)造 kd 樹相當于不斷地用垂直于坐標軸的超平面將 m 維空間進行切分，構(gòu)成一系列的 m 維超矩形區(qū)域端幼。kd 樹的每個節(jié)點對應于一個 m 維超矩形區(qū)域礼烈。

??構(gòu)造方式如下：

（1）開始：構(gòu)造根節(jié)點，根節(jié)點對應于包含 T 個 m 維空間的超矩形區(qū)域婆跑。
??選擇 m 維特征向量的第 1 維作為坐標軸此熬，以所有實例第一維坐標值的中位數(shù)作為切分點，將數(shù)據(jù)集分為兩堆滑进，存放在左右節(jié)點上犀忱，特例（也就是坐標值等于中位數(shù)的樣例）存放在根節(jié)點上；
（2）重復：對深度為 j 的節(jié)點上的集合扶关，使用第 l 維坐標的中位數(shù)進行繼續(xù)分割阴汇，直至分割的左右子區(qū)域沒有實例存在。（ l = j(mod m) + 1 ）
通過上述方法得到的 kd搜索樹 是平衡的节槐，但未必是最優(yōu)的（因為它不能保證平均搜索次數(shù)最少搀庶，所以不一定是最優(yōu)的）

??搜索方式如下：

（1）對于目標點 x ，遞歸地向下搜索铜异，直到子結(jié)點為葉結(jié)點哥倔，并將改葉結(jié)點設(shè)置為“當前最近點”
（2）遞歸地向上回退，對每個節(jié)點執(zhí)行以下操作：
- a）如果該結(jié)點保存的實例點比當前最近點到目標點的距離更近揍庄，那么更新最近點咆蒿；
- b）以目標點為球心，當前最近距離為半徑畫超球體蚂子，判斷當前節(jié)點及其子節(jié)點是否與球體相交沃测，如果相交，說明更近點可能存在于這個結(jié)點的分值中缆镣，遞歸地對這個結(jié)點進行近鄰搜索芽突；若不相交，那么一定不存在更近點董瞻，向上回退即可寞蚌；
（3）當回退到根節(jié)點的時候，搜索結(jié)束钠糊，當當前最近點即為 x 的最近鄰點

問：如果想要最優(yōu)挟秤，需要什么樹結(jié)構(gòu)？B+樹抄伍？紅黑樹艘刚？

2. K-Means（k 均值聚類）

1）是什么

??k 均值聚類是基于樣本集合劃分大的聚類算法。k 均值聚類將樣本集合劃分為 k 個子集截珍，構(gòu)成 k 個類攀甚，將 n 個樣本分到 k 個類中箩朴，每個樣本到期所屬類的中心的據(jù)里最小。每個樣本只能屬于一個類秋度，所以 k 均值聚類是硬聚類炸庞。分幾個模塊介紹：

模型：給定樣本集合 $X={x_1, x_2, ..., x_n}$ 每個樣本由一個特征向量表示，特征向量的維數(shù)是 $m$ 荚斯。k 均值聚類的目標是將 $n$ 個樣本分到 $k$ 個不同的類或簇中埠居。

2）為什么

策略：k 均值聚類歸結(jié)為樣本集合 X 的劃分，或者從樣本到類的函數(shù)的選擇問題事期。其策略是通過損失函數(shù)的最小化選取最優(yōu)的劃分滥壕。
- 首先采用歐氏距離平方作為樣本之間的距離 $d(x_i, x_j)$
- 然后定義樣本與其所屬類的中心之間的距離的總和為損失函數(shù)，即
  
  k 均值聚類就是求解最優(yōu)化問題

3）怎么做

??但由于這是一個組合優(yōu)化問題兽泣，n 個樣本分到 k 類的可能分法有指數(shù)級個绎橘。k 均值聚類的最優(yōu)求解問題是 NP 難問題，現(xiàn)實中采用迭代的方法進行求解撞叨。

算法：下面就說說這個迭代的過程金踪，每次迭代包括兩個步驟。
- 首先隨機選擇 k 個樣本點作為初始聚類中心牵敷，將樣本逐個指派到與其最近的中心的類中，得到一個聚類結(jié)果法希；
- 然后更新每個類的樣本的均值枷餐，作為類的新的中心；
- 重復以上步驟苫亦，直至收斂為止（譬如聚類結(jié)果不再變化）
  ??k 均值聚類屬于啟發(fā)式方法毛肋，不能保證收斂到全局最優(yōu)，初始中心的選擇會直接影響聚類結(jié)果（包括數(shù)量 k 和具體位置）屋剑，那么除了隨機選擇k和初始中心點润匙，還有沒有更好的方案呢？肯定是有的：
k 值得選劝ω摇：
- 可以根據(jù)業(yè)務需求進行選取孕讳，譬如需要分為高、中巍膘、低三類厂财，那么 k 等于3
- 不過像名詞聚類這樣的任務，更多是無法提前知曉類別數(shù)量的峡懈，那么我們可以用比較直接的方法推測最優(yōu)的 k 值璃饱，也就是對于同一個數(shù)據(jù)集，嘗試使用不同的 k 值進行聚類肪康，然后用類的平均直徑來檢驗各自得到聚類結(jié)果的質(zhì)量荚恶，平均直徑越小越好撩穿。一般來說，平均直徑與類別數(shù)負相關(guān)谒撼，當類別數(shù)增加到某個值k后冗锁，平均直徑不再減小或平緩減小，那么這個k就是一個較優(yōu)的k值嗤栓。為了加速冻河，我們還可以用二分查找的方式確定k的值。
初始中心的選擇：
- 除了隨機初始化茉帅，還可以使用層次聚類的方式來獲得初始中心（k 值要先確定）叨叙，流程如下
  ????1) 將每個樣例看作一類數(shù)據(jù)，計算兩兩之間的最小距離堪澎；
  ????2) 將距離最小的兩個類合并成一個新類擂错，重新計算新類與所有類之間的距離；
  ????3) 重復上述步驟樱蛤，直到類別數(shù)量縮減為k钮呀。
  ????4）計算 k 個類別的中心，作為K-Means的初始中心點