Improved k-means clustering algorithm

In allusion to the disadvantage of having to obtain the number of clusters of data sets in advance and the sensitivity to selecting initial clustering centers in the k-means algorithm, an improved k-means clustering algorithm is proposed. First, the concept of a silhouette coefficient is introduced, and the optimal clustering number Kopt of a data set with unknown class information is confirmed by calculating the silhouette coefficient of objects in clusters under different K values. Then the distribution of the data set is obtained through hierarchical clustering and the initial clustering-centers are confirmed. Finally, the clustering is completed by the traditional k-means clustering. By the theoretical analysis, it is proved that the improved k-means clustering algorithm has proper computational complexity. The experimental results of IRIS testing data set show that the algorithm can distinguish different clusters reasonably and recognize the outliers efficiently, and the entropy generated by the algorithm is lower.

An efficient enhanced k-means clustering algorithm

In k-means clustering, we are given a set of n data points in d-dimensional space R^d and an integer k and the problem is to determine a set of k points in R^d, called centers, so as to minimize the mean squared distance from each data point to its nearest center. In this paper, we present a simple and efficient clustering algorithm based on the k-means algorithm, which we call enhanced k-means algorithm. This algorithm is easy to implement, requiring a simple data structure to keep some information in each iteration to be used in the next iteration. Our experimental results demonstrated that our scheme can improve the computational speed of the k-means algorithm by the magnitude in the total number of distance calculations and the overall time of computation.

Estimating wheat fractional vegetation cover using a density peak k-means algorithm based on hyperspectral image data

Fractional vegetation cover(FVC)is an important parameter to measure crop growth.In studies of crop growth monitoring,it is very important to extract FVC quickly and accurately.As the most widely used FVC extraction method,the photographic method has the advantages of simple operation and high extraction accuracy.However,when soil moisture and acquisition times vary,the extraction results are less accurate.To accommodate various conditions of FVC extraction,this study proposes a new FVC extraction method that extracts FVC from a normalized difference vegetation index(NDVI)greyscale image of wheat by using a density peak k-means(DPK-means)algorithm.In this study,Yangfumai 4(YF4)planted in pots and Yangmai 16(Y16)planted in the field were used as the research materials.With a hyperspectral imaging camera mounted on a tripod,ground hyperspectral images of winter wheat under different soil conditions(dry and wet)were collected at 1 m above the potted wheat canopy.Unmanned aerial vehicle(UAV)hyperspectral images of winter wheat at various stages were collected at 50 m above the field wheat canopy by a UAV equipped with a hyperspectral camera.The pixel dichotomy method and DPK-means algorithm were used to classify vegetation pixels and non-vegetation pixels in NDVI greyscale images of wheat,and the extraction effects of the two methods were compared and analysed.The results showed that extraction by pixel dichotomy was influenced by the acquisition conditions and its error distribution was relatively scattered,while the extraction effect of the DPK-means algorithm was less affected by the acquisition conditions and its error distribution was concentrated.The absolute values of error were 0.042 and 0.044,the root mean square errors(RMSE)were 0.028 and 0.030,and the fitting accuracy R2 of the FVC was 0.87 and 0.93,under dry and wet soil conditions and under various time conditions,respectively.This study found that the DPK-means algorithm was capable of achieving more accurate results than the pixel dichotomy method in various soil and time conditions and was an accurate and robust method for FVC extraction.

Polarimetric Meteorological Satellite Data Processing Software Classification Based on Principal Component Analysis and Improved K-Means Algorithm

With the increasing variety of application software of meteorological satellite ground system, how to provide reasonable hardware resources and improve the efficiency of software is paid more and more attention. In this paper, a set of software classification method based on software operating characteristics is proposed. The method uses software run-time resource consumption to describe the software running characteristics. Firstly, principal component analysis (PCA) is used to reduce the dimension of software running feature data and to interpret software characteristic information. Then the modified K-means algorithm was used to classify the meteorological data processing software. Finally, it combined with the results of principal component analysis to explain the significance of various types of integrated software operating characteristics. And it is used as the basis for optimizing the allocation of software hardware resources and improving the efficiency of software operation.

Hybrid Genetic Algorithm with K-Means for Clustering Problems

