Basic Tenets of Classification Algorithms K-Nearest-Neighbor, Support Vector Machine, Random Forest and Neural Network: A Review

In this paper, sixty-eight research articles published between 2000 and 2017 as well as textbooks which employed four classification algorithms: K-Nearest-Neighbor (KNN), Support Vector Machines (SVM), Random Forest (RF) and Neural Network (NN) as the main statistical tools were reviewed. The aim was to examine and compare these nonparametric classification methods on the following attributes: robustness to training data, sensitivity to changes, data fitting, stability, ability to handle large data sizes, sensitivity to noise, time invested in parameter tuning, and accuracy. The performances, strengths and shortcomings of each of the algorithms were examined, and finally, a conclusion was arrived at on which one has higher performance. It was evident from the literature reviewed that RF is too sensitive to small changes in the training dataset and is occasionally unstable and tends to overfit in the model. KNN is easy to implement and understand but has a major drawback of becoming significantly slow as the size of the data in use grows, while the ideal value of K for the KNN classifier is difficult to set. SVM and RF are insensitive to noise or overtraining, which shows their ability in dealing with unbalanced data. Larger input datasets will lengthen classification times for NN and KNN more than for SVM and RF. Among these nonparametric classification methods, NN has the potential to become a more widely used classification algorithm, but because of their time-consuming parameter tuning procedure, high level of complexity in computational processing, the numerous types of NN architectures to choose from and the high number of algorithms used for training, most researchers recommend SVM and RF as easier and wieldy used methods which repeatedly achieve results with high accuracies and are often faster to implement.

Nearest neighbor search algorithm based on multiple background grids for fluid simulation

The core of smoothed particle hydrodynamics （SPH） is the nearest neighbor search subroutine. In this paper, a nearest neighbor search algorithm which is based on multiple background grids and support variable smooth length is introduced. Through tested on lid driven cavity flow, it is clear that this method can provide high accuracy. Analysis and experiments have been made on its parallelism, and the results show that this method has better parallelism and with adding processors its accuracy become higher, thus it achieves that efficiency grows in pace with accuracy.

A Short-Term Traffic Flow Forecasting Method Based on a Three-Layer K-Nearest Neighbor Non-Parametric Regression Algorithm

Short-term traffic flow is one of the core technologies to realize traffic flow guidance. In this article, in view of the characteristics that the traffic flow changes repeatedly, a short-term traffic flow forecasting method based on a three-layer K-nearest neighbor non-parametric regression algorithm is proposed. Specifically, two screening layers based on shape similarity were introduced in K-nearest neighbor non-parametric regression method, and the forecasting results were output using the weighted averaging on the reciprocal values of the shape similarity distances and the most-similar-point distance adjustment method. According to the experimental results, the proposed algorithm has improved the predictive ability of the traditional K-nearest neighbor non-parametric regression method, and greatly enhanced the accuracy and real-time performance of short-term traffic flow forecasting.

基于K-Nearest Neighbor和神经网络的糖尿病分类研究

为实现糖尿病的早期筛查,提高对糖尿病分类的准确度,在研究有关糖尿病危险因素的基础上,增加糖化血红蛋白作为糖尿病早期筛查的特征之一。研究中选取与人类最为相似的食蟹猴作为研究对象,利用年龄、血压、腹围、BMI、糖化血红蛋白以及空腹血糖作为特征输入,将正常、糖尿病前期和糖尿病作为类别输出,利用K-Nearest Neighbor(KNN)和神经网络两种方法对其分类。发现在增加糖化血红蛋白作为分类特征之一时,KNN(K=3)和神经网络的分类准确率分别为81.8%和92.6%,明显高于没有这一特征时的准确率(68.1%和89.7%),KNN和神经网络都可以对食蟹猴数据进行分类和识别,起到早期筛查作用。

一种基于特征加权的K Nearest Neighbor算法

传统的KNN算法一般采用欧式距离公式度量两样本间的距离.由于在实际样本数据集合中每一个属性对样本的贡献作用是不尽相同的,通常采用加权欧式距离公式.笔者提出一种计算权重的方法,即基于特征加权KNN算法.经实验证明,该算法与经典的赋权算法相比具有较好的分类效果.

基于不规则区域划分方法的k-Nearest Neighbor查询算法

