基于K邻近算法的LocalLDtree分类模型分析

摘 要 重点对懒惰式分类算法加以分析实验，针对提高分类器（Classifier）的分类效果，从急切式学习策略与懒惰式学习相结合和K-邻近思想与懒惰式决策树相结合的角度进行了研究，提出了LocalLDtree分类器，充实了分类研究领域的内容，并取得了较为理想的分类效果。

关键词 K邻近算法；Local LDtree；分类器；LazzDT

中图分类号：TP391 文献标识码：A 文章编号：1671-7597（2013）23-0033-01

1 LocalLDtree的分类模型及算法分析

1.1 LocalLDtree的基本思路

本文中在选择测试实例集中最近实例集合时，是基于K-邻近算法的思想来进行选择的，确定实例集合后对测试实例进行分类，使用了LazzDT分类器。实验证明，本文提出的LocalLDtree分类模型在绝大部分数据集上取得了较高的分类精度。

实验过程中使用Lazz DT分类器，结合K-邻近算法筛选出的与实例集合中最为接近的部分实例，在局部训练实例集合中进行实例的分类，实验证明，本文提出的LocalLDtree分类模型在绝大部分数据集上取得了较高的分类精度。

经过对懒惰式学习策略的研究，经过实验验证，提出了新分类模型―LocalLDtree。本文主要阐述LocalLDtree分类模型的算法，通过实验比较LocalLDtree、J48、Lazy decision tree与SimpleBias等四种分类器的分类精度。

1.2 实例间距离的计算

LocalLDtree分类模型在进行测试实例分类时，按照K-邻近算法的思路选择与本测试实例最为接近的K个训练实例，依据LazzDT分类模型在局部训练实例集中来对测试实例分类。

LocalLDtree分类器的建立，要根据测试实例计算其与每个训练实例的距离。关于实例间距的确定是本文需要重点描述的问题。实验中实例间距的确定采用的是Euclidean distance。

实验中假设全部实例对应于n维Euclidean distance中的点。任何一个实例z的特征向量都可以表示为：

其中ar（z）表示训练实例z第r个属性的值。两个实例zi和zj间距表示为d（zi，zj），其中：

d（zi，zj）=

使用Euclidean distance进行实例之间间距的确定在实验过程中也取得较好效果。

1.3 LocalLDtree分类器模型

结合K邻近算法与懒惰式决策树算法衍生出新分类模型LocalLDtree，是基于懒惰式学习策略分类算法。在给测试实例分类的时候，第一步，在最接近的部分训练实例中按照K邻近算法来进行筛选，第二步，测试实例的分类使用LazzDT模型在训练实例集合中来进行。LocalLDtree分类算法在多数数据集合上与其它常用的分类模型相比取得了较高的分类精确度。

LocalLDtree分类算法：

输入项，带类标的数据训练集SET；

某个没有类标等待分类实例z；

输出项，带类标的实例z；

1）对SET中的所有实例set，确定z到set的间距d（z，set）；

2）在SET中选择与z的间距最近的K个训练实例，标记为z1，z2，…，zk，使用数据集SUBset来存储这K个实例；

3）LazzDT的输入项使用SUBset集合及z，经过LazzDT分类器进行分类，以得到z的类标；

4）LazzDT得到的z类标值作为输出项来使用。

实验的关键，首先是，测试用例集合到任何一个实例的间距，采用何种方式来进行合适间距的确定，选择适合的间距计算标准，针对测试用例集计算它到每个训练实例的间距。其次，进行局部训练实例上给出的测试实例z分类时，采用的是Lazy decision tree分类算法，算法要正确的在选择分裂属性和与z相对应的训练实例集。

1.4 实验数据及结果分析

Lazy decision tree算法的提出者Friedman采用的实验数据集合都来自UCI的数据文件，为了将LocalLDtree算法和Lazy decision tree算法进行比较，在所有的数据集合中使用十重交叉验证，来衡量分类器的性能，运行分类器进行分类时使用默认参数设置。

实验主要目的是进行LocalLDtree、Lazy decision tree、The general decision tree与SimpleBias分类器在二十二个数据集中分类精度的比较。每个分类器分类精度是在测试集中成功预测实例所占总实例的百分比，使用十重交叉检验估计分类器的精度。

每个数据集合将被分为大小基本相同的十个子集合，并且每一个子集合都没有交叉数据。在选择训练集合时，分类器共进行十次训练和测试，在每次训练过程中，将分类器中的数据集合分离出一个子集来作为测试集合来使用，在其它未被分离的数据子集合中进行训练。通过分类器计算所得到的精度平均值作为性能评估的精度即十重交叉验证精度。对于The general decision tree分类器，实验过程中，在Weka实验测试平台下将j48作为运行环境，使用C4.5分类算法。LazzDT是在Weka实验测试平台中懒惰决策树运行实现算法。在运行j48、SimpleBias、LazzDT三种分类器时，都使用其默认参数设置。

根据对实验结果的分析，LocalLDtree在绝大部分实验数据集合中分类性能是最好的。在22个实验数据集中，Lazz DT的平均分类精确度为80.9400；J48的平均分类精确度为81.2513；朴素贝叶斯的平均分类精确度为78.7254；LocalLDtree的平均分类精度为84.90899。在实验过程中，对Audio，Lung-Cancer，Anneal，Tic-Tac-Toe等四个数据集合，LocalLDtree的分类精度都比LazzDT，SimpleBias分类器与J48的精度要高。对于Anneal，Audio， Zoo，Sonar，Tic-Tac-Toe，Echocardiogram数据集中，Semi-LDtree的分类精度都比J48高出很多。在Audio，Anneal，Tic-Tac-Toe，German，Solarflare-M五个大数据集中，LocalLDtree的分类精度要比LazzDT分类器的精度高。

2 结论

LocalLDtree分类模型在给测试实例分类时，通过实验证明，本文中提出的LocalLDtree分类模型在大多数数据集合上取得了较高的分类精确度。

参考文献

[1]张建勋，谷志民，郑超.云计算研究进展综述[J].计算机应用研究，2010，27（2）：429-433.

[2]卢润彩，庞超，时志素.基于K-近邻的局部懒惰式决策树分类模型[J].无线电工程，2010（2）.

[3]Z Xie，Wznne HSU，Z Liu，M L Lee：SNNB.A Selective Neighborhood based Na？ve Bazes for Lazz Learning.