论文部分内容阅读
当面临大量的统计数据时,传统的k-means聚类算法需要大量的距离计算和内存空间来处理这些数据,导致时间和空间复杂度太高,无法满足海量数据分析的要求。此外,随着互联网技术的飞跃发展,在医学领域积累了大量的医疗数据,如何使用数据挖掘技术精确和快速提取出人们感兴趣的信息成为当前研究的一大热点。因此本文的研究重点是在保证精确度的条件下更快速的从海量医疗数据里提取信息。本文基于MapReduce分布式并行计算框架提出了一种基于MapReduce改进的并行k-means聚类算法,以对医疗数据进行聚类分析,挖掘出疾病与药品之间的关系。具体工作如下:首先,分析了传统k-means聚类算法的缺陷,其缺陷主要表现为在每次迭代过程需要进行大量冗余距离计算。为此,提出了一种简化模型来简化非聚类中心点与其他聚类中心点之间的距离计算。根据聚类过程中存在的极端点,提出了使用曼哈顿距离代替欧氏距离来计算极端点和中心点之间的距离,以减少极端点和中心点的距离计算量。其次,由于k-means聚类算法的中心点选择对聚类结果有较大影响,为此,在第一次迭代时中心点从数据库中选择出的k条记录,每条记录代表着唯一一种疾病,剩下迭代都采用所有点的平均值为依据来选择新的中心点,从而保证最终聚类结果的准确性。最后,根据提出的改进策略,提出了一种基于MapReduce的改进并行k-means聚类算法。借鉴MapReduce并行计算框架上的开源实现,本文实现并比较了基于MapReduce并行计算框架改进的k-means聚类算法(IMR-KCA)、Mahout中的k-means聚类算法(Mahout-KCA)和传统基于MapReduce的k-means聚类算法(MR-KCA)。实验结果表明基于MapReduce并行计算框架改进的k-means聚类算法在可靠性、效率和可扩展性等方面较其它同类算法更优。