KNN 算法及 Java 实现
1.KNN 算法原理
基于类比学习，通过比较训练元组和测试元组的相似度来学习。
将训练元组和测试元组看作是 n 维（若元组有 n 的属性）空间内的点，给定一条测试元组，搜索 n 维空间，
找出与测试
元组最相近的 k 个点（即训练元组），最后取这 k 个点中的多数类作为测试元组的类别。
相近的度量方法：用空间内两个点的距离来度量。距离越大，表示两个点越不相似。
距离的选择：可采用欧几里得距离、曼哈顿距离或其它距离度量。多采用欧几里得距离，简单！
2.KNN 算法中的细节处理
数值属性规范化：将数值属性规范到 0-1 区间以便于计算，也可防止大数值型属性对分类的主导作用。
可选的方法有：v' = （v - vmin）/ (vmax - vmin)，当然也可以采用其它的规范化方法
比较的属性是分类类型而不是数值类型的：同则差为 0，异则差为 1.有时候可以作更为精确的处理，比如
黑色与白色的差肯定要大于灰色与白色的差。
缺失值的处理：取最大的可能差，对于分类属性，如果属性 A 的一个或两个对应值丢失，则取差值为 1；
如果 A 是数值属性，若两个比较的元组 A 属性值均缺失，则取差值为 1，若只有一个缺失，另一个值为 v，
则取差值为｜1-v｜和｜0-v｜中的最大值
确定 K 的值：通过实验确定。进行若干次实验，取分类误差率最小的 k 值。
对噪声数据或不相关属性的处理：对属性赋予相关性权重 w，w 越大说明属性对分类的影响越相关。对噪声
数据可以将所在的元组直接 cut 掉。
3.KNN 算法流程
1）准备数据，对数据进行预处理
2）选用合适的数据结构存储训练数据和测试元组
3）设定参数，如 k
4）维护一个大小为 k 的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选
取 k 个元组作为初始的最近邻元组，分别计算测试元组到这 k 个元组的距离，将训练元组标号和距离存入
优先级队列
