数据挖掘算法（一）--K近邻算法（KNN）

数据挖掘算法学习笔记汇总

数据挖掘算法（一）–K近邻算法（KNN）

数据挖掘算法（二）–决策树

 数据挖掘算法（三）–logistic回归

算法简介

KNN算法的训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。

在分类阶段，k是一个用户定义的常数。一个没有类别标签的向量（查询或测试点）将被归类为最接近该点的k个样本点中最频繁使用的一类。

一般情况下，将欧氏距离作为距离度量

d=(x1−x2)2+(y1−y2)2−−−−−−−−−−−−−−−−−−−√

但是这是只适用于连续变量。在文本分类这种离散变量情况下，另一个度量——重叠度量（或海明距离）可以用来作为度量。例如对于基因表达微阵列数据，k-NN也与Pearson和Spearman相关系数结合起来使用。通常情况下，如果运用一些特殊的算法来计算度量的话，k近邻分类精度可显著提高，如运用大间隔最近邻居或者邻里成分分析法。

算法流程简述

1、计算待分类点与已知类别数据集中每个点的距离；

2、按照距离递增次序排序；

3、选取与待分类点距离最小的k个点；

4、确定前k个点类别出现的频率；

5、返回前k个点出现频率最高的类别作为当前待分类点的预测分类。

代码

主要自己利用python代码实现了一遍KNN算法，另外也使用了sklearn的neighbors进行计算，学习sklearn包怎么使用。

本文代码运行环境：

python：3.5.1

pandas：0.19.2

sklearn：0.18.1

其他环境可能有细微差别

# -*coding:utf-8*-

import numpy as np

import pandas as pd

import operator

from sklearn import neighbors

def weight(onedata):

    #作为下面的pd.read_csv的转换函数

    if onedata == 'largeDoses':

        return 3

    elif onedata == 'smallDoses':

        return 2

    else:

        return 1

def autoNorm(dataFrame):

    minValues = dataFrame.min(0)  # 获取一列的最小值

    maxValues = dataFrame.max(0)  # 获取一列的最大值

    ranges = maxValues - minValues

    m = dataFrame.shape[0]

    dataFrame = dataFrame - np.tile(minValues, (m, 1))

    dataFrame = dataFrame / np.tile(ranges, (m, 1))

    return dataFrame, ranges, minValues

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

    rowNum = dataSet.shape[0]

    diffMat = np.tile(input, (rowNum, 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.index[sortedDistIndicies.values[i]]]

        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)

        return sortedClassCount[0][0]

# 读取数据

data = pd.read_csv("./datingTestSet.txt", sep='\t', header=None, converters={3: weight})

# 归一化数据

normData, ranges, minValues = autoNorm(data.iloc[:, 0:3])

# 利用后50%作为训练数据，前50%作为测试数据

Percent = 0.50

m = normData.shape[0]

numTest = int(m * Percent)

errorCount = 0.0

for i in range(numTest):

    classifierResult = classify0(normData.iloc[i, :], normData.iloc[numTest:m, :], data.iloc[numTest:m, 3], 3)

    # print("KNN计算值: %d, 真实值: %d" % (classifierResult, data.iloc[i, 3]))

    if classifierResult != data.iloc[i, 3]:

        errorCount += 1.0

print("KNN的正确率: %f" % (1 - errorCount / float(numTest)))

clf = neighbors.KNeighborsClassifier(3)

classifierResult = clf.fit(normData.iloc[numTest:m, :], data.iloc[numTest:m, 3])

score = clf.score(normData.iloc[0:numTest, :], data.iloc[0:numTest, 3])

print("sklearn的正确率: %f"% score)

运行结果

KNN的正确率: 0.920000

sklearn的正确率: 0.936000

代码和测试数据下载地址：

链接：http://pan.baidu.com/s/1kU8rEcR 密码：w57h

参考资料：

1、《机器学习实战》

2、wiki

欢迎python爱好者加入：学习交流群 667279387

巴特西

数据挖掘算法（一）--K近邻算法（KNN）

算法简介

代码

最新文章

热门文章

巴特西

数据挖掘算法（一）--K近邻算法 （KNN）

算法简介

代码

最新文章

热门文章

数据挖掘算法（一）--K近邻算法（KNN）