机器学习算法之k邻算法

初步接触机器学习,真心觉得好有意思。决定要来学习机器学习的时候,是看到某个大牛用机器学习加大量的训练样本写了一个waf,真心觉得牛逼的不行,还有自动学习和训练功能,原来waf还可以这么玩,让我进一步认识到自己还是个弱鸡。虽然现在到不了把机器学习应用到编写waf的程度,但是觉得用来做一两个demo也是挺有意思的。

这个应该是机器学习里面最简单的一种算法了,不是说算法意义多大,而是它会让我感觉到,啊,机器学习原来是这么一回事啊,真的很有意思。

需求

现在提出一个需求,小明通过某个在线约会网站来自动寻找和判断是不是适合自己约会的对象。经过一番的总结,小明总结出他以前交往的三类人: A.不喜欢的人 B.魅力一般的人 C.极具魅力的人 现在小名想根据婚恋网上的女性的一些特性来自动判断是不是自己想约会的人。在此之前,小明已经收集了大量样本,主要包括以下三个特性,(ps:我也是瞎bb的,主要是训练样本不好找) 1.每年获得的飞行常客里程数 2.玩视频游戏所消耗的时间百分比 3.每周消费冰淇凌公升数 大致看一下样本 为了方便统计,把后面的largeDoses,smallDoses,didntLike转换成数字1,2,3,转换之后的样本,其实根本不用转,但还是转了。 有了这么多的样本,在下一次输入婚恋网的女性三个条件时,程序来判断下是不是小明喜欢的类型,当然会有一定的误差,但是误差在可以接受范围之类。 先说说算法思路,根据上面的样本特性,可以建立一个三维坐标,横纵竖左边分别时那三个特性,这样就建立起一个个点了。这时候输入样本的特性,也会形成一个点,然后再计算点与点之间的距离。 公式就是 (这里以二维为例) 通过计算这个新输入的点和所有样本的距离,选取距离最小的k个点,然后再求出这k个点里面largeDoses,smallDoses,didntLike所占的比例。选取比例最高的那个,比如说largeDoses。 算法的思路讲了,现在具体怎么做,不可能去新建一个类,包含这些属性吧。借助矩阵的一些特性,可以让一些需要计算的地方变得简单很多。(于是就去翻翻了忘干了的矩阵知识,捡回来一点点了。) 先定义一个函数,传入的参数是要测试的数据,已有的样本数据,已有的标签,还有实数k,之所以选择python是,numpy这个库使得矩阵的很多操作变的极其的简单,不需要自己去写矩阵方面的算法

def classify0(inX, dataSet, labels, k):
	dataSetSize = dataSet.shape[0]
	diffMat = tile(inX, (dataSetSize,1))- dataSet
	sqDiffMat = diffMat**2
	sqDistances = sqDiffMat.sum(axis=1)
	distances = sqDistances**0.5
	sortedDistIndicies = distances.argsort()
	classCount = {}
	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]

用测试点(0,0)测试下,

if __name__ == "__main__":
	group, labels = createDataSet()
	print classify0([0, 0], group, labels, 3)

和预期的一样,这样算法就算完成了。下一步就是要去解析出我们的txt样本数据了,化成一个1000行3列的矩阵,还有最后一列的数据化成一个1000数组

def file2matrix(filename):
	fr = open(filename)
	arrayOLines = fr.readlines()
	numberOfLines = len(arrayOLines)
	returnMat = zeros((numberOfLines, 3))
	classLabelVector = []
	index = 0
	for line in arrayOLines:
		line = line.strip()
		listFromLine = line.split('\t')
		returnMat[index, :] = listFromLine[0:3]
		classLabelVector.append(int(listFromLine[-1]))
		index += 1
	return returnMat, classLabelVector

测试一下
returnMat, classLabelVector = file2matrix('datingTestSet2.txt') print returnMat
其实到这一步,绝大部份工作已经完成,可是仔细想想的话,如果直接就去求距离,其实还有一个问题,就是飞行客里程数太大,都是万级别的数字,玩视频所占的比例太小,都是小于1的,求平方差的时候,玩视频这个性质对于飞行客里程数来说,几乎可以忽略不计,但实际上这三者是等权的,都很重要,都占3分之1。所以归一化特征

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

现在是等权了 到这一步基本上是完成了,为了测试算法的准确性,我用用1000个样本中的900作为训练样本,剩下100用来作为测试准确性的样本。
def datingClassTest(): hoRatio = 0.10 datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape[0] numTestVecs = int(m*hoRatio) errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m, :],datingLabels[numTestVecs:m], 3) print "the classifier came back with: %d,the real answer is %d" % (classifierResult, datingLabels[i]) if (classifierResult != datingLabels[i]): errorCount += 1.0 print "the total error rate is : %f" % (errorCount/float(numTestVecs))
错误率百分之五,勉强接受的范围。 觉得机器学习还是蛮有意思的一件事,我会投入更多的时间去学习。