基于Spark框架的高效KNN中文文本分类算法

针对K-最近邻（KNN）分类算法时间复杂度与训练样本数量成正比而导致的计算量大的问题以及当前大数据背景下面临的传统架构处理速度慢的问题,提出了一种基于Spark框架与聚类优化的高效KNN分类算法。该算法首先利用引入收缩因子的优化K-medoids聚类算法对训练集进行两次裁剪;然后在分类过程中迭代K值获得分类结果,并在计算过程中结合Spark计算框架对数据进行分区迭代实现并行化。实验结果表明,在不同数据集中传统K-最近邻算法、基于K-medoids的K-最近邻算法所耗费时间是所提Spark框架下的K-最近邻算法的3.92~31.90倍,所提算法具有较高的计算效率,相较于Hadoop平台有较好的加速比,可有效地对大数据进行分类处理。     

基于改进AP选择和K最近邻法算法的室内定位技术

针对复杂的室内环境和在传统K最近邻法（KNN）算法中认为信号差相等时物理距离就相等两个问题,提出了一种新的接入点（AP）选择方法和基于缩放权重的KNN室内定位算法。首先,改进AP的选择方法,使用箱形图过滤接收信号强度（RSS）的异常值,初步建立指纹库,剔除指纹库中丢失率高的AP,使用标准偏差分析RSS的变化,选择干扰较小的前n个AP;其次,在传统的KNN算法中引入缩放权重,构建一个基于RSS的缩放权重模型;最后,计算出获得最小有效信号距离的前K个参考点坐标,得到未知位置坐标。定位仿真实验中,仅对AP选择方法进行改进的算法平均定位误差比传统的KNN算法降低了21.9%,引入缩放权重算法的平均定位误差为1.82 m,比传统KNN降低了53.6%。     

分布熵惩罚的支持向量数据描述

针对支持向量数据描述（SVDD）对惩罚参数相当敏感的问题,提出一种新颖的异常检测方法,称为分布熵惩罚的支持向量数据描述（DEP-SVDD）。首先,将正常样本作为数据的全局分布,并在高斯核空间中定义每个样本点与正常样本分布中心的距离度量;然后,基于该距离设计评估样本点属于正常或异常样本的概率;最后,利用此概率构造基于分布熵的惩罚度以对相应的样本进行惩罚。在9个真实数据集上,将所提方法与SVDD、密度权的支持向量数据描述 （DW-SVDD）、位置正则的支持向量数据描述（P-SVDD）、K最近邻（KNN）和孤立森林（iForest）算法进行对比实验,结果表明DEP-SVDD在6个数据集上获得了最高的分类精度,可见相较于多种异常检测方法,DEP-SVDD在异常检测中具有更好的性能优势。     

基于谱回归核判别分析的候机楼室内快速定位算法

针对机场候机楼客流量大、室内环境复杂多变的特点，提出了一种基于谱回归核判别分析（SRKDA）的室内定位算法。在离线阶段，采集已知位置的接收信号强度（RSS）数据，使用SRKDA算法提取原始位置指纹（OLF）的非线性特征生成新的特征指纹库；在线阶段，先使用SRKDA对待定位点的RSS数据进行处理，进而使用加权K最近邻（WKNN）算法进行位置估计。定位仿真实验中，在两个不同的定位场景中，所提算法在1.5 m定位精度下的误差累积分布函数（CDF）和定位准确率分别达到91.2%和88.25%，相对于核主成分分析法（KPCA）+WKNN模型分别提高了16.7个百分点和18.64个百分点，相对于KDA+WKNN模型分别提高了3.5个百分点和9.07个百分点；在大量离线样本（大于1100条）的情况下，该算法数据处理时间远小于KPCA和KDA。实验结果表明，所提算法能够提高室内定位精度，同时节省了数据处理时间，提高了定位效率。     

基于主成分分析和K近邻的文件类型识别算法

为解决基于文件后缀名和文件特征标识识别文件类型误判率较高的问题,在基于文件内容识别文件类型的算法基础上,提出主成分分析（PCA）和K近邻（KNN）算法相结合的文件类型识别算法。首先,使用PCA方法对样本预处理以降低样本空间的维数;然后,对降维后的训练样本集进行聚类处理,即用聚类质心代表每种类型的文件;最后,针对训练样本分布不均匀可能造成的分类误差,提出基于距离加权的KNN算法。实验结果表明,改进算法在样本数较多的情况下,能降低分类的计算复杂度,并保持了较高的识别正确率;而且该算法不依赖文件类型的特征标识,应用范围更为广泛。     

参数独立的加权局部均值伪近邻分类算法

