模式识别 特征选择的遗传算法目录模式识别 特征选择的遗传算法 0一、特征选择的遗传算法介绍 11.1 特征选择 11.2 遗传算法Genetic Algorithm 1二、实验数据集介绍 42.1 Iris数据集介绍 42.2 Sonar数据集介绍 4三、实验设置 43.1 算法流程 41、读取数据集按照一定比例随机分为测试集、训练集 52、编码及种群的初始化 53、开始迭代直至达到指定的迭代次数 53.2 在数据集上验证遗传算法 6四、实验结果展示与分析 74.1 在iris数据集上验证遗传算法 74.2 在sonar数据集上验证遗传算法 84.3 总结 10五、Python代码 10三、实验设置3.1 算法流程本次实验选用的是K近邻法作为分类器来评价所选特征的好坏用来计算种群的适应度函数。由于上述算法流程较为简略在实际编程实现对编码、选择、交叉、变异又使用了一些其他方法下面具体说明整体流程由于iris数据集维度较低故使用sonar数据集具体说明1、读取数据集按照一定比例随机分为测试集、训练集2、编码及种群的初始化对所有特征描述为一个由60个0/1元素组成的列表代表染色体0代表该特征没有被选中1代表该特征被选中。用户给定选择的数据维度d和种群数目p将染色体列表初始化全0然后随机将染色体中的d位变为1这样就从60维特征中随机选择了d维。重复上述过程p次则可以得到一个有p条染色体的初代种群P(0)并且每条染色体都不尽相同。并随机选定一个最优个体。3、开始迭代直至达到指定的迭代次数1 更新每个个体的适应度函数并更新最优个体、统计种群的平均适应度。计算每个个体的适应度时根据个体的染色体情况将没有选中的特征删除包括训练集和测试集将数据送入分类器计算分类准确率作为该个体的适应度函数。分类器使用之前实现的K近邻根据之前的经验K取2。2 根据适应度函数对种群进行轮盘赌选择。对种群中的染色体进行采样由采样出的染色体经过一定的操作繁殖出下一代染色体组成下一代的种群。这里实用的是轮盘赌的方式进行选择首先将种群中所有个体的适应度归一化将这些适应度值累加起来得到p个区间每个区间的长度代表对应染色体的适应度值。从0-1之间取随机数该数落到哪个区间就选用哪条染色体。本文转载自http://www.biyezuopin.vip/onews.asp?id15003为保证种群的染色体数目不变重复p次就得到了基于上一代种群适应度的新子代种群。3交叉。对一条染色体按照一定的概率交叉概率设为0.4选择是否进行交叉操作。再从种群中随机寻找到另外一条父代染色体与之进行交叉为了使交叉之后的染色体特征维数不变采用了如下方法先从一个父代染色体中随机选取一个片段长度为60/230统计该片段中有几个为1的基因再从与之匹配的父代染色体中寻找长度相同、1基因数目相同的片段若找到则进行交叉操作若未找到则寻找下一对父代染色体直到将所有父代种群遍历完毕。4 变异。同样的对一条染色体按照一定的概率变异概率设为0.01选择是否进行变异操作。为了使变异之后染色体中特征数量不变又采用了以下方法随机从种群中选择一个个体再随机地选择一个基因进行反转若该基因由1变为了0则再随机选一个0变成1反之也执行同样的操作。直至遍历完种群中所有的个体。5重复迭代。在进行完选择、交叉、和变异操作之后上一代的种群已经变成了新一代的种群。重复上述过程1-4在遗传算法迭代的过程中种群中的染色体会趋于所选特征数中的最优解达到一定的迭代次数 t 后算法停止输出最终种群中适应度值最大的染色体和每次迭代过程中的种群平均适应度即完成了在 D 维特征中选择d个最优的特征。# -*- coding: utf-8 -* import pandas as pd import numpy as np import matplotlib.pyplot as plt sonar pd.read_csv(sonar.all-data,headerNone,sep,) sonar1 sonar.iloc[0:208,0:60] sonar2 np.mat(sonar1) pc 0.02 # pc为变异的概率 t 150 #遗传算法迭代的次数 n 60 #种群的个体数,要求大于20以保证具有随机性 # d 30 # d为要选择的特征个数 #遗传算法 def GA(d): population np.zeros((n,60)) # 初始化种群 for i in range(n): # 定义种群的个体数为 n a np.zeros(60-d) b np.ones(d) # 将选择的d维特征定义为个体c中的1 c np.append(a,b) c (np.random.permutation(c.T)).T # 随机生成一个d维的个体 population[i] c # 初代的种群为 population共有n个个体 #遗传算法的迭代次数为t fitness_change np.zeros(t) for i in range(t): fitness np.zeros(n) # fitness为每一个个体的适应度值 for j in range(n): fitness[j] Jd(population[j]) # 计算每一个体的适应度值 population selection(population,fitness) # 通过概率选择产生新一代的种群 population crossover(population) # 通过交叉产生新的个体 population mutation(population) # 通过变异产生新个体 fitness_change[i] max(fitness) #找出每一代的适应度最大的染色体的适应度值 # 随着迭代的进行每个个体的适应度值应该会不断增加所以总的适应度值fitness求平均应该会变大 best_fitness max(fitness) best_people population[fitness.argmax()] return best_people,best_fitness,fitness_change,population #轮盘赌选择 def selection(population,fitness): fitness_sum np.zeros(n) for i in range(n): if i0: fitness_sum[i] fitness[i] else: fitness_sum[i] fitness[i] fitness_sum[i-1] for i in range(n): fitness_sum[i] fitness_sum[i] / sum(fitness) #选择新的种群 population_new np.zeros((n,60)) for i in range(n): rand np.random.uniform(0,1) for j in range(n): if j0: if randfitness_sum[j]: population_new[i] population[j] else: if fitness_sum[j-1]rand and randfitness_sum[j]: population_new[i] population[j] return population_new #交叉操作 def crossover(population): father population[0:10,:] mother population[10:,:] np.random.shuffle(father) # 将父代个体按行打乱以随机配对 np.random.shuffle(mother) for i in range(10): father_1 father[i] mother_1 mother[i] one_zero [] zero_one [] for j in range(60): if father_1[j]1 and mother_1[j]0: one_zero.append(j) if father_1[j]0 and mother_1[j]1: zero_one.append(j) length1 len(one_zero) length2 len(zero_one) length max(length1,length2) half_length int(length/2) #half_length为交叉的位数 for k in range(half_length): #进行交叉操作 p one_zero[k] q zero_one[k] father_1[p]0 mother_1[p]1 father_1[q]1 mother_1[q]0 father[i] father_1 #将交叉后的个体替换原来的个体 mother[i] mother_1 population np.append(father,mother,axis0) return population #变异操作 def mutation(population): for i in range(n): c np.random.uniform(0,1) if cpc: mutation_s population[i] zero [] # zero存的是变异个体中第几个数为0 one [] # one存的是变异个体中第几个数为1 for j in range(60): if mutation_s[j]0: zero.append(j) else: one.append(j) if (len(zero)!0) and (len(one)!0): a np.random.randint(0,len(zero)) # e是随机选择由0变为1的位置 b np.random.randint(0,len(one)) # f是随机选择由1变为0的位置 e zero[a] f one[b] mutation_s[e] 1 mutation_s[f] 0 population[i] mutation_s return population #个体适应度函数 Jd(x)x是d维特征向量(1*60维的行向量,1表示选择该特征) def Jd(x): #从特征向量x中提取出相应的特征 Feature np.zeros(d) #数组Feature用来存 x选择的是哪d个特征 k 0 for i in range(60): if x[i] 1: Feature[k] i k1 #将30个特征从sonar2数据集中取出重组成一个208*d的矩阵sonar3 sonar3 np.zeros((208,1)) for i in range(d): p Feature[i] p p.astype(int) q sonar2[:,p] q q.reshape(208,1) sonar3 np.append(sonar3,q,axis1) sonar3 np.delete(sonar3,0,axis1) #求类间离散度矩阵Sb sonar3_1 sonar3[0:97,:] #sonar数据集分为两类 sonar3_2 sonar3[97:208,:] m np.mean(sonar3,axis0) #总体均值向量 m1 np.mean(sonar3_1,axis0) #第一类的均值向量 m2 np.mean(sonar3_2,axis0) #第二类的均值向量 m m.reshape(d,1) #将均值向量转换为列向量以便于计算 m1 m1.reshape(d,1) m2 m2.reshape(d,1) Sb ((m1 - m).dot((m1 - m).T)*(97/208) (m2 - m).dot((m2 - m).T)*(111/208)) #除以类别个数 #求类内离散度矩阵Sw S1 np.zeros((d,d)) S2 np.zeros((d,d)) for i in range(97): S1 (sonar3_1[i].reshape(d,1)-m1).dot((sonar3_1[i].reshape(d,1)-m1).T) S1 S1/97 for i in range(111): S2 (sonar3_2[i].reshape(d,1)-m2).dot((sonar3_2[i].reshape(d,1)-m2).T) S2 S2/111 Sw (S1*(97/208) S2*(111/208)) # Sw (S1 S2) / 2 #计算个体适应度函数 Jd(x) J1 np.trace(Sb) J2 np.trace(Sw) Jd J1/J2 return Jd if __name__ __main__: best_d np.zeros(59) # judge存的是每一个维数的最优适应度 for d in range(30,31): # d为从60个特征中选择的特征维数 best_people,best_fitness,fitness_change,best_population GA(d) # fitness_change是遗传算法在迭代过程中适应度变化 best_d[d-1] best_fitness # best是每一维数迭代到最后的最优的适应度用于比较 print(在取%d维的时候通过遗传算法得出的最优适应度值为%.6f%(d,best_fitness)) 若要看遗传算法的收敛情况则看在d30的情况下的fitness_change就可以 #画图 x np.arange(0,59,1) plt.xlabel(dimension) plt.ylabel(fitness) plt.ylim((0,0.3)) # y坐标的范围 plt.plot(x,best_d,r) # plt.savefig(Sonar_best_d.jpg,dpi2000) x np.arange(0,t,1) plt.xlabel(dimension) plt.ylabel(fitness) plt.ylim((0,0.1)) # y坐标的范围 plt.plot(x,fitness_change,r) plt.show()