KNN 算法原理
KNN(K-Nearest Neighbor)最邻近分类算法是数据挖掘分类 (classification) 技术中最简单的算法之一, 其指导思想是 "近朱者赤, 近墨者黑", 即由你的邻居来推断出你的类别.
KNN 最邻近分类算法的实现原理: 为了判断未知样本的类别, 以所有已知类别的样本作为参照, 计算未知样本与所有已知样本的距离, 从中选取与未知样本距离最近的 K 个已知样本, 根据少数服从多数的投票法则(majority-voting), 将未知样本与 K 个最邻近样本中所属类别占比较多的归为一类.
Python 实现 KNN 算法
- import numpy as np
- import operator
- def createDataset():
- #四组二维特征
- group = np.array([[5,115],[7,106],[56,11],[66,9]])
- #四组对应标签
- labels = ('动作片','动作片','爱情片','爱情片')
- return group,labels
- def classify(intX,dataSet,labels,k):
- '''
- KNN 算法
- '''
- #numpy 中 shape[0]返回数组的行数, shape[1]返回列数
- dataSetSize = dataSet.shape[0]
- #将 intX 在横向重复 dataSetSize 次, 纵向重复 1 次
- #例如 intX=([1,2])--->([[1,2],[1,2],[1,2],[1,2]])便于后面计算
- diffMat = np.tile(intX,(dataSetSize,1))-dataSet
- #二维特征相减后乘方
- sqdifMax = diffMat**2
- #计算距离
- seqDistances = sqdifMax.sum(axis=1)
- distances = seqDistances**0.5
- print ("distances:",distances)
- #返回 distance 中元素从小到大排序后的索引
- sortDistance = distances.argsort()
- print ("sortDistance:",sortDistance)
- classCount = {}
- for i in range(k):
- #取出前 k 个元素的类别
- voteLabel = labels[sortDistance[i]]
- classCount[voteLabel] = classCount.get(voteLabel,0)+1
- #dict.get(key,default=None), 字典的 get()方法, 返回指定键的值, 如果值不在字典中返回默认值.
- #reverse 降序排序字典
- #classCount.iteritems()将 classCount 字典分解为元组列表, operator.itemgetter(1)按照第二个元素的次序对元组进行排序, reverse=True 是逆序, 即按照从大到小的顺序排列
- sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
- #结果 sortedClassCount = [('动作片', 2), ('爱情片', 1)]
- print ("sortedClassCount:",sortedClassCount)
- print("===>>>%s",classCount.items())
- return sortedClassCount[0][0]
- if __name__ == '__main__':
- group,labels = createDataset()
- test = [20,101]
- test_class = classify(test,group,labels,3)
- print (test_class)
- View Code
来源: http://www.bubuko.com/infodetail-3157255.html