该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下：
STEP ONE: 对于每个测试元组，计算其到每个样本元组的距离，选择距离最近（或相似度最大）的元组K个
STEP TWO:从k个候选元组中，计算元组所属类别，属于哪个类别更多，则判断测试元组为此类
java版本实现：
package cluster;
public class KNNNode {
private int index; // 元组标号
private double distance; // 与测试元组的距离
private String c; // 所属类别
public KNNNode(int index, double distance, String c) {
//super();
this.index = index;
this.distance = distance;
this.c = c;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public String getC() {
return c;
}
public void setC(String c) {
this.c = c;
}
}
package cluster;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap; //hashMap的使用
import java.util.PriorityQueue;
/**
* KNN 计算只有两步，对于每一个测试元组，计算到其距离最近的k各训练元组
* 根据上一步获得的K个训练元组，选出其中所属类别比例最大的为测试元组类别
* @author chenjinandy
*
*/
public class KNN {
/**
* 用于表示PriorityQueue的排序方式，是升序还是降序，本例为降序
* Comaprator 的内部类，类似于c++中的 cmp 函数的意义，告知比较的方式，是降序排序
*/
private Comparator comparator=new Comparator()
{
public int compare(KNNNode o1,KNNNode o2)
{
if(o1.getDistance()>=o2.getDistance())
{
return 1;
}
else{
return 0;
}
}
};
/**
* 随机数产生函数，产生K各不相等的随机整数，范围为0-max之间
* 生成一个大小为K的链表，链表的内容是Integer，其值是随机生成不重复数值
*/
public List getRandKNum(int k,int max)
{ www.2cto.com
List rand=new ArrayList(k);
for(int i=0;i
{
int temp=(int)(Math.random()*max);
if(!rand.contains(temp))
rand.add(temp);
else
i--;
}
return rand;
}
/**
* 计算两个元组之间的距离，元组都为数据列表，采用平方欧式距离表述距离
* @param d1
* @param d2
* @return
*/
public double calDistance(List d1,List d2) // d1 为测试元祖样例
{
double distance=0.0;
for(int i=0;i
{
distance+=(d1.get(i)-d2.get(i))*(d1.get(i)-d2.get(i)); //平方欧式距离
}
return distance;
}
/**
* dates为训练元组，testdate为测试元组，K为KNN中的k参数，即选取多少各距离最近的
* @param dates
* @param testdate
* @param k
* @return
*/
public String knn(List> dates,List testdate,int k)
{
/*
* 以下过程是初始化一个优先队列的过程，首先构造K个值不大于训练元组大小dates.size()的随机数
*/
PriorityQueue pq=new PriorityQueue(k,comparator);
List randNum=getRandKNum(k,dates.size()); //仅仅为了初始一个pq所做的准备工作，其实完全可以0-K-1 替换
// randNum 中是随机的k个数值
for(int i=0;i
{
int index=randNum.get(i);
List currData=dates.get(index);
String c=currData.get(currData.size()-1).toString();
KNNNode node=new KNNNode(index,calDistance(testdate,currData),c);
pq.add(node);
// 这个只是初始化pq中的元祖，其实完全可以，比较之后再加入
}
/*
* priorityQueue 的用法，初始化时，确定大小和比较的类型，comparator，此例中是逐渐变小的，因此在链头是最大距离元祖
* 计算当前测试元组和每个训练元组的距离，如果距离比优先队列中最大距离小，则将其替换
*/