Efficient Parallel Processing of k-Nearest Neighbor Queries by Using a Centroid-based and Hierarchical Clustering Algorithm

The k-Nearest Neighbor method is one of the most popular techniques for both classification and regression purposes.Because of its operation,the application of this classification may be limited to problems with a certain number of instances,particularly,when run time is a consideration.However,the classification of large amounts of data has become a fundamental task in many real-world applications.It is logical to scale the k-Nearest Neighbor method to large scale datasets.This paper proposes a new k-Nearest Neighbor classification method(KNN-CCL)which uses a parallel centroid-based and hierarchical clustering algorithm to separate the sample of training dataset into multiple parts.The introduced clustering algorithm uses four stages of successive refinements and generates high quality clusters.The k-Nearest Neighbor approach subsequently makes use of them to predict the test datasets.Finally,sets of experiments are conducted on the UCI datasets.The experimental results confirm that the proposed k-Nearest Neighbor classification method performs well with regard to classification accuracy and performance.

Density Clustering Algorithm Based on KD-Tree and Voting Rules

Traditional clustering algorithms often struggle to produce satisfactory results when dealing with datasets withuneven density. Additionally, they incur substantial computational costs when applied to high-dimensional datadue to calculating similarity matrices. To alleviate these issues, we employ the KD-Tree to partition the dataset andcompute the K-nearest neighbors (KNN) density for each point, thereby avoiding the computation of similaritymatrices. Moreover, we apply the rules of voting elections, treating each data point as a voter and casting a votefor the point with the highest density among its KNN. By utilizing the vote counts of each point, we develop thestrategy for classifying noise points and potential cluster centers, allowing the algorithm to identify clusters withuneven density and complex shapes. Additionally, we define the concept of “adhesive points” between two clustersto merge adjacent clusters that have similar densities. This process helps us identify the optimal number of clustersautomatically. Experimental results indicate that our algorithm not only improves the efficiency of clustering butalso increases its accuracy.

Real-Time Spreading Thickness Monitoring of High-core Rockfill Dam Based on K-nearest Neighbor Algorithm

During the storehouse surface rolling construction of a core rockfilldam, the spreading thickness of dam face is an important factor that affects the construction quality of the dam storehouse' rolling surface and the overallquality of the entire dam. Currently, the method used to monitor and controlspreading thickness during the dam construction process is artificialsampling check after spreading, which makes it difficult to monitor the entire dam storehouse surface. In this paper, we present an in-depth study based on real-time monitoring and controltheory of storehouse surface rolling construction and obtain the rolling compaction thickness by analyzing the construction track of the rolling machine. Comparatively, the traditionalmethod can only analyze the rolling thickness of the dam storehouse surface after it has been compacted and cannot determine the thickness of the dam storehouse surface in realtime. To solve these problems, our system monitors the construction progress of the leveling machine and employs a real-time spreading thickness monitoring modelbased on the K-nearest neighbor algorithm. Taking the LHK core rockfilldam in Southwest China as an example, we performed real-time monitoring for the spreading thickness and conducted real-time interactive queries regarding the spreading thickness. This approach provides a new method for controlling the spreading thickness of the core rockfilldam storehouse surface.

A KNN-based two-step fuzzy clustering weighted algorithm for WLAN indoor positioning

Although k-nearest neighbors （KNN） is a popular fingerprint match algorithm for its simplicity and accuracy, because it is sensitive to the circumstances, a fuzzy c-means （FCM） clustering algorithm is applied to improve it. Thus, a KNN-based two-step FCM weighted （KTFW） algorithm for indoor positioning in wireless local area networks （WLAN） is presented in this paper. In KTFW algorithm, k reference points （RPs） chosen by KNN are clustered through FCM based on received signal strength （RSS） and location coordinates. The right clusters are chosen according to rules, so three sets of RPs are formed including the set of k RPs chosen by KNN and are given different weights. RPs supposed to have better contribution to positioning accuracy are given larger weights to improve the positioning accuracy. Simulation results indicate that KTFW generally outperforms KNN and its complexity is greatly reduced through providing initial clustering centers for FCM.

