Machine Learning in Action::k-Nearest Neighbour（kNN）

kNN-概述

	关键词：分类·监督学习

	原理：基于特征距离的最相近样本的等权重投票制。
	简单来讲：存在一个样本数据集合（训练集），样本中的每一条数据都存在一个标签（所属分类）。预测数据集合是仅有特征数据没有标签的数据集合。
		对于预测集的每一条数据，我们均可以将其与样本集合中的数据在特征空间进行距离计算，挑选出与之距离最相近的K个样本数据。然后这K个
		样本数据中，出现次数最多的分类即为我们要预测的那个分类。
	优缺点：显而易见，计算的时间复杂度与空间复杂度均较高,并且无法理解数据的内在含义。

kNN-核心算法实现

函数名称：
	classify0(intX,dataSet,labels,k)
函数说明：
	kNN 实现分类
输入参数：
	intX : 预测数据（特征向量） : list
	dataSet ： 训练集（特征向量集） : array
	labels : 训练集对应的标签（类型向量） : list
	k : 投票个体数 : int
返回参数：
	预测结果：最有可能的分类 : str

def classify0(intX,dataSet,labels,k):

	#计算距离（此处采用的是欧式距离）
	dataSetSize = dataSet.shape[0]
	diffMat = tile(intX,(dataSetSize,1)) - dataSet
	sqDiffMat = diffMat**2
	sqDistances = sqDiffMat.sum(axis = 1)
	distances = sqDistances**0.5

	#选择距离最小的K个点
	sortedDistIndicies = distances.argsort()
	classCount = {}
	for i in range(k):
		voteILabel = labels[sortedDistIndicies[i]]
		classCount[voteILabel] = classCount.get(voteILable,0) + 1

	#排序
	sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse=True)
	return sortedClassCount[0][0]

Tips

[1]通用函数

	测试时，难免会用到一些复用性较高的函数(模块)来提高效率。
	比如，针对classify0中的dataSet和labels,我们可以编写模块来从数据源读取。当然在前期较简单的方式如下：
	
	#kNN.py
	from numpy import *
	import operator
	
	def createDataSet():
		featureVecSet = array([[1,0],[0,1],[0,0]])
		labels = ['A','B','C']
		return featureVecSet,labels

	当我们需要测试时，可以这样：
	import kNN
	dataSet,labels = kNN.createDataSet()
	…………………………
	
------------------------------------------------------------------------------------------------------------------------------

[2]文本记录转换为NumPy的解析程序

	将特征数据（一般是保存在文本中的）输入分类器之前，必须将其格式化为可接受的形式。
	
	def file2matrix(filename):
		
		#获取文件行数
		fr = open(filename)
		arrayOLines = fr.readlines()
		numberOfLine = len(arrayOLines)
		
		#创建返回特征集合矩阵(N为特征数，硬编码)
		returnMat = zeros((numberOfLine,N))
		#创建返回分类向量
		classLabelVector = []
		index = 0

		for line in arrayOLines:
			line = line.strip()
			listFromLine = line.split('\t')
			returnMat[index,:] = listFromLine[:,N]
			classLabelVector.append(int(listFromLine[-1]))
			index += 1
		
		return returnMat,classLabelVector

------------------------------------------------------------------------------------------------------------------------------

[3]数据归一化

	在处理”距离“时，一定要注意数据归一化的问题。因为不同特征的取值范围是不一样的。
	比如: Feature1的范围[0,1] Feature2的范围[0,1000]，若不进行归一化处理，Feature2对结果造成的影响远远大于Feature1。
	
	通常采用的方法，将范围处理为0到1（或者-1到1）之间。下面给出一种处理为 0到1 的方案：
	
	newValue = (oldValue - minValue) / （maxValue - minValue)
	
	下面给出实现代码：
	def autoNorm(dataSet):
		minVals = dataSet.min(0)
		maxVals = dataSet.max(0)
		ranges = maxVals - minVals
		normDataSet = zeros(shape(dataSet))
		m = dataSet.shape[0]
		normDataSet = dataSet - tile(minVals,(m,1))
		normDataSet = normDataSet/tile(ranges,(m,1))
		return normDataSet, ranges, minVals

Welcome to contact me,the friends who like Machine-Learning and Data-Mining.

:)

02 Nov 2014