一种快速KNN文本分类算法

KNN(K-Nearest Neighbor)是向量空间模型中最好的文本分类算法之一。但是,当样本集较大以及文本向量维数较多时,KNN算法分类的效率就会大大降低。该文提出了一种提高KNN分类效率的改进算法。算法在训练过程中计算出各类文本的分布范围,在分类过程中,根据待分类文本向量在样本空间中的分布位置,缩小其K最近邻搜索范围。实验表明改进的算法可以在保持KNN分类性能基本不变的情况下,显著提高分类效率。     

基于K-均值聚类的小样本集KNN分类算法

KNN及其改进算法进行分类时,如样本集中、样本过少或各类样本的密度差异较大,都将会影响最后的分类精度。提出一种基于聚类技术的小样本集KNN分类算法。通过聚类和剪理,形成各类的样本密度接近的新的样本集,并利用该新样本集对类标号未知数据对象进行类别标识。通过使用标准数据集的测试,发现该算法能够提高KNN的分类精度,取得了较满意的结果。     

基于FLANN改进的KNN医疗分类算法

本文通过研究KNN（K-最近邻）算法在疾病预测领域的使用与分析,总结出KNN的2点不足,针对不足进行相应改进并提出F_KNN（循环最近邻搜索）算法：1）针对KNN计算量大、效率低下的缺点,本文采用FLANN（快速最近邻搜索）循环搜索与待测样本距离最近的点,记录若干个最近邻点作为最近邻点子集,利用此子集取代全集对待测样本进行计算,可以降低计算量,极大地提高了KNN算法效率;2）针对KNN难以对高维数据集分类的缺点,本文采用AHP（层次分析法）对样本的特征属性进行相关性研究,使用合适的参数分配权重,提高了KNN算法准确率。本文采用一组脑中风数据集对优化后的算法进行实验,实验结果表明,F_KNN准确率达96.2%。与传统KNN相比,F_KNN提高了分类性能且极大地提高了算法效率。在处理高维且较大的数据集时,F_KNN算法优势明显,具有较好的应用前景。     

基于K-Medoids聚类的改进KNN文本分类算法

为有效提高传统KNN算法(K最近邻算法)在海量数据的分类效率,分析传统KNN算法的分类过程,提出基于K-Medoids聚类的改进KNN算法。利用K-Medoids算法对文本训练集进行聚类,把文本训练集分成相似度较高的簇;根据待分类文本与簇的相对位置,对文本训练集进行裁剪,解决传统KNN算法在文本训练集过大时速度慢的问题。分析与实验结果表明,该裁剪方法能够合理有效地裁剪文本训练集,提高了KNN算法的运行效率和分类能力。     

基于Spark的大规模文本k-means并行聚类算法

互联网文本数据量的激增使得对其作聚类运算的处理时间显著加长,虽有研究者利用Hadoop架构进行了k-means并行化研究,但由于很难有效满足k-means需要频繁迭代的特点,因此执行效率仍然不能让人满意。该文研究提出了基于新一代并行计算系统Spark的k-means文本聚类并行化算法,利用RDD编程模型充分满足了k-means频繁迭代运算的需求。实验结果表明,针对同一聚类文本大数据集和同样的计算环境,基于Spark的k-means文本聚类并行算法在加速比、扩展性等主要性能指标上明显优于基于Hadoop的实现,因此能更好地满足大规模文本数据挖掘算法的需求。     

基于粗糙集的快速KNN文本分类算法

传统K最近邻一个明显缺陷是样本相似度的计算量很大,在具有大量高维样本的文本分类中,由于复杂度太高而缺乏实用性。为此,将粗糙集理论引入到文本分类中,利用上下近似概念刻画各类训练样本的分布,并在训练过程中计算出各类上下近似的范围。在分类过程中根据待分类文本向量在样本空间中的分布位置,改进算法可以直接判定一些文本的归属,缩小K最近邻搜索范围。实验表明,该算法可以在保持K最近邻分类性能基本不变的情况下,显著提高分类效率。     

Spark框架结合分布式KNN分类器的网络大数据分类处理方法

