特征联合熵的一种改进K近邻分类算法

收稿日期:2011-01-07;修回日期:2011-02-24。

作者简介:周靖（1980－），女，广东茂名人，实验师, 硕士，主要研究方向：人工智能、数据挖掘； 刘晋胜（1979-），男，广东梅州人，实验师, 硕士，主要研究方向：人工智能、嵌入式系统、信号系统处理。

文章编号:1001-9081（2011）07-1785-04doi:10.3724/SP.J.1087.2011.01785

（广东石油化工学院 计算机与电子信息学院，广东 茂名 525000）

（）

摘 要:特征参数分类泛化性差及分类计算量大影响着K近邻（KNN）的分类性能。提出了一种降维条件下基于联合熵的改进KNN算法，其具体思路是，通过计算任意两个条件属性下对应的特征参数的联合熵衡量数据特征针对分类影响程度的大小，建立特征分类特性与具体分类过程的内在联系，并给出根据特征联合熵集约简条件属性的方法。理论分析与仿真实验表明，与经典KNN等算法相比，提出的算法具有更高的分类性能。

关键词:K近邻；特征；联合熵；条件属性；分类

中图分类号:TP301;TP311 文献标志码:A

Improved K-nearest neighbor algorithm for feature union entropy

ZHOU Jing, LIU Jin-sheng

（College of Computer and Electronic Information, Guangdong University of Petrochemical Technology, Maoming Guangdong 525000, China）

Abstract: Poor generalization of feature parameters classification and large category computation reduce the classification performace of K-Nearest Neighbor （KNN）. An improved KNN based on union entropy under the attribute reduction condition was proposed. Firstly, the size of classification impact of data feature was measured by calculating the union entropy of two feature parameters relative to any two condition attributes, and the intrinsic relation was established between classified features and the specific classification process. Then, the method which reduced condition attributes according feature union entropy set was given. The theoretical analysis and the simulation experiment show that compared with the classical KNN, the improved algorithm has better classification performance.

Key words: K-Nearest Neighbor （KNN）；feature；union entropy；condition attribute；classification

0 引言

作为一种基于实例的分类算法，K近邻（K-Nearest Neighbor, KNN）被认为是向量模型下最好的分类算法之一［1-2］。但作为一种有监督机器学习的非参数方法，KNN却具有一些明显的缺陷：一是分类性能受训练样本分布情况影响较大，当数据分布倾斜严重时，分类性能可能很差；二是样本间距离计算量大；三是近邻间距离由大多数不能充分体现分类相关性和重要性的表面特征参数所支配，特征分类特性泛化性差。目前，就KNN分类性能不足的改进方法主要有基于粗糙集理论［3］、主成分分析（Principal Component Analysis,PCA）算法［4］及神经网络理论［1］。文献［5］提出一种基于密度的样裁剪方法以降低KNN的计算量。文献［6］使用少量样本聚类中心来代替大量的原始样本，期望能在保持较高分类准确率的条件下，克服KNN分类速度慢的缺陷。文献［7］提出一种基于特征词缩减的KNN改进算法。这类型算法主要是通过直接减少训练集样本的数目或降低条件属性的维数来减少分类时的计算量。显然，如果样本或条件属性维数裁剪过多，会导致分类精度的下降。同时大量的研究表明，选择裁剪的样本及条件属性本身就是非常复杂、困难的问题。针对这些缺陷，许多学者提出了使用信息熵进行特征选择的改进KNN算法。文献［8］提出基于信息熵的特征分类相关性计算方法FE-KNN，文献［9］采用特征熵进行分类属性数据的优化。由于重点考虑了每个单一特征的分类特性对样本距离计算的影响，该类算法的准确率相对较高。

