SVM-KNN分类算法研究

SVM-KNN分类算法是一种将支持向量机（SVM）分类和最近邻（NN）分类相结合的新分类方法。针对传统SVM分类器中存在的问题,该算法通过支持向量机的序列最小优化（SMO）训练算法对数据集进行训练,将距离差小于给定阈值的样本代入以每类所有的支持向量作为代表点的K近邻分类器中进行分类。在UCI数据集上的实验结果表明,该分类器的分类准确率比单纯使用SVM分类器要高,它在一定程度上不受核函数参数选择的影响,具有较好的稳健性。     

一种基于划分的层次聚类算法

CURE算法是针对大规模数据聚类算法的典型代表。提出了一种新的算法K－CURE,该方法基于划分思想对CURE算法作了改进,同时给出了在聚类中剔除孤立点的时机选择方法。测试表明,改进后的算法效率明显高于原算法,且聚类效果良好。     

基于样本密度和分类误差率的增量学习矢量量化算法研究

作为一种简单而成熟的分类方法, K最近邻(K nearest neighbor, KNN)算法在数据挖掘、模式识别等领域获得了广泛的应用, 但仍存在计算量大、高空间消耗、运行时间长等问题. 针对这些问题, 本文在增量学习型矢量量化(Incremental learning vector quantization, ILVQ)的单层竞争学习基础上, 融合样本密度和分类误差率的邻域思想, 提出了一种新的增量学习型矢量量化方法, 通过竞争学习策略对代表点邻域实现自适应增删、合并、分裂等操作, 快速获取原始数据集的原型集, 进而在保障分类精度基础上, 达到对大规模数据的高压缩效应. 此外, 对传统近邻分类算法进行了改进, 将原型近邻集的样本密度和分类误差率纳入到近邻判决准则中. 所提出算法通过单遍扫描学习训练集可快速生成有效的代表原型集, 具有较好的通用性. 实验结果表明, 该方法同其他算法相比较, 不仅可以保持甚至提高分类的准确性和压缩比, 且具有快速分类的优势.     

基于支持向量机与反K近邻的分类算法研究

针对支持向量机在对样本进行分类时,决策超平面附近的点较易错分的问题,首先将反K近邻法引入分类问题,提出了反K近邻分类算法;然后,将支持向量机（SVM）与反K近邻分类算法（RKNN）相结合,提出了基于支持向量机与反K近邻的分类算法（SVM-RKNN）;最后,为了避免单一分类器可能存在的片面性问题,提出了基于SVM-RKNN的多特征融合分类方法。实验结果表明：SVM-RKNN分类算法的分类准确率比SVM方法平均提高了2.13%,而基于SVM-RKNN的多特征融合分类算法的分类准确率分别比SVM和SVM-RKNN算法平均提高了2.54%和0.41%。     

考虑局部均值和类全局信息的快速近邻原型选择算法

压缩近邻法是一种简单的非参数原型选择算法,其原型选取易受样本读取序列、异常样本等干扰.为克服上述问题,提出了一个基于局部均值与类全局信息的近邻原型选择方法.该方法既在原型选取过程中,充分利用了待学习样本在原型集中k个同异类近邻局部均值和类全局信息的知识,又设定原型集更新策略实现对原型集的动态更新.该方法不仅能较好克服读取序列、异常样本对原型选取的影响,降低了原型集规模,而且在保持高分类精度的同时,实现了对数据集的高压缩效应.图像识别及UCI（University of California Irvine）基准数据集实验结果表明,所提出算法集具有较比较算法更有效的分类性能.     

基于自然邻居和最小生成树的原型选择算法

K最近邻居是最流行的有监督分类算法之一。然而,传统的K最近邻居有两个主要的问题:参数K的选择以及在大规模数据集下过高的时间和空间复杂度需求。为了解决这些问题,提出了一种新的原型选择算法,它保留了一些对分类贡献很大的关键原型点,同时移除噪声点和大多数对分类贡献较小的点。不同于其他原型选择算法,该算法使用了自然邻居这个新的邻居概念来做数据预处理,然后基于设定的终止条件构建若干个最小生成树。基于最小生成树,保留边界原型,同时生成一些具有代表性的内部原型。基于UCI基准数据集进行实验,结果表明提出的算法有效地约简了原型的数量,同时保持了与传统KNN相同水平的分类准确率;而且,该算法在分类准确率和原型保留率上优于其他原型选择算法。     

有序规范实数对多相似度K最近邻分类算法

针对最近邻分类算法性能受到所采用的相似度或距离度量方法影响大，且难以选择最优的相似度或距离度量方法的问题，提出一种采用多相似度的基于有序规范实数对的K最近邻分类算法（OPNs-KNN）。首先，在机器学习领域中引入有序规范实数对（OPN）这一新的数学理论，利用多种相似度或距离度量方法将训练集和测试集中所有样本全部转换为OPN，使每个OPN均包含不同的相似度信息；然后再通过改进的最近邻算法对OPN进行分类，实现不同相似度或距离度量方法的结合与互补，从而提高分类性能。实验结果表明，在Iris、seeds等数据集上与距离加权K近邻规则（WKNN）等6种最近邻分类的改进算法相比，OPNs-KNN的分类准确率提高了0.29～15.28个百分点，验证了所提算法能大幅提升分类的性能。     

基于证据K-NN改进算法的水声目标识别

证据分类算法已广泛应用于目标识别当中。针对传统证据K近邻算法在近邻证据组合规则上的局限,研究一种新的基于PCR5规则的证据K近邻改进算法(IEK-NN)。首先在总样本集中随机重复采样来构造多个训练子集;然后在各训练子集中,利用目标数据与其近邻的特征距离来构造基本置信指派;最后利用证据推理中的PCR5规则对近邻证据进行融合,并根据融合结果以及所建立的分类规则判断目标的类别属性。通过水声目标实测数据实验,将IEK-NN与传统的证据近邻分类算法进行对比分析,结果表明新算法能有效提高识别的准确率。     