Wireless Communication Signal Strength Prediction Method Based on the K-nearest Neighbor Algorithm

Existing interference protection systems lack automatic evaluation methods to provide scientific, objective and accurate assessment results. To address this issue, this paper develops a layout scheme by geometrically modeling the actual scene, so that the hand-held full-band spectrum analyzer would be able to collect signal field strength values for indoor complex scenes. An improved prediction algorithm based on the K-nearest neighbor non-parametric kernel regression was proposed to predict the signal field strengths for the whole plane before and after being shield. Then the highest accuracy set of data could be picked out by comparison. The experimental results show that the improved prediction algorithm based on the K-nearest neighbor non-parametric kernel regression can scientifically and objectively predict the indoor complex scenes’ signal strength and evaluate the interference protection with high accuracy.

Enhancing Cancer Classification through a Hybrid Bio-Inspired Evolutionary Algorithm for Biomarker Gene Selection

In this study,our aim is to address the problem of gene selection by proposing a hybrid bio-inspired evolutionary algorithm that combines Grey Wolf Optimization(GWO)with Harris Hawks Optimization(HHO)for feature selection.Themotivation for utilizingGWOandHHOstems fromtheir bio-inspired nature and their demonstrated success in optimization problems.We aimto leverage the strengths of these algorithms to enhance the effectiveness of feature selection in microarray-based cancer classification.We selected leave-one-out cross-validation(LOOCV)to evaluate the performance of both two widely used classifiers,k-nearest neighbors(KNN)and support vector machine(SVM),on high-dimensional cancer microarray data.The proposed method is extensively tested on six publicly available cancer microarray datasets,and a comprehensive comparison with recently published methods is conducted.Our hybrid algorithm demonstrates its effectiveness in improving classification performance,Surpassing alternative approaches in terms of precision.The outcomes confirm the capability of our method to substantially improve both the precision and efficiency of cancer classification,thereby advancing the development ofmore efficient treatment strategies.The proposed hybridmethod offers a promising solution to the gene selection problem in microarray-based cancer classification.It improves the accuracy and efficiency of cancer diagnosis and treatment,and its superior performance compared to other methods highlights its potential applicability in realworld cancer classification tasks.By harnessing the complementary search mechanisms of GWO and HHO,we leverage their bio-inspired behavior to identify informative genes relevant to cancer diagnosis and treatment.

Contrastive Clustering for Unsupervised Recognition of Interference Signals

Interference signals recognition plays an important role in anti-jamming communication.With the development of deep learning,many supervised interference signals recognition algorithms based on deep learning have emerged recently and show better performance than traditional recognition algorithms.However,there is no unsupervised interference signals recognition algorithm at present.In this paper,an unsupervised interference signals recognition method called double phases and double dimensions contrastive clustering(DDCC)is proposed.Specifically,in the first phase,four data augmentation strategies for interference signals are used in data-augmentation-based(DA-based)contrastive learning.In the second phase,the original dataset’s k-nearest neighbor set(KNNset)is designed in double dimensions contrastive learning.In addition,a dynamic entropy parameter strategy is proposed.The simulation experiments of 9 types of interference signals show that random cropping is the best one of the four data augmentation strategies;the feature dimensional contrastive learning in the second phase can improve the clustering purity;the dynamic entropy parameter strategy can improve the stability of DDCC effectively.The unsupervised interference signals recognition results of DDCC and five other deep clustering algorithms show that the clustering performance of DDCC is superior to other algorithms.In particular,the clustering purity of our method is above 92%,SCAN’s is 81%,and the other three methods’are below 71%when jammingnoise-ratio(JNR)is−5 dB.In addition,our method is close to the supervised learning algorithm.

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.