针对现有大数据分类方法难以满足大数据应用中时间和储存空间的限制,提出了一种基于Apache Spark框架的大数据并行多标签K最近邻分类器设计方法。为了通过使用其他内存操作来减轻现有MapReduce方案的成本消耗,首先,结合Apache Spark框架的并行机制将训练集划分成若干分区;然后在Map阶段找到待预测样本每个分区的K近邻,进一步在reduce阶段根据map阶段的结果确定最终的K近邻;最后并行地对近邻的标签集合进行聚合,通过最大化后验概率输出待预测样本的目标标签集合。在PokerHand等四个大数据分类数据集上进行实验,提出方法取得了较低的汉明损失,证明了其有效性。     

用于WEB文档分类的并行KNN算法

针对WEB文档分类中KNN算法计算复杂度高的缺点,不同于以往从减少训练样本集大小和采用快速算法角度来降低KNN算法的计算复杂度,从并行的角度出发,提出一种在Hyper-cube SIMD模型上的并行算法,其关键部分的时间计算复杂度从O（n²）降为O（log（n））,该算法与传统的串行算法相比,能显著地提高分类速度。     

一种改进的KNN文本分类

在文本分类中,文本特征空间维数巨大以及训练样本分布不均衡等问题影响分类性能。针对这个问题,提出一种改进的KNN分类方法。利用隐含语义分析方法对特征样本空间进行降维处理;利用基于样本密度的改进的KNN分类器进行分类。实验结果表明提出的方法能够收到较好的分类效果。     

基于Spark平台的并行KNN异常检测算法

随着大数据时代的到来,异常检测受到了广泛关注。针对传统KNN异常检测算法处理速度和计算资源的瓶颈,以及Hadoop平台上的MapReduce不能友好支持迭代计算和基于内存计算等问题,提出了一种基于Spark平台的并行KNN异常检测算法。该算法首先对数据集进行分区和广播,然后用map函数计算数据集在每个分区的K近邻,使用reduce函数归并map函数的输出计算全局K近邻得到异常度,将异常度前n个对象视为异常。与传统KNN异常检测算法相比,在保证检测精度的前提下该算法的性能与计算资源呈近似线性关系;与其他并行异常检测算法相比,该算法无需额外扩展数据,支持迭代,而且通过在内存中缓存中间结果来减少I/O花销。实验结果证明,该算法可以提高KNN算法在大规模数据上的异常检测效率。     

结合属性值贡献度与平均相似度的KNN改进算法

与传统的K-近邻算法不同,提出了一种结合属性值贡献度与平均相似度的KNN改进算法。首先考虑测试样本与相似样本点间的平均相似度,其次考虑不同类别中的相似样本点的个数,最后还考虑与相似样本相同的属性值对类别的贡献度。在蘑菇数据集上进行实验结果表明,改进后的KNN分类算法的准确率比传统的K-近邻分类算法的准确率更高。     

基于熵权的K最临近算法改进

维度灾难直接影响到K最临近算法（KNN）的效率和准确率,将信息论中的信息熵理论与KNN算法结合起来,用信息熵理论进行属性约简,并根据特征属性与分类的相关度来确定各属性的权限,从而建立相关度与权重的内在联系。仿真实验表明,与传统的KNN相比,基于熵权的KNN改进方法在保持分类效率的情况下,使分类器的准确率得到了极大的提高。     

基于Storm的流数据KNN分类算法的研究与实现

KNN算法是一种简单、有效且易于实现的分类算法,可用于类域较大的分类。近年来对KNN算法的研究偏向于静态大数据集,不过,在越来越多的情况下要用KNN算法在线实时处理流数据。考虑到流式数据流量大,连续且快速,不易存储和恢复等特性,以及流处理系统Storm对流数据处理具有实时性、可靠性的特点,提出了基于Storm的流数据KNN分类算法,该算法首先对整个样本集进行划分,形成多个片集,然后计算出待分类向量在各片集上的[K]近邻,最后再将所有片集[K]近邻归约得出整体[K]近邻,实现待分类向量的分类。实验结果表明,基于Storm的流数据KNN分类算法能够满足大数据背景下对流数据分类的高吞吐量、可扩展性、实时性和准确性的要求。     

简化的粒子群优化快速KNN分类算法