SDN中基于MS-KNN算法的LFA攻击检测方法

针对一种新型的DDoS攻击—链路泛洪攻击（link-flooding attack,LFA）难以检测的问题,提出了SDN中基于MS-KNN（mean shift-K-nearestneighbor）方法的LFA检测方法。首先通过搭建SDN实验平台,模拟LFA并构建LFA数据集;然后利用改进的加权欧氏距离均值漂移（mean shift,MS）算法对LFA数据集进行分类;最后利用K近邻（K-nearestneighbor,KNN）算法判断分类结果中是否具有LFA数据。实验结果表明,相较于KNN算法,利用MS-KNN不仅得到了更高的准确率,同时也得到了更低的假阳性率。     

基于ASM和K近邻算法的人脸脸型分类

针对人脸特征分类问题,提出一种基于主动形状模型(ASM)和K近邻算法的人脸脸型分类方法。将Hausdorff距离作为K近邻算法的距离函数,利用ASM算法提取待测图像的特征点,对点集进行归一化后计算人脸轮廓特征点与样本库中所有样本点集的Hausdorff距离,根据该距离值,通过K近邻算法实现待测图像的脸型分类。实验结果证明,该方法分类正确率高、速度快、易于实现。     

一种基于投票机制的代表点选择算法

代表点选择是面向数据挖掘与模式识别的数据预处理的重要内容之一，是提高分类器分类正确率和执行效率的重要途径。提出了一种基于投票机制的代表点选择算法，该算法能使所得到的代表点尽可能分布在类别边界上，且投票选择机制易于排除异常点，减少数据量，从而有利于提高最近邻分类器的分类精度和效率。通过与多个经典的代表点选择算法的实验比较分析，表明所提出的基于投票机制的代表点选择算法在提高最近邻分类器分类精度和数据降低率上都具有一定的优势。     

一种基于置信度的代表点选择算法

代表点选择是实现缩减数据集规模的有效途径,可以提高分类的准确率和执行效率.为此,通过引入分类置信度熵的概念,提出适应度评价函数,用于评估代表点的选择效果,以此找到最优的代表点集.该方法可与其他代表点选择方法结合,得到性能更优的代表点选择方法.与多个经典代表点选择方法进行实验比较,结果表明基于置信度的代表点选择方法在分类准确率和数据降低率上有一定优势.     

基于哈希技术和MapReduce的大数据集K-近邻算法

K-近邻是一种著名的分类算法。由于简单且易于实现,因此其被广泛应用于许多领域,如人脸识别、基因分类、决策支持等。然而,在大数据环境中,K-近邻算法变得非常低效,甚至不可行。针对这一问题,提出了一种基于哈希技术和MapReduce的大数据集K-近邻分类算法。为了验证算法的有效性,在4个大数据集上进行了实验,结果显示,在保持分类能力的前提下,所提算法可以大幅度地提高K-近邻算法的效率。     

基于模拟退火算法和最近邻分类器识别率的特征选择方法

为了提高分类器的识别率,提出一种基于模拟退火算法和最近邻类器识别率的特征选择方法。该方法采用特征度量中的准确性度量(分类器识别率),能直接评价特征组合的优劣,并结合改进的模拟退火算法使用,能确保收敛到近似全局最优解。仿真试验表明,该方法所求解的质量优于传统特征选择方法,并且有很强的噪声容忍性,有一定的工程实用价值。     

一种基于加权多代表点的层次聚类算法

CURE算法是一种凝聚的层次聚类算法,它首先提出了使用多代表点描述簇的思想。本文通过对已有的基于多代表点的层次聚类算法特点的分析,提出了一种新的基于多代表点的层次聚类算法WRPC。它使用了基于影响因子的簇代表点选取机制和基于k-近邻方法的小簇合并机制,可以发现形状、尺寸更为复杂的簇。实验结果表明,该算法在保证执行效率的情况下取得了更好的聚类效果。     

基于双向选择的伪近邻算法

针对伪近邻分类算法（LMPNN）对异常点和噪声点仍然敏感的问题,提出了一种基于双向选择的伪近邻算法（BS-PNN）。利用邻近性度量选取[k]个最近邻,让测试样本和近邻样本通过互近邻定义进行双向选择;通过计算每类中互近邻的个数及其局部均值的加权距离,从而得到测试样本到伪近邻的欧氏距离;利用改进的类可信度作为投票度量方式,对测试样本进行分类。BS-PNN算法在处理复杂的分类任务时,具有能够准确识别噪声点,降低近邻个数[k]的敏感性,提高分类精度等优势。在UCI和KEEL的15个实际数据集上进行仿真实验,并与KNN、WKNN、LMKNN、PNN、LMPNN、DNN算法以及P-KNN算法进行比较,实验结果表明,基于双向选择的伪近邻算法的分类性能明显优于其他几种近邻分类算法。     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

引入信息熵的CURE聚类算法

为了提高传统CURE(Clustering Using REpresentatives) 聚类算法的质量,引入信息熵对其进行改进。该算法使用K-means算法对样本数据集进行预聚类;采用基于信息熵的相似性度量,利用簇中的元素提供的信息度量不同簇之间的相互关系,并描述数据的分布;在高层、低层聚类阶段,采取不同的选取策略,分别选取相应的代表点。在UCI数据集和人造数据集上的实验结果表明,提出的算法在一定程度上提高了聚类的准确率,且在大型数据集上比传统CURE算法有着更高的聚类效率。