论文研究-基于距离学习的集成KNN分类器 .pdf

所需积分/C币:16 2019-08-21 05:06:39 225KB .PDF
收藏 收藏
举报

基于距离学习的集成KNN分类器,于飞,顾宏,近年来,数据挖掘引起了信息产业界的极大关注,其主要原因是存在大量数据,可以广泛适用,并且迫切需要将这些数据转换成有用的信
国科技论又在线 http://www.paper.edu.cn 票决定结果。装袋算法在建立决策树和神经网络分类器上都取得巨大的成功,最近的实验数 据表明,袋装算法建立的KNN分类器也取得了稳定的分类效果,最具代表性的是 FABSIR。 个自助数据集,就是从原始训练集D中随机选择n个样本组成个新的训练集。(由 」原始数据集的D的大小就是n,因此自助数据集中不可避免的存在着重复的样木)。装袋 集成,则是指从大小为n的原始数据集D中,分别独立随机的选取n个样木形成自助数据 集,并且将这个过程重复多次,直到产生很多个独立的自助数据集。然后,每一个自助数据 集都被独立地用于训练个了分类器,最终的分类判决将根据这些了分类器的判决结果投票 米决定。通常,这些子分类器的模式都是一样的。 实际上,建立一个有效地集成,必须在每一个子分类器本身具有很高的准确性的同时, 分类器之间要具有很大的差异性。KNN方法相对比较难以利用装袋法集成,打个比方:给 定一个具有N个样本点的数据集,第i个样本被选中0,1,2次的概率近似服从A=1的泊 松分布,那么第i个样本在至少出现一次的概率为1-(1/e)≈0.632,假设一个两类分类问题 要自助生成个子分类器,当且仅当某个检测样木在这些训练集中的最近邻(设k=1)出现 次数少于L/2次吋,该检测样本的分类结果将会发生变化。发生这种分类情况改变的概率相 当于投掷t次硬币问题中,出现止面的次数小于0.5t的概率,(假设每次投掷出现正面的概 率为0.632),很明显,随着t值的增大,这个概率是不断减小的。 如此看来,单一利用自助方法随机抽取训练样本无法得到准确性和差异性兼备的子分类 器,需要引入其亡的添加扰动的机制。实际上,对于输入属性的扰动已经成功的被用在BP 神经网络分类器和C4.5决策树分类器中,而前文提到的 FABSIR分类器就很好的运用这种 对输入属伫添加扰动的方法集成了KNN分类器,取得了很好的实验结果 本文中采用的袋装集成方法在自助生成子分类器的计算过程中,借鉴了 FABSIR对输入 属性添加扰动的方法ε具体来说,每一次的自助不但独立随机抽取η个样本,也从原数据集 中随札抽取了这一次自助中n个样木的属性,也就是最后生成的每一个子分类器的样木属性 各不相同。设生成的子分类器的个数为t,在自助过程方法中,对此t个子分类器都是对原 数据集进行随机的属性抽取后生成的,并设一个参数因子s用来控制抽取属性的数量:如果 原数据集经过属性过滤之后共有d个属性,那么选取后的子集有d×s个属性。这种对输入 属性添加扰动的方法会提升分类效果,主要取决于这种方法生成的子分类器之间将差异明 本文的装袋集成算法,每一个子分类器都利用一和基于距离学习的KNN算法来计算分 类结果,最后利用多数投票制综合子分类器的结果,得到最终判定。 23距离学习 对」装袋集成所生成的t个子分类器,各个子分类器之间差异明显,利用距离学方法 计算每个了分类器的距离度量,将大大提高分类器的分类准确度。本文借鉴了NCA距 离学习算法,以优化留一法(LOO的交错验证结果为目标,以下是距离学习算法的具体实现 假设一个已标签的子分类器包含n个实的输入向量x,…,xnX∈R,而相应的类别标为 G1,…,cn,选择一个距离度量使得KNN的分类效果达到最佳 本距离学习方法采用马氏距离模型,求半正定矩阵Q=AA,如(3)式所示: d(x,y)=(x-y)Q(x-y)=(4x-4y)(Ax-4y) 国科技论又在线 http://www.paper.edu.cn 但是留一法验证的错误率是一个自变量为A矩阵的一个闫断函数,如此一来A矩阵的 一个极小的变化将对KNN的留一法验证结果产生很大的影响。本算法引入一个可微分的非 线性函数,具体来说,每一个点i将另外的一个点j作为其邻近并继承其类别标签C的概率 为P。在马氏距离的基础上,利用 softmax非线性函数,定义P为 exp(Ax;-Ax (4) ∑exp(|Ax;-Ax 由于是随机选择,第i点被正确分类的概率P为 ∑ 那么最好的分类效果就是被上确分类的点的数量达到最大,设目标函数为 f(=∑∑P=∑P 这是一个矩阵函数,NCA方法就是通过共轭梯度法或者是二次规划方法来优化这个矩 阵函数,得到最优解A,从而得到最优的距离学习模型。另外,对于(6)式的日标函数可以 转化成计算目标函数对于A的梯度(x=x1-x) OA 2∑∑P(x∑ 整理后得到: ∑(p∑Px-∑Pxx) (8 本文利用 Polack - Ribiere共轭梯度法来计算(8)式的最大值,得到最优解A矩阵,得到新 的距离度量d(x,y)=(x-y)Q(x-y)=(4x-y)(Ax-A1y)作为KNN算法的距离度量 来实施分类。 3.实验结果 五组常用的UCI数据集被用来检测本算法的分类效果,这些数据集中的数据都是数字 类型的。由于KNN无法处理缺失的数据,所以在引入数据集之前提前忽略掉一些缺失的数 据,关于数据集的信息如下表所小 表1五组实验用LCI数据集 Tab 1 five data sets used in experiment 数据集 样本数 属性数 类別数 Winc l78 2100 19 150 4 Bal 625 4 Ion 351 国科技论又在线 http://www.paper.edu.cn 利用留一法交错验证来计算每一个数据集的分类正确率。即对一个拥有n个样木的数据 集,每次抽取一个样木作为检测样木,剩卜n-1个样木组成的新数据集作为训练集,对检 测样木分类,同样的步骤重复n次,使得每一个样木都充当过一次检测样木,最后判断这n 次循环中检测样本被分类正桷的个数,从而得到正桷率。 首先设置不同的K值,对比传统KNN和距离学习KNN算法对这五组UCI数据集的分 类效果。设置集成学习中子分类器个数为50,K值取1,属性过滤系数f取0.3,针对不 同的数据集,属性提取系数Ion取0.6, Segement取0.8,Wine,Iris,Bal取1,利用留一法 交错验证的计算结果如下 表2Wine数据集对比结果 Tab. 2 a compared results of wine Wine K=1 传统KNN0.9494 0.9663 0.9494 0.9551 距离学丬后 0.9888 0.983l 0.9831 l.0000 集成后 1.0000 1.0000 1.0000 1.0000 表3 Segement数据集对比结果 Tab. 3 a compared resul ts of segement Segment K=1 K=5 K=10 传统KNN0.9 0.95570.9514 0. 距离学习后 0.9700 0.9690 0.9548 集成后 0.9787 0.9654 0.9631 0.9741 表4Iris数据集对比结果 Tab. 1 a compared results of Iris Iris K=1 K=10 传统KN09133 0.9467 0.9133 0.9533 距离学习后 0.9067 0.9267 0.9333 0.9533 集成后 0.9867 0.9800 0.9600 0.9667 表5Bal数据集对比结果 Tab. 5 a compared results of Bal Bal K-3 K-5 K-10 传统KNN 0.72 0.7344 0.7344 0.7136 距离学习后 0.9200 0.9376 0.9344 0.9168 集成后 0.9648 0.9632 0.9456 0.9632 表6Ion数据集对比结果 Tab. 6 a compared resul ts of Ton K=1 K=3 K=10 传统KNN 0.8476 0.8775 0.9031 0.8946 距离学习后 0.9860 0.8917 0.8945 0.8860 集成后 0.940 09173 0.9145 0.9144 其次,对于每一个数据集,分别用五和不同的算法进行计算并比对结果。它们分别是传 国科技论又在线 httpi/www.paper.edu.cn 统KNN分类器、改进的KNN分类器(传统马氏距离作为距离度量)、多模扰动的集成算法 FABSIR、NCA距离学习KNN分类器和本文所介绍的新KNN分类器(NEW),各项系数取 值不变,分类结果如下所示: 表7五种分类算法的对比 Tab. 7 a comparsion of 5 different methods KNN KNN(改) FABSIR NCA NEW e 0).9494 ()9438 .9785 0.9690 0.9697 0.9715 0.9748 928 Iris 0.9133 0.9267 0.9254 0.9067 0.9867 Bal 0.7248 0.7344 0.8l45 0.9200 0.9648 Ion 0.8476 0.8775 0.8753 0.8860 0.9401 average0.88020.89040.90220.93530.9769 从实验数据我们看到,新的算法把集成算法和NCA距离学习算法结合到起,其分类 的效果要比单独的集成和距离学习都有所提升,相对传统KNN算法更是提升明显,对于某 些数据集比如Bal,距离学习算法对于分类效果的提升更加明显。但是,新算法分类效果的 提升带来的也是许多计算量的消耗,特别是利用留一法进行交错验证,一个数据集需要进行 的距离学习计算的次数相当于样本数ⅹ子分类器数,而对于样本和属性都很多的大型数据 集,NCA距离学习环节中计算显得尤为迟缓。所以如果让本算法在计算效率上得到更大的 提升,还需要在计算速度和计算札硬件支持上加以改进。 4.结论 本文实现了一种基于距离学习的集成KNN分类算法,与传统KNN算法和其他距离学 习或集成算法相比,分类效果提升明显。但是由于NCA距离学习的日标函数利用了 Polack- Ribiere共轭梯度法进行训算,当输入的样本数和属性比较多的时候,学习最优化得 距离模型耗费大量的讣算,就个人电脑的训算速度而言,尚个能利用本算法分类过于庞大复 杂的数据集。所以在算法速度的改进上仍然有大量工作要做 参考文献 [11 Jocab Goldberger, Sam Roweis, Geoff Hinton. Neighbourhood Components Analysis. In International Conference on Machine Learning[], 2003 [2] Ricard O Duda, Peter E. Hart, David G. Stork. Pattern ClassificationM]. Tele-medicine Journal and e-Health 2003,9(2):141-147. [3 Zhi-hua Zhou, Yang Yu. Ensembling Local I earners Through Mutimodal Pertubation[]. IEEE Transaction on System,200ol.5:725-735. L4 Kreshna (opal, Thomas R loerger. Distance Metric Learning through Optimization of Ranking[ J]. SevenlEEI International Conference on Data Mining [5http://www.cs.cmu.edu/liuy/distlearn.htm 国科技论又在线 http://www.paper.edu.cn A New ensemble nn classifier based on metric-earning Method Yu上el, Gu hong Department of Automation, Dalian University of Technology, Liaoning Dalian(116031) Ensemble learning algorithms train multiple component learners which is based on a metric-learning knn classifier and then combine their predictions. On one hand, in order to generate a strong ensemble, a way of perturbing the training data with resampling methods such as boostrap sampling used in bagging On the other hand, in order to get a high accuracy within the knn classifier, we introduce a metric-learning method which can calculate a more specific distance model according to each component learners with a high diversity. In this paper. a new Ensemble learning algorithm which is based on a metric-learning knn classifier is proposed In detail, in ensembling procedure we use a perturbation which fliters the input attributes and then randomly picks the filtered attributes out to form several component learners; In metric-learning procedure we use a Neighborhood Component Analysis(NCA) method to calculate the optime metric. A large emperical study show that this algorithm has a better performance compared to the traditional knn, other metric-learning algorithms or ensemble learning algorithms Keywords: Data Mining, MetricLearning: NearestNeighbor Classifier; EnsembleLearning 作者简介: 于飞,男,1984年生,硕士研究生,主婁硏究方向是数据挖掘。

...展开详情
试读 7P 论文研究-基于距离学习的集成KNN分类器 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于距离学习的集成KNN分类器 .pdf 16积分/C币 立即下载
    1/7
    论文研究-基于距离学习的集成KNN分类器 .pdf第1页
    论文研究-基于距离学习的集成KNN分类器 .pdf第2页
    论文研究-基于距离学习的集成KNN分类器 .pdf第3页

    试读已结束,剩余4页未读...

    16积分/C币 立即下载 >