The K-means method is one of the most widely used clustering methods and has been implemented in many fields of science and technology. One of the major problems of the k-means algorithm is that it may produce empty clusters depending on initial center vectors. Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary principles of natural selection and genetics. This paper presents a hybrid version of the k-means algorithm with GAs that efficiently eliminates this empty cluster problem. Results of simulation experiments using several data sets prove our claim.

Development of slope mass rating system using K-means and fuzzy c-means clustering algorithms

Classification systems such as Slope Mass Rating(SMR) are currently being used to undertake slope stability analysis. In SMR classification system, data is allocated to certain classes based on linguistic and experience-based criteria. In order to eliminate linguistic criteria resulted from experience-based judgments and account for uncertainties in determining class boundaries developed by SMR system,the system classification results were corrected using two clustering algorithms, namely K-means and fuzzy c-means(FCM), for the ratings obtained via continuous and discrete functions. By applying clustering algorithms in SMR classification system, no in-advance experience-based judgment was made on the number of extracted classes in this system, and it was only after all steps of the clustering algorithms were accomplished that new classification scheme was proposed for SMR system under different failure modes based on the ratings obtained via continuous and discrete functions. The results of this study showed that, engineers can achieve more reliable and objective evaluations over slope stability by using SMR system based on the ratings calculated via continuous and discrete functions.

Similarity matrix-based K-means algorithm for text clustering

K-means algorithm is one of the most widely used algorithms in the clustering analysis. To deal with the problem caused by the random selection of initial center points in the traditional al- gorithm, this paper proposes an improved K-means algorithm based on the similarity matrix. The im- proved algorithm can effectively avoid the random selection of initial center points, therefore it can provide effective initial points for clustering process, and reduce the fluctuation of clustering results which are resulted from initial points selections, thus a better clustering quality can be obtained. The experimental results also show that the F-measure of the improved K-means algorithm has been greatly improved and the clustering results are more stable.

Plant Leaf Diseases Classification Using Improved K-Means Clustering and SVM Algorithm for Segmentation

Several pests feed on leaves,stems,bases,and the entire plant,causing plant illnesses.As a result,it is vital to identify and eliminate the disease before causing any damage to plants.Manually detecting plant disease and treating it is pretty challenging in this period.Image processing is employed to detect plant disease since it requires much effort and an extended processing period.The main goal of this study is to discover the disease that affects the plants by creating an image processing system that can recognize and classify four different forms of plant diseases,including Phytophthora infestans,Fusarium graminearum,Puccinia graminis,tomato yellow leaf curl.Therefore,this work uses the Support vector machine(SVM)classifier to detect and classify the plant disease using various steps like image acquisition,Pre-processing,Segmentation,feature extraction,and classification.The gray level co-occurrence matrix(GLCM)and the local binary pattern features(LBP)are used to identify the disease-affected portion of the plant leaf.According to experimental data,the proposed technology can correctly detect and diagnose plant sickness with a 97.2 percent accuracy.

A Hybrid Method Combining Improved K-means Algorithm with BADA Model for Generating Nominal Flight Profiles

A high-precision nominal flight profile,involving controllers′intentions is critical for 4Dtrajectory estimation in modern automatic air traffic control systems.We proposed a novel method to effectively improve the accuracy of the nominal flight profile,including the nominal altitude profile and the speed profile.First,considering the characteristics of trajectory data,we developed an improved K-means algorithm.The approach was to measure the similarity between different altitude profiles by integrating the space warp edit distance algorithm,thereby to acquire several fitted nominal flight altitude profiles.This approach breaks the constraints of traditional K-means algorithms.Second,to eliminate the influence of meteorological factors,we introduced historical gridded binary data to determine the en-route wind speed and temperature via inverse distance weighted interpolation.Finally,we facilitated the true airspeed determined by speed triangle relationships and the calibrated airspeed determined by aircraft data model to extract a more accurate nominal speed profile from each cluster,therefore we could describe the airspeed profiles above and below the airspeed transition altitude,respectively.Our experimental results showed that the proposed method could obtain a highly accurate nominal flight profile,which reflects the actual aircraft flight status.

Genetic Algorithm Combined with the K-Means Algorithm:A Hybrid Technique for Unsupervised Feature Selection