随着越来越多的数据累积,对数据处理能力和分析能力的要求也越来越高.传统k-Nearest Neighbor(k NN)查询算法由于其容易导致计算负载整体不均衡的规则区域划分方法及其单个进程或单台计算机运行环境的较低数据处理能力.本文提出并详细介绍了一种基于不规则区域划分方法的改进型k NN查询算法,并利用对大规模数据集进行分布式并行计算的模型Map Reduce对该算法加以实现.实验结果与分析表明,Map Reduce框架下基于不规则区域划分方法的k NN查询算法可以获得较高的数据处理效率,并可以较好的支持大数据环境下数据的高效查询.

Mapping aboveground biomass by integrating geospatial and forest inventory data through a k-nearest neighbor strategy in North Central Mexico

As climate change negotiations progress,monitoring biomass and carbon stocks is becoming an important part of the current forest research.Therefore,national governments are interested in developing forest-monitoring strategies using geospatial technology.Among statistical methods for mapping biomass,there is a nonparametric approach called k-nearest neighbor(kNN).We compared four variations of distance metrics of the kNN for the spatially-explicit estimation of aboveground biomass in a portion of the Mexican north border of the intertropical zone.Satellite derived,climatic,and topographic predictor variables were combined with the Mexican National Forest Inventory(NFI)data to accomplish the purpose.Performance of distance metrics applied into the kNN algorithm was evaluated using a cross validation leave-one-out technique.The results indicate that the Most Similar Neighbor(MSN)approach maximizes the correlation between predictor and response variables(r=0.9).Our results are in agreement with those reported in the literature.These findings confirm the predictive potential of the MSN approach for mapping forest variables at pixel level under the policy of Reducing Emission from Deforestation and Forest Degradation(REDD+).

Support Vector Machine-Based Fault Diagnosis of Power Transformer Using k Nearest-Neighbor Imputed DGA Dataset

Missing values are prevalent in real-world datasets and they may reduce predictive performance of a learning algorithm. Dissolved Gas Analysis (DGA), one of the most deployable methods for detecting and predicting incipient faults in power transformers is one of the casualties. Thus, this paper proposes filling-in the missing values found in a DGA dataset using the k-nearest neighbor imputation method with two different distance metrics: Euclidean and Cityblock. Thereafter, using these imputed datasets as inputs, this study applies Support Vector Machine (SVM) to built models which are used to classify transformer faults. Experimental results are provided to show the effectiveness of the proposed approach.

Pruned fuzzy K-nearest neighbor classifier for beat classification

Arrhythmia beat classification is an active area of research in ECG based clinical decision support systems. In this paper, Pruned Fuzzy K-nearest neighbor (PFKNN) classifier is proposed to classify six types of beats present in the MIT-BIH Arrhythmia database. We have tested our classifier on ~ 103100 beats for six beat types present in the database. Fuzzy KNN (FKNN) can be implemented very easily but large number of training examples used for classification can be very time consuming and requires large storage space. Hence, we have proposed a time efficient Arif-Fayyaz pruning algorithm especially suitable for FKNN which can maintain good classification accuracy with appropriate retained ratio of training data. By using Arif-Fayyaz pruning algorithm with Fuzzy KNN, we have achieved a beat classification accuracy of 97% and geometric mean of sensitivity of 94.5% with only 19% of the total training examples. The accuracy and sensitivity is comparable to FKNN when all the training data is used. Principal Component Analysis is used to further reduce the dimension of feature space from eleven to six without compromising the accuracy and sensitivity. PFKNN was found to robust against noise present in the ECG data.

Empirical Mode Decomposition-k Nearest Neighbor Models for Wind Speed Forecasting

Hybrid model is a popular forecasting model in renewable energy related forecasting applications. Wind speed forecasting, as a common application, requires fast and accurate forecasting models. This paper introduces an Empirical Mode Decomposition (EMD) followed by a k Nearest Neighbor (kNN) hybrid model for wind speed forecasting. Two configurations of EMD-kNN are discussed in details: an EMD-kNN-P that applies kNN on each decomposed intrinsic mode function (IMF) and residue for separate modelling and forecasting followed by summation and an EMD-kNN-M that forms a feature vector set from all IMFs and residue followed by a single kNN modelling and forecasting. These two configurations are compared with the persistent model and the conventional kNN model on a wind speed time series dataset from Singapore. The results show that the two EMD-kNN hybrid models have good performance for longer term forecasting and EMD-kNN-M has better performance than EMD-kNN-P for shorter term forecasting.

