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.

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 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.

A Study of EM Algorithm as an Imputation Method: A Model-Based Simulation Study with Application to a Synthetic Compositional Data

Compositional data, such as relative information, is a crucial aspect of machine learning and other related fields. It is typically recorded as closed data or sums to a constant, like 100%. The statistical linear model is the most used technique for identifying hidden relationships between underlying random variables of interest. However, data quality is a significant challenge in machine learning, especially when missing data is present. The linear regression model is a commonly used statistical modeling technique used in various applications to find relationships between variables of interest. When estimating linear regression parameters which are useful for things like future prediction and partial effects analysis of independent variables, maximum likelihood estimation (MLE) is the method of choice. However, many datasets contain missing observations, which can lead to costly and time-consuming data recovery. To address this issue, the expectation-maximization (EM) algorithm has been suggested as a solution for situations including missing data. The EM algorithm repeatedly finds the best estimates of parameters in statistical models that depend on variables or data that have not been observed. This is called maximum likelihood or maximum a posteriori (MAP). Using the present estimate as input, the expectation (E) step constructs a log-likelihood function. Finding the parameters that maximize the anticipated log-likelihood, as determined in the E step, is the job of the maximization (M) phase. This study looked at how well the EM algorithm worked on a made-up compositional dataset with missing observations. It used both the robust least square version and ordinary least square regression techniques. The efficacy of the EM algorithm was compared with two alternative imputation techniques, k-Nearest Neighbor (k-NN) and mean imputation (), in terms of Aitchison distances and covariance.

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

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

A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

