01-knn k临近算法

一、knn简介

k临近算法采用测量不同特征值之间的距离来分类,在样本数据及中找出k个待分类数据最相似的样本，这k个样本中出现最多的类别作为待分类样本的类别

算法流程

遍历所有样本

对输入数据计算和每一个样本数据的误差

找出k个误差最小的样本

统计k个最相似的样本中出现最多的类别作为待分类样本类别

二、代码实现

样本数据

这是一份约会网站数据,

数据有三种分类：

1. largeDoses 极具魅力的人

2. smallDoses 魅力一般的人

3. didntlike 不喜欢的人

每条数据共有三种特征:

1. 每年乘飞机飞行里程数

2. 玩游戏时间百分比

3. 每周消耗冰欺凌公升数

40920    8.326976    0.953952    largeDoses

14488    7.153469    1.673904    smallDoses

26052    1.441871    0.805124    didntLike

75136    13.147394    0.428964    didntLike

38344    1.669788    0.134296    didntLike

72993    10.141740    1.032955    didntLike

35948    6.830792    1.213192    largeDoses

42666    13.276369    0.543880    largeDoses

67497    8.631577    0.749278    didntLike

35483    12.273169    1.508053    largeDoses

... ...

这些数据保存在datingTestData.txt中。

读取数据

将数据文件中特征值读取为numpy 3*n数组ret_mat

标签去读取为1*n数组labels

for line in lines:

line = line.strip()

l = line.split('\t')

ret_mat[index] = l[0:3]

labels.append(l[-1])

index += 1

---

数据归一化

不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影响到数据分析的结果，为了消除指标之间的量纲影响，需要进行数据标准化处理，以解决数据指标之间的可比性。原始数据经过数据标准化处理后，各指标处于同一数量级，适合进行综合对比评价.

常用的归一化方法有:

• min-max标准化法

• Z-score标准化方法

这里我们使用min-max标准化法。

$\frac{x-minval}{maxval-minval}$

分类

knn与其他机器学习方法不同的是，没有训练过程，直接对数据集上所有数据计算。分类时需要计算待分类样本与每一个样本数据的相似度，这里相似度我们用L2距离(就是我们常见的欧氏距离)表示

$L_2 = \sqrt{\sum_{k=1}^n x_{ik} - x_{jk}}$

简单的说就是向量每个元素平方和再开根，距离越小误差越小，即相似度越大

def classify0(in_x,dataset,labels,k):

dataset_size = dataset.shape[0]

diff_mat = in_x - dataset # numpy Broadcasting

sq_mat = diff_mat**2

sq_distance = sq_mat.sum(axis=1)

distances = sq_distance**0.5

sort_distance_index = distances.argsort()

class_count = {}

for i in range(k):

cur_label = labels[sort_distance_index[i]]

class_count[cur_label] = class_count.get(cur_label,0) + 1

sort_class_cout = sorted(class_count.iteritems(),key = operator.itemgetter(1),reverse=True)

return sort_class_cout[0][0]

测试我们的分类器

文本中有1000条数据，我们将其中一部分用来做测试数据，一部分用来做样本库，每隔1/10 取一条数据作为测试数据

test_data = dataset[0:data_size/10:1,0:]

test_labels = labels[0:data_size/10:1]

剩下的作为样本库

dataset = dataset[data_size/10:data_size:1,0:]

labels = labels[data_size/10:data_size:1]

完整代码