针对局部均值伪近邻（LMPNN）算法对k值敏感且忽略了每个属性对分类结果的不同影响等问题,提出了一种参数独立的加权局部均值伪近邻分类（PIW-LMPNN）算法。首先,利用差分进化算法的最新变体——基于成功历史记录的自适应参数差分进化（SHADE）算法对训练集样本进行优化,从而得到最佳k值和一组与类别相关的最佳权重;其次,计算样本间的距离时赋予每类的每个属性不同的权重,并对测试集样本进行分类。在15个实际数据集上进行了仿真实验,并把所提算法与其他8种分类算法进行了比较,实验结果表明,所提算法的分类准确率和F1值分别最大提高了约28个百分点和23.1个百分点;同时Wilcoxon符号秩检验、Friedman秩方差检验以及Hollander-Wolfe两处理的比较结果表明,所提出的改进算法在分类精度以及k值选择方面相较其他8种分类算法具有明显优势。     

基于云平台的任务性能采集和分类方法

由于用户在实际使用云平台时,很难确定云平台的云主机类型,所以造成了云平台资源利用率低下的问题。许多典型的解决资源利用率低下的方法,都是从云提供商的角度优化放置算法,而用户选择将限制资源利用率增加;也有一些方法采用云平台下的任务性能短时间采集并预测,但会降低任务分类的准确性。为了达到提高云平台资源利用率、简化用户操作的目的,首先提出一种多属性的任务性能采集工具Lbenchmark,全面采集任务的性能特征,和Ganglia相比负载降低了50%以上。然后,利用该性能数据,提出一种基于权值可配的多KD树-K最近邻（KNN）应用性能分类算法,挑选适合参数建立多个基于KD树的KNN分类器,通过交叉验证方法调整每个属性在不同分类器的权重,进行选举分类。实验结果表明,所提算法与传统的KNN相比,计算量明显提高了约10倍以上,而准确性平均提高约10%。该算法可利用数据特征映射将资源建议提供给用户和云提供商,进而提高云平台整体的利用率。     

基于代表的留一法集成学习分类

为应对抽样不均匀带来的影响,以基于代表的分类算法为基础,提出一种用于符号型数据分类的留一法集成学习分类算法（LOOELCA）。首先采用留一法获得n个小训练集,其中n为初始训练集大小。然后使用每个训练集构建独立的基于代表的分类器,并标注出分类错误的分类器及对象。最后,标注分类器和原始分类器形成委员会并对测试集对象进行分类。如委员会表决一致,则直接给该测试对象贴上类标签;否则,基于k最近邻（kNN）算法并利用标注对象对测试对象分类。在UCI标准数据集上的实验结果表明,LOOELCA与基于代表的粗糙集覆盖分类（RBC-CBNRS）算法相比,精度平均提升0.35~2.76个百分点,LOOELCA与ID3、J48、Naïve Bayes、OneR等方法相比也有更高的分类准确率。     

基于多源信息相似度的微博用户推荐算法

针对传统的协同过滤（CF）推荐算法中存在的数据稀疏性和推荐准确率不高的问题,提出了基于多源信息相似度的微博用户推荐算法（MISUR）。首先,根据微博用户的标签信息运用K最近邻（KNN）算法对用户进行分类;然后,对得到的每个类中的用户分别计算其多源信息（微博内容、交互关系和社交信息）的相似度;其次,引入时间权重和丰富度权重计算多源信息的总相似度,并根据其大小进行TOP-N用户推荐;最后,在并行计算框架Spark上进行实验。实验结果表明,MISUR算法与CF算法和基于多社交行为的微博好友推荐算法（MBFR）相比,在准确率、召回率和效率方面都有较大幅度的提升,说明了MISUR算法的有效性。     

基于遗传进化的最近邻聚类算法及其应用

提出了基于遗传进化的最近邻聚类算法，该算法结合了遗传算法（GA）与最近邻聚类算法（NN）。对要进行分类的样本和特征量进行优化选取，去除位于类交界的模糊样本，并对样本分类有效的特征量进行放大，对不利于样本分类的特征量进行抑制，从而提高了样本分类的精度，将该算法应用于抽水蓄能发电机组的工况分类，大大提高了机组工况的识别效果，验证了基于遗传算法的最近邻聚类算法的有效性。     

基于知识块摘要和词转移距离的高效司法文档分类

随着全国司法机关智能化建设的深入推进,通过信息化建设应用所积累的海量司法文书为开展司法智能服务提供了司法数据分析基础。通过司法文书的相似性分析实现类案推送,可以为司法人员提供智能辅助办案决策支持,从而提高办案的质量和效率。针对面向通用领域的文本分类方法因没有考虑特定司法领域文本的复杂结构和知识语义而导致司法文本分类的效能低问题,提出一种基于司法知识块摘要和词转移距离（WMD）的高效司法文档分类方法。首先为司法文书构建领域本体知识模型,进而基于领域本体,利用信息抽取技术获取司法文档中核心知识块摘要;然后基于司法文本的知识块摘要利用WMD进行司法文档相似度计算;最后利用K最近邻算法进行司法文本分类。以两个典型罪名的案件文档集作为实验数据,与传统的WMD文档相似度计算方法进行对比,实验结果表明,所提方法能明显提高司法文本分类的正确率（分别有5.5和9.9个百分点的提升）,同时也降低了文档分类所需的时间（速度分别提升到原来的52.4和89.1倍）。     

