基于最小生成树的集成多目标进化自动聚类方法

摘要

本发明提出了一种基于最小生成树的集成多目标进化自动聚类方法，克服了现有技术中对高维数据集处理效果不佳的问题。其实现步骤是：(1)输入待聚类的基因数据集；(2)初始化；(3)设定迭代参数；(4)计算簇间相似性；(5)生成最小生成树；(6)断开最小生成树；(7)合并种群；(8)快速非支配排序；(9)计算拥挤度；(10)生成新的父代种群；(11)判断迭代次数是否小于50；(12)选择最优个体；(13)计算最优个体的精确值；本发明提出的方法运行速度快，可有效地对各种基因数据集进行聚类分析，不需要预先设定数据集的类别数，能够应用于生物医学识别、肿瘤检测等领域中存在的高维度数据分析。

主权项

一种基于最小生成树的集成多目标进化自动聚类方法，具体步骤如下：(1)输入待聚类的基因数据集；(2)初始化：(2a)设定待聚类基因数据集的类别数区间；(2b)采用K均值算法，分别将待聚类基因数据集的类别数区间中的每一个值作为待聚类基因数据集的类别数，对确定类别数的待聚类基因数据集进行聚类，得到不同的K均值基聚类种群；(2c)采用平均距离算法，分别将待聚类基因数据集的类别数区间中的每一个值作为待聚类基因数据集的类别数，对确定类别数的待聚类基因数据集进行聚类，得到不同的平均距离基聚类种群；(2d)采用最大距离算法，分别将待聚类基因数据集的类别数区间中的每一个值作为待聚类基因数据集的类别数，对确定类别数的待聚类基因数据集进行聚类，得到不同的最大距离基聚类种群；(2e)采用谱聚类算法，分别将待聚类基因数据集的类别数区间中的每一个值作为待聚类基因数据集的类别数，对确定类别数的待聚类基因数据集进行聚类，得到不同的谱聚类基聚类种群；(2f)将K均值基聚类种群、平均距离基聚类种群、最大距离基聚类种群、谱聚类基聚类种群合并为父代种群；(3)设定迭代参数：将最大迭代次数设定为50次，初始迭代次数为1，迭代步长为1；(4)计算簇间相似性：按照下式，计算父代种群中所有簇之间的相似性：$ECS(C_1,C_2)=\frac{1}{\left|C_1\right|\left|C_2\right|}\underset{d_1\in C_1,d_2\in C_2}{\Sigma }sim(d_1,d_2)$其中，ECS(·)表示父代种群中任意两个簇的簇间相似性，C₁，C₂分别表示父代种群中不同的两个簇，|C₁|、|C₂|分别表示簇C₁和簇C₂中所包含的数据点个数，∑表示求和操作，∈表示属于符号，d₁表示父代种群簇C₁中的数据点，d₂表示父代种群簇C₂中的数据点，sim(·)表示父代种群中不同的数据点出现在同一个簇中的次数；(5)生成最小生成树：(5a)采用普利姆算法，生成最小生成树，最小生成树中的每个节点代表父代种群中的每个簇；(5b)将最小生成树中任意两个节点的簇间相似性的值赋予连接这两个节点边的权值；(6)断开最小生成树：(6a)将最小生成树所有边中权值最小的边断开，将整个最小生成树分成c个子生成树，其中，c表示待聚类基因数据集的真实类别数；(6b)采用投票法，确定每个节点表示的簇中的数据点所属的个子生成树；(6c)判断最小生成树中的所有边是否都断开，若是，则得到一个与父代种群规模相同的子种群，执行步骤(7)；否则，执行步骤(6a)；(7)合并种群：将与父代种群规模相同的子种群与父代种群合并为二倍种群；(8)快速非支配排序：(8a)搜索二倍种群中的被支配个体数量为0的个体，将其全部放入第一集合中，并赋予该集合中每个个体相应的非支配序；(8b)对第一集合中个体所支配个体的子集合中的被支配个体数量为1的个体，其放入第二集合中，赋予该集合中个体相应的非支配序；(8c)判断二倍种群中的所有个体是否都被分级，若是，则执行步骤(9)；否则，执行步骤(8b)；(9)计算拥挤度：计算二倍种群中每个个体的拥挤度，按照拥挤度的大小进行降序排列，得到拥挤度序；(10)生成新的父代种群：将二倍种群中每个个体按照非支配序从小到大排列，相同的非支配序个体之间按照拥挤度序从大到小排列，从排列好的二倍种群中选择前一半个体组成新的父代种群；(11)判断迭代次数是否小于50，若是，将迭代次数加1，执行步骤(4)；否则，执行步骤(12)；(12)选择最优个体：计算父代种群中每个个体的评价函数值，将父代种群中评价函数值最大的个体作为父代种群中的最优个体；(13)计算最优个体的精确值：按照下式，计算父代种群中的最优个体的精确值：$CR=\frac{{\Sigma }_i^R{\Sigma }_j^C{n}_{ij}-n{\Sigma }_i^R{n}_i{\Sigma }_j^C{n}_j}{\frac{1}{2}\left[{\Sigma }_i^R{n}_i+{\Sigma }_j^C{n}_j\right]-\frac{1}{n}{\Sigma }_i^R{n}_i{\Sigma }_j^C{n}_j}$其中，CR表示父代种群中最优个体的精确值，∑表示求和操作，R表示父代种群中个体u所包含的数据点个数，i表示父代种群个体u中的任意一个数据点，C表示父代种群中个体v所包含的数据点个数，j表示父代种群个体v中的任意一个数据点，u、v分别表示父代种群中的任意两个个体，n_ij表示同时出现在簇u_i和簇v_i中的数据点的个数，n表示输入的待聚类数据集的数据点个数，n_i表示只出现在簇u_i中的数据点个数，n_j表示只出现在簇u_j中的数据点个数，u_i表示父代种群中个体u中任意一个簇，v_i表示父代种群中个体v中的任意一个簇。