ML - KNN算法-最邻近规则分类(K-Nearest Nei

综述

1.1 Cover和Hart在1968年提出了最初的邻近算法

1.2 分类(classification)算法

1.3 输入基于实例的学习(instance-based learning), 懒惰学习(lazy learning)

例子：

未知电影属于什么类型？

import math


def computeEuclideanDistance(x1, y1, x2, y2):
    d = math.sqrt(math.pow((x1 - x2), 2) + math.pow((y1 - y2), 2))
    return d


d_ag = computeEuclideanDistance(3, 104, 18, 90)
d_bg = computeEuclideanDistance(2, 100, 18, 90)
d_cg = computeEuclideanDistance(1, 81, 18, 90)
d_dg = computeEuclideanDistance(101, 10, 18, 90)
d_eg = computeEuclideanDistance(99, 5, 18, 90)
d_fg = computeEuclideanDistance(98, 2, 18, 90)

print(d_ag)
print(d_bg)
print(d_cg)
print(d_dg)
print(d_eg)
print(d_fg)
# 20.518284528683193
# 18.867962264113206
# 19.235384061671343
# 115.27792503337315
# 117.41379816699569
# 118.92854997854805

# 取K=3，最近的三个点都是 Romance，所有 未知点G点 为Romance

KNN

每一个电影当做空间中的一个点，每一个点是特征向量表示的值。

算法详述

• 步骤：

为了判断未知实例的类别，以所有已知类别的实例作为参照

选择参数K（参照已知实例的个数，一般为奇数，方便投票）

计算未知实例与所有已知实例的距离

选择最近K个已知实例

根据少数服从多数的投票法则(majority-voting)，让未知实例归类为K个最邻近样本中最多数的类别

• 细节:

关于K

关于距离的衡量方法:
Euclidean Distance 定义

其他距离衡量：余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）

• 举例

k的选择带来不同结果

算法优缺点：

• 算法优点

简单

易于理解

容易实现

通过对K的选择可具备丢噪音数据的健壮性

• 算法缺点

  
  

需要大量空间储存所有已知实例(计算和存储距离)

算法复杂度高（需要比较所有已知实例与要分类的实例）

当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本（Y点）

改进版本

考虑距离，根据距离加上权重（比如: 1/d (d: 距离））

应用

数据集介绍：

虹膜

150个实例

萼片长度，萼片宽度，花瓣长度，花瓣宽度（衡量四个维度）

(sepal length, sepal width, petal length and petal width）

分为三个类别：

Iris setosa, Iris versicolor, Iris virginica.

利用Python的机器学习库sklearn

SkLearnExample.py

from sklearn import neighbors
from sklearn import datasets

knn = neighbors.KNeighborsClassifier()

iris = datasets.load_iris()

# KNeighborsClassifier(n_neighbors=5, weights='uniform',
#                      algorithm='auto', leaf_size=30,
#                       p=2, metric='minkowski',
#                       metric_params=None, n_jobs=1, **kwargs)
#  n_neighbors: 默认值为5，表示查询k个最近邻的数目
#  algorithm:   {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’},指定用于计算最近邻的算法，auto表示试图采用最适合的算法计算最近邻
#  leaf_size:   传递给‘ball_tree’或‘kd_tree’的叶子大小
#  metric:      用于树的距离度量。默认'minkowski与P = 2（即欧氏度量）
#  n_jobs:      并行工作的数量，如果设为-1，则作业的数量被设置为CPU内核的数量
#  查看官方api：http://scikit-learn.org/dev/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier

# save data 可以看一哈
f = open("iris.data.csv", 'w')
f.write(str(iris))
f.close()

print(iris.data)
# [[5.1 3.5 1.4 0.2]
#  [4.9 3.  1.4 0.2]
#  [4.7 3.2 1.3 0.2]
#  [4.6 3.1 1.5 0.2]
#  ......
#  [5.9 3.  5.1 1.8]]
print(iris.target)
# [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
#  0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
#  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#  2 2]
print(iris.target_names)
# ['setosa' 'versicolor' 'virginica']

knn.fit(iris.data, iris.target)

score = knn.score(iris.data, iris.target)
print(score)
# 0.9666666666666667

predictedLabel = knn.predict([[0.1, 0.2, 0.3, 0.4]])

print(predictedLabel)
# [0]