王芳
（天津师范大学计算机与信息工程学院，中国 天津 300387）
【摘要】模式识别的目的就是对未知的样本，判断它所在的类别。人类的模式识别能力使得人们可以很好的认识周围的环境并与之交流。分类器是模式识别系统的重要组成部分；也是机器学习的重要研究领域。
教育期刊网 http://www.jyqkw.com
关键词 模式识别；分类器
1近邻分类器
1.1算法原理
１）分类问题的两大类基本方法
（１）决策域/判别函数：利用判别函数或决策面方程将特征空间划分成决策域
（２）模板匹配：将待分类样本与标准模板进行比较，根据与各类别模板的匹配度情况，确定测试样本的类别
近邻法属于典型的模板匹配方法也是基于样本直接设计的非线性分类器
２）最小距离分类器：
（１）将各类训练样本划分若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本作为代表点，测试样本的类别则以这些代表点的距离最近作决策。
（２）当选择的代表点不一定能很好地代表各类时，错误率增加
３）最近邻分类器(NNC-Nearest Neighbor Classifier)
基本思想：以全部训练样本为代表点，计算测试样本与这些代表点，即所有样本的距离，并以最近者的类别作为决策。
（１）Cover和Hart于1968年提出，非参数法中最重要的方法之一
（２）可以理解为最小距离分类器的一种极端情况
（３）从模板匹配的角度理解：将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，按最相似模板的类别作为自己的类别
（４）最近邻决策规则：
①对于C类模式识别问题ωi，i=1，2，3，4…C，各类有Ni个训练样本。
与离它最近的样本同类。
（５）缺点：近邻法的缺点：存储量大，计算量大
1.2算法实现
本分类器采用的是UCI机器学习数据集中的Letter_Recognition。这个数据集中一共有20000个样本，根据前人经验，该分类器的设计取前16000个样本作为训练样本，将得到的运算结果模型用于预测剩下的4000个样本的分类情况。
本程序的设计采用的是C语言，是在Microsoft Visual Studio 2008这个开发环境下进行的。Microsoft Visual Studio 2008是对Microsoft Visual Studio 2005版本的升级，适用于win7、vista等操作系统。
Visual Studio 2008的语言更加的简洁，使用起来更加的方便。同时VS2008还提供了很多其他开发软件不具有的高级的开发工具，可以帮助开发者提高开发程序的效率，开发出更有价值的程序。
（1）数据的读入和存储
定义了结构体SAMPLE用来存放读入的样本集；利用整型二维数组test[WangFang_TSIZE][16]存放读入的测试样本；利用compare[WangFang_TSIZE]数组存放测试样本的正确分类情况，为正确率的计算做准备。由于样本的数量较大，采用文件的方式进行数据的读入与存储。
struct SAMPLE
{
char wf_classlabel;
int wf_attribute[16];/*已知特征向量为位*/
};
typedef struct SAMPLE SAMPLE;
SAMPLE sample[WangFang_SSIZE];/*样本集*/
int test[WangFang_TSIZE][16];/*测试集*/
char compare[WangFang_TSIZE];/*对比集*/
（2）计算测试样本到每个已知类别样本的距离
距离的计算采用的是n维空间的欧氏距离公式。n维欧氏空间是一个点集,它的每个点 X 可以表示为 (x[1]，x[2]，…，x[n]) ，其中 x[i] (i = 1，2，…，n) 是实数，称为 X 的第i个坐标，两个点 A = (a[1]，a[2]，…，a[n]) 和 B = (b[1]，b[2]，…，b[n]) 之间的距离 d(A，B) 定义为下面的公式：
d(A，B) =sqrt [ ∑( ( a[i] - b[i] )2 ) ] (i = 1，2，…，n)
部分代码如下：
double distance(struct SAMPLE m,int n[16])
{
int i;
double dd;
double sum=0.0;
for(i=0;i<16;i++)sum+=(m.wf_attribute[i]-n[i])*(m.wf_attribute[i]-n[i]);
dd=sqrt(sum);
return dd;
}
（3）寻找最小距离并分类
对于某一测试样本，一次计算他与各个样本的距离，存入数组d[SSIZE]，设一个最小距离dmin，dmin的初始值设为d[0]，一次用dmin和d[i]比较，如果d[i]大于dmin，则将其值存入dmin，并记录标号i。
（4）计算正确率
将测试集的分类结果和数组compare的内容比较，计算正确率。部分代码如下：
double Accuracy(char a[WangFang_TSIZE])
{
int i;
double j;
int sum=0;
for(i=0;i<WangFang_TSIZE;i++)if(a[i]==compare[i])sum+=1;
j=(double)sum/WangFang_TSIZE;
return j;
}
（5）执行结果的输出，把程序的执行结果输出到put out.txt中。
1.3运行结果
由于采用的是文件输入输出，因而详细结果在文件中显示。见put out.txt文档。
2结论
经历了数月的设计，基本实现了K-近邻算法的分类器，并且对数据测试结果表明：基本实现了预定目标，达到分类的效果。
K-近邻分类算法具有主观性，因为必须定义一个距离尺度，由于对距离的理解还不是深刻的，而分类的结果完全依赖使用的距离，这样对于用一组数据，两个不同的分类算法会产生两种完全不同的分类结果，一般需要专家来评测结果是否有效。由于对结果的认识是往往属于经验性的，这就限制了对各种距离的使用。
教育期刊网 http://www.jyqkw.com
参考文献
［１］边肇祺.模式识别[M]．北京:清华大学出版社,2000．
［２］孙即祥．现代模式识别[M]．长沙:国防科技大学出版社,2001．
［３］王立柱,等．C语言程序设计[M]．北京:机械工业出版社,2011.
［责任编辑：杨玉洁］