基于量子粒子群优化改进的模糊C-均值聚类方法

摘要

本发明涉及一种聚类方法，尤其是一种基于量子粒子群优化改进的模糊C-均值聚类方法，属于数据挖掘和人工智能的技术领域。本发明在传统的模糊C-均值聚类算法中，首先利用新距离标准取代Euclidean标准，以提高传统聚类算法下的模糊精确度，同时通过AFCM算法单次快速分类替代随机分配初始聚类中心，来降低聚类算法对初始聚类中心的敏感度，最后在聚类过程中引入基于距离改进的QPSO（AQPSO）并行优化思想使其聚类算法具有较强的全局搜索能力、更高的收敛精度，保证收敛速度也明显改善了聚类效果。

主权项

1.一种基于量子粒子群优化改进的模糊C-均值聚类方法，其特征是，所述模糊C-均值聚类方法包括如下步骤：步骤一、聚类参数设定：给定所需的聚类类别c、粒子群规模N、最大迭代次数MAXTER，当前迭代次数t，收缩扩张系数α；步骤二、种群的初始化：定义距离标准d(x_k,v_i)＝1-exp(-β||x_k-v_i||²)                            （1）其中，$\beta ={\left[\frac{1}{n}\left(\underset{k=1}{\overset{n}{\Sigma }}\right||x_k-\bar{x}|\left|\right)\right]}^{-1},$且$\bar{x}=\frac{1}{n}\left(\underset{k=1}{\overset{n}{\Sigma }}{x}_k\right);$利用单次AFCM算法进行快速分类，结合公式（1）得到目标函数$J_{\mathrm{AFCM}}(X,U,V)=\underset{i=1}{\overset{c}{\Sigma }}\underset{k=1}{\overset{n}{\Sigma }}{U}_{\mathrm{ik}}^m[1-\exp (-\beta {\left|\right|x_k-v_i\left|\right|}^2)]---\left(2\right)$其中，X＝{x₁,x₂,…x_k,…x_n}是给定的数据集，n为数据集中样本的个数，x_k(x_k1,x_k2，…,x_kd)表示具有d个属性的数据对象，聚类个数为c，聚类中心集合V＝{v₁,v₂,…,v_c}，其中v_i(v_i1，v_i2，…,v_id)表示第i个聚类中心，U_ik表示第k个样本属于第i类的模糊隶属度，对于任意k,i和模糊加权指数m,使公式（2）达到最小值的必要条件为：$U_{\mathrm{ik}}=\frac{1}{{\Sigma }_{j=1}^c\left\{\right[1-\exp (-\beta {\left|\right|x_k-v_i\left|\right|}^2)]/{[1-\exp (-\beta {\left|\right|x_k-v_j\left|\right|}^2)]\}}^{1/m-1}},1\le i\le c,1\le k\le n---\left(3\right)$中心向量为：$v_i=\frac{\underset{k=1}{\overset{n}{\Sigma }}{U}_{\mathrm{ik}}^m\left(\exp (-\beta {\left|\right|x_k-v_i\left|\right|}^2)\right)x_k}{\underset{k=1}{\overset{n}{\Sigma }}{U}_{\mathrm{ik}}^m\left(\exp (-\beta {\left|\right|x_k-v_i\left|\right|}^2)\right)}---\left(4\right)$利用公式（4）得到的聚类中心向量作为种群中的一个初始粒子，并重复进行N次，生成初始种群；步骤三、粒子的全局搜索：在一个d维的目标搜索空间中，QPSO算法由N个代表潜在问题解的粒子组成群体X(t)＝{X₁(t),X₂(t),…,X_N(t)}，在t时刻，第i个粒子位置为粒子没有速度向量，个体最优位置Pbest表示为p_i(t)＝(p_i1(t),p_i2(t),…,p_id(t))，全局最优位置Gbest表示为G(t)＝(G₁(t),G₂(t),…,G_j(t)…,G_d(t))，且G(t)＝p_g(t)，其中g为粒子群体处于全局最优位置的下标，g∈{1,2,…,N}；定义所有粒子个体的最优平均位置C(t)，即$C\left(t\right)=(C_1\left(t\right),C_2\left(t\right),...C_j\left(t\right),...C_d\left(t\right))$$=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{p}_i\left(t\right)=(\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{p}_{i1}\left(t\right),\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{p}_{i2}\left(t\right),...,\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{p}_{\mathrm{ij}}\left(t\right),...,\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{p}_{\mathrm{id}}\left(t\right))---\left(6\right)$粒子的个体最优位置Pbest由下述公式确定为$p_i\left(t\right)=\left\{\begin{array}{cc}{X}_i\left(t\right)& f\left[X_i\left(t\right)\right]<f\left[p_i(t-1)\right]\\ p_i(t-1)& f\left[X_i\left(t\right)\right]\ge f\left[p_i(t-1)\right]\end{array}\right.---\left(7\right)$其中，f[X]＝J_AFCM(X，U，V)；整个粒子群的全局最优位置Gbest由下述公式确定为$g=\arg \underset{1<i\le N}{\mathrm{Min}}\left\{f\right[p_i\left(t\right)\left]\right\}---\left(8\right)$G(t)＝P_g(t)                                                    (9)更新粒子时，首先得到粒子的个体最优位置Pbest及整个粒子群的全局最优位置Gbest，其次利用公式(2)更新所有粒子个体的适应度值，并将每一个粒子的当前个体位置适应度值与全局最优位置的适应度值比较；若每一个粒子的当前个体位置适应度值优于全局最优位置的适应度值，更新公式(9)中的G(t)；令则粒子的进化方程为：$X_{i,j}(t+1)=P_{i,j}\left(t\right)\pm \alpha *|C_j\left(t\right)-X_{i,j}\left(t\right)|*\ln \left(\frac{1}{u_{i,j}\left(t\right)}\right),u_{i,j}\left(t\right)~U\left(\mathrm{0,1}\right)---\left(11\right)$其中，u_i，j(t)为符合正态分布的辅助参数；G_j(t)表示粒子群体的全局最优位置；步骤四、输出聚类结果：重复上述粒子更新操作，如果当前的迭代次数达到预先设定的最大次数MAXTER，则停止迭代输出最佳聚类效果。