算法执行步骤:
对未知类别属性的数据集中的每个点依次执行以下操作:
1)计算已知类别数据集中的点与当前点之间的距离;
2)按照距离递增次序进行排序;
3)选取与当前点距离最小的k个点;
4)确定前k个点所在类别的出现频率;
5)返回前k个点出现频率最高的类别作为当前点的预测分类。
k的取值不大于20
适用于数值型和标称型数据的分类
不需要提前训练,即用即练。
实现代码如下:
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
def classify(intX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] #shape函数是numpy.core.fromnumeric中的函数,它的功能是查看矩阵或者数组的维数
diffMat = tile(intX, (dataSetSize, 1)) - dataSet #tile(A, B),将A按B的格式要求进行重复,B可以是int(此时在列上重复,行默认重复一次)
#若B为元祖(a,b),则在行上重复a次,列上重复b次
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1) #axis=0表示按列相加,axis=1表示按照行相加
distances = sqDistances ** 0.5
sortedDistIndicies = distances.argsort() #得到数组值从小到大的索引值
#print(sortedDistIndicies)
classCount = {}
for i in range(k):
voteLabel = labels[sortedDistIndicies[i]]
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 #get()返回指定键的值, 如果指定键的值不存在时,返回默认值值(此处为0)
#此处即为记录每个入选标签在所有入选标签中出现的次数
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse=True) #items() 函数以列表返回可遍历的(键,值)元组
return sortedClassCount[0][0]
if __name__ == '__main__':
group, labels = createDataSet()
result = classify([0, 0], group, labels, 3)
print(result)
执行结果
[2 3 1 0]
B
上面是k-近邻算法的基本实现,为了完全理解算法在实际过程中的应用,还做了个有关约会对象是否为理想对象的实战练习,源码:https://github.com/YanniYao/algorithm_in_machine_learning/tree/master/kNN_exercise
网友评论