Nearest neighbor search algorithm for GBD tree spatial data structure

This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.

基于融合K-近邻算法的电压互感器在线监测方法

由于受工作时长和环境因素的影响,电容式电压互感器(capacitor voltage transformer,CVT)在运行过程中误差稳定性不高,易出现电能计量失准现象。为此,该文提出了一种基于融合K-近邻算法(fusion K-nearest neighbor algorithm,FKNN)的电压互感器在线评估方法。该方法利用互感器的历史运行数据构建虚拟标准器,通过改进K-近邻算法对互感器实时状态进行监测,实现对异常情况的报警。同时,提出了一种加权移动时间窗的方法,自适应更新异常阈值,有效削弱电网不平衡波动的影响。实验结果表明,该文方法能够准确监测互感器的0.2级误差漂移。

结合精英初始化和K近邻的蛇优化算法

蛇优化算法(SO)是一种受自然界中蛇生存行为启发产生的元启发式优化算法。原始蛇优化算法存在收敛速度慢、易陷入局部最优的问题,因此提出了一种结合精英初始化和K近邻的改进蛇优化算法(elite initia-lization and K-nearest neighbors improved snake optimizer,EKISO)。首先,为了提高初始种群质量,在种群初始化阶段提出精英初始化的方法,根据种群精英个体产生优质初始种群个体;其次,通过振荡因子优化螺旋觅食策略扩大全局勘探阶段的搜索范围、提高算法的局部逃逸能力;最后,在局部开发阶段提出K近邻思想的位置更新方法,增强种群个体之间的信息交互能力,从而加快收敛速度、提高收敛精度。利用14个经典测试函数和4个CEC2017测试函数将该方法与其他7种优化算法进行对比,证明EKISO收敛速度更快、精度更高且不易陷入局部最优。为了进一步验证EKISO的实用性与可行性,将EKISO应用于压力容器设计问题中,通过实验对比分析可知,EKISO在处理实际优化问题上具有一定的优越性。

基于组合加权k近邻分类的无线传感网络节点复制攻击检测方法

无线传感网络节点体积小,隐蔽性强,节点复制攻击检测的难度较大,为此提出一种基于组合加权k近邻分类的无线传感网络节点复制攻击检测方法。通过信标节点的空间位置数据与相距跳数得出各节点之间的相似程度,结合高斯径向基核函数求解未知节点的横轴、纵轴的空间坐标,确定各网络节点的空间位置;根据网络节点的属性特征与投票机制建立节点复制攻击模型,凭借组合加权k近邻分类法划分节点类型,并将结果传送至簇头节点,由簇头节点做出最后的仲裁,识别出节点复制攻击行为。仿真结果表明,所提方法的节点复制攻击检测率最大值为99.5%,最小值为97.9%,对节点复制攻击检测的耗时为5.41 s,通信开销数据包数量最大值为209个,最小值为81个。

基于数字孪生与k-近邻算法的车间设备运行状态预测研究

由于传统车间设备运行状态预测不能有效利用历史数据进行学习,实时响应能力有限,难以在复杂调度环境中取得良好效果,因此文章提出一种数字孪生与k-近邻算法相结合的车间设备运行状态预测模型。构建车间设备实体在信息空间的数字孪生模型,并建立设备实体与模型之间的映射关系,从而获取实时特征数据,即设备的运行状态特征数据。运用k-近邻算法计算实时特征数据与历史数据之间的欧几里得距离,即计算设备当前运行状态与历史已知状态的相似度,最终通过前k个距离所对应的设备历史运行状态数据,预测设备的当前运行状态。该模型的本质是通过数字孪生的实时数据采集,获取指定设备运行状态特征数据,运用k-近邻算法预测设备的实时运行状态。相较以往研究,本研究贡献在于提高设备实时运行状态预测的准确率。如果将数字孪生、k-近邻算法与具备自我学习能力的相关算法相结合,模型的预测效果会更好。

基于概率密度的自适应k近邻缺失值填充方法

