【作者】 王浩；

【导师】 林晓霞； 刘振国；

【作者基本信息】 山东科技大学 ， 电子信息（专业学位）， 2023， 硕士

【摘要】 随着信息时代的高速发展,如何通过数据挖掘技术从海量的数据中挖掘出有价值的信息已经成为当今各行业发展的关键因素之一。聚类分析是数据挖掘技术中最常用的技术。其中,K-means算法是应用最广泛的一种基于划分的聚类方法,具有简洁高效的特点,因此在许多场景中被广泛采用。但K-means算法也存在着一定的缺陷:(1)对聚类数6)值过于依赖,最佳聚类数不易确定。(2)对初始中心点太过敏感,初始中心点随机生成的方式使得聚类效果不稳定。(3)计算冗余度高,在样本划分阶段,每个样本点都需要与簇中心点进行距离计算导致计算冗余过多。本文对上述K-means算法缺点进行优化,提出一种融合多策略的改进K-means算法—MSIK-means(Multi-strategy improvement K-means)算法。针对传统K-means算法不同缺陷,提出不同策略进行改进。主要研究工作如下:(1)在对聚类数6)值过于依赖方面,针对传统手肘法所基于的聚类有效性指标不能够基于每个簇类的聚类情况来反映聚类效果的问题。将幂函数基本性质、误差权重以及手肘法则相结合,提出一种新的6)值选择方法—PF-ELBOW(Power Function Elbow)算法,提高了聚类效果欠佳的簇的误差平方和在总体误差平方和中所占的比重,从而使得最佳聚类数的确定更加精准。(2)在对初始中心点敏感方面,在确定聚类数优化的基础上,利用方差来衡量样本点密度,选择方差较小(密度较大)的样本点,同时基于样本间平均距离来选择初始聚类中心,可以避免选择的初始中心点为离群点和位于同一簇类的情况,从而使得聚类迭代次数更少,聚类准确度更高。(3)在样本划分计算冗余过多方面,在初始中心点优化的基础上,提出了基于邻域空间的样本点划分方法。为每个簇中心点划分各自的邻域空间。每个邻域空间中的簇中心点为邻域空间中所有样本点的最近簇中心点。在样本划分过程中,将每个邻域空间中的样本点直接划分到邻域空间中簇中心点所在的簇类中,有效地避免了每个样本点与簇中心点之间的一些不必要的距离计算,降低了传统K-means算法样本划分的时间复杂度。将MSIK-means算法在不同的UCI数据集和人工合成数据集上与传统K-means算法以及其他改进K-means算法进行实验对比分析。实验结果表明,MSIK-means算法相比其他算法而言,在不同的聚类评价指标上有一定的提升。最后采用MSIK-means算法对某银行客户进行客户细分并对细分结果中的每一类客户进行说明分析。相比使用传统K-means算法进行银行客户细分,MSIK-means算法在聚类误差平方和、迭代次数以及样本划分时间上均有一定提升。更多还原

【Abstract】 With the rapid development of the information age,how to mine valuable information from massive amounts of data through data mining technology has become one of the key factors in the development of various industries today.Cluster analysis is the most commonly used technique in data mining.Among them,the K-means algorithm is the most widely used partition based clustering method,which has the characteristics of simplicity and efficiency,and is therefore widely used in many scenarios.However,the K-means algorithm also has certain drawbacks:(1)it relies too heavily on the k-value of the number of clusters,making it difficult to determine the optimal number of clusters.(2)The initial center point is too sensitive,and the random generation of the initial center point makes the clustering effect unstable.(3)The computational redundancy is high,and during the sample partitioning stage,each sample point needs to calculate the distance from the cluster center point,resulting in excessive computational redundancy.This paper optimises the above K-means algorithm for its shortcomings and proposes an improved K-means algorithm incorporating multi-strategy-MSIK-means(Multi-strategy improvement K-means)algorithm.Different strategies are proposed to improve the traditional K-means algorithm for different shortcomings.The main research work is as follows:(1)In terms of over-reliance on the k-value of the clustering number,the problem that the clustering validity index based on the traditional elbow method does not reflect the clustering effect based on the clustering of each cluster class is addressed.By combining the basic properties of the power function,the error weights and the elbow rule,a new k-value selection method,the PF-ELBOW(Power Function Elbow)algorithm,is proposed,which increases the proportion of the error sum of squares of the clusters with poor clustering effectiveness in the overall error sum of squares,thus making the determination of the optimal number of clusters more accurate.(2)In terms of sensitivity to the initial centroid,on the basis of determining the optimal number of clusters,the variance is used to measure the density of sample points,and the sample points with smaller variance(higher density)are selected,while the initial clustering center is selected based on the average distance between samples,which can avoid the situation that the selected initial centroids are outliers and located in the same cluster class,thus making the number of clustering iterations less and the clustering accuracy higher.(3)Based on the initial centroid optimisation,a neighbourhood space-based sample point delineation method is proposed when redundancy is over-calculated in the sample delineation.Each cluster centroid is divided into its own neighbourhood space.The cluster centroids in each neighbourhood space are the nearest cluster centroids of all sample points in the neighbourhood space.In the sample partitioning process,the sample points in each neighbourhood space are directly divided into the cluster classes in which the cluster centroids in the neighbourhood space are located,effectively avoiding some unnecessary distance calculation between each sample point and the cluster centroids and reducing the time complexity of the traditional K-means algorithm sample partitioning.The MSIK-means algorithm is experimentally compared and analysed with traditional K-means and other improved K-means algorithms on different UCI datasets and synthetic datasets.The experimental results show that the MSIK-means algorithm has some improvement in different clustering evaluation metrics compared to other algorithms.Finally,the MSIK-means algorithm is used to segment a bank customer and to illustrate and analyse each class of customer in the segmentation results.Compared to the traditional K-means algorithm for bank customer segmentation,the MSIK-means algorithm shows some improvement in the sum of squared clustering errors,the number of iterations and the sample segmentation time.更多还原