GNG-SVM构架-基于生长型神经气的支持向量机队大数据集进行分类

GNG-SVM构架-基于生长型神经气的支持向量机队大数据集进行分类OndrejLinda,MilosManic摘要：在数据分类领域，支持向量机是一种很著名的技术。然而，由于训练过程的复杂性，导致SVM不适用于对大数据集进行分类。目前的解决方案就是对输入数据集进行抽样或者对其进行聚类。在另一方面，生长型神经气它可以学习拓扑型数据，是一种具有很好鲁棒性的聚类分析方法。它克服了在绝大多数聚类中需要预先知道聚类数目或者聚类半径的问题。该文提出了一种通过学习数据的拓扑结构解决大数据集分类问题。这种解决方案结合GNG和SVM，形成为大数据集分类的GNG-SVM框架。输入数据首先经过GNG进行预处理。通过拓扑网络的学习，构造了一个新的压缩的数据集。因为数据集的规模被明显减小了，处理过程所需要的内存消耗也明显的减少了。在人工合成的和机遇显示世界数据集上，GNG-SVM框架的性能得到了验证。关键字：数据分类，生长型神经气，大数据集，支持向量机引言数据分类和模式识别这些年被予以很高的重视[1]-[3],支持向量机(SVM)被证明是一种非常成功的数据分类工具[4],[5].在预先看不到的实例上，这种算法尽量找出不同类别之间的最大分界面。为了处理非线性可分问题，输入空间被核函数转换到一个特征空间[5].在训练阶段，标准支持向量机的解决方案的一个不足之处是需要很多的内存空间。这成为他在训练大样本时的重大需解决的问题[6],[7].因为训练的复杂程度直接取决于数据集的大小。因此，缩减数据集大小变得非常必要。传统的，这个问题通过各种各样的聚类或者抽样方法解决。抽样方法是选取可以代表元数据集合的子数据集[8][9].聚类方法通过把相似的实例聚合在一起，用以去除冗余的信息或者以之为蓝本建立聚类代替原数据集[7],[10],[11].这篇论文通过拓扑学习，研究数据集缩小的概率。拓扑信息对于SVM的训练是极其重要的。它描述了在输入空间中的数据集的密度和分布情况。这些知识被SVM用于构架一个理想的分类器。虽然数据集的大小被显著的减小，但该学习算法的分类精度被保存下来。前面介绍的GNG-SVM构架利用生长新神经气（GNG）算法，用以明显的减少输入样本集[12].GNG是一种基于增量向量的模型，不管是什么样维数的数据集，它都可以学习数据的拓扑机构。GNG对每个类的拓扑结构进行学习，然后从拓扑网络中抽取相关拓扑信息得到一个新的缩小的样本规模的训练集。这个小的样本集大体上反应了原数据集的分布状况。明显地，在缩小样本集的过程程中会有大量的信息损失。但这是为了问题复杂性的一个经过权衡的办法。进一步说，在训练过程，GNG算法本身中对于噪声有很强的鲁棒特性，在这种情况下可以提高分类性能。最后，在新的小规模数据集上训练SVM算法。在线性数据集合非线性数据集，GNG-SVM框架的性能得到了综合测试。下面为篇论文的组织方式：第二部分给出SVM的一个基本的概述。第三部分，提出GNG-SVM框架。第四部分用于讨论实验结果，第五部分提出一个最终结果。1背景概述1．1支持向量机支持向量机（SVMs）是一种应用很广泛的而且性能很好的分类器和回归分析方法[14],[15].它的主要优势是具有可靠地数学支撑。而且支持向量机时给予结构风险最小化的原则[4].在不同类别数据点之间构造最优分界面。在支持向量机理论中，构建最大分割面意味着分类器有跟强的泛化能力。对于一个数据集S,它由N个m维空间向量组成，这项空间向量属于两个不相交的类别组成，用li表示：{(,)|,{1,1},1,2...}miiiiSxlxRliN（1）在线性可分问题中，存在一个超平面由于确定一个最大分界面。这个超平面可以被看作是m维的带权重的向量iw，和一个标量偏移量组成：0Tiiwxb（2）构造一个拉格朗日乘子并且求解一组对偶问题求解：1111max()()2NNNiijijijiijWyyxx（3）约束条件为：100,1,2,...NiiiiyandCiN在这里1(,...,)N表示拉格朗日乘子中的一组向量。对于输入向量ix中，如果它的i不为0，则称之为支持向量（SVs），决策面仅仅由支持向量决定。另一句话说，剩余非支持向量都与最后的分类结果无关。例如：i的系数可以被二次方乘子技术或者序列最小优化学习(SMO)算法[16][17]确定。这个决策面被下列公式决定：isiiixSVwyx（5）1issixSVsvbbN（6）这里isv是数据集S中的支持向量，ssvN是这些支持向量的数目。目前有多种处理SVM大样本数据集的方法。训练任务可以划分为一系列子问题，然后分别处理这些子问题。分解算法或者SMO都是这种算法的应用[17]-[19].进一步而言，通过去除无关实例，数据集的大小可以被缩小。选择抽样，主动学习或者随机抽样都试图最大化学习性能而同时尽可能最小化输入数据集[8],[9].各种聚类方法可以用选取分界面处的相关数据实例或者构造数据点的模型[7],[10],[11].在线学习SVM或者增量SVMs提出来用于处理非静态数据[20][21].当需要处理新数据时，模型被有效地维护。1．2生长型神经气由Martinetz和Schulten提出的原来的神经气受到启发[22],Fritzke提出了生长型神经气[12]。它应用于聚类分析和增量学习.GNG克服了标准的自适应网络之中存在的问题。这中算法结合了生长型细胞结构的机制GCS和拓扑竞争学习Hebbian学习[23].CNG自动化机制中没有维数的限制，相反的他可以自我调节以适应局部维数和输入数据的密度。而基于GCS算法的更新策略，让它对于噪声和过度拟合有很强的鲁棒特性。GNG由一系列的处于更新状态的神经元组成。每个神经元组成，每个神经元都对应一个参考向量NiwR，其中N代表着向量的维数。输入空间中的神经元的位置由参考向量决定。而且，每一个神经元有一个连接相邻节点的无向边。这些边没有权重，仅仅用来决定网络的拓扑结构。因此，相邻的边不是由欧式距离而是由这些边之间的联通性决定的。每一次迭代，根据输入分布概率()P，可以描绘出输入信号。通过欧式距离，可以找出两个最近神经元。如果这样的神经元之间没有边连接，那么创造他们之间的一条新边。该神经元an的局部误差按照下面方法修改：2()aaaerrorerrorw（7）an的参考向量和他的拓扑网络结构中邻居的通过如下方式被修改:()aabawwew（8）(),()jjnjjawwewnn（9）,[0,1],bnbneeee（10）在这里,bnee都是修改权重的系数，表示与给定的神经元直接相连的神经元。算法开始的时候有两个随机产生的神经元。每次迭代一个新的神经元被加入都具有最高局部误差的地方，然后这个神经元的邻居有了最大局部误差,因此一个神经元被放在了一个并不能很好反应原数据集状况区域。一种边界年龄机制被应用于维护一个仅有的有效边界。每一次创造一个新的边界，都对他赋予一个为0的年龄。当加入一个获胜的神经元an，他的所有边都加1。每一次迭代，这些边都与建立的最大年龄maxa进行比较。所有的边界中年龄大于maxa的边界都将被移除，因此许多神经元是没有边的。GNG算法优于其他聚类方法，他不需要预先知道聚类的参数，例如在K-Means或者C-Means算法中那样[3][24]。在训练数据集中一个网络在不断地形成，直到一个具体的聚类标准被达到了。而且不像最近邻聚类或者抽样聚类那样，需要预先知道聚类半径。[3][11]。随着拓扑网络的不断增长，不断调整聚类半径。GNG算法中迭代的特性，使之适合于学习拓扑网络结构的大数据集。2GNG-SVM框架上文提到的GNG-SVM框架为大数据集分类构造了一个混合数据分类器，两类分类问题如同公式（1）所描述。一般而言一个机器学习问题可以用于判断多类问题。因此，（1）可以推广用来学习C类问题：{(,)|,{1,...,},1,2...}miiiiSxlxRlciN（11）这里m表示问题的维数。N表示训练的数据集合数目，ix和il是输入向量并且被分别标好了类别。多类分类的SVM的细节描述可以在文献[25]中找到。例如：多类分类器可以组合多个两类分类器或者将它转换文一个复杂的最优化问题。SVM的训练过程直接依赖于输入数据集合的规模大小。这导致SVM不适合处理大数据集问题。然而，缩减样本必须相关信息，尽量没有信息损失，这对于成功的训练样本集合时非常重要的。GNG-SVM框架由两个步骤组成。第一步是抽取多类GNG算法实例数据的拓扑结构。通过抽取拓扑信息原有的数据集被减少了。在第二步，在缩减后的数据集合上训练SVM分类器。步骤1.1：将训练数据集合S分割成C个子数据集iS，每个数据集包含一个类的实例：12{,,...,}csss（12）步骤1.2：构造C个实例的生长型神经气:12{,,...,}cGNGGNGGNG（13）步骤1.3：将每个子集iS分配给它对应的生长型神经气iGNG。步骤1.4：在训练子集iS上对训练每一个iGNG实例，直到达到某种收敛条件。步骤1.5：从收敛的iGNG实例中抽取拓扑信息这些拓扑信息被包含在一组参考向量iw中：12{,,...,}c（14）通过把第i类的类标分配给它对应的参考向量，把参考向量iW放入集合*iw中*1,2,...,{(,)}iijijNwwl（15）步骤1.7：创建一个新的输入集*S，通过将*iw组合起来。**1ciiSw（16）图表3可以看出，支持向量机最后得出的分类边界由两个类别组成。最优分类超平面由一条直线表现出来。一些点组成的训练用于描述分类分类的边界。做为一个比较，图3，b中的分类超平面，是由一个压缩后的样本集组成。原训练集中每个类别被压缩成只有20个节点。通过两个图的比较可以看出，当训练集规模大规模的减小时，分类超平面只有非常轻微的改变。3实验结果GNG-SVM的框架又两部分组成。首先数据集用过C++程序用GNG算法处理，用以压缩训练集。然后，这个压缩的训练集将被用于训练SMO支持向量机，这是一个weka上提供的组件。在这一部分，我们将分析实验数据和实验结果。首先GNG-SVM的性能将在模拟数据集和显示数据集中衡量。另外，训练时间和训练精度之间的关系将被仔细研究。GNG算法的参数在表一中都给出来了。这样参数可以让GNG算法得到较好的训练结果。SMO支持向量机算法将采用polynomial核函数，复杂的参数将被设定成1。1仿真数据首先，GNG-SVM的性能将在两个仿真数据集上进行衡量。这些生成的数据包含2维的数据，被分成了两个类别。每个类别都包含50000个实例样本。这些样本呈现高斯分布。第一组数据是线性可分，而第二组数据线性不可分。当每个类别中的节点数目达到50个时，GNG网络结束迭代。数据被随机分成10次，用于训练分类器。而50%的训练数据集被用于测试分类器。当训练集通过GNG算法被压缩，支持向量机将在新的训练集上训练。训练好的支持向量机分类器，将在50000个样本上测试。表2和3给出了算法的10次分类结果。本文提出算法在线性训练集上训练的分类器的分类性能非常好，近似于完美。然而在非线性数据集上，表现却差强人意，分类精度比传统的支持向量机分类器低了4%。然而训练集的规模比原来分类器的训练集规模小了将近500倍。B真实数据第二步，GNG-SVM将在真实训练集上测试，这些真实训练集的维度将会更高。两个真实训练集均来自UCI训练集。这两个训练集一个有10个属性，也就是说这个训练集的维度高达10维，其正负两类训练集的规模分别为12332和6688。另一个训练集有9个属性，也就是说这个训练集的维度有9维，该训练集包含43500个训练集。最开始，7个不同的训练集被包含在这个训练集中，80%的样本属于单一的一个类别。为了更好的测试基于生长型神经气的支持向量机的分类性能，剩下的6个类别被放在另一个类别里面。对于另一个训练集，它的正负两类的选择是基于