文件名称：K-均值聚类算法研究
文件大小：3.67MB
文件格式：CAJ
更新时间：2023-07-25 09:53:30
数据挖掘 聚类分析 K-均值聚类算法 自组织特征映射网络
【摘要】 目前,对于聚类问题的研究普遍存在于社会生活中的各个领域,如模式识别、图像处理、机器学习和统计学等。关于对生活中各种各样的数据的聚类分类问题已经成为众多学者的研究热题之一。聚类和分类的区别在于,聚类没有任何先验知识可循,要通过数据自身的特点,将数据自动的划分到不同的类别中。聚类的基本形式定义为“在已给的数据集合中寻找数据点集的同类集合。每一个集合叫做一个类,并确定了一个区域,在区域中对象的密度高于其他区域中的密度。”聚类方法有很多种,其中最简单的形式便是划分式聚类,划分式聚类试图将给定的数据集合分割成不相交的子集,使具体的聚类准则是最优的。实际中应用最广泛的准则是聚类误差平方和准则,即对于每一个点都计算它到相应的聚类中心点的平方距离,并对数据集合上的所有点的距离进行求和。一种最流行的基于最小聚类误差平法和的聚类方法是K-均值算法。然而,K-均值算法是一个局部搜索的算法,它存在一些严重的不足,比如K值需要预先确定、聚类结果的好坏依赖于初始点的选取。为了解决这些问题,这个领域的研究者开发了很多其他的一些技术,试图基于全局最优化的方法来解决聚类问题(比如模拟退火算法、遗传算法等)。然而这些技术并没有得到广泛的认可,在许多实际应用中应用最多的还是反复利用K-均值算法。K-均值算法是一种基于划分的聚类算法,它通过不断的迭代来进行聚类,当算法收敛到一个结束条件时就终止迭代过程,输出聚类结果。由于其算法思想简便,又容易实现对大规模数据的聚类,因此K-均值算法已成为一种最常用的聚类算法之一K-均值算法能找到关于聚类误差的局部的最优解,是一个能应用在许多聚类问题上的快速迭代算法。它是一种以点为基础的聚类算法,以随机选取的初始点为聚类中心,迭代地改变聚类中心来使聚类误差最小化。这种方法最主要的不足就是对于初始聚类中心点位置的选取敏感。因此,为了得到近似最优解,初始聚类中心的位置必须安排的有差异。本文就K-均值聚类算法的聚类结果依赖于初始中心,而且经常收敛于局部最优解,而非全局最优解,以及聚类类别数K需要事先给定这两大缺憾展开研究。提出了分别解决这两个问题的算法各一个首先,本文将Hae-Sang等人的快速K-中心点算法确定初始中心点的思想应用于Aristidis Likas的全局K-均值聚类算法中下一个簇的初始中心选择上,提出一种改进的全局K-均值聚类算法,试图寻找一个周围样本点分布比较密集,且距离现有簇的中心都较远的样本点,将其作为下一个簇的最佳初始中心。通过对UCI机器学习数据库数据及人工随机模拟数据的测试,证明本文算法与Aristidis Likas的全局K-均值聚类算法和快速全局K-均值聚类算法比,在不影响聚类误差平方和的前提下,聚类时间更短,具有更好的性能。同时,本文介绍了自组织特征映射网络(Self-Organizing Feature Map, SOFM)的相关内容,SOFM网络是将多维数据映射到低维规则网格中,可以有效的进行大规模的数据挖掘,其特点是速度快,但是分类的精度不高。而K-均值聚类算法,是一种通过不断迭代调整聚类质心的算法,其特点是精度高,主要用于中小数据集的分类,但是聚类速度比较慢。因此,本文在分析了基于自组织特征映射网络聚类的学习过程,权系数自组织过程中邻域函数,以及学习步长的一般取值问题后,给出了基于自组织特征映射网络聚类实现的具体算法,将自组织特征网络与K-均值聚类算法相结合,提出了一种基于自组织映射网络的聚类方法,来实现对输入模式进行聚类,实现K-均值聚类算法的聚类类别数的自动确定。同时通过实验进行仿真实现,证明该算法的有效性。 还原 【Abstract】 Clustering is a fundamental problem that frequently arises in a great variety of fields such as pattern recognition, image processing, machine learning and statistics. In general, clustering is defined as the problem of finding homogeneous groups of samples in a given data set. Each of these groups is called a cluster and can be defined as a region in which the density of exemplars is locally higher than in other regions.The simplest form of clustering is partition clustering which aims at partitioning a given data set into disjoint subsets (clusters) so that specific clustering criteria are optimized. The most widely used criterion is the clustering error criterion which for each exemplar computes its squared distance from the corresponding cluster center and then sums these distances for all exemplars in data set. A popular clustering algorithm that minimizes the clustering error is the K-means algorithm. However, the K-means algorithm is a local search procedure. It suffers from some serious drawbacks that influence its performance.K-means clustering is the most popular clustering algorithm based on the partition of data. However, there are some shortcomings of it, such as its requiring a user to give out the number of clusters at first, and its sensitiveness to initial conditions, and its easily fall into the local solution et cetera.The K-means algorithm finds locally optimal solutions with respect to the clustering error. It is a fast iterative algorithm that has been used in many applications. It is a point-based clustering method that starts with the cluster centers initially placed at arbitrary positions and proceeds by moving at each step the cluster centers in order to minimize the clustering error. The main disadvantage of this method lies in its sensitivity to initial positions of cluster centers. Therefore, in order to obtain near optimal solutions using the K-means algorithm several runs must be scheduled differing in the initial positions of the cluster centers.The global K-means algorithm proposed by Likas et al is an incremental approach to clustering that dynamically adds one cluster center at a time through a deterministic global search procedure consisting of N (with N being the size of the data set) runs of the K-means algorithm from suitable initial positions. It avoids the depending on any initial conditions or parameters, and considerably outperforms the K-means algorithms, but it has a heavy computational load. In this paper, a new version of the global K-means algorithm is proposed. We improved the way of creating the next cluster center by introducing some idea of K-medoids clustering algorithm suggested by Park and Jun. Our new algorithm can not only reduce the computational load of the global K-means without affecting the performance of it, but also avoid the influence of the noisy data on clustering result. Our clustering algorithm is tested on some well-known data sets from UCI and on some synthetic data. The experiment results show that our method outperforms the global K-means algorithm.And then, a self-organizing feature map (SOFM) network is researched. The main investigation in this paper is designing a classifier with self-organizing feature map neural network and K-means algorithm. The SOFM network can project multi-dimensional data on a low-dimensional regular grid, so that it can be utilized to explore the potential properties of the large data. The characteristic of SOFM is its