基于k近邻的缺失值填充方法通常使用样本间的距离来度量样本的相似性,在计算距离时,没有区分样本各属性的权重,即所有属性对距离的贡献是一样的。然而,在非均匀分布的不平衡数据集中,样本的异质性往往体现在取值不常见的属性上,即样本之间的相似性受属性取值概率影响,此时用传统的距离公式来度量相似性是不够准确的。因此,文章针对非均匀分布的不平衡数据集提出了一种自适应k近邻缺失值填充方法(AkNNI):首先,引入属性的概率密度,动态调整各个属性的重要性,凸显稀疏值与缩小频繁值在距离计算上的贡献,从而更好地表达样本的异质性以及捕捉样本之间的相似性;然后,针对高缺失率下数据集中完备样本稀少的情况,综合考虑了样本的相似性和完整性,设计了新的k近邻的选择流程。实验选取了6个非均匀分布数据集,对比了AkNNI方法与其他5种经典填充方法的填充效果,验证了填充后的数据集在k近邻分类器的分类效果,深入探索了3种评估指标的相互关系。实验结果表明AkNNI方法具有更高的填充准确度和分类准确度:在6种缺失值填充算法中,AkNNI方法在各个数据集上取得的平均RMSE最低、平均皮尔逊相关系数最高以及平均分类准确率最高。同时,在高缺失率下,AkNNI方法在各个数据集上仍能保持较低的RMSE、较高的皮尔逊相关系数和较高的分类准确度。

基于IKNN和LOF的变压器回复电压数据清洗方法研究

基于回复电压极化谱提取特征参量是目前广泛应用的变压器油纸绝缘状态评估方法,但极化谱易受工况干扰、人工失误等因素影响而出现特征数据异常的情况,严重降低评估准确性。针对上述问题,该文提出了一种基于局部离群因子(LOF)和改进K最近邻(IKNN)的回复电压数据清洗方法。首先,选取回复电压极化谱的回复电压极大值Urmax、初始斜率Sr与主时间常数tcdom作为老化特征参量,并基于LOF算法对非标准极化谱中的异常特征量数据进行识别与筛除。其次,利用模糊C均值(FCM)聚类算法减小噪声点对KNN算法的干扰,并通过加权欧氏距离标度突出各特征量间的关联性,进而构建出基于IKNN的数据填补模型架构以实现特征缺失数据的填补。最后,代入多组实测数据验证所提数据清洗方法的实效性。结果表明,数据清洗后的状态评估准确率相较于原有数据上升了50%左右,有效提高了变压器回复电压数据质量,为准确感知变压器运行状况奠定坚实的基础。

基于密文KNN检索的室内定位隐私保护算法

在定位请求服务中,如何保护用户的位置隐私和位置服务提供商(Localization service provider,LSP)的数据隐私是关系到WiFi指纹定位应用的一个具有挑战性的问题。基于密文域的K-近邻(K-nearest neighbors,KNN)检索,本文提出了一种适用于三方的定位隐私保护算法,能有效提升对LSP指纹信息隐私的保护强度并降低计算开销。服务器和用户分别完成对指纹信息和定位请求的加密,而第三方则基于加密指纹库和加密定位请求,在隐私状态下完成对用户的位置估计。所提算法把各参考点的位置信息随机嵌入指纹,可避免恶意用户获取各参考点的具体位置;进一步利用布隆滤波器在隐藏接入点信息的情况下,第三方可完成参考点的在线匹配,实现对用户隐私状态下的粗定位,可与定位算法结合降低计算开销。在公共数据集和实验室数据集中,对两种算法的安全、开销和定位性能进行了全面的评估。与同类加密算法比较,在不降低定位精度的情况下,进一步增强了对数据隐私的保护。

基于AKNN异常检验与ADPC聚类的低压台区拓扑识别方法

低压台区拓扑信息的准确记录是进行台区线损分析、三相不平衡治理等工作的基础。针对目前拓扑档案排查成本高且效率低的问题,提出一种基于自适应k近邻(adaptive k nearest neighbor,AKNN)异常检验和自适应密度峰值(adaptive density peaks clustering,ADPC)聚类的低压台区拓扑识别方法。该方法利用动态时间弯曲(dynamic time warping,DTW)距离度量低压台区用户间电压序列的相似性,通过AKNN异常检验算法检验并校正异常的用户与变压器之间的关系(简称“户变关系”),在得到正确户变关系的基础上,采用ADPC聚类算法对台区内用户进行相位识别;最后,通过实际台区算例分析验证了该方法不需要人为设置参数,能有效实现低压台区的拓扑识别,具有较高的适用性与准确性。