Machine Learning Knowledge
K-th Nearest Neighbor
[Supervised, regression]
已有一个带label的数据集，给定一个样本，求其label。计算与其他所有samples的距离，取前k近的samples，统计这k个samples的label，认为最多的那个为此样本的label。
- k的选择不能太大，否则没有意义（当k=n是就是一个统计）同时k也不能太小，否则就overfit（当k=1时就近选择，对于测试集没有帮助）；可以通过划分验证集的方式来找到合适的k
- 数据的维度需要归一化，否则某个维度的距离会dominate其他的维度。
- 时间复杂度高，kd tree
K-means clustering
- 选择初始化的k个样本作为初始聚类中心$a=a_1,a_2,…,a_k$
- 针对数据集中每个样本$x_i$计算它到k个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中
- 针对每个类别$a_j$，重新计算它的聚类中心$a_j=\frac{1}{|c_i|}\sum_{x\in c_i}x$（即属于该类的所有样本的质心）
- 重复2，3两步操作，直到达到某个终止条件（迭代次数，最小误差变化等）