第3期 程麟焰，等：基于模糊超网络的知识获取方法研究 ·485· 7)if Confg≤0.5then 26)return G=<X,Ee,>;/*输出模糊超网络*/ 8)参照算法1中的生成超边方法，该超边对 令训练集样本数目为n,样本的属性数目为 应的原始样本重新生成一条新超边eew,E=E-{e: m。算法1的平均时间复杂度为O(m×n2),算法 E=EUlenew) 2的时间复杂度为O(m×n),算法3的时间复杂度 9)end if 为O(m×n),所以建模的时间复杂度为O(m×n)。 10)end if 计算最优模糊相似度阈值时循环迭代所用的 ll)ife∈NEG(E)then 时间约为建模时间的10×5倍，迭代步长s在(0， 12)参照算法1，原始样本重新生成一条新超 1)范围内取值。s值越小，计算所用的时间越长， ienew,E=E-{e);E=EU(enew) 得到的结果越接近理论上的最优阈值。最优模糊 13)end if 相似度阈值是一个非常重要的参数，在部分数据 14)end for 集上，略微改变阈值，分类结果就会有较大的改 l5)return E,/体输出更新后的超边库*/ 变。对于这类数据集而言，计算最优模糊相似度 算法3生成模糊超网络算法 阈值是非常重要的环节。但也有一些数据集，例 输入训练样本集X,最优阈值： 如大部分的离散型数据集，在一定范围内改变阈 输出超网络G。 值，生成的超网络的分类效果不变，处理这些数据 1)执行算法1生成初始超边集E 集时，可以通过设置合理的步长和初始阈值，达 2)k=0,Ebes=O,Pma=0/体用于保存最高分类正 到既不影响分类效果又能减少迭代时间的目的。 确率*/ 3)while (k<100) 3实验评价 /*设置最小迭代次数用以保障超网络能够得 到充分的演化，可根据实际演化效果增减次数*/ 3.1数据集及评价指标 4)for each x in X do 为验证算法的有效性，本文选取机器学习数 5)计算样本x在1下的模糊等价类超边集合 据库UCI中的15个数据集进行实验，每个数据集 [,计算x的类别D(x) 的详细信息如表3所示，按数据集大小从小到大 6)end for 排序。 7)根据训练样本的实际类别，计算当前超边 表3实验数据集 集对训练集的分类正确率P;++ Table 3 Experimental data sets 8)if p>Pmax then 序号 数据集 属性 类别数样本数 9)Pmax=P,Ebe=E;/体保存当前最优超边集*/ 1 BLOGGER 5N 2 100 10)end if 3 lymph 3C15N 148 11)执行算法2更新超边集 tae 1C4N 3 151 12)end while y flags 2C26N 194 13)m=0 5 Glass 9℃ 7 214 14)while(m<10)/*退出迭代条件*/ 6 breast-cancer 9N 2 15)for each x in X do 286 16)计算样本x在1下的模糊等价类超边集 7 Haberman 3C 2 306 合[xu,计算x的类别D(x) 8 column 2C weka 6C 2 310 17)end for 9 column_3C_weka 6C 3 310 18)根据训练样本的实际类别，计算当前超边 10 ecoli 7C 8 336 集对训练集的分类正确率P lonosphere 34C 2 351 19)if p>Pma then 12 balance-scale 4N 3 625 20)Pmax =P,Ebes=E,m-0 13 Pima diabetes 8C 2 768 21)else m++ 14 tic-tac-toe 9N 2 958 22)end if 15 car 6N 4 1728 23)执行算法2更新超边集 24)end while 注：C为continuous,N为nominal7) if ConfB ⩽ 0.5 then E ∪ {enew} 8) 参照算法 1 中的生成超边方法，该超边对 应的原始样本重新生成一条新超边 enew，E=E−{e}； E = 9) end if 10) end if 11) if e ∈ NEG(E) then E = E ∪ {enew} 12) 参照算法 1，原始样本重新生成一条新超 边 enew，E=E−{e}； 13) end if 14) end for 15) return E; /*输出更新后的超边库*/ 算法 3 生成模糊超网络算法 输入 训练样本集 X，最优阈值 λ； 输出 超网络 G。 1) 执行算法 1 生成初始超边集 E 2) k=0，Ebest=∅，Pmax=0 /*用于保存最高分类正 确率*/ 3) while (k<100) /*设置最小迭代次数用以保障超网络能够得 到充分的演化，可根据实际演化效果增减次数*/ 4) for each x in X do [x]λ D(x) 5) 计算样本 x 在 λ 下的模糊等价类超边集合 ，计算 x 的类别 6) end for 7) 根据训练样本的实际类别，计算当前超边 集对训练集的分类正确率 P；k++ 8) if P>Pmax then 9) Pmax = P，Ebest=E；/*保存当前最优超边集*/ 10) end if 11) 执行算法 2 更新超边集 12) end while 13) m=0 14) while (m<10) /*退出迭代条件 */ 15) for each x in X do [x]λ D(x) 16) 计算样本 x 在 λ 下的模糊等价类超边集 合 ，计算 x 的类别 17) end for 18) 根据训练样本的实际类别，计算当前超边 集对训练集的分类正确率 P 19) if P > Pmax then 20) Pmax = P，Ebest=E，m=0 21) else m++ 22) end if 23) 执行算法 2 更新超边集 24) end while 26) return G=<X, Ebest, λ>；/*输出模糊超网络*/ 令训练集样本数目为 n，样本的属性数目为 m。算法 1 的平均时间复杂度为 O(m×n 2 )，算法 2 的时间复杂度为 O(m×n)，算法 3 的时间复杂度 为 O(m×n 2 )，所以建模的时间复杂度为 O(m×n 2 )。 计算最优模糊相似度阈值时循环迭代所用的 时间约为建模时间的 10×s -1 倍，迭代步长 s 在 (0, 1) 范围内取值。s 值越小，计算所用的时间越长， 得到的结果越接近理论上的最优阈值。最优模糊 相似度阈值是一个非常重要的参数，在部分数据 集上，略微改变阈值，分类结果就会有较大的改 变。对于这类数据集而言，计算最优模糊相似度 阈值是非常重要的环节。但也有一些数据集，例 如大部分的离散型数据集，在一定范围内改变阈 值，生成的超网络的分类效果不变，处理这些数据 集时，可以通过设置合理的步长和初始阈值，达 到既不影响分类效果又能减少迭代时间的目的。 3 实验评价 3.1 数据集及评价指标 为验证算法的有效性，本文选取机器学习数 据库 UCI 中的 15 个数据集进行实验，每个数据集 的详细信息如表 3 所示，按数据集大小从小到大 排序。 表 3 实验数据集 Table 3 Experimental data sets 序号 数据集 属性 类别数 样本数 1 BLOGGER 5N 2 100 2 lymph 3C 15N 4 148 3 tae 1C 4N 3 151 4 flags 2C 26N 8 194 5 Glass 9C 7 214 6 breast-cancer 9N 2 286 7 Haberman 3C 2 306 8 column_2C_weka 6C 2 310 9 column_3C_weka 6C 3 310 10 ecoli 7C 8 336 11 Ionosphere 34C 2 351 12 balance-scale 4N 3 625 13 Pima_diabetes 8C 2 768 14 tic-tac-toe 9N 2 958 15 car 6N 4 1 728 注：C 为 continuous, N 为 nominal 第 3 期 程麟焰，等：基于模糊超网络的知识获取方法研究 ·485·