聚类分析是数据挖掘的一种非常重要的方法, K-means算法是一个基于划分且应用非常广泛的聚类算法[1], 但它的初始聚类中心的选择决定了K-means算法的划分结果, 若选取不当, 可能会导致算法陷入局部最优解.很多学者对该问题进行了研究与改进, 如文献[2]利用云模型云滴的随机性和稳定趋向性设计遗传算法的交叉和变异概率, 并与K均值结合, 有效提高收敛速度和聚类能力; 文献[3]通过动态调整粒子的惯性权重系数及飞行时间增强了粒子群的全局搜索能力, 消除K-means算法聚类结果对初始聚类中心的依赖性; 文献[4]利用改进后的人工蜂群算法与K均值算法结合改善聚类性能; 文献[5]提出基于最优类中心扰动的萤火虫聚类算法, 提高算法的聚类效果; 文献[6]将改进的差分进化算法和K-means聚类算法相结合, 有效提高聚类结果的质量和稳定性; 文献[7]将自适应策略用于人工鱼群算法的改进中, 与K均值算法融合, 避免陷入局部最优, 提高收敛速度.但数据集中常常会因一些人为因素或固有数据变异而存在孤立点, 孤立点有时会隐藏一些重要的信息, 上述文献虽然都有效地提高了算法的聚类能力, 但均未考虑孤立点对聚类结果的影响.本文考虑用最近邻距离差的检测算法[8]检测孤立点, 用马氏距离再将孤立点重新归类的方法减弱孤立点对聚类的影响.另外, 为了避免K-means算法陷入局部最优解, 用花粉算法(FPA) 搜寻K-means算法的初始聚类中心, 但花粉算法的花粉配子在过于集中时, 算法易陷入局部极值, 收敛速度缓慢, 因此为了使得花粉算法在陷入局部最优时能重新获得解的多样性, 跳出局部极值, 考虑将高斯白噪声扰动加入到花粉算法中.而且高斯白噪声扰动已被成功地加入到粒子群[9]、布谷鸟[10]、蝙蝠[11]等优化算法中, 有效提高了算法的全局搜索能力.最后验证了改进后K-means算法的有效性.
1 相关算法 1.1 K-means算法K-means算法是由McQueen在1967年提出的, 它是聚类分析中最常用一种典型的划分算法, 其目标是将数据根据某种相似性度量方法进行划分, 使每个数据到所属簇类中心的距离尽可能小, 不同簇类间的距离尽可能大.由于该算法具有简单、容易理解、效率较高, 并且适用于大数据集的优点而被广泛应用.其算法的步骤为: (1) 从待操作的数据集里面随机选择k个初始聚类中心点；(2) 逐个计算每个数据对象到各个聚类中心点的距离, 然后分配给距离最短的集合；(3) 重新计算每个划分的中心点坐标并更新产生新的划分；(4) 判断是否满足停止条件, 若满足则输出聚类结果, 否则转至步骤(2).其中, 相似性度量采用欧几里得距离计算方法, 聚类中心为类内所有数据对象的均值.
1.2 花粉算法花粉算法是英国剑桥大学学者Yang于2012年提出一种新型元启发式群智能优化算法[12-13].由于该算法实现简单、参数少、易调节, 能较好地解决全局搜索和局部搜索的平衡问题, 且同时采用了Levy飞行机制, 使其具有良好的全局寻优能力.花粉算法使用有四条规则[14-15]:
(1) 生物异花授粉是带花粉的传粉者以式(1) 进行全局授粉过程, 其中L服从式(2);
(2) 非生物自花授粉是按照式(3) 进行局部授粉过程;
(3) 花恒常可以被认为是正比于某两朵相似性的繁殖概率；
(4) 转换概率p∈[0，1]控制全局授粉和局部授粉之间的转换, p对局部授粉影响大.
| $x_i^{i + 1} = x_i^i + L\left( {x_i^i-g} \right)$ | (1) |
| $L \sim \frac{{\lambda \mathit{\Gamma }\left( \lambda \right)\sin \left( {\pi \lambda /2} \right)}}{\pi }\frac{1}{{{s^{1 + \lambda }}}}, \left( {s \gg {s_0} > 0} \right), $ | (2) |
| $x_i^{i + 1} = x_i^i + \varepsilon \left( {x_j^i-x_k^i} \right).$ | (3) |
花粉算法虽已在函数优化[16]、文本聚类[17]、电力系统[18]等应用领域取得了较好的成效, 但也存在易陷入局部极值且后期收敛速度慢等缺陷, 使其应用范围受到限制.为了保证算法跳出局部最优, 考虑在花粉配子过分集中的时候将种群分散, 在当前最优解gbest附近进行高斯白噪声扰动以增加解的多样性, 即作以下改进:
| ${g_{{\rm{best}}d}} = {g_{{\rm{best}}d}} + 0.1{\rm{rand}}n\left( {1, S} \right).$ | (4) |
其中, randn(1, S) 为产生正态分布的高斯白噪声; S=size (gbestd, 1), gbestd表示全局最优解的第d维.
为了检验高斯白噪声扰动改进花粉算法(GFPA) 的全局搜索能力, 用4个测试函数对FPA和GFPA算法进行对比实验, 测试函数见表 1, 测试函数最优解位置与2种算法搜索到的最优解的位置见表 2，测试函数电优解与算法搜索到的最优解间的距离见表 3.其中D1和D2分别表示FPA算法和GFPA算法搜索到的最优解的位置与测试函数最优解的位置的距离.
| 名称 | 测试函数 | |
| 1 | Booth′s function | f1(x)=(x1+2x2-7)2+(2x1+x2-5)2, -10≤xi≤10 i=1, 2 |
| 2 | Mc Cormick function | f2(x)=sin (x1+x2)+(x1-x2)2-1.5x1+2.5x2+1, -1.5≤x1≤4, -3≤x2≤4 |
| 3 | Hump function | f3(x)=4x1-2.1x14+(1/3)x16+x1x2-4x22+4x24, -5≤xi≤5 i=1, 2 |
| 4 | Price1 function | f4(x)=(|x1|-5)2+(|x2|-5)2, -500≤xi≤500 i=1, 2 |
| f1(x) | f2(x) | f3(x) | f4(x) | |
| 最优解位置 | (1, 3) | (-0.547 19, -1.549 8) | (0.089 8, -0.712 6) (-0.089 8, 0.712 6) |
(5, 5) (5, -5) (-5, 5) (-5, -5) |
| FPA | (1.8, 2) | (-0.494 38, -1.517 6) | (0.160 4, -0.777 4) (-0.155 1, 0.557 3) |
(5.002 5, 4.997 9) (4.998 2, -5.002 0) (-4.997 6, 5.002 3) (-5.002 1, -5.000 9) |
| GFPA | (1.7, 2.4) | (-0.526 03, -1.537 6) | (0.115 7, -0.755 6) (-0.098 6, 0.723 6) |
(5.000 7, 5.001 1) (5.000 4, -5.000 9) (-5.000 2, 5.000 8) (-5.001 3, -5.000 5) |
| 距离 | f1(x) | f2(x) | f3(x) | f4(x) | |
| D1 | 1.280 6 | 0.061 9 | 0.095 8 0.168 5 |
0.003 265 0.003 324 |
0.002 691 0.002 285 |
| D2 | 0.922 0 | 0.024 4 | 0.050 2 0.014 1 |
0.001 304 0.000 825 |
0.000 985 0.001 393 |
| D1-D2 | 0.358 6 | 0.037 5 | 0.045 6 0.154 4 |
0.001 961 0.002 499 |
0.001 706 0.000 892 |
由表 2和3可知对于测试函数1, (1, 3) 为测试函数全局最优解的位置, FPA算法搜索到的全局最优解的位置为(1.8, 2), 而GFPA算法搜索到全局最优解的位置为(1.7, 2.4), (1.7, 2.4) 到(1, 3) 之间的距离为1.280 6, 比(1.8, 2) 到(1, 3) 之间的距离小, 说明GFPA算法搜索到最优解位置更接近于测试函数全局最优解位置; 同理对于测试函数2, 3, 4, 从D1-D2这项都大于0说明对于有单个或多个最优解的测试函数, GFPA算法搜索到最优解位置更接近于测试函数全局最优解位置, 说明GFPA算法优于FPA算法, 有更强大的全局搜索能力.
2 基于改进FPA的K-means聚类算法 2.1 基于距离的孤立点检测与处理数据集中常常会因一些人为因素或固有数据变异而存在孤立点, 且孤立点有时会隐藏一些重要的信息, 若直接排除, 会造成重要信息的丢失.为了使K均值算法免受孤立点的影响, 考虑用最近邻距离差的检测算法[8]检测孤立点, 计算数据集中所有数据对象两两之间的欧氏距离的平方, 按升序排列得N*N的矩阵D, 选取第k个最近邻距离完成对所有数据对象的降序排列和排在前n0位数据对象的选取, 计算选出对象的相邻距离差得到阈半径maxΔD; 并取得计算D矩阵的每一行小于阈半径的距离数目和其位置各为一列, 按降序组成N*2矩阵Num, 将Num矩阵相邻两行第一列元素两两相除, 得到最大比值的除数C, 作为密集度阈值; 找出Num矩阵中第一列元素小于C的所有数据对象, 即强孤立点.根据需要再设置较大的密集度阈值可找出弱孤立点.
利用该方法对本文的实验数据进行孤立点检测, 两组数据检测出来的孤立点为:(-0.516 5, 2.609 5), (-0.679 1, -1.257 8), (2.377 5, 1.805 1), (0.608 4, 2.533 4), (0.712 6, 2.208 3), (-0.088 1, 1.242 9), (-1.143 3, 0.132 1), (0.738 3, 1.265 2, 0.785 1), (0.912 0, 1.580 2, 1.805 0), (0.619 9, 1.457 7, 1.151 8), (2.254 5, 1.040 3, 1.235 0), (-0.379 4, 2.749 1, -0.421 1), (2.059 7, 1.568 2, 1.660 8).再将孤立点到聚类中心以马氏距离最小原则重新归类, 消弱聚类对孤立点的敏感, 改善无监督聚类的结果.
2.2 GFPA-Kmeans算法利用改进后的花粉算法搜索K-means全局最优的初始聚类中心, 再用基于距离的方法检测并将孤立点归类.由均值-标准差来决定初始聚类中心, 即初始解.
假设所有数据的均值为μ, 标准差为σ, 分类个数为K, 设第i类的初始分类中心为mi, 则
| ${m_i} = \left( {\mu-\sigma } \right) + \frac{{2{\sigma _i}}}{K}, i = 1, \cdots, K.$ | (5) |
若参与分类的是d维数据, 设第i类聚类初始中心值为(mi1, mi2, …, mid), 则
| ${m_{il}} = \left( {{\mu _l}-{\sigma _l}} \right) + \frac{{2\sigma _l^i}}{K}, i = 1, \cdots, K;l = 1, \cdots, d.$ | (6) |
GFPA-Kmeans聚类算法的步骤如下:
Step 1 对种群的n个花粉配子进行初始化, 定义转移概率p∈[0, 1], 最大迭代次数Tmax.从数据集X中随机选择K个中心点, 将其作为花粉配子xi的初值, 找出此时目标函数最优解g.
Step 2 执行FPA算法进行迭代搜索对FPA中的每个花粉配子进行以下操作:
(1) 随机产生一个随机数rand, 若rand < p则按式(1) 进行全局授粉, 其中L服从式(2);否则, 按照式(3) 进行局部授粉.评价新解, 若新解更好, 则更新种群, 找到当前最优解g.
(2) 若全局最优解连续若干代没有得到提升, 按照式(4) 对其进行高斯白噪声扰动以产生新的全局最优解, 计算花粉配子的适应度值.
(3) 由均值-标准差决定初始聚类中心, 按照式(5) 或式(6) 计算更新聚类中心.
(4) pre_u是上一次求得的聚类中心位置, u为当前得到的聚类中心位置, 规定‖pre_u-u‖ < 0.001为判断准则.
Step 3 若通过准则判断花粉配子已趋向收敛或者循环达到最大迭代次数Tmax, 终止花粉算法的迭代并将gbest对应的花粉配子作为K个初始聚类中心, 否则转Step 2继续迭代执行.
Step 4 执行K-means算法, 指定阈半径maxΔD和密集度阈值C, 找出Num矩阵中第一列元素小于C的所有数据对象, 即强孤立点, 根据需要设置较大的密集度阈值可找出弱孤立点, 并存储.否则依照最近邻原则划分数据集.
Step 5 以马氏距离最小原则重新归类孤立点到聚类中心, 按类输出最终的聚类结果.
3 实验与分析为了验证GFPA-Kmeans算法的有效性, 随机100次取样, 运算后取平均值.实验环境为:操作系统Windows 7, Intel Core3CPU 2.20GHz, 内存2GB, 编译软件为Matlab 7.11.0.实验中算法的各个参数分别为:花粉的种群规模大小m=20, 最大迭代次Tmax=100, 转移概率p=0.8, K=3.每组由3个小数据集组合而成, 其中每个小数据集服从不同均值和协方差的高斯分布.第一组为300个二维数据, 聚类中心为3×2的矩阵; 第二组为300个三维数据, 聚类中心为3×3的矩阵.两组实验数据原始分类:1~100为类别1, 101~200为类别2, 201~300为类别3.得到聚类结果如图 1~4所示.
|
| 图 1 K-means聚类结果 Fig.1 K-means clustering results |
|
| 图 2 GFPA-Kmeans聚类结果 Fig.2 GFPA-Kmeans clustering results |
|
| 图 3 K-means聚类结果 Fig.3 K-means clustering results |
|
| 图 4 GFPA-Kmeans聚类结果 Fig.4 GFPA-Kmeans clustering results |
由图 1可知传统的K-means聚类对二维数据的聚类图不理想, 易受孤立点和初值的影响, 存在不稳定性, 其中第1类数据错误归为第2类, 第2类数据和第3类数据归类不明显.而由图 2可知GFPA-Kmeans聚类结果比较理想, 聚类效果图更明显且稳定, 能有效克服孤立点和初始聚类中心对聚类结果的影响.由表 4可知相比K-means聚类, GFPA-Kmeans的准确性有明显的提高, 结果更准确.
| % | |||
| 算法 | 第1类 | 第2类 | 第3类 |
| K-means GFPA-Kmeans |
84.2 91.4 |
79.4 90.2 |
84.6 91.3 |
由图 3可知传统的K-means聚类对三维数据的聚类结果存在缺陷, 因初始聚类中心和孤立点的影响会出现偏差导致错误分类, 尤其在各类的边界处聚类出错率比较大.而由图 4可知GFPA-Kmeans聚类结果比K-means更好并且稳定, 由表 5可知相比K-means聚类, GFPA-Kmeans算法聚类的准确性较高, 有效地克服了传统K-means聚类对初始聚类中心敏感的缺点.
| % | |||
| 算法 | 第1类 | 第2类 | 第3类 |
| K-means GFPA-Kmeans |
84.6 90.5 |
81.2 90.7 |
85.2 90.4 |
为了进一步验证GFPA-Kmeans算法的性能, 通过UCI中的iris和wine数据集对算法进行测试.iris数据集包括3类共150个样本, 每个样本有4个属性, wine数据集包括3类共178个样本, 每个样本有13个属性.对每个数据集分别用K-means算法, FPA-Kmeans算法、改进PSO-Kmeans算法[3]、(IABC-Kmeans) 算法[4]以及本文的GFPA-Kmeans算法进行实验, 每个算法均随机运行50次.结果见表 6~7.
| 算法 | 平均耗时/s | 准确率/% | 迭代次数 |
| Kmeans FPA-Kmeans 改进PSO-Kmeans IABC-Kmeans GFPA-Kmeans |
0.328 1 0.361 7 0.292 8 0.342 1 0.261 2 |
80.3 85.6 90.2 89.7 91.4 |
100 150 160 200 100 |
| 算法 | 平均耗时/s | 准确率/% | 迭代次数 |
| Kmeans FPA-Kmeans 改进PSO-Kmeans IABC-Kmeans GFPA-Kmeans |
0.343 7 0.334 5 0.471 9 0.394 2 0.270 1 |
68.5 70.3 71.6 79.5 80.2 |
120 140 200 210 110 |
从表 6中可以看出, GFPA-Kmeans算法对于iris数据集平均耗时为0.261 2, 准确率为91.4%, 迭代次数为100.从表 7中可以看出, GFPA-Kmeans算法对于wine数据集平均耗时为0.270 1, 准确率为80.2%, 迭代次数为110.在所有对比算法中耗时最短, 准确率最高, 迭代次数最少.表 6和表 7均说明GFPA-Kmeans算法能够在最短的时间内跳出局部极值, 得到新的适应度值, 迭代次数减少, 从而得到最优的初始聚类中心, 消弱了孤立点的影响, 算法更稳定, 聚类结果更理想.
4 结束语通过对陷入局部极值的花粉配子加入高斯白噪声扰动, 增加花粉算法的多样性, 克服早熟收敛的问题.利用改进后的花粉算法强大的全局搜索能力对K-means初始聚类中心优化, 以均值-标准差的方法选取初始聚类中心, 并用基于距离的方法消弱孤立点对聚类的影响, 使其更好地归类.实验结果表明文中提出的改进算法与传统K-means算法相比具有更高的正确率, 聚类效果更好.
| [1] | BRADLEY P S, FAYYAD U M.Refining initial points for K-Means clustering[C].Proceeding of the 15th International Conference on Machine Learning, Sam Francisco, 1998:91-99. |
| [2] |
许茂增, 余国印. 基于云自适应遗传算法的K-means聚类分析[J].
数学的实践与认识, 2015, 45(17): 48-55 XU Maozeng, YU Guoyin. K-means clustering analysis based on cloud adaptive genetic algorithm[J]. Mathematice in Practice and Theory, 2015, 45(17): 48-55 |
| [3] |
谢秀华, 李陶深. 一种基于改进PSO的K-means优化聚类算法[J].
计算机技术与发展, 2014, 24(2): 34-38 XIE Xiuhua, LI Taoshen. An optimized K-means clustering algorithm based on improved particle swarm optimization[J]. Computer Technology and Development, 2014, 24(2): 34-38 |
| [4] |
喻金平, 郑杰, 梅宏标. 基于改进人工蜂群算法的K均值聚类算法[J].
计算机应用, 2014, 34(4): 1065-1069 YU Jingping, ZHENG Jie, MEI Hongbiao. K-means clustering algorithm based on improved artificial bee colony algorithm[J]. Journal of Computer Applications, 2014, 34(4): 1065-1069 |
| [5] |
赵杰, 雷秀娟, 吴振强. 基于最优类中心扰动的萤火虫聚类算法[J].
计算机工程与科学及仪表, 2015, 37(2): 342-347 ZHAO Jie, LEI Xiujuan, WU Zhenqiang. An improved firefly clustering algorithm based on optimal class-center disturbance[J]. Computer Engineering and Science, 2015, 37(2): 342-347 |
| [6] |
刘莉莉, 曹宝香. 基于差分进化算法的K-means算法改进[J].
计算机技术与发展, 2015, 25(10): 88-92 LIU Lili, CAO Baoxiang. Improvement of K-means algorithm based on differential evolution algorithm[J]. Computer Technology and Development, 2015, 25(10): 88-92 |
| [7] |
吕少娟, 张桂珠. 一种融合K-means算法和人工鱼群算法的聚类方法[J].
计算机应用与软件, 2015, 32(9): 240-243 LYU Shaojuan, ZHANG Guizhu. A new clustering method combining K-means and artificial fish swarm[J]. Computer Applications and Software, 2015, 32(9): 240-243 |
| [8] |
侯晓晶, 王会青, 陈俊杰, 等. 基于最近邻距离差的改进孤立点检测算法[J].
计算机工程与设计, 2013, 34(4): 1265-1268 HOU Xiaojing, WANG Huiqing, CHEN Junjie, et al. Improved outlier detection algorithm based on difference between nearest neighbors distance[J]. Computer Engineering and Design, 2013, 34(4): 1265-1268 |
| [9] |
刘衍民. 一种求解约束优化问题的混合粒子群算法[J].
清华大学学报:自然科学版, 2013, 53(2): 242-246 LIU Yanmin. Hybrid particle swarm optimizer for constrained optimization problems[J]. Journal of Tsinghua University:Science & Technology, 2013, 53(2): 242-246 |
| [10] |
张毅, 贺兴时, 杨新社. 基于模拟退火与高斯扰动的布谷鸟算法[J].
纺织高校基础科学学报, 2015, 28(4): 515-521 ZHANG Yi, HE Xingshi, YANG Xinshe. A cuckoo search algorithm based on simulated annealing and Gaussian disturbance[J]. Basic Science Journal of Textile Universities, 2015, 28(4): 515-521 |
| [11] |
贺兴时, 丁文静, 杨新社. 基于模拟退火高斯扰动的蝙蝠优化算法[J].
计算机应用研究, 2014, 31(2): 392-397 HE Xingshi, DING Wenjing, YANG Xinshe. Bat algorithm based on simulated annealing and Gaussian perturbations[J]. Application Research of Computers, 2014, 31(2): 392-397 |
| [12] | YANG Xinshe.Flower pollination algorithm for global optimization[C]//Proceeding of the 11th International Conference on Unconventional Computation and Natural Computation, Belin:Spring-Verlag, 2012:240-249. |
| [13] | YANG Xinshe, KARAMANOGLU Mehmet, HE Xingshi.Flower pollination algorithm:A novel approach for multiobjective optimization[C]//Engineering Optimization, London:Taylor & Francis, 2013:1-16. |
| [14] |
乔现伟, 贺兴时, 杨新社, 等. 基于混沌的花粉算法[J].
纺织高校基础科学学报, 2015, 28(3): 330-334 QIAO Xianwei, HE Xingshi, YANG Xinshe, et al. Chaos-based flower algorithm[J]. Basic Science Journal of Textile Universities, 2015, 28(3): 330-334 |
| [15] | YANG Xinshe. Review of Meta-heuristics and generalised evolutionary walk algorithm[J]. International Journal of Bio-Inspired Computation, 2011, 3(2): 77-84 DOI:10.1504/IJBIC.2011.039907 |
| [16] | YANG Xinshe, KARAMANOGLU M, HE Xingshi. Multi-objective flower algorithm for optimization[J]. Procedia Computer Science, 2013, 18(1): 861-868 |
| [17] | KAUR M, KAUR N. Text clustering using PBO algorithm for analysis and optimization[J]. International Journal of Current Engineering and Technology, 2014, 4(6): 3876-3878 |
| [18] | PRATHIBA R, MOSES M B, SAKTHIVEL S. Flower pollination algorithm applied for different economic load dispatch problems[J]. International Journal of Engineering and Technology, 2014, 6(2): 1009-1016 |