The dimensionality of data is increasing very rapidly,which creates challenges for most of the current mining and learning algorithms,such as large memory requirements and high computational costs.The literature includes much research on feature selection for supervised learning.However,feature selection for unsupervised learning has only recently been studied.Finding the subset of features in unsupervised learning that enhances the performance is challenging since the clusters are indeterminate.This work proposes a hybrid technique for unsupervised feature selection called GAk-MEANS,which combines the genetic algorithm(GA)approach with the classical k-Means algorithm.In the proposed algorithm,a new fitness func-tion is designed in addition to new smart crossover and mutation operators.The effectiveness of this algorithm is demonstrated on various datasets.Fur-thermore,the performance of GAk-MEANS has been compared with other genetic algorithms,such as the genetic algorithm using the Sammon Error Function and the genetic algorithm using the Sum of Squared Error Function.Additionally,the performance of GAk-MEANS is compared with the state-of-the-art statistical unsupervised feature selection techniques.Experimental results show that GAk-MEANS consistently selects subsets of features that result in better classification accuracy compared to others.In particular,GAk-MEANS is able to significantly reduce the size of the subset of selected features by an average of 86.35%(72%–96.14%),which leads to an increase of the accuracy by an average of 3.78%(1.05%–6.32%)compared to using all features.When compared with the genetic algorithm using the Sammon Error Function,GAk-MEANS is able to reduce the size of the subset of selected features by 41.29%on average,improve the accuracy by 5.37%,and reduce the time by 70.71%.When compared with the genetic algorithm using the Sum of Squared Error Function,GAk-MEANS on average is able to reduce the size of the subset of selected features by 15.91%,and improve the accuracy by 9.81%,but the time is increased by a factor of 3.When compared with the machine-learning based methods,we observed that GAk-MEANS is able to increase the accuracy by 13.67%on average with an 88.76%average increase in time.

An Improved K-Means Algorithm Based on Initial Clustering Center Optimization

The K-means algorithm is widely known for its simplicity and fastness in text clustering.However,the selection of the initial clus?tering center with the traditional K-means algorithm is some random,and therefore,the fluctuations and instability of the clustering results are strongly affected by the initial clustering center.This paper proposed an algorithm to select the initial clustering center to eliminate the uncertainty of central point selection.The experiment results show that the improved K-means clustering algorithm is superior to the traditional algorithm.

A State of Art Analysis of Telecommunication Data by k-Means and k-Medoids Clustering Algorithms

Cluster analysis is one of the major data analysis methods widely used for many practical applications in emerging areas of data mining. A good clustering method will produce high quality clusters with high intra-cluster similarity and low inter-cluster similarity. Clustering techniques are applied in different domains to predict future trends of available data and its uses for the real world. This research work is carried out to find the performance of two of the most delegated, partition based clustering algorithms namely k-Means and k-Medoids. A state of art analysis of these two algorithms is implemented and performance is analyzed based on their clustering result quality by means of its execution time and other components. Telecommunication data is the source data for this analysis. The connection oriented broadband data is given as input to find the clustering quality of the algorithms. Distance between the server locations and their connection is considered for clustering. Execution time for each algorithm is analyzed and the results are compared with one another. Results found in comparison study are satisfactory for the chosen application.

Multiple Parameter Based Clustering (MPC): Prospective Analysis for Effective Clustering in Wireless Sensor Network (WSN) Using K-Means Algorithm

In wireless sensor network cluster architecture is useful because of its inherent suitability for data fusion. In this paper we represent a new approach called Multiple Parameter based Clustering (MPC) embedded with the traditional k-means algorithm which takes different parameters (Node energy level, Euclidian distance from the base station, RSSI, Latency of data to reach base station) into consideration to form clusters. Then the effectiveness of the clusters is evaluated based on the uniformity of the node distribution, Node range per cluster, Intra and Inter cluster distance and required energy level of each centroid. Our result shows that by varying multiple parameters we can create clusters with more uniformly distributed nodes, minimize intra and maximize inter cluster distance and elect less power consuming centroid.

粗糙核k-means聚类算法

