首頁  >  文章  >  knn和k-means的差別是什麼

knn和k-means的差別是什麼

coldplay.xixi
coldplay.xixi原創
2020-12-17 15:17:4310512瀏覽

knn和k-means的區別:1、【k-means】演算法典型的基於距離的聚類演算法,採用距離作為相似性的評估指標,即認為兩個對象的距離越近,其相似度就越大;2、knn演算法沒有明顯的前期訓練過程,程式開始運行時,把資料集載入記憶體後開始分類。

knn和k-means的差別是什麼

knn和k-means的區別:

1. k-means聚類演算法過程與原理

k-means演算法(k-均值聚類演算法)是一種基本的已知聚類類別數的劃分演算法。它是很典型的基於距離的聚類演算法,採用距離作為相似性的評估指標,即認為兩個對象的距離越近,其相似度就越大。它是使用歐氏距離測量的(簡單理解就是兩點間直線距離,歐氏距離只是將這個距離定義更規範化,擴展到N維而已)。它可以處理大數據集,且高效。聚類結果是劃分為k類的k個資料集。根據聚類結果的表達方式又可以分為硬 k-means(H CM)演算法、模糊k-means演算法(F CM)和機率k-means演算法(P CM)。

1.1.基本思想

它是基於給定的聚類目標函數,演算法採用迭代更新的方法,每一次迭代過程都是向目標函數減小的方向進行,最終聚類結果使得目標函數取得極小值,達到較好的分類效果

1.2 原理

原始的k-means演算法首先隨機選取k個點作為初始聚類中心,然後計算各個資料物件到各聚類中心的距離,把資料物件歸到離它最近的那個聚類中心所在的類別; 調整後的新類別計算新的聚類中心,如果相鄰兩次的聚類中心沒有任何變化,說明資料物件調整結束,聚類準則函數f已經收斂。在每次迭 代中都要考察每個樣本的分類是否正確,若不正確,就要調整。在全部資料調整 完後,再修改聚類中心,進入下次迭代。如果在一次迭代演算法中,所有的資料 物件被正確分類,則不會有調整,聚類中心也不會有任何變化,這標誌著f已 經收斂,演算法結束。

1.3 演算法流程圖

knn和k-means的差別是什麼

1.4 演算法初始點怎麼選擇?

1) 選擇批次距離盡可能遠的K個點

先隨機選擇一個點作為第一個初始類別簇中心點,然後選擇距離該點最遠的點作為第二個初始類別簇中心點,然後再選擇距離前兩個點的最近距離最大的點作為第三個初始類別簇的中心點,以此類推,直至選出K個初始類別簇中心點。

2) 選用層次聚類或Canopy演算法進行初始聚類,然後利用這些類別簇的中心點作為K-Means演算法初始類別簇中心點。

1.5演算法中的k如何選取?

只要我們假設的類簇的數目等於或高於真實的類簇的數目時,該指標上升會很緩慢,而一旦試圖得到少於真實數目的類簇時,該指標會急劇上升。類簇指標 作為一個重要的參考指標。

類別簇的直徑是指類簇內任兩點之間的最大距離。

類別簇的半徑是指類別簇內所有點到類別簇中心距離的最大值。

1.6 優缺點以及如何改進?

使用簡單,是因為它使用了一個隨機的元素,所以它不能保證找到最佳的類別。無需要一個合理初始化要聚類的個數:即要初始化K 。

2. K-最近鄰分類演算法(K N N)

2.1 問題引入

knn和k-means的差別是什麼

K N N的思想: 從上圖我們可以看到,圖中的數據集是良好的數據,即都打好了label,一類是藍色的正方形,一類是紅色的三角形,那個綠色的圓形是我們待分類的數據。如果K=3,那麼離綠色點最近的有2個紅色三角形和1個藍色的正方形,這3個點投票,於是綠色的這個待分類點屬於紅色的三角形如果K=5,那麼離綠色點最近的有2個紅色三角形和3個藍色的正方形,這5個點投票,於是綠色的這個待分類點屬於藍色的正方形即如果一個樣本在特徵空間中的k個最相鄰的樣本中,大多數屬於某一個類別,則該樣本也屬於這個類別。我們可以看到,K N N本質是基於一種數據統計的方法!其實很多機器學習演算法也是基於數據統計的。

2.2 K N N演算法

介紹

#

K N N即K-Nearest Neighbor,是一種memory-based learning,也叫instance-based learning,屬於lazy learning。也就是它沒有明顯的前期訓練過程,而是程式開始運作時,把資料集載入到記憶體後,不需要進行訓練,就可以開始分類了。 K N N也是一種監督學習演算法,透過計算新資料與訓練資料特徵值之間的距離,然後選取K(K>=1)個距離最近的鄰居進行分類判(投票法)或回歸。若K=1,新資料被簡單分配給其近鄰的類別。

步驟

1)計算測試資料與各個訓練資料之間的距離;可以使用歐式距離的公式來進行計算。

2)依照距離的遞增關係進行排序;

3)選取距離最小的K個點(k值是由自己決定的)

#4)決定前K個點所在類別的出現頻率;

5)傳回前K個點中出現頻率最高的類別作為測試資料的預測分類。

特點

非參數統計方法:不需要引入參數 K的選擇: K = 1時,將待分類樣本劃入與其最接近的樣本的類別。 K = |X|時,僅依訓練樣本進行頻率統計,將待分類樣本劃入最多的類別。 K需要合理選擇,太小容易受干擾,太大增加計算複雜度。演算法的複雜度:維度災難,當維度增加時,所需的訓練樣本數急劇增加,一般採用降維處理。

2.3 演算法的優缺點

優點:簡單、有效

#缺點:計算量較大。輸出的可解釋性不強。需要儲存全部的訓練樣本。

3. K N N與k-means的差異

knn和k-means的差別是什麼

#相關免費學習推薦:php程式設計(影片)

以上是knn和k-means的差別是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

相關文章

看更多