機器學習入門:K-近鄰算法

先來一個簡單的例子，我們如何來區分動作類電影與愛情類電影呢？動作片中存在很多的打斗鏡頭，愛情片中可能更多的是親吻鏡頭，所以我們姑且通過這兩種鏡頭的數量來預測這部電影的主題。簡單的說，?k-近鄰算法?采用了測量不同特征值之間的距離方法進行分類。
優點：精度高、對異常值不敏感、無數據輸入假定 缺點：計算復雜度高、控件復雜度高 適用數據范圍：數值型和標稱型
首先我們來理解它的工作原理：
存在一個樣本數據集（訓練集），并且我們知道每一數據與目標變量的對應關系，輸入沒有標簽的新數據后，將新數據的每個特征與樣本集中數據對應的特征進行比較，然后算法提取樣本集中最相近的分類標簽，一般來說，我們只選擇樣本集中前k個最相似的數據，通常k為不大于20的整數，最后，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。
現在我們回到文章開頭所提到的電影的例子，根據下表如何確定未知的電影類型呢？
電影名稱?? ?打斗鏡頭?? ?接吻鏡頭?? ?電影類型
電影1?? ?3?? ?104?? ?愛情
電影2?? ?2?? ?100?? ?愛情
電影3?? ?1?? ?81?? ?愛情
電影4?? ?101?? ?10?? ?動作
電影5?? ?99?? ?5?? ?動作
電影6?? ?98?? ?2?? ?動作
電影7?? ?18?? ?90?? ?未知？
該如何計算電影7的電影類型呢？計算電影7與樣本集中其他電影的距離，然后我們假定k=3，看一下最近的3部電影是什么類型即可預測出電影7的電影類型。
流程介紹
收集數據
準備數據：距離計算所需要的值，最好是結構化的數據格式
分析數據
測試算法：計算錯誤率
使用算法
開始工作
使用python導入數據
首先，創建名為kNN.py的Python模塊，在構造算法之前，我們還需要編寫一些通用的函數等，我們先寫入一些簡單的代碼：
from numpy import *
import operator

def createDataSet():
??? group = array([
????? [1.0, 1.1],?
????? [1.0, 1.0],
????? [0, 0],
????? [0, 0.1]
??? ])

??? labels = ["A", "A", "B", "B"]

??? return group, labels
然后將終端改變到代碼文件目錄，輸入命令python進入到交互界面：
>>> import kNN

>>> group, labels = kNN.createDataSet()

>>> group
array([[ 1. ,? 1.1],
?????? [ 1. ,? 1. ],
?????? [ 0. ,? 0. ],
?????? [ 0. ,? 0.1]])
>>> labels
['A', 'A', 'B', 'B']
這里有4組數據，每組數據有2個我們已知的特征值，上面的group矩陣每行為一條數據，對于每個數據點我們通常使用2個特征（所以特征的選擇很重要），向量labels包含了每個數據點的標簽信息，labels的維度等于矩陣的行數，這里我們將 [1, 1,1] 定為類A， [0, 0.1] 定為類B，接下來我們進行算法的編寫：
計算已知數據集中點到當前點之間的距離
按照距離遞增次序排序
選取與當前點距離最小的k個點
確定前k個點所在類別的出現頻率
返回前k個點中頻次最高的類別作為預測類別
接著定義函數：
# inX: 用于分類的輸入向量
# dataSet：輸入的訓練集
# labels：標簽向量
# k：選擇近鄰項目的個數
def classify0(inX, dataSet, labels, k) :
??? dataSetSize = dataSet.shape[0]
??? # 距離計算
??? diffMat = tile(inX, (dataSetSize, 1)) - dataSet
??? sqDiffMat = diffMat ** 2 # python中, **2 代表2平方，**0.5代表開方
??? sqDistances = sqDiffMat.sum(axis=1) # 加入axis=1以后就是將一個矩陣的每一行向量相加
??? distances = sqDistances ** 0.5
??? sortedDistIndicies = distances.argsort()
??? classCount = {}

??? # 選擇距離最小的k個點
??? 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]
然后我們進行測試，重新打開python編譯環境：
>>> import kNN
>>> group, labels = kNN.createDataSet()
>>> kNN.classify0([0, 0], group, labels, 3)
'B'
>>> kNN.classify0([0.3, 0], group, labels, 3)
'B'
>>> kNN.classify0([0.8, 0.9], group, labels, 3)
'A'
我們看到，一個簡單的分類器就這樣搞定了。這時，我們來將電影數據進行樣本寫入：
def createDataSet():
??? group = array([
????? [3, 104],?
????? [2, 100],
????? [1, 81],
????? [101, 10],
????? [99, 5],
????? [98, 2]
??? ])

??? labels = ["love", "love", "love", "action", "action", "action"]

??? return group, labels
>>> import kNN
>>> group, labels = kNN.createDataSet()
>>> kNN.classify0([18, 90], group, labels, 3)
'love'
我們看到預測結果為愛情片。這是一個簡單的分類器，當然，我們應該通過大量的測試，看預測結果與預期結果是否相同，進而得出錯誤率，完美的分類器錯誤率為0，最差的錯誤率為1，上邊電影分類的例子已經可以使用了，但是貌似沒有太大的作用，下邊我們來看一個生活中的實例，使用k-近鄰算法改進約會網站的效果，然后使用k-近鄰算法改進手寫識別系統。
改進約會網站的配對效果
有個姑娘，一直在使用某交友網站，但是推薦來的人總是不盡人意，她總結了一番，曾交往過3中類型的人：
不喜歡的人
魅力一般的人
極具魅力的人
她覺得自己可以在周一~周五約會那些魅力一般的人，周末與那些極具魅力的人約會，因為她希望我們可以更好的幫助她將匹配的對象劃分到確切的分類中，她還收集了一些約會網站未曾記錄過的數據信息，她認為這些數據信息會有幫助。這些數據存放在代碼文件夾下 datingTestSet2.txt 中，總共有1000行數據（妹的約了1000個人），主要包含以下特征：
每年獲得的飛行常客里程數
玩視頻游戲所消耗的時間百分比
每周消費的冰激凌公升數
我們看到，統計的東西都比較奇葩，我們先從文件中把這些數值解析出來，輸出訓練樣本矩陣和分類標簽向量。在kNN.py中繼續書寫代碼：
從文本中讀入數據
def file2matrix(filename) :
??? fr = open(filename)
??? arrayOfLines = fr.readlines()
??? numberOfLines = len(arrayOfLines) # 得到文件行數
??? returnMat = zeros((numberOfLines, 3)) # 創建用0填充的矩陣，這里為了簡化處理，我們將矩陣的另一個緯度設置為3，可以按照自己的需求增加數量。

??? classLabelVector = []
??? index = 0
??? # 解析文件

轉載于:https://www.cnblogs.com/amengduo/p/9587160.html

總結

以上是生活随笔為你收集整理的机器学习入门:K-近邻算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。