通过研究核聚类算法,以及粗糙集,提出了一个新的用于聚类分析的粗糙核聚类方法。通过mercer核映射把输入空间中的样本映射到Hilbert空间,使样本空间中没有显现的特征在特征空间中突现出来,在这种样本差异加大的基础上,结合粗糙集的思想,把样本分别划到相应聚类中心的上、下近似中,上、下近似中的样本按照一定的比例来共同决定新的聚类中心。这样不但聚类精度大大提高,而且算法收敛速度也较快。仿真实验的结果表明该算法的可行性和有效性。

基于相对距离的改进粗K-means方法

对现有的两种基于绝对距离的粗K-means方法进行了讨论,指出了各自的不足之处。在此基础之上,讨论了用相对距离替代绝对距离的合理性,从而给出了基于相对距离的粗K-means方法。通过对随机数据、Iris数据和文本数据进行聚类效果比较,验证了基于相对距离的粗K-means方法的可行性和有效性。

基于改进流形距离的粗糙集k-means聚类算法

针对现有的基于流形距离的聚类算法对"绝对流形"数据集较"相对流形"数据集聚类效果佳和参数ρ在较大范围内变化时,聚类性能较差等问题,提出基于改进流形距离的粗糙集k-means聚类算法。该算法通过用属性划分和最大最小距离选择初始聚类中心,以改进的流形距离和粗糙集优化k-means,并结合终止判断条件以达到解决边界数据聚类问题和提升聚类效果的目的。仿真结果表明:该算法对"绝对流形"和"相对流形"数据集聚类效果均有较好改善,且参数变化对聚类性能影响较大。

具有自适应参数的粗糙k-means聚类算法

粗糙聚类是不确定聚类算法中一种有效的聚类算法,这里通过分析粗糙k-means算法,指出了其中3个参数wl,wu和ε设置时存在的缺点,提出了一种自适应粗糙k-means聚类算法,该算法能进一步优化粗糙k-means的聚类效果,降低对"噪声"的敏感程度,最后通过实验验证了算法的有效性。

结合人工蜂群优化的粗糙K-means聚类算法

粗糙K-means聚类算法具有较强的处理边界不确定数据能力,但该算法也存在对初始聚类中心选取敏感,以及采用固定权重和阈值方式而导致聚类结果不稳定、精度下降等问题。许多研究工作从不同角度致力于解决这些问题。引入人工蜂群算法(ABC)从三方面对算法进行了改进:首先,以下近似和边界集中数据对象个数与对象在数据集中空间分布的差异性乘积的比值为基础,设计了一种更为合理的动态调整下近似和边界集的权重方法。其次,为加快算法的收敛速度,给出了一种与迭代次数相关联的自适应阈值ε的实现方法。最后,通过构造蜜源位置的适应度函数,引导蜂群向高质量蜜源全局搜索,把蜂群每次迭代得到的最优源位置作为初始聚类中心,并在此基础上进行交替聚类。实验结果表明,改进后的算法提高了聚类结果的稳定性,获得了较好的聚类效果。

基于空间距离自适应权重度量的粗糙K-means算法

粗糙K-means算法中下近似和边界区域权重系数的设置对算法的聚类效果有着重要的影响。传统的粗糙K-means算法及很多改进的粗糙K-means算法对所有类簇的下近似和边界区域设置固定的权重,忽视了簇内数据对象分布差异性的影响。针对这个问题,根据下近似和边界区域的数据对象相对于类簇中心的空间分布情况,提出一种新的基于空间距离自适应权重度量的粗糙K-means算法。该算法在每次迭代过程中,根据每个类簇的下近似和边界区域的数据对象相对于类簇中心的平均距离,综合度量下近似和边界区域对于类簇中心迭代计算的不同重要程度,动态地计算下近似和边界区域的相对权重系数。通过实例验证及实验仿真证明了所提算法的有效性。

A Hybrid Genetic Algorithm for Reduct of Attributes in Decision System Based on Rough Set Theory

Knowledge reduction is an important issue when dealing with huge amounts of data. And it has been proved that computing the minimal reduct of decision system is NP-complete. By introducing heuristic information into genetic algorithm, we proposed a heuristic genetic algorithm. In the genetic algorithm, we constructed a new operator to maintaining the classification ability. The experiment shows that our algorithm is efficient and effective for minimal reduct, even for the special example that the simple heuristic algorithm can’t get the right result.