C++【实现】利用KNN约会分类

代码来于《机器上实战》

题目背景

小红时在约会网站搜索可自己之约会对象。经过自己的总,发现已接触了三种植档次的丁:

非爱的食指

魅力一般的总人口

极致有魅力的人数

意识了上述规律,小红还是无法以大体见面网站援引的相当对象由到相当的品种。她要当周一届周五大概见面那些魅力一般的人数,周末纪念那些最有魅力之人造伴(世界一直围绕在小红于转移啊转……)。我们怎么帮它们?

1. 数额处理

数据保存于datingTestSet2.txt中,每个样本占据一行,共有1000推行(哇,人才)。样本主要含有以下3单特性:

每月工资

玩游戏所吃时间百分比

每周消费的冰淇淋公升数

稍样例示意图

A 处理数据:将文件中之多少化分类器能经受的格式。

导入需要之家伙确保

from numpy import *

定义函数file2Matrix:将文件数据易成矩阵形式

def file2Matrix(filename):

    fr= open(filename)

    arrayOLines=
fr.readlines()#直拿数据全读取进来,形成列表,每一样表现一个因素

    numberOfLines= len(arrayOLines)#行数

    returnMatrix= zeros((numberOfLines,3))

    classLabelVector= []

    index= 0

    for linein arrayOLines:

        line= line.strip()

        listFromLine= line.split(‘\t’)

        returnMatrix[index,:] =
listFromLine[0:3]#赋值方式很厉害!

        classLabelVector.append(listFromLine[-1])

        index+= 1

    return returnMatrix,classLabelVector

B 数据归一化处理

多少遭到特征“每月工资”,取值范围最特别,计算距离时,产生的熏陶过非常。但咱以为3个特点的要是平等的。所以,有必不可少开展多少归一化处理。将数据归一化到
0~1 之间。

公式

newValue = (oldValue-min)/(max-min)

概念归一化函数autoNorm;返回归一化的数量,每个特征的最小值以及范围(方便对新数据进行归一化处理)。

def autoNorm(dataSet):

    minVals= dataSet.min(0)#a.min()
:全部底绝小价;;a.min(axis=0):每列中之太小值;a.min(axis=1):每行中的极其小值

    maxVals= dataSet.max(0)

    ranges= maxVals- minVals

    m= dataSet.shape[0]#行数

    normDataSet= dataSet-
tile(minVals,(m,1))#(m,n)重复次数:行方向上重复m次,列方向达成重复1破

    normDataSet= normDataSet/tile(ranges,(m,1))

    return normDataSet,ranges, minVals

内部,调用的函数

dataSet.min(0)

dataSet:python numpy array类型

array.min():求数组吃之无比小值

array.min(axis=0):对数组中的各级列求最小值

array.min(axis=1):对数组中的各个行求最小值

numpy.tile(A, reps):

Construct an array by repeating A the number of times given by
reps.通过更A ,reps不善构建一个新的数组。

tile(minVals, (m, 1)):重复minVals 构造一个m*1的copy

2. 分拣算法KNN

伪代码:

针对未知类别属性的数额汇总之每个点依次执行以下操作:

(1)计算都了解路数据集中的点和目前接触中的偏离;

(2)按照距离递增次序排序;

(3)选取与当下接触距离最近底k个点;

(4)确定前k个点所在类别的产出频率;

(5)返回前k个点出现频率高的品类作为当前接触之预计分类。

实在是计算两个数据的相似性:有距离相似性度量和角度相似性度量【knn算法介绍】。

此运用距离相似性度量,欧式距离。

欧式距离计算公式

分类器算法实现:

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

    dataSetSize= dataSet.shape[0]

    diffMat= tile(inX,(dataSetSize,1)) – dataSet

    sqDiffMat= diffMat** 2

    sqDiffMat= sqDiffMat.sum(axis=1)#遵照列求和

    distances= sqDiffMat** 0.5

    sortedDistIndicies=
distances.argsort()#argsort函数返回的是累组值从小到死的索引值

    classCount= {}

    for iin range(k):

        voteLabel= labels[sortedDistIndicies[i]]

        classCount[voteLabel] = classCount.get(voteLabel,0) +
1#每当字典classCount中通过 键
查找相应的价,如果字典中没有键,值为0;有收获其值;最后加1

    sortedClassCount= sorted(classCount.items(),key=lambda
a:a[1],reverse=True)#因出现次数排序,降序排序

    return
sortedClassCount[0][0]#返概率最老(出现次数最多之键,即类别)

里,调用函数:

numpy.argsort:

Returns the indices that would sort an array.
返回数组排序后底下标(默认升序排序)。

eg:[10, 1, 51]

调用函数,返回的是:[1, 0, 2]  ;1是数据1的下标。

3. 测试算法

数量指标:误分率。

算算方式: 错误分类的记录数/测试数据的总数;

def datingClassTest():

    “””

    使用测试数据测试分类器效果

    :return: 误分率”””

    hoRatio=
0.10#测试数据所占用的比重—将数据集按照1:9之比例划分,1凡测试集;9是训练集

    datingDataMat,datingLabels= file2Matrix(‘datingTestSet2.txt’)

    normMat,ranges,minVals= autoNorm(datingDataMat)

    m= normMat.shape[0]#数码集总数

    numTestVecs= int(m*hoRatio)#测试集数目

    errorCount= 0

    for i  in range(numTestVecs):

        classifierResult=
classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)

        print (“the classifier came back with: %s,the real answer is:
%s”  % (classifierResult, datingLabels[i]))

        if (classifierResult!= datingLabels[i]):

            errorCount+= 1

    print (“the total error rate is: %f”
%(errorCount/float(numTestVecs)))

运行结果:

测试算法运行结果

错误率:5%

4. 运用算法

中心:使用knn分类算法,方便小红约见面哦!

def classifyPerson1():

    resultList= [“不喜”,”魅力一般”,”极有魅力(韩国欧巴)”]

    percentTats= float(raw_input(\

“花费在娱乐、视频上之时百分比?”))#raw_input:读取控制高输入数据,赋值给变量,等效为C++里的cin>>a;

    ffMiles= float(raw_input(“每月工资发多少?”))

    iceCream= float(raw_input(“每年消耗的冰淇淋有微起?”))

    datingDataMat,datingLabels= file2Matrix(“datingTestSet2.txt”)

    normMat,ranges,minVals= autoNorm(datingDataMat)

    inArr= array([ffMiles,percentTats,iceCream])

    classifierResult=
classify0((inArr-minVals)/ranges,normMat,datingLabels,k=3)#本着输入数据开展归一化,然后重新分类

    print (“你用约会的人头很可能是: %s” %
resultList[int(classifierResult)-1])

应用:

小红以大约见面韩国欧巴(安排在星期日)

小红遇到不喜的档次(pass)

5. 小结

A。 矩阵运算—-能加速运算速度;

B。knn算法分类数据略可行,不用进行训练,是因实例的学习,使用的多少要接近实际多少的训练样本数据;必须保留有数据,如果数量集了特别,需要耗费巨大的储存空间;必须对数据遭到之有着样例点进行测算距离值,非常耗时(即使用矩阵展开演算)。

C。人生苦短,我用Python!

圆代码和数据集:github