一种改进的ZigBee网络Cluster-Tree路由算法

针对ZigBee网络Cluster-Tree算法只按父子关系选择路由可能会带来额外路由开销的问题,提出一种改进的Cluster-Tree路由算法。首先介绍ZigBee网络的地址分配机制,分析Cluster-Tree路由算法,并在此基础上引入邻居表提出改进算法。该算法的基本思想:如果选择邻居节点的路由开销与原算法相比更小,则会选择邻居节点作为下一跳。仿真结果表明,该算法可以减少约30%的路由开销。

ZigBee中改进的Cluster-Tree路由算法

针对ZigBee网络的Cluster-Tree算法对簇首能量要求高、选择的路由非最佳路由等问题,结合节点能量分析和节点邻居表,提出一种改进的簇首生成方法,利用AODVjr算法为节点选择最佳路由。仿真结果证明,与原Cluster-Tree算法相比,改进的算法能有效提高数据发送成功率,减少源节点与目标节点间的跳数,降低端到端的报文传输时延,提高网络的使用价值。

基于ZigBee无线网络的Cluster-Tree路由算法研究

针对ZigBee无线网络中Cluster-Tree算法只依靠父子关系路由且ZigBee技术传输带宽的限制,致使网络中负载较重的链路不能及时传递信息,而造成网络拥塞、丢包和较低的吞吐量问题,提出了一种改进算法Z-DMHCTR。该算法针对负载超过一定限度的节点,除了按照原等级树算法路由之外,结合引入的邻居列表信息,寻找节点不与原路径相交的路径同时进行信息传输,从而提高网络带宽利用率,达到提升网络的吞吐量的目的。仿真实验主要从网络吞吐量、端到端数据传输延时等方面入手进行对比。结果表明,改进算法能够有效地提高网络吞吐量,并降低了传输数据的延时。

ZigBee网络Cluster-Tree优化路由算法研究

通过分析ZigBee协议中Cluster-Tree和AODVjr算法的优缺点,提出一种基于Cluster-Tree+AODVjr的优化路由算法。该算法利用ZigBee协议中的邻居表,通过定义分区来确定目的节点的范围,从而控制广播RREQ分组的跳数,防止无效的RREQ泛洪。此优化算法能够有效地减小路由跳数,缩短传输时延,减少网络中死亡节点的数量,提高数据传送的成功率。

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 Improved Whale Optimization Algorithm for Feature Selection

Whale optimization algorithm(WOA)is a new population-based meta-heuristic algorithm.WOA uses shrinking encircling mechanism,spiral rise,and random learning strategies to update whale’s positions.WOA has merit in terms of simple calculation and high computational accuracy,but its convergence speed is slow and it is easy to fall into the local optimal solution.In order to overcome the shortcomings,this paper integrates adaptive neighborhood and hybrid mutation strategies into whale optimization algorithms,designs the average distance from itself to other whales as an adaptive neighborhood radius,and chooses to learn from the optimal solution in the neighborhood instead of random learning strategies.The hybrid mutation strategy is used to enhance the ability of algorithm to jump out of the local optimal solution.A new whale optimization algorithm(HMNWOA)is proposed.The proposed algorithm inherits the global search capability of the original algorithm,enhances the exploitation ability,improves the quality of the population,and thus improves the convergence speed of the algorithm.A feature selection algorithm based on binary HMNWOA is proposed.Twelve standard datasets from UCI repository test the validity of the proposed algorithm for feature selection.The experimental results show that HMNWOA is very competitive compared to the other six popular feature selection methods in improving the classification accuracy and reducing the number of features,and ensures that HMNWOA has strong search ability in the search feature space.

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.

基于ZigBee网络的Cluster-Tree能量优化算法

在ZigBee网络的Cluster-Tree算法中,簇首节点容易过早耗尽自身能量,减少网络的整体寿命。针对此问题,给出了更改簇首节点的方法,避免剩余能量低的簇首节点转发大数据,减少节点到协调器的跳数,提高网络的应用价值。

