KNN
http://www.cnblogs.com/pinard/p/6061661.html
如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别
简单的说就是让最相似的K个样本来投票决定。
1 实现方法
- 暴力
- KD树
- Balltree树
2 参数
* k的选择：更加样本的分布选择较小值，然后交叉验证选择合适的值
选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
- 一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。
3 KNN的实现
因为我们经常碰到样本的特征数有上千以上，样本量有几十万以上，如果我们这要去预测少量的测试集样本，算法的时间效率很成问题。因此，这个方法我们一般称之为蛮力实现。比较适合于少量样本的简单模型的时候用。
所谓的KD树就是K个特征维度的树，注意这里的K和KNN中的K的意思不同。KNN中的K代表特征输出类别，KD树中的K代表样本特征的维数。为了防止混淆，后面我们称特征维数为n。
KD树算法包括三步，第一步是建树，第二部是搜索最近邻，最后一步是预测。
3.1 KD树的实现
http://www.cnblogs.com/pinard/p/6061661.html
* balltree的实现
http://www.cnblogs.com/pinard/p/6061661.html
算法总结
* KNN的主要优点有：
- 理论成熟，思想简单，既可以用来做分类也可以用来做回归
- 可用于非线性分类
- 训练时间复杂度比支持向量机之类的算法低，仅为O(n)
- 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
- 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合
- 该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分
* KNN的主要缺点有：
- 计算量大，尤其是特征数非常多的时候
- 样本不平衡的时候，对稀有类别的预测准确率低
- KD树，球树之类的模型建立需要大量的内存
- 使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
- 相比决策树模型，KNN模型可解释性不强
demo
# -*- coding: utf-8 -*-
# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_classification
# X为样本特征，Y为样本类别输出， 共1000个样本，每个样本2个特征，输出有3个类别，没有冗余特征，每个类别一个簇
X, Y = make_classification(n_samples=1000, n_features=2, n_redundant=0,
n_clusters_per_class=1, n_classes=3)
plt.scatter(X[:, 0], X[:, 1], marker='o', c=Y)
from sklearn import neighbors
clf=neighbors.KNeighborsClassifier(n_neighbors=15, weights='distance')
# weights='distance':权重和距离成反比
clf.fit(X,Y)
###############
# 预测效果
from matplotlib.colors import ListedColormap
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
#确认训练集的边界
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
#生成随机数据来做测试集，然后作预测
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
np.arange(y_min, y_max, 0.02))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# 画出测试集数据
Z = Z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)
# 也画出所有的训练集数据
plt.scatter(X[:, 0], X[:, 1], c=Y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = 15, weights = 'distance')" )
# -*- coding: utf-8 -*-
# -*- coding: utf-8 -*-
import numpy as np
from sklearn import neighbors
from sklearn.metrics import precision_recall_curve
from sklearn.metrics import classification_report
from sklearn.cross_validation import train_test_split
import matplotlib.pyplot as plt
# 数据的读取
data = []
labels = []
with open("/Users/mijian/Desktop/mlPyCode/data/1.txt") as ifile:
for line in ifile:
tokens = line.strip().split(' ')
data.append([float(tk) for tk in tokens[:-1]])
labels.append(tokens[-1])
x = np.array(data)
labels = np.array(labels)
y = np.zeros(labels.shape)
# 标签转换为0/1
y[labels=='fat']=1
# 数据集合的拆分
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2)
h = .01
x_min, x_max = x[:, 0].min() - 0.1, x[:, 0].max() + 0.1
y_min, y_max = x[:, 1].min() - 1, x[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
# meshgried生成网格
# arange生成间隔为h，数组
# 训练knn分类器
clf = neighbors.KNeighborsClassifier(algorithm='kd_tree')
# 默认k=5
clf.fit(x_train, y_train)
# 打印结果
answer = clf.predict(x)
print(x)
print(answer)
print(y)
print(np.mean( answer == y))
# 准确率和召回率
precision, recall, thresholds = precision_recall_curve(y_train, clf.predict(x_train))
answer = clf.predict(x)
print(classification_report(y, answer, target_names = ['thin', 'fat']))
# 绘图
# 将整个测试空间的分类结果用不同颜色区分开
answer = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:,1]
z = answer.reshape(xx.shape)
# reshape生成数组：对answer重新生成数组
# shape：读取形状
plt.contourf(xx, yy, z, cmap=plt.cm.Paired, alpha=0.8)
# contourf：等实线绘制，cmap控制颜色
plt.scatter(x_train[:, 0], x_train[:, 1], c=y_train, cmap=plt.cm.Paired)
# scatter：散点图
plt.xlabel(u'身高')
plt.ylabel(u'体重')
plt.show()