在分类数据集中，每个特征参数对分类的贡献程度都不一样，有些特征本身就比其他特征具有更高、更多的分类信息。联合熵可以综合衡量在不同条件下两个变量取值的不确定性。通过计算特征的联合熵，可以归并两个不同条件属性下两个特征参数针对样本分类的影响程度。因此，本文将联合熵理论引入KNN分类算法，提出了改进算法FUE-KNN（Feature Union Entropy-KNN）。具体地说就是两两归并原始条件属性下的特征参数，以联合熵的形式计算样本特征针对分类的重要性及相关性，并用这些特征联合熵集替代原始样本建立分类模型，同时围绕特征联合熵集确定样本条件属性的分类相关度，在囊括所有原始样本特征信息的条件下，剔除分类相关性相对较弱的条件属性，这样就减少了选择近邻样本时样本间距离度量的计算量。理论分析及仿真实验显示，特征联合熵体现出较原始数据样本、特征熵要多的分类信息量，与经典KNN等算法相比，FUE-KNN在保持分类效率的同时，有效地提高了分类准确率。

1 K近邻分类算法

K近邻分类算法的核心思想是：先计算测试与训练样本集之间的相似性距离，对每个测试样本找到与其最近的K个近邻；再根据这些近邻所属的类别来判断该测试样本的类别。以K个近邻中占多数的类别来确定该测试样本的类别。KNN算法主要以原始输入空间特征为计算因子，对各条件属性按照相同的权重来确定样本间的距离，具体采用欧氏距离公式如下：

d（xi,xj）（1）

其中tik，tjk表示为条件属性k下样本xi和xj的特征参数。

2 基于特征联合熵的改进K近邻分类算法

引入信息学中联合熵理论衡量特征针对分类的期望信息（对分类的影响程度），首先介绍特征熵的定义，并在此基础上提出特征联合熵的概念；然后给出围绕特征联合熵约简条件属性的方法；最后描述基于特征联合熵的改进KNN算法的具体过程。

2.1 联合熵优化特征参数

定义1 特征熵。设训练集S有m个样本，分为T类，具有n个条件属性，对xi∈S，条件属性j∈n的特征tij对xi类别判断的影响程度表示为：

H（tij）・－∑Tr1p（trij）・ln p（trij）

－・∑Tr1・ln（2）

其中：|trij|表示属于类r的特征tij的实例个数，|tij|表示特征tij在S中出现的次数。从式（2）可以看出，若特征tij在类r中出现的次数越多，同时在非r类里出现的次数越少，则tij对xi判断归属类r的影响就越大，综合tij对T个类的影响，即是tij对分类的整体影响，H（tij）越小，则影响程度越大。

定义2 特征联合熵。设j,k∈n，归并任意两个条件属性j、k（j≠k）下的特征参数为一个新的特征参数，记为〈tij, tik〉，设tij和tik对分类的影响是相互关联的两个特征参数，则〈tij, tik〉对xi分类判断的影响程度用联合熵形式表示为：

H（〈tij,tik〉）・

－∑Tr1p（〈tij,tik〉r）・ln p（〈tij,tik〉r）・{－∑Tr1・・〖ln+

ln・－ln〗}

H（tij）+H（tik/tij）（3）

其中|trik|/|trij|表示含有属于类r的特征tij的样本中，对应含有属于类r的特征tik的概率。分析式（3），其包含了两方面类别影响因子：一方面，H（tij）体现了特征tij对xi类别判断的影响程度；另一方面，H（tik/tij）表示在tij已经对xi类别判断造成影响的条件下，tik对xi类别判断的影响程度。综合两者，H（〈tik,tij〉）衡量了同时具有tij和tik时对xi类别判断的影响程度大小，H（〈tik,tij〉）越小，影响程度越大。另外，根据联合熵性质，H（〈tik,tij〉）H（tik）+ H（tij/ tik）H（〈tij,tik〉），即tij、 tik共同作用于xi类别判断的影响度可以以tij （或tik）为主体，tik （或tij）为条件设置来进行计算，只需一次特征扫描。

2.2 集成特征联合熵约简条件属性

