论文部分内容阅读
【摘要】众所周知我们已经生活在信息时代。随着大量数据不断的涌入到数据库，使得我们数据库中的信息不断的增长，以至于我们很难从庞大的数据库中发现知识，发现对我们来说还有潜在意义的知识。本文主要对传统的聚类分析中的经典算法K_means进行改进，增强其对庞大数据聚类的伸缩性以及时效性。本次算法的改进对收敛速度和准确率以及算法的伸缩性都有了很大的提升。
【关键词】数据挖掘；聚类 K_means 并行K均值；初始值优化
随着数据库和数据管理产业的不断发展，如今大型的的数据库系统已经普及发展，从常见的关系数据库到企业级的数据仓库已经包含了大量的数据，而数据库系统只提供事务处理，数据仓库提供决策级的数据分析。面对众多的层积在数据库中的知识，对其发现和分析变得越来越重要也越来越困难，在这种背景下数据挖掘便应运而生，从大量的数据中发现知识也变得至关重要。所以我们对数据挖掘的研究显得尤为重要。然而在数据挖掘中聚类分析是最基本也是最重要的，现在国内外对聚类方法中的K_means算法的研究也是如火如荼。面对不通的应用领域K_means算法的改进也是多种多样，但对大型数据K_means算法的局限性也展示了出来，于是并列K_means算法也得到了很好的发展和研究。本文章主要针对大型数据做聚类分析，采用基于Mapreduce并列K_means算法，并对K_means算法的初始值选择加以优化，主要从效率和准确度出发进行研究。
一、传统的K_means算法思想
K_means算法是一种最著名和最普及的聚类方法之一，其目的是将数据对象的数据集M划分成K个相互排斥的簇，使簇与簇之间有高度的相异性，而簇内部具有高度的相似性。在划分的时候一般采取欧式距离为参考。
一般步骤：根据经验确定要聚类的数目K，然后随机的选取K个对象作为K个簇的中心点，再按照欧式距离对其余对象进行距离计算，将其余对象分配到离中心最近的簇中。然后分配完毕后，重新计算各个簇中的平局数，并将这个平均数作为新的中心点。重复这个过程直到簇没有变化为止。
K-均值算法的过程如下：算法：K_means。每个簇都用簇中心表示，簇中心用簇内的对象的均值来表示。输入：K：簇的个数 M：包含n个对象的数据集
输出：k个簇的集合，方法：
（一）从M中任意选择K个对象作为初始簇的中心；
（二）Repeat
（三）根据簇中对象的均值，将每个对象分配到最相似的簇
（四）更新簇的中心
（五）Until不在发生变化
二、改进的K_means并行处理算法
改进的K_means算法，通过预先对大数据进行抽样，然后对样本进行分析采用最长距离法选定簇中心。然后用基于MapReduce的并列K_means算法进行聚类。本文数据来源由随机生成函数随机产生40000条1-100的随机数，然后人为插入10条4位数到数据中。通过抽样函数在数据中抽样100个数为抽样样本。
（一）K_均值初始簇中心的选定
传统的初始中心都是随机抽取，我们对随机抽取进行一些优化。对于初始簇中心选择采取基于距离与密度而确定。基本思想为在样本中选取相距距离最远且样本的密度最大的k个点作为初始簇中心。
下面定义样本点x所处区域的密度 ：
P (x )= {x∈D|Dis(x,d)≤r}其中 D 为样本点集，r为球体半径，Dis (x ,d)为距离测量。样本点x所处区域的密度计算规则为以x为中心，r 为半径的球体所包含的样本个数。半径r的确定规则如下 ：<1> 求解每两个数据对象的距离，然后求出所有距离的平均值λ。然后求出每个样本点所在区域的密度，然后把密度大的区域中的点组成新的集合D1，在集合中取 P 值最大的样本点作为第一个初始中心K1，然后取离K1最远的高密度样本点作为第二个初始簇中心K2 ，然后取满足 max(min(d(Xi，K1),d(Xi，K2))) i=1,2,…,n 的样本点Xi作为第三个初始中心K3，依次类推，取满足 max(min(d(Xi，K1),d(Xi，K2),…d(Xi，KK-1))) i=1,2,…,n 的 样 本 点Xi作为第K个初始簇中心，最后确定了聚类的 k 个初始中心。多次实验改进算法取距离最远的k 个密度大的样本点作为聚类的初始簇中心，这些簇中心点基本上是稳定的，从而而消除了初始中心选择的随机性，提高了聚类结果的精确度。
（二）基于MapReduce的并行K_means算法实现
K_means算法中的主要计算工作是将每个样本分配到距离其最近的聚簇，并且分配不同对象之间的操作是相互独立的，因此可以将这一步在Ｈａｄｏｏｐ分布式框架中并行操作．首先，将这Ｋ个聚簇存储在ＨＤＦＳ上作为全局变量，并在每次迭代执行完成后进行更新．簇中包含该簇的簇符、簇中含有的对象的个数及簇的中心，初始聚簇的中心心就是我们先前确定Ｋ个簇中心本．算 法 的 执 行 迭 代 的 过 程 中 包 含Ｍａｐ和Ｒｅｄｕｃｅ2个部分． 在Map函数部分计算各节点数据与初始簇中心的距离，然后将对象标记为离他最近的簇标记。在reduce部分，对输出结果进行归并，将数据点编号和所属的类别的对应关系输出。然后汇总各个map的新的簇中心点重新计算中心点。然后依次迭代。
三、总结
经过改进后的K_均值算法，在簇初始中心点选择上没有采用随机的选择还是采用了基于最大密度与最大距离的思想，减小了随机性带来的影响同时也减小了离群点对算法的影响，因为离群点是属于小密度数据，所以在基于这种改进的情况下，是不会选到离群点的。然后与原来的串行K_means算法比较，本文采用了基于MapReduce的并列算法思想，在运算的时效上有了很大的改进。最后经过在实验室的数据测试，本次算法的改进大大的提高了K_means算法的准确性，并且收敛速度也有了很大提升，在map节点越多的情况下效率越快，解决了在对大数据处理时间长的问题。
参考文献:
[1]Han J,Kamber M,Pei J.数据挖掘概念与技术[M].机械工业出版社,2012.7.
[2]Dunham,M.H.著,郭崇慧,田凤占,勒晓明等译.数据挖掘教程[M].北京:清华大学出版社,2005.
[3]张云涛,龚玲.数据挖掘原理与技术[M].北京:电子工业出版社,2004:123.
【关键词】数据挖掘；聚类 K_means 并行K均值；初始值优化
随着数据库和数据管理产业的不断发展，如今大型的的数据库系统已经普及发展，从常见的关系数据库到企业级的数据仓库已经包含了大量的数据，而数据库系统只提供事务处理，数据仓库提供决策级的数据分析。面对众多的层积在数据库中的知识，对其发现和分析变得越来越重要也越来越困难，在这种背景下数据挖掘便应运而生，从大量的数据中发现知识也变得至关重要。所以我们对数据挖掘的研究显得尤为重要。然而在数据挖掘中聚类分析是最基本也是最重要的，现在国内外对聚类方法中的K_means算法的研究也是如火如荼。面对不通的应用领域K_means算法的改进也是多种多样，但对大型数据K_means算法的局限性也展示了出来，于是并列K_means算法也得到了很好的发展和研究。本文章主要针对大型数据做聚类分析，采用基于Mapreduce并列K_means算法，并对K_means算法的初始值选择加以优化，主要从效率和准确度出发进行研究。
一、传统的K_means算法思想
K_means算法是一种最著名和最普及的聚类方法之一，其目的是将数据对象的数据集M划分成K个相互排斥的簇，使簇与簇之间有高度的相异性，而簇内部具有高度的相似性。在划分的时候一般采取欧式距离为参考。
一般步骤：根据经验确定要聚类的数目K，然后随机的选取K个对象作为K个簇的中心点，再按照欧式距离对其余对象进行距离计算，将其余对象分配到离中心最近的簇中。然后分配完毕后，重新计算各个簇中的平局数，并将这个平均数作为新的中心点。重复这个过程直到簇没有变化为止。
K-均值算法的过程如下：算法：K_means。每个簇都用簇中心表示，簇中心用簇内的对象的均值来表示。输入：K：簇的个数 M：包含n个对象的数据集
输出：k个簇的集合，方法：
（一）从M中任意选择K个对象作为初始簇的中心；
（二）Repeat
（三）根据簇中对象的均值，将每个对象分配到最相似的簇
（四）更新簇的中心
（五）Until不在发生变化
二、改进的K_means并行处理算法
改进的K_means算法，通过预先对大数据进行抽样，然后对样本进行分析采用最长距离法选定簇中心。然后用基于MapReduce的并列K_means算法进行聚类。本文数据来源由随机生成函数随机产生40000条1-100的随机数，然后人为插入10条4位数到数据中。通过抽样函数在数据中抽样100个数为抽样样本。
（一）K_均值初始簇中心的选定
传统的初始中心都是随机抽取，我们对随机抽取进行一些优化。对于初始簇中心选择采取基于距离与密度而确定。基本思想为在样本中选取相距距离最远且样本的密度最大的k个点作为初始簇中心。
下面定义样本点x所处区域的密度 ：
P (x )= {x∈D|Dis(x,d)≤r}其中 D 为样本点集，r为球体半径，Dis (x ,d)为距离测量。样本点x所处区域的密度计算规则为以x为中心，r 为半径的球体所包含的样本个数。半径r的确定规则如下 ：<1> 求解每两个数据对象的距离，然后求出所有距离的平均值λ。然后求出每个样本点所在区域的密度，然后把密度大的区域中的点组成新的集合D1，在集合中取 P 值最大的样本点作为第一个初始中心K1，然后取离K1最远的高密度样本点作为第二个初始簇中心K2 ，然后取满足 max(min(d(Xi，K1),d(Xi，K2))) i=1,2,…,n 的样本点Xi作为第三个初始中心K3，依次类推，取满足 max(min(d(Xi，K1),d(Xi，K2),…d(Xi，KK-1))) i=1,2,…,n 的 样 本 点Xi作为第K个初始簇中心，最后确定了聚类的 k 个初始中心。多次实验改进算法取距离最远的k 个密度大的样本点作为聚类的初始簇中心，这些簇中心点基本上是稳定的，从而而消除了初始中心选择的随机性，提高了聚类结果的精确度。
（二）基于MapReduce的并行K_means算法实现
K_means算法中的主要计算工作是将每个样本分配到距离其最近的聚簇，并且分配不同对象之间的操作是相互独立的，因此可以将这一步在Ｈａｄｏｏｐ分布式框架中并行操作．首先，将这Ｋ个聚簇存储在ＨＤＦＳ上作为全局变量，并在每次迭代执行完成后进行更新．簇中包含该簇的簇符、簇中含有的对象的个数及簇的中心，初始聚簇的中心心就是我们先前确定Ｋ个簇中心本．算 法 的 执 行 迭 代 的 过 程 中 包 含Ｍａｐ和Ｒｅｄｕｃｅ2个部分． 在Map函数部分计算各节点数据与初始簇中心的距离，然后将对象标记为离他最近的簇标记。在reduce部分，对输出结果进行归并，将数据点编号和所属的类别的对应关系输出。然后汇总各个map的新的簇中心点重新计算中心点。然后依次迭代。
三、总结
经过改进后的K_均值算法，在簇初始中心点选择上没有采用随机的选择还是采用了基于最大密度与最大距离的思想，减小了随机性带来的影响同时也减小了离群点对算法的影响，因为离群点是属于小密度数据，所以在基于这种改进的情况下，是不会选到离群点的。然后与原来的串行K_means算法比较，本文采用了基于MapReduce的并列算法思想，在运算的时效上有了很大的改进。最后经过在实验室的数据测试，本次算法的改进大大的提高了K_means算法的准确性，并且收敛速度也有了很大提升，在map节点越多的情况下效率越快，解决了在对大数据处理时间长的问题。
参考文献:
[1]Han J,Kamber M,Pei J.数据挖掘概念与技术[M].机械工业出版社,2012.7.
[2]Dunham,M.H.著,郭崇慧,田凤占,勒晓明等译.数据挖掘教程[M].北京:清华大学出版社,2005.
[3]张云涛,龚玲.数据挖掘原理与技术[M].北京:电子工业出版社,2004:123.