基于分组模型的引力搜索智能大数据聚类方法.docx

? ? 基于分组模型的引力搜索智能大数据聚类方法 ? ? 胡晓东，高嘉伟 (1.山西经济管理干部学院 电子信息工程系，山西 太原 030024； 2.山西大学 计算机学院，山西 太原 030024) 0 引 言 数据聚簇是目前最为流行也最为重要的一种数据分析手段[1]，其目标是以数据对象集合分组的方式将其聚类成簇，使同一聚簇内的数据对象具有最大的相似性，即同质数据，而不同聚簇内的数据对象间具有最大的差异性，即异质数据[2]。数据聚簇广泛应用于诸多领域，如机器学习[3]、模式识别[4]、图像处理[5]、数据挖掘[6]等。 目前，受万有引力定理和物体运动规律的启发，一种基于随机种群的元启发式算法被提出，即引力搜索算法GSA[7]。GSA的设计初衷是求解连续最优化问题，与多数元启发式算法相似，该算法拥有较好灵活性，且在加强搜索和开发能力的均衡性上表现突出。GSA的搜索策略是利用万有引力定理将种群成员向着种群中最优的K个解移动。受该算法在变体最优化问题中的启发，本文提出一种基于分组的GSA算法GGSA实现大数据的聚簇求解。提出的GGSA算法与标准的GSA具有两个方面的不同。首先，算法设计一种分组编码策略，将数据聚簇问题的相关结构映射为解的部分；其次，对于给定的聚簇编码，适合于分组编码的解的位置更新与速度更新公式在GGSA算法中被重新定义。为了评估GGSA算法在数据聚簇上的性能，选取了13种经典的数据集进行了测试。对于给定的D个聚簇的数据集，GGSA试图通过随机选择的给定数据集的75%来寻找D个聚簇中心，这75%的数据集称为GGSA的训练数据集。而剩余的25%数据集则用于评估GGSA算法的性能，称之为测试集，而分类失误比率CEP则用于评估算法在测试集中的聚簇性能。 1 相关研究 数据聚簇方法已有很多研究，传统的数据聚簇算法的分类主要以分层和分割的方式进行区分[8]。分层的聚簇算法主要以凝聚式模式或群集式模式递归寻找数据聚簇。凝聚式方法以单个数据对象作为一个分离聚簇，然后连续地合并最具最似性的聚簇直到满足聚簇终止条件。群集式方法初始将所有数据对象视为一个聚簇，然后重复地分割每个聚簇为更小的聚簇，直到满足终止条件。另一方面，分割式聚簇算法试图在不构建分层结构的情况下同步寻找所有的聚簇。事实上，分割聚簇算法初始获得的是不相交的聚簇集合，然后逐步提炼使其满足最小化的预定义目标函数，其目标是在最小化聚簇间的联系的同时最大化聚簇内的联系性，从而实现最大化的数据紧密度，该方法也是本文的研究方法背景。 除了传统的数据聚类方法以外，基于算法聚类标准的不同还有几种聚类方法[9]。第一种是基于邻居共享相同聚类的聚类算法，这类方法主要有基于密度的算法[10]和最近邻邻居方法[11]，前者根据对象密度进行聚类，后者则将近邻对象归属于相同聚类中。双聚类算法[12]同步通过行和列进行数据聚类，多目标聚类算法[13]则同步优化了数据集的不同特征进行聚类。重叠聚类算法[14]不同于多数的聚类算法，传统算法中每个对象仅属于一个聚类，而重叠聚类中每个对象可分属于不同的聚类中，最具代表性的重叠聚类即为模糊C均值聚类算法[15]。 近年来，元启发式方法广泛应用在数据聚类问题中。从优化角度上看，聚类问题可建立模型为一类NP难的群组划分问题[16]。这类算法需要搜索一个聚类的最优解，可以降低搜索过程陷入局部最优的风险。具体包括遗传算法GA[17]、模拟退火算法SA[18]、禁忌搜索算法Tabu[19]、智能蜂群算法ABC[20]、贪婪随机自适应搜索算法GRASP[21]、迭代局部搜索算法ILS[22]、可变邻居搜索算法VNS[23]、蚁群算法ACO[24]、粒子群优化算法PSO[25]等。 引力搜索算法GSA是受牛顿的万有引力定理的启发而提出的一种元启发式优化算法。算法中，搜索空间中的一个对象因为质量和重力的关系相互吸引，其吸引力与对象的质量成正比，而与距离的平方成反比。GSA已经被证明可应用于不同类型的优化方法中，包括数据聚类[26]、模糊系统识别[27]、分类问题[28]、排放负载分配[29]、风力涡轮控制[30]以及供电系统[31]中。然而，传统的引力搜索算法直接应用于数据聚类问题时，在问题解的编码机制和解的迭代更新机制上依然存在不足，会导致最优解的搜索过程过早收敛，本文将从这两个方面进行改进，并验证改进后的聚类算法性能。 2 数据聚簇问题 数据对象距离的度量是数据聚簇问题的关键，两个不同的数据对象Oi和Oj间的相似性与特征空间S中的距离是密切相关的，而空间S中的距离度量常用方式是Euclidean欧氏距离。衡量聚簇结果质量的常用目标函数为考虑聚簇内聚度的二次误差之和，可以评价一个给定数据分割的质量，定义为 (1) (2) 式中：|Ci|代表聚簇Ci的基数，即聚簇i中