In this paper, a memetic algorithm with competition(MAC) is proposed to solve the capacitated green vehicle routing problem(CGVRP). Firstly, the permutation array called traveling salesman problem(TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor(k NN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search(VNS) framework and the simulated annealing(SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station(AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-ofexperiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.

AN EFFICIENT FAST ENCODING ALGORITHM FOR VECTOR QUANTIZATION

A fast encoding algorithm was presented which made full use of two characteristics of a vector, its sum and variance. In this paper, a vector was separated into two subvectors, one is the first half of the coordinates and the other contains the remaining coordinates. Three inequalities based on the characteristics of the sums and variances of a vector and its two subvectors were introduced to reject those codewords which are impossible to be the nearest codeword. The simulation results show that the proposed algorithm is faster than the improved equal average eaual variance nearest neighbor search (EENNS) algorithm.

Novel Apriori-Based Multi-Label Learning Algorithm by Exploiting Coupled Label Relationship

It is a key challenge to exploit the label coupling relationship in multi-label classification（MLC）problems.Most previous work focused on label pairwise relations,in which generally only global statistical information is used to analyze the coupled label relationship.In this work,firstly Bayesian and hypothesis testing methods are applied to predict the label set size of testing samples within their k nearest neighbor samples,which combines global and local statistical information,and then apriori algorithm is used to mine the label coupling relationship among multiple labels rather than pairwise labels,which can exploit the label coupling relations more accurately and comprehensively.The experimental results on text,biology and audio datasets shown that,compared with the state-of-the-art algorithm,the proposed algorithm can obtain better performance on 5 common criteria.

Research on Initialization on EM Algorithm Based on Gaussian Mixture Model

The EM algorithm is a very popular maximum likelihood estimation method, the iterative algorithm for solving the maximum likelihood estimator when the observation data is the incomplete data, but also is very effective algorithm to estimate the finite mixture model parameters. However, EM algorithm can not guarantee to find the global optimal solution, and often easy to fall into local optimal solution, so it is sensitive to the determination of initial value to iteration. Traditional EM algorithm select the initial value at random, we propose an improved method of selection of initial value. First, we use the k-nearest-neighbor method to delete outliers. Second, use the k-means to initialize the EM algorithm. Compare this method with the original random initial value method, numerical experiments show that the parameter estimation effect of the initialization of the EM algorithm is significantly better than the effect of the original EM algorithm.

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

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

Comparison of Two Quantum Nearest Neighbor Classifiers on IBM’s Quantum Simulator

Today computers are used to store data in memory and then process them. In our big data era, we are facing the challenge of storing and processing the data simply due to their fast ever growing size. Quantum computation offers solutions to these two prominent issues quantum mechanically and beautifully. Through careful design to employ superposition, entanglement, and interference of quantum states, a quantum algorithm can allow a quantum computer to store datasets of exponentially large size as linear size and then process them in parallel. Quantum computing has found its way in the world of machine learning where new ideas and approaches are in great need as the classical computers have reached their capacity and the demand for processing big data grows much faster than the computing power the classical computers can provide today. Nearest neighbor algorithms are simple, robust, and versatile supervised machine learning algorithms, which store all training data points as their learned “model” and make the prediction of a new test data point by computing the distances between the query point and all the training data points. Quantum counterparts of these classical algorithms provide efficient and elegant ways to deal with the two major issues of storing data in memory and computing the distances. The purpose of our study is to select two similar quantum nearest neighbor algorithms and use a simple dataset to give insight into how they work, highlight their quantum nature, and compare their performances on IBM’s quantum simulator.

基于PCA+KNN和kernal-PCA+KNN算法的废旧纺织物鉴别

该研究采集了15类废旧纺织物的4 998张近红外谱图,以7∶3的比例分为训练集和验证集,并分别采用主成分分析(PCA)与核主成分分析(kernal-PCA)两种不同降维方法对数据进行降维,并选用余弦相似度(cosine)核作为kernal-PCA的最佳核函数,最后分别将PCA和kernal-PCA降维处理后的数据进行k-近邻算法(KNN)训练。结果表明,kernal-PCA+KNN的模型准确率(95.17%)优于PCA+KNN模型的准确率(92.34%)。研究表明,kernal-PCA+KNN算法可以实现15类废旧纺织物识别准确率的提升,为废旧纺织物在线近红外自动分拣提供有力的技术支撑。

基于KNN算法的教学质量评价模型建立

针对当前教学质量评价存在主观性较强的不足,基于K-最近邻(K-nearest neighbor,KNN)算法,提出教学质量评价模型.确立教学质量评价体系;以教学督导的评价数据为样本数据,通过交叉验证求解最近邻算法参数K的最佳值,从而建立教学质量评价模型.模型以专家数据为样本,评价精度高,评价结果具有较高的可靠性,能根据相关指标快速产生评价等级,提高了教学质量评价效率,使教学质量评价更加客观全面.

基于改进KNN近邻实体的知识图谱嵌入模型

为了更好地表示邻居节点数量较少的罕见实体,提出基于近邻实体的知识图谱嵌入模型NNKGE,使用K近邻算法获得目标实体的近邻实体作为扩展信息,并在此基础上提出RNNKGE模型,使用改进的K近邻算法获得目标实体在关系上的近邻实体,通过图记忆网络对其编码生成增强的实体表示。通过对公共数据集上实验结果的分析,以上两个模型在仅使用近邻节点的情况下均实现了对基准模型(CoNE)的性能超越,缓解了数据稀疏问题并改善了知识表示性能。

基于KNN-TCN模型的蒸发皿蒸发量预测研究

蒸发量的精确预测对合理开发利用水资源、旱涝变化趋势研究和农作物灌溉用水量的估算具有十分重要的意义。选取我国北方地区14个地面国际交换站观测的7项气象数据,以时间卷积网络(TCN)模型为基础模型,运用K-近邻(KNN)算法对蒸发皿蒸发量的空间因素进行筛选,构建KNN-TCN蒸发皿蒸发量预测模型,并利用平均绝对误差、均方根误差和判定系数3项指标对目标站点的蒸发量预测精度进行评价。结果表明:1)KNN-TCN模型预测结果明显优于LSTM模型;2)相比基础TCN模型,KNN-TCN模型预测结果的判定系数提升了2.52%,平均绝对误差、均方根误差分别降低了23.97%、13.06%。

基于KNN和多特征融合的苹果叶部病害识别检测

准确识别与防治苹果叶部病害,能够有效提高苹果的产量与品质。以常见的苹果叶部病害(锈病、黑腐病、黑星病)为研究对象,构建基于KNN和多特征融合的无损检测模型。使用K-means聚类算法分割苹果叶部图像,通过颜色矩、灰度共生矩阵、Hu距分别提取图像的颜色、纹理和形状特征,利用KNN对特征参数进行分类模型训练,能够实现绿色准确识别苹果叶部病害的目的。实验结果表明,以颜色、纹理、形状为单特征检测的苹果叶部病害识别精确率分别为75%、57%、45%,其中颜色特征更加直观,有9个特征量识别率较高,形状特征在进行图像分割时很难确定K点导致识别率低。该研究基于颜色、纹理、形状等多特征融合提取13个特征量,能够准确识别苹果叶部病害,其识别率达84%,为实现绿色农业果园病虫害防治提供技术支持。

基于投票加权GS-KNN的离心风机故障诊断

风机作为火力发电的重要辅机,对其进行及时高效的故障诊断,可有效减少停机损失,提高火力发电效率。k近邻(KNN)对非平稳数据样本有良好的分类能力。为了改进传统KNN算法存在的缺陷,构建投票加权网格搜索-k近邻算法(投票加权GS-KNN)故障诊断模型,利用网格搜索完成k值的选取,基于前k个近邻构建与距离值呈负相关的权值投票公式,依据投票得分情况进行故障诊断。使用投票加权GS-KNN模型对离心风机常见的9种运行状态进行故障诊断,拟合k值与准确率的关系,诊断准确率可达到100%。

基于WT-kNN的沥青混凝土心墙坝渗流监测数据异常检测

安全监测数据的质量,对沥青混凝土心墙坝安全状况分析具有重要意义。时间效应导致的趋势性问题是渗流监测数据异常检测的难点。模态分解方法能较好地对时间序列的趋势项进行分离,进而识别处异常信号。但是,土石坝渗流监测数据中的异常值和真实信号往往存在模态混叠。为了解决上述问题,通过引入了小波变换结合局部kNN加权回归(WT-kNN)异常检测方法,使用连续小波变换分离趋势项,通过局部kNN加权回归进一步对小波变换的检测结果进行筛选,提高模型的异常检测准确率。工程应用结果表明:对于粗差占比2.5%~10%的监测序列,WT-kNN的召回率均高于95%,误判率低于5%;该模型与WT-MAD方法和SSA-DBSCAN方法对比实验验证了WT-kNN的有效性和优越性。敏感性分析结果表明,提出模型对异常值数量占总数据量比例和异常值波动范围大小敏感性低,可为后续监测数据分析处理及预测预警建立基础。

改进型加权KNN算法的不平衡数据集分类

K最邻近(KNN)算法对不平衡数据集进行分类时分类判决总会倾向于多数类。为此,提出一种加权KNN算法GAK-KNN。定义新的权重分配模型,综合考虑类间分布不平衡及类内分布不均匀的不良影响,采用基于遗传算法的K-means算法对训练样本集进行聚类,按照权重分配模型计算各训练样本的权重,通过改进的KNN算法对测试样本进行分类。基于UCI数据集的大量实验结果表明,GAK-KNN算法的识别率和整体性能都优于传统KNN算法及其他改进算法。

基于KNN的特征自适应加权自然图像分类研究

针对自然图像类型广泛、结构复杂、分类精度不高的实际问题,提出了一种为自然图像不同特征自动加权值的K-近邻(K-nearest neighbors,KNN)分类方法。通过分析自然图像的不同特征对于分类结果的影响,采用基因遗传算法求得一组最优分类权值向量解,利用该最优权值对自然图像纹理和颜色两个特征分别进行加权,最后用自适应加权K-近邻算法实现对自然图像的分类。实验结果表明,在用户给定分类精度需求和低时间复杂度的约束下,算法能快速、高精度地进行自然图像分类。提出的自适应加权K-近邻分类方法对于门类繁多的自然图像具有普遍适用性,可以有效地提高自然图像的分类性能。