基于复杂网络描述的图像深度卷积分类方法

为了在不增加较多计算量的前提下,提高卷积网络模型用于图像分类的正确率,提出了一种基于复杂网络模型描述的图像深度卷积分类方法。首先,对图像进行复杂网络描述,得到不同阈值下的复杂网络模型度矩阵;然后,在图像度矩阵描述的基础上,通过深度卷积网络得到特征向量;最后,根据得到的特征向量进行K近邻（KNN）分类。在ILSVRC2014数据库上进行了验证实验,实验结果表明,所提出的模型具有较高的正确率和较少的迭代次数。     

基于多目标骨架粒子群优化的特征选择算法

针对在分类问题中,数据之间存在大量的冗余特征,不仅影响分类的准确性,而且会降低分类算法执行速度的问题,提出了一种基于多目标骨架粒子群优化（BPSO）的特征选择算法,以获取在特征子集个数与分类精确度之间折中的最优策略。为了提高多目标骨架粒子群优化算法的效率,首先使用了一个外部存档,用来引导粒子的更新方向;然后通过变异算子,改善粒子的搜索空间;最后,将多目标骨架粒子群算法应用到特征选择问题中,并利用K近邻（KNN）分类器的分类性能和特征子集的个数作为特征子集的评价标准,对UCI数据集以及基因表达数据集的12个数据集进行实验。实验结果表明,所提算法选择的特征子集具有较好的分类性能,最小分类错误率最大可以降低7.4%,并且分类算法的执行时间最多能缩短12 s,能够有效提高算法的分类性能与执行速度。     

多子域隔离学习组合决策用于不均衡样本

为进一步弱化数据不均衡对分类算法的束缚,从数据集区域分布特性着手,提出了不均衡数据集上基于子域学习的复合分类模型。子域划分阶段,扩展支持向量数据描述（SVDD）算法给出类的最小界定域,划分出域内密集区与域外稀疏区。借鉴不同类存在相似样本的类重叠概念,对边界样本进行搜索,组合构成重叠域。子域清理阶段,基于邻近算法（KNN）的邻近性假设,结合不同域的密疏程度,设置样本有效性参数,对域内样本逐个检测以清理噪声。各子域隔离参与分类建模,按序组合产生出用于不均衡数据集的复合分类器CCRD。在相似算法对比以及代价敏感MetaCost对比中,CCRD对正类的正确分类改善明显,且未加重负类误判;在SMOTE抽样比较中,CCRD改善了负类的误判情形,且未影响正类的正确分类;在五类数据集的逐个比较中,CCRD分类性能均有提升,在Haberman_sur的正类分类性能提升上尤为明显。结果表明,基于子域学习的复合分类模型的分类性能较好,是一种研究不均衡数据集的较有效的方法。     

基于深度学习的安卓恶意应用检测

针对传统安卓恶意程序检测技术检测准确率低,对采用了重打包和代码混淆等技术的安卓恶意程序无法成功识别等问题,设计并实现了DeepDroid算法。首先,提取安卓应用程序的静态特征和动态特征,结合静态特征和动态特征生成应用程序的特征向量;然后,使用深度学习算法中的深度置信网络（DBN）对收集到的训练集进行训练,生成深度学习网络;最后,利用生成的深度学习网络对待测安卓应用程序进行检测。实验结果表明,在使用相同测试集的情况下,DeepDroid算法的正确率比支持向量机（SVM）算法高出3.96个百分点,比朴素贝叶斯（Naive Bayes）算法高出12.16个百分点,比K最邻近（KNN）算法高出13.62个百分点。DeepDroid算法结合了安卓应用程序的静态特征和动态特征,采用了动态检测和静态检测相结合的检测方法,弥补了静态检测代码覆盖率不足和动态检测误报率高的缺点,在特征识别的部分采用DBN算法使得网络训练速度得到保证的同时还有很高的检测正确率。     

结合局部敏感哈希的k近邻数据填补算法

k近邻(kNN)算法是缺失数据填补的常用算法,但由于需要逐个计算所有记录对之间的相似度,因此其填补耗时较高。为提高算法效率,提出结合局部敏感哈希(LSH)的kNN数据填补算法LSH-kNN。首先,对不存在缺失的完整记录进行局部敏感哈希,为之后查找近似最近邻提供索引;其次,针对枚举型、数值型以及混合型缺失数据分别提出对应的局部敏感哈希方法,对每一条待填补的不完整记录进行局部敏感哈希,按得到的哈希值找到与其疑似相似的候选记录;最后在候选记录中通过逐个计算相似度来找到其中相似程度最高的k条记录,并按照kNN算法对不完整记录进行填补。通过在4个真实数据集上的实验表明,结合局部敏感哈希的kNN填补算法LSH-kNN相对经典的kNN算法能够显著提高填补效率,并且保持准确性基本不变。