K均值算法研究及其应用

数据挖掘技术诞生于信息大爆炸的时代,用于在大规模数据中获取数据中隐含的关系和模式。其中,聚类方式作为数据挖掘技术中的一项重要的技术,随着其理论的不断发展和完善,该技术已经应用到了极其广泛的领域,如商务决策,图像识别,数据模式识别等。交通事故原因分析对于聚类分析来说,则是一个较为新颖的应用领域。随着交通事故数据的不断累积,亟需要一种数据挖掘技术对其发生的模式进行挖掘,从而能有效规避事故。聚类分析,尤其是聚类分析中的K均值算法是一个较好的选择。 本文首先对K均值算法进行了较为深入地研究。K均值聚类算法是一种被广泛应用的聚类算法,其特点是高效,实现简单。然而,该算法本身存在着多方面的不足,其中,初始聚类中心点的选择不当和离群点严重影响着该聚类算法的准确性和收敛速度。目前存在的针对于K均值算法改进中,基于密度加权的K均值改进算法具有较好的聚类效果,然而该算法的时间复杂度为O(N2),是较为低效的。本文则提出一种改进,既能获得较好的聚类效果,又能保证改进后算法的线性时间复杂度。本文首先针对初始聚类中心点的选择提出了一种方法,能够在数据对象空间中均匀选择中心点；而对于离群点,本文也给出了相应的检测方法,以防止离群点对聚类效果的干扰。本文通过理论证明改进后的算法能够保持线性的时间复杂度,因此改进算法相对于基于密度加权的K均值算法更高效。本文选用UCI机器学习数据库的数据集进行对比实验进一步说明改进后算法的高效性和准确性。 本文针对交通事故数据的特点进行了深入地研究。交通事故数据的类型往往包含连续值和离散值,而目前存在的对于交通事故数据的聚类分析中,处理连续值和离散值的方式是一样的,这显然是不合适的。因此本文在交通事故数据的预处理步骤中,对离散值的处理方式进行了改进。然后本文将改进后的K均值算法应用到交通事故原因分析中；在得到了聚类簇后,本文又提出了如何针对交通事故数据中不同的数据类型,得到每个聚类簇的典型的表征；然后根据这些表征进行分析并得出了较为合理的事故原因分类。