提出了一种有效的k近邻分类文本分类算法,即SPSOKNN算法,该算法利用粒子群优化方法的随机搜索能力在训练集中随机搜索.在搜索k近邻的过程中,粒子群跳跃式移动,掠过大量不可能成为k近邻的文档向量,并且去除了粒子群进化过程中粒子速度的影响,从而可以更快速地找到测试样本的k个近邻.通过验证算法的有效性表明,在查找k近邻相同时,SPOSKNN算法的分类精度高于基本KNN算法。     

基于VPRS理论的一种混合分类算法

在文本分类领域中,KNN与SVM算法都具有较高的分类准确率,但两者都有其内在的缺点,KNN算法会因为大量的训练样本而导致计算量过大;SVM算法对于噪声数据过于敏感,对分布在分类超平面附近的数据点无法进行准确的分类,基于此提出一种基于变精度粗糙集理论的混合分类算法,该算法能够充分利用二者的优势同时又能克服二者的弱点,最后通过实验证明混合算法能够有效改善计算复杂度与分类精度。     

Spark框架优化的大规模谱聚类并行算法

为解决谱聚类在大规模数据集上存在的计算耗时和无法聚类等性能瓶颈制约,提出了基于Spark技术的大规模数据集谱聚类的并行化算法。首先,通过单向循环迭代优化相似矩阵的构建,避免重复计算;然后,通过位置变换和标量乘法替换来优化Laplacian矩阵的构建与正规化,降低存储需求;最后,采用近似特征向量计算来进一步减少计算量。不同测试数据集上的实验结果表明：随着测试数据集的规模增加,所提算法的单向循环迭代和近似特征值计算的运行时间呈线性增长,增长缓慢,其近似特征向量计算与精确特征向量计算取得相近的聚类效果,并且算法在大规模数据集上表现出良好的可扩展性。在获得较好的谱聚类性能的基础上,改进算法提高了运行效率,有效缓解了谱聚类的计算耗时及无法聚类问题。     

基于余弦距离的局部敏感哈希的KNN算法在中文文本上的快速分类

文本分类是文本挖掘中最重要的研究内容之一。为了克服目前以距离衡量的近似分类算法在海量数据下耗费大量时间的缺陷,提出了结合基于余弦距离的局部敏感哈希的方式将KNN算法在TF-IDF下对中文文本进行快速分类。同时结合文本数据的特性给出了不同的哈希函数级联方式分别进行实验。在实验过程采用了布尔向量的方式规避重复访问,使分类的结果在可以允许的范围内,分类速度比原始KNN提高了许多。     

Spark下的并行多标签最近邻算法

随着大数据时代的到来,大规模多标签数据挖掘方法受到广泛关注。多标签最近邻算法MLKNN是一种简单高效、应用广泛的多标签分类方法,其分类精度在很多应用中都高于其他常见的多标签学习方法。然而随着需要处理的数据规模越来越大,传统串行ML-KNN算法已经难以满足大数据应用中时间和存储空间上的限制。结合Spark的并行机制和其基于内存的迭代计算特点,提出了一种基于Spark并行框架的ML-KNN算法SML-KNN。在Map阶段分别找到待预测样本每个分区的K近邻,随后Reduce阶段根据每个分区的近邻集合确定最终的K近邻,最后并行地对近邻的标签集合进行聚合,通过最大化后验概率准则输出待预测样本的目标标签集合。串行和并行环境下的对比实验结果表明,SML-KNN在保证分类精度的前提下性能与计算资源呈近似线性关系,提高了ML-KNN算法对大规模多标签数据的处理能力。     

一种基于Canopy和粗糙集的CRS-KNN文本分类算法

针对KNN算法的分类效率随着训练集规模和特征维数的增加而逐渐降低的问题,提出了一种基于Canopy和粗糙集的CRS-KNN（Canopy Rough Set-KNN）文本分类算法。算法首先将待处理的文本数据通过Canopy进行聚类,然后对得到的每个类簇运用粗糙集理论进行上、下近似分割,对于分割得到的下近似区域无需再进行分类,而通过上、下近似作差所得的边界区域数据需要通过KNN算法确定其最终的类别。实验结果表明,该算法降低了KNN算法的数据计算规模,提高了分类效率。同时与传统的KNN算法和基于聚类改进的KNN文本分类算法相比,准确率、召回率和[F1]值都得到了一定的提高。