用于雷达信号分选的K中位最近邻聚类算法

在处理雷达信号时,基于密度的空间聚类(Density-based spatial clustering of applications with noise,DBSCAN)分选算法依赖于参数或阈值的选取,影响分选的准确率。为此提出了一种改进的雷达信号脉冲分选算法,在DBSCAN聚类基础上结合了K中位最近邻(K-median nearest neighbor,KMNN)算法,通过引入自衰减系数并设置阈值上限对参数值列表进行二次处理,可以自适应根据聚类结果与不同参数时的K值之间的关系确定最优的邻域半径和最少点个数,提高了分选的正确率。通过仿真实验验证了算法利用雷达脉冲描述字特征进行自适应分选的有效性。

基于t-SNE的多参数岩体结构面分步聚类方法

结构面聚类是进行岩体稳定性评价的重要步骤。常用聚类方法多以产状作为分组依据,忽略了结构面物理特性指标对岩体稳定性的影响。针对分组依据单一化的不足,综合考虑结构面倾向、倾角、迹长、张开度、填充状态和粗糙度的影响,提出一种基于学生分布随机邻近嵌入(student-distributed stochastic neighbor embedding,简称t-SNE)的多参数岩体结构面分步聚类方法。首先,利用t-SNE算法对除产状外的结构面特征进行数据降维;进而利用模拟退火算法搜索K-means算法的全局最优初始值,并采用分步聚类思想完成聚类。研究表明:所提方法有效地解决了高维空间样本稀疏的问题,同时保留了数据的局部结构与全局结构。新方法相比于传统方法能对空间分布相似区内结构面的物理特性进行精确划分,分组精度更高,且在避免复杂权重值计算的条件下,能有效区分产状与物理特性参数对岩体稳定性的影响差异。最后,将所提方法应用于中国新疆某露天矿坡结构面实测数据分析中,所得分组结果合理可靠,进一步证明该方法在实际工程中的有效性。研究方法可为多参数岩体结构面的分步聚类提供参考。

基于AP聚类的时序数据缺失值有序填充算法

为提高数据的完整性,便于从数据中获得更多有价值的信息,提出基于AP聚类的时序数据缺失值有序填充算法。为提高数据质量,将数据分为不同子集,根据标准差思想对数据作归一化处理,将数值控制在固定区间,减少数据的不平衡性;分别构建吸引度与归属度更新矩阵,确保消息正常传递,达到近邻传播目的;设计不完整信息系统,将不同数据间的相似度作为聚类依据;获取聚类邻域的半径参数,通过数据点密度指标确定聚类中心,将相邻数据聚集在一起;利用熵值概念,根据数据相似度计算加权系数,确定缺失数据属性值,实现缺失值有序填充。实验结果表明,所提方法能够将具有相同属性特征的数据聚集在一起,即使数据缺失率较高,也能达到很高的填充准确率。

自适应邻域密度聚类及事故黑点识别应用

聚类作为识别交通事故黑点的主要方法之一,其主要问题是交通事故多发区事先无法确定,即无法提前知道聚类簇数。利用样本点之间的连接概率定义了数据点的局部密度,根据局部密度大小来确定聚类中心和簇数,再对数据点进行聚类。结果表明:一是算法对参数不敏感,具有较好的通用性;二是算法能自动确定聚类簇数;三是算法聚类过程只依赖局部密度与邻接点,能够识别噪声点,提升结果的准确性。运用算法在一些真实数据集上进行试验,将聚类结果与其他算法结果利用评价指标ARI(Adjusted Rand Index)和NMI(Normalized Mutual Information)进行比较。最后利用算法对美国6个州的交通事故进行聚类,结果表明算法对交通事故有较好的适应性,能将城市及周边道路上事故密集区域准确识别出来。