综述
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]
