K近邻算法 | wsztrush
给定一个数据集，其中实例的类别已经标注完毕，那么：
当有新的实例时，怎么判断它的类别？
最简单的规则便是少数服从多数，假设训练集为$T={(x_1,y_1),(x_2,y_2)…(x_n,y_n)}$，找到与新实例$x$最近的$k$个实例，于是有：
$$
y = \arg \max_{c_j} \sum I(y_i = c_j) \quad i=1,2,..,n,\;j=1,2,..,k
$$
那么效果的好坏由：
- 距离的定义
- K值的选取
来决定。每次如果都遍历整个样本，效率比较低下，需要借助一些数据结构来优化。
kd-tree
通过将空间中的实例地划分到不同的子集中，在检索时就可能可以忽略掉部分子集，从而提高搜索速度，构造步骤为：
- 构造根节点，代表所有元素；
- 对深度为$j$的节点，选择$x^{(l)}$为切分坐标，其中$l = j \% k + 1$，以该节点区域对应的实例的$x^{(l)}$的中位数为切分点，分成两个子区域；
- 递归切分，直到切分后的子区域中没有实例；
搜索步骤为：
- 找到包含$x$的叶子节点；
- 在该节点中找到最近邻；
- 递归向上回退，并执行：
- 检查该节点保存的实例；
- 检查另一子节点中是否可能有最近的点（与当前得到的距离构成的圆是否有交集）；
- 回退到根节点时，搜索完成，所保留的便是最近邻；
工具
使用sklearn处理如下：
1 2 3 4 5 6 7 8 9 10 | from sklearn.neighbors import KNeighborsClassifier X = [[0], [1], [2], [3]] y = [0, 0, 1, 1] neigh = KNeighborsClassifier(n_neighbors=3) neigh.fit(X, y) print(neigh.predict([[1.1]])) print(neigh.predict_proba([[0.9]])) |
