K-近鄰算法
k-近鄰算法簡單饶囚、直觀：給定一個訓練數(shù)據(jù)集军援，對新的輸入實例腿短，在訓練數(shù)據(jù)集中找到與該實例最鄰近的k個實例屏箍，這k個實例的多數(shù)屬于某個類，就把該輸入實例分為這個類橘忱。
優(yōu)點：精度高赴魁、對異常值不敏感、無數(shù)據(jù)輸入假定钝诚。
缺點：計算復雜度高颖御、空間復雜度高。
適用數(shù)據(jù)范圍：數(shù)值型和標稱型（只在有限目標集中取值凝颇，如真與假潘拱，常用于分類問題。）拧略。
K-近鄰算法
Python實現(xiàn)
- 使用Python導入數(shù)據(jù)
def createDataSet():
'''
創(chuàng)建帶標簽的數(shù)據(jù)集
:return: 返回訓練集和標簽
'''
# 4*2的特征變量矩陣
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
group矩陣包含4組數(shù)據(jù)芦岂，向量labels包含了每個數(shù)據(jù)點的標簽信息。此處垫蛆，我們將數(shù)據(jù)點(1, 1.1)和(1, 1)定義為類A盔腔，將數(shù)據(jù)點(0, 0)和(0, 0.1)定義為類B。
- 實施KNN分類算法
算法偽代碼如下：
(1) 計算已知類別數(shù)據(jù)集中的點與當前點之間的距離；
(2) 按照距離遞增次序排列弛随；
(3) 選取與當前點距離最小的k個點瓢喉；
(4) 確定前k個點所在類別的出現(xiàn)頻率；
(5) 返回前k個點出現(xiàn)頻率最高的類別作為當前點的預測分類舀透。
def classify0(inX, dataSet, labels, k):
'''
KNN算法
:param inX: 用于分類的輸入向量
:param dataSet: 訓練集
:param labels: 標簽向量
:param k: 用于選擇最近鄰居的數(shù)目
:return: 返回分類類別
'''
# 距離計算
dataSetSize = dataSet.shape[0] # 讀取dataSet的第一維長度
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1) # 對矩陣的每一行求和
distances = sqDistances ** 0.5
# 將數(shù)據(jù)按照距離從小到大排序
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]
- 測試代碼
if __name__ == '__main__':
# KNN算法實現(xiàn)
group, labels = createDataSet()
label = classify0([0, 0], group, labels, 3)
print label
測試結果為：
B
因簡書不支持Latex語法，可以訪問本人CSDN博客查看愕够，謝謝走贪！
