認識-什么是KNN
KNN 即 K-nearest neighbors, 是一個hello world級別, 但被廣泛使用的機器學習演算法, 中文叫K近鄰演算法, 是一種基本的分類和回歸方法.
KNN既可用來分類, 也可用于回歸, 不過我還是覺得分類好一些哦
KNN的核心思想是, 如果一個樣本, 在特征空間中的K個最相鄰的樣本中的大多數屬于某一個類別, 則該樣本也屬于該類別, 即"近朱者赤, 近墨者黑". 這樣子兄嘚, 最通俗一點, 每個資料其實就是一個向量, 畫成圖就是一個點嘛, 每個樣本就是一個點, 然后計算這個點到其他所有點的距離, 降序取前K個結果, 在這K個中, 看哪個占比多, 則該樣本就屬于哪一個類別.
所以, 一般在選取K的時候, 一般是選擇奇數, 我猜這樣可能是為了好投票.
如果能get到"計算距離和投票"這兩個點, 則自然引出如下幾個問題:
- K該如何取值?
- 計算距離, 距離這個詞該怎么理解和計算呢?
- 每判斷一個樣本,要計算其到每個點的距離, 這個量有些大, 時間復雜度如何呢?
- 加入一個點離某個點非常之近, 此時另外2個也很近,且這兩個點是一個類的, 那么投票的,它們有2票, 而我只有一票, 這該怎么辦?
- 訓練資料不均衡( (Imbalance data) 咋能呢?
- 特征維度量綱跨度大 ( 一列是整數, 一列是百分比) 如何消除量綱影響?
超引數 (Hyperparameter) K的選取
共同問題: 特征工程: 即特征選取, 樣本均衡, 標準化 歸一化, 編碼等
其實我更喜歡翻譯為操引數, 別誤會, 是指需要人工去操作的引數, 好聽些就是經驗, 還是不夠智能嘛.
超引數是在訓練模型之前手動設定的引數, 而非模型訓練中得到的引數資料. 比如:
- 訓練神經網路的學習速率
- 學習速率 ( eg. 撰寫梯度下降原理時, 設定引數向量沿偏導數方向改變值的幅度 ,如0.2, 0.4等
- SVM的sigma超引數
- Knn的 k 值選取
KNN中, K越大則類與類的分界會越平緩, k越小則會越陡峭. 當k越小的時候, 就很容易過擬合了, 都搞成一團了, 這些點.
k取小了, 容易過擬合, 大了吧, 大量投票反而不準, 我好難.
交叉驗證法 (Cross Validation)
為了驗證模型靠不靠譜, 一般都會把資料分為訓練資料和測驗資料., 訓練資料用來計算模型的, 測驗資料用來驗證的.
-
The Validation Set Approach
-
Cross-Validatioin
The Validation Set Approach (訓練集+測驗集), 訓練資料越多,當然就越好啦, 但這里又要分出一部分做測驗, 即不能充分利用樣本.這是不足之處.
基于此, 有個大兄弟就是提出了交叉驗證法(Cross-Validation)
k-fold cross-validation, 指把所有訓練資料折成K份. 假設將訓練資料分為5折. 如當k=1的時候的, 可得到5個準確率, 取平均值作為超引數K=1時候的準確率. 探后繼續算k=3, k=5, k=7.. 這樣就可以就可選取到一個準確最高的超引數K了.
KNN中的距離
之前說了, 一個樣本寫成數字就是一個向量, 畫出來, 就是一個有方向的箭頭, 或者一個點唄.計算向量距離, 其實就是計量兩個向量的相似性.
歐式距離
平面上有兩個坐標點 A(x1, y1), B(x2, y2) 則歐式距離為:
\[d(A,B) = \sqrt{(x2-x1)^2+(y2-y1)^2} \]
推廣到高維空間的兩個點(向量) a向量, (x1, x2, x3, ...), b點(向量), (y1, 12, y3, y4...)的距離為:
\[d(a,b)=\sqrt{(y1-x1)^2+(y2-x2)^2+...(yn-xn)^2} = \sqrt{\sum_{i=1}^{n}(xi-yi)^2} \]
曼哈頓距離
指向量在各坐標軸上投影的距離總和. 曼哈頓距離也稱為城市街區距離. 好比你現在要從一個十字路口開車到另一個路口, 中間有樓擋著, 顯然不能穿墻吧, 直線距離就不太適用了. 而實際上你開車繞過彎路才到的距離, 才是"曼哈頓距離".
\[d12 = \sum_{k=1}^{n}|x_{1k}-x_{2k}| \]
馬氏距離
由印度統計學家馬哈拉諾比斯(P. C. Mahalanobis)提出，表示資料的協方差距離，是一種有效的計算兩個未知樣本集的相似度的方法，
與歐氏距離不同的是它考慮到各種特性之間的聯系（例如：一條關于身高的資訊會帶來一條關于體重的資訊，因為兩者是有關聯的）,并且是尺度無關的(scale-invariant)，即獨立于測量尺度， 如果協方差矩陣為單位矩陣,那么馬氏距離就簡化為歐氏距離，
\[d = ((\vec x - \vec y)'C^{-1}(\vec x - \vec y))^{\frac {1}{2}} \]
其他
- 切比雪夫距離
- 閔可夫斯基距離
- 標準歐式距離
- 巴氏距離
- 皮爾遜系數
- 杰卡德相似系數
- 余弦距離
大資料性能優化
KNN演算法的時間復雜度是O(N), 這里舉兩個思路方向, 就不闡釋了
-
K-D tree
-
LSH
樣本特征
其實就是設定權重唄, 總體感覺knn還是蠻好理解的哈.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69707.html
標籤：其他
上一篇：主動降噪(Active Noise Control)
下一篇：「天下隨拍」蘇州的那些湖