根据上述定义及分析，特征联合熵优化原始特征参数的形式，实际上是两两特征归并衡量对样本分类所能提供的信息量，集成在具有n个条件属性的训练集S上能够从维数、准确率上优化条件属性，具体方法如下：在训练集S范围内，两两集成任意条件属性j、k（j≠k）下所有的特征参数，计算特征联合熵值，生成新的特征参数和条件属性，分别记为〈tik,tij〉和条件属性j∧k，则条件属性j∧k的分类相关性表示为： A（j∧k）∑mi1H（tij,tik），A（j∧k）值越小，表示条件属性j∧k对分类的影响程度越大，是强相关属性。显然对n个条件属性，能够两两归并成〖n×（n－1）〗/2个新的条件属性。在能够囊括原始n个条件属性信息的情况下，根据A（j∧k）值的大小进行属性裁剪，n个条件属性约简为n′（n/2≤n′≤n-1）个新的条件属性。

2.3 改进K近邻分类算法描述

针对KNN算法的缺陷，FUE-KNN采用了特征联合熵优化原始样本特征和条件属性的预处理机制，并在这些预处理的基础上对KNN算法进行改进。设训练样本集S和测试样本集D的样本数量均为m，具有n个条件属性，FUE-KNN核心思想为：借助式（2）、式（3）优化原始输入空间的样本特征参数，构建新的训练样本S′和测试特征集D′；依据2.2节简约条件属性；计算优化后的条件属性的分类相关度，依据相关度值的大小为新的条件属性赋予相应的权重；由于S′和D′中的特征联合熵是对分类影响程度的衡量，因此用特征联合熵差异度来表示特征间的相似度，进而计算样本间的距离。算法过程如下：

第一阶段：特征联合熵预处理。

1）声明结构体类型LIST{tij,|tij|,|trij|, H（tij）}（各成员语义信息详见式（2））；

定义LIST类型数组list0［m］［n］；

For i1 to m

For j1 to n{

对S中每个特征进行搜索统计，计算每个特征tij对分类的作用程度H（tij）（参见式（2））；

记录tij的统计信息及H（tij）值，并存储于list0［i］［j］；}

2）集合set_A用于描述条件属性j∧k的权重，初始化set_A＝空集，并定义LIST类型数组list1［n］［n］［m］；

For j1 to n

For k2 to n{

For i1 to m{

从list［i］［j］和list［i］［k］中提取tij，tik的相关信息|trij|，|trik|，|tij|，|tik|及H（tij）；

计算〈tij,tik〉对分类的影响程度H（t（〈tij, tik 〉））（参见式（3））；

H（t（〈tij, tik 〉））存储于list1［j］［k］［i］中；｝

计算条件属性j∧k针对分类的相关度（权重）：A（j∧k）∑mi1H（t〈tij,tik〉）；

将A（j∧k）放入集合set_A中；}

//对n个条件属性进行两两归并，生成新的n′个条件属性

3）集合set_pairs用于描述S新的条件属性集合，初始化set_pairs＝粒

4）while（集合set_pairs未包含条件属性j）{

A（j∧k）′min{A（j∧k）, j, k1,2,…,n}，从set_A中选择分类相关度最小的归并条件属性；

将A（j∧k）′放入集合set_pairs中；

从set_A集合中删除A（j∧k）；}

//修剪n个条件属性，归并后最少为n/2个，最多为n-1个

5）For i1 to m

For q1 to n′{

依次从set_pairs集合中提取A（j∧k）′；

根据j、k的信息在list1链表中选中相应的H（t（〈tij, tik 〉））；

使Tiq H（t（〈tij, tik 〉））；}//构建新的训练样本特征集S′

6）对样本测试集D重复1）～5）的操作，构建新的测试样本特征集D′；

第二阶段：计算样本间距离，判断测试样本类别。

1）定义变量Diff，用于描述S′和D′中任意样本各特征参数Tij间的差异度；

定义数组Sum_Diff［m］［m］，用于存储S′和D′中任意样本间整体特征的差异度

For i1 to m

For j1 to m{

For k1 to n′{

if（TikTjk或具有Tik的样本归属类别与具有Tjk的样本归属类别相同）

Diff0； //Tik与Tjk无差异；

if（具有Tik的样本归属类别与具有Tjk的样本归属类别不相同）

Diff1； //Tik与Tjk差异无限大

else DiffA（j∧k）.|Tik-Tjk|；

Sum_Diffij Sum_Diffij+ Diff；}//计算特征分类差异度

计算测试样本xi与训练集样本xj的距离：d（xi,xj）・Sum_Diffij；}

2）对测试样本集中xi∈D′，找出与xi最接近的k个已知类别的训练集样本xj的集合X，统计X中每个训练集样本所属类别的个数，出现次数最多的类别确定为xi的类别。

3 FUE-KNN算法性能分析与比较

从特征鲁棒性、分类精度和时间复杂度三个方面对比FE-KNN、经典KNN和FUE-KNN的性能。

3.1 特征鲁棒性

经典KNN具有良好的推广能力，但在很大程度上却依赖参数k的选择，对样本分布、k值变化极其敏感，因而鲁棒性低。FE-KNN、FUE-KNN分别通过特征熵、特征联合熵优化原始特征参数的形式来提高算法的鲁棒性，具体分类误差分析如下：设训练集S中任一xi∈Rm按分布p（x）随机抽取；设a（xi）为样本xi依据任意单个原始条件属性判断类别的平均输出信息，H′（xi）为综合n个原始条件属性判断xi类别的期望信息，显然，H′（xi）较a（xi）更接近实际的xi类别判断输出信息，即H′（xi）< a（xi）。将n个条件属性上综合判断xi分类的信息及其与任意单个原始条件属性判断xi的泛化误差分别记为：

H′（xi）∑nj1wijH（tij）； H′（xi）

γ（xi）（H′（xi）－a（xi））2 （5）

对任意条件属性j和条件属性归并j∧k判断xi类别的泛化误差z（tij, xi）和z（〈tij,tik〉, xi）分别为：

z（tij,xi）（H（tij）－a（xi））2

z（〈tij,tik〉,xi）（H（〈tij,tik〉）－a（xi））2 （6）

条件属性j和归并条件属性j∧k相对n个条件属性对判断xi分类影响程度的差异和这些差异的集成分别为：

φ（tij,xi）（H（tij）－H′（xi））2

φ（xi（j））∑nj1φ（tij,xi） （7）

φ（〈tij,tik〉,xi）（H（〈tij,tik〉）－H′（xi））2

φ（xi（j∧k））∑n′j,k∈1，2，…，nφ（〈tij,tik〉,xi）; n′

对式（7）、（8）中的第二个式子均加上a（xi）再减去a（xi）分别可以得到：

φ（xi（j））∑nj1z（tij,xi）－γ（xi）

φ（xi（j∧k））∑n′j,k∈1，2，…，nz（〈tij,tik〉,xi）－γ（xi） （9）

令z（tij,xi）∑nj1z（tij,xi）和z（〈tij,tik〉,xi）∑n′j,k∈1，2，…，nz（〈tij,tik〉,xi），则上式可变为：γ（xi）z（tij,xi）－φ（xi（j））和γ（xi）z（〈tij,tik〉,xi）－φ（xi（j∧k）），因此n′个条件属性在训练集上对分类影响程度的整体误差可以表示为：

Error（X（j∧k））∑mi1γ（xi）∑mi1（z（〈tij,tik〉,xi）－

φ（xi（j∧k）））∑mi1（∑n′j,k∈1,2,…,nz（〈tij,tik〉,

xi）－∑n′j,k∈1,2,…,nφ（〈tij,tik〉,xi））

∑mi1∑n′j,k∈1,2,…,nz（〈tij,tik〉,xi）－

∑mi1∑n′j,k∈1,2,…,nφ（〈tij,tik〉,xi）

Error（j∧k）－Diff（j∧k） （10）

依据式（9）和式（10）也可得出：

Error（X（j））∑mi1∑nj1z（tij,xi）－∑mi1∑nj1φ（tij,xi）

Error（j）－Diff（j） （11）

定义函数：E（x）1, x

0.5, x0

0, x>0，则整体误差期望值为Error（x）∑mi1E（H′（xi）・a（xi）），比较Error（X）和Error（X（j∧k））、Error（X（j）），假设把它们的累加分为判断正确和判断错误两个部分，对比后可推断，判断正确部分泛化误差在Error（X（j∧k））和Error（X（j））中都≥0，在Error（X）中则等于0；判断错误部分泛化误差在Error（X（j∧k））和Error（X（j））中必≥1，在Error（X）中必≤1。因此，结合联合熵性质H（〈tij,tik〉）H（tij）+ H（tik /tij）得：

Error（X）≤Error（X（j∧k））2〖H（tij）+H（tik）〗・

〖H′（xi）－a（xi）〗+a（xi）－H′（xi）2

Error（X）≤Error（X（j））2H（tij）・

〖H′（xi）－a（xi）〗+a（xi）－H′（xi）2（12）

显然Error（X（j∧k））< Error（X（j）），即Error（X（j∧k））比Error（X（j））更接近实际整体误差期望值。因此认为这种从根本上优化特征分类特性的KNN算法不依赖于参数k的变化，具有良好的鲁棒性，且FUE-KNN优于FE-KNN。

3.2 分类精度

基于3.1节的误差分析验证，FUE-KNN以联合熵的形式两两归并任意条件属性下的特征从而获得新的特征参数，比FE-KNN相应的单个条件属性下的特征熵所能提供的分类信息量要大，且分类误差要小。从距离机制的角度分析，FE-KNN和经典KNN采用欧氏距离公式，由于将样本不同条件属性、不同特征之间的差别等同看待，错分率较高的同时也极易产生由于不同类别邻近点个数相同而导致待分样本与各类的平均距离相同进而无法对测试样本进行投票判断的情况。FUE-KNN距离机制采用简单的特征联合熵差异度计算方法。由于特征联合熵参数本身已经体现出对分类有用的大量信息，且对任意优化后的条件属性，以特征联合熵集成的形式A（j∧k）作为该条件属性的权重，因而认为FUE-KNN的距离计算精度应高于FE-KNN及经典KNN。

3.3 分类效率

FUE-KNN包括了联合熵预处理和分类两个阶段，虽然预处理阶段的时间复杂度达到立方级，但该阶段在不损失所有原始特征参数信息的情况下，通过联合熵的两两集成对原始样本维数进行了约简，使得在分类阶段样本间的距离计算量明显减少，且距离的度量仅需做简单的特征差异度扫描，计算时间接近线性。FE-KNN的特征熵预处理阶段时间复杂度也达到立方级，由3.1节的误差分析可知，其提取的分类信息量低于特征联合熵，不适合采用简单的差异度方式来衡量样本间的距离，且没有降维处理，样本距离的计算量高于FUE-KNN。而经典KNN无数据特征预处理过程，直接依据原始特征参数，逐个特征地进行训练集与测试集中所有样本的距离计算，其时间复杂度与样本数量、特征维数成正比，且计算过程均在分类时才开始，因而效率最低。

4 实验分析

为了验证FUE-KNN算法的有效性、准确性以及较其他KNN算法的优越性，利用UCI数据库（ftp://ics.uci.edu/pub/machine-learning-database）中的letter数据集进行实验，letter数据集条件属性维数为16，样本总数为15000，共分为26类，具体实验数据描述及分布如表1。

表1 实验数据及其分布

4.1 参数K的选择

为了检验不同类别间样本数目不均衡因素对算法的影响，对参数K的确定实验采用训练集Tr4和测试集Te2，实验结果如图1所示。

图1 不同K值的分类效果

从图1可以看出，当K>31时，经典KNN分类效果大幅度下降；FE-KNN准确率曲线存在明显的陡度，当28≤K≤32时，分类准确率最高达到90%；FUE-KNN的准确率曲线最为平缓，算法表现出极高的稳定性。分析认为，由于原始数据特征参数噪声过多，特征特性不纯，使得经典KNN算法选择的近邻样本代表点中错误类别的训练集样本较多，从而影响了分类效果。同时，也鉴于KNN算法本身具有趋强弃弱的缺点［10］，容易导致测试样本被错分到样本较多的类别中去，对样本的分布极其敏感。而FE-KNN、EUF-KNN均通过优化原始输入空间参数来抑制上述缺陷，屏蔽原有参数中冗余、混淆的特性，尤其EUF-KNN使得K值的选择受样本分布的影响较小。

4.2 对比实验

设计FUE-KNN、FE-KNN、SVM和经典KNN的对比实验。由于经典KNN与FE-KNN在K31时分类效果最佳，此外为了体现FUE-KNN算法的优越性，以下实验均取K31。其中，SVM采用性能较好的径向基核函数：ker（x,xi）exp（－），并通过三交叉验证法得到核函数宽度arg10.4和惩罚参数C500。从表2的对比结果可以看出，FUE-KNN的分类精度已接近SVM，较FE-KNN有提高了5百分点，比经典KNN则提高了近10百分点。由此可知，使用特征联合熵代替原始数据特征参数后，分类准确率提升的幅度很大。同时，FUE-KNN条件属性的维数下降近1/3，分类效率仅略低于SVM，改进的效果是令人满意的。

表2 四种算法对比实验的结果

5 结语

条件属性降维的有效性和提取特征分类特性是KNN算法的重点。本文工作重点是在保持分类效率的条件下，提高KNN的分类精度。通过对特征参数和条件属性两个方面进行的研究，提出基于特征联合熵优化原始数据特征参数的改进KNN算法――FUE-KNN。仿真实验表明，FUE-KNN性能优于经典KNN等算法，与SVM相比也相差无几，能够有效地解决KNN在大样本集、样本分布不均等环境下健壮性差的缺陷。下一步的研究主要有两点：1）特征联合熵预处理阶段所占据的较大的存储空间及检索技术是制约FUE-KNN分类效率的瓶颈，研究选用更好的技术来构造特征联合熵集；2）条件属性分类相关度值，即条件属性权重的计算方法的研究，使得样本间相似性计算更精确。

参考文献:

［1］ 王煜,王正欧,白石.用于文本分类的改进KNN算法［J］.中文信息学报,2007,21（3）:76-81.

［2］ 刘海峰,张学仁,姚泽清,等. 基于类别选择的改进KNN文本分类［J］. 计算机科学,2009,36（11）:213-216.

［3］ PAWLAK Z. Rough sets［J］.International Journal of Computer Information Science, 1982, 11（5）:341-356.

［4］ MARTINEZ A M, KAK A C. PCA versus LDA［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001,23（2）:228-233.

［5］ 李荣陆.基于密度的KNN文本分类器训练样本的裁剪方法［J］.计算机研究与发展,2004,41（4）:539-545.

［6］ 张孝飞,黄河燕.一种采用聚类技术改进的KNN文本分类方法［J］.模式识别与人工智能, 2009,22（6）:936-940.

［7］ 胡燕,吴虎子,钟珞.基于改进的KNN算法的中文网页自动分类方法研究［J］.武汉大学学报:工学版,2007, 40（4）: 141-144.

［8］ DEBOLE F, SEBASTIANI F. An analysis of the relative hardness of reuters-21578 subsets［J］.Journal of the American Society for Information Science and Technology,2004,56（6）:584-596.

［9］ BARBARA D, LI Y, COUTO J. COOLCAT: An entropy-based algorithm for categorical clustering［C］// Proceedings of the 11th International Conference on Information and Knowledge Management. New York: ACM, 2002: 582.

［10］ VRIES A D, MAMOULIS N, NES N, et al. Efficient KNN search on vertically decomposed data［C］// Proceedings of the 2002 ACMSIGMOD International Conference on Management of Data. New York: ACM,2002:322-333.