Page 377 - 《软件学报》2024年第4期

徐怡 等: 基于遗传算法的划分序乘积空间问题求解层选择 1955

O(N) . 因此, 两阶段遗传算法的第 1 O(m×|U| ×|C|× N ×T 1 ) . 两
2
复杂度为 阶段, 迭代次数为 T 1 , 其时间复杂度为
2
阶段遗传算法的第 2 阶段, 迭代次数为 T 2 , 其时间复杂度为 O(m×|U| ×|C|× N ×T 2 ) . 通常 T 1 ⩽ T 2 , 所以两阶段自
2
适应遗传算法的时间复杂度为 O(m×|U| ×|C|× N ×T 2 ) .
对于两阶段自适应遗传算法, 在算法的一次迭代过程中, 对于适应度函数需要计算分类精度, 空间复杂度为
|C| 为视角中属性个数. 选择算子
O(m×|U|×|C|) , 其中 m 为视角的个数, 即染色体的长度, |U| 为视角中对象个数,
的空间复杂度均为 O(N ×m) , 其中 N 为种群规模. 交叉算子的空间复杂度为 O(N ×m) . 变异算子的空间复杂度为
O(N ×m) . 对于两阶段遗传算法的两个阶段, 每次迭代之后空间可以释放, 所以空间复杂度和迭代次数无关, 因此,
O(m×|U|×|C|+ N ×m) .
两阶段自适应遗传算法的空间复杂度为
3 实验分析

3.1 实验数据
为验证本文提出的两阶段自适应遗传算法 (TSAGA) 的有效性, 我们分别选取了来自 UCI 机器学习数据库 [37]
和 Kaggle 数据库 [38] 的 9 个数据集进行实验验证, 数据集的具体信息如表 2 所示. 其中 Sonar 和 Urban 是连续数据
集, 对于连续数据集, 我们基于文献 [39] 的等宽分箱法进行离散化处理. 在每个数据集上, 首先, 将条件属性集划
AT i 定义为不同的视角. 然后, 将每个视角中的属性再划分为
,
分成多个子集 AT i AT i ⊆ C 1 ⩽ i ⩽ n , 每个属性子集
,
k ∪ k
多个子集 AT , 1 ⩽ k ⩽ m . 通过将属性子集组合起来生成嵌套的属性集序列 C 1 ⊂ C 2 ⊂ ... ⊂ C n , 其中 C j = 1⩽k⩽j AT ,
i
i
构成多个层次. 最后, 基于多个视角和多个层次构建划分序乘积空间. 每个数据集的多视角多层次结构如表 3 所
示. 需要注意的是, 在构造划分序乘积空间时, 通过不同的方法, 例如选取属性个数不同, 可以构造出不同的视角和
层次, 进而构造不同的划分序乘积空间. 实验中, 我们对于所有的数据集都是先构造出划分序乘积空间, 然后所有
实验都是基于相同的划分序乘积空间进行, 从而保证实验的公平性. 但是我们没有考虑不同划分序乘积空间的构
造方法对算法实验性能的影响, 我们将在以后的工作中对此问题进行深入研究.

表 2 数据集

序号 数据集 对象数量 属性数量 类别数量
1 Kr-vs-kp 1 056 36 2
2 Dermatology 358 34 6
3 Student-por 649 32 2
4 Divorce 170 54 2
5 Urban 168 147 9
6 Sonar 208 60 2
7 Phishing 11 055 30 2
8 Mushroom 8 124 22 2
9 SCADI 70 205 7

表 3 数据集的多视角多层次结构

数据集 每个视角和层次下的属性
层次1 层次2 层次5
视角1 ...
{a 1 } {a 1 ,a 2 } {a 1 ,a 2 ,a 3 ,a 4 ,a 5 }
层次1 层次2 层次5
视角2 ...
{a 6 } {a 6 ,a 7 } {a 6 ,a 7 ,a 8 ,a 9 ,a 10 }
Kr-vs-kp
. . . . .
. . . . .
. . . . .
层次1
视角8 － － －
{a 36 }