首页> 中国专利> 一种基于遗传算法和粗糙集的属性约简方法及精神状态评估方法

一种基于遗传算法和粗糙集的属性约简方法及精神状态评估方法

摘要

本发明公开了一种基于遗传算法和粗糙集的属性约简方法及精神状态评估方法,该基于遗传算法和粗糙集完成了粗糙集属性约简方法通过设定合适的适应度函数,扩大了基于遗传算法和粗糙集的属性约简方法的适用范围,且能够快速有效地获取决策表中属性集中的关键性指标,本发明的精神状态评估方法在进行精神状态评估时,先基于遗传算法和粗糙集的属性约简方法提取决策表中属性集中的关键性指标,在根据提取结果构建并训练贝叶斯网络,得到分类模型,用于进行精神状态评估。大大提高了精神状态评估的效率,且准确性好,易于实施,对数据具有广泛的适应性。

著录项

  • 公开/公告号CN104298873A

    专利类型发明专利

  • 公开/公告日2015-01-21

    原文格式PDF

  • 申请/专利权人 浙江大学;

    申请/专利号CN201410530885.6

  • 发明设计人 段会龙;吕旭东;尹梓名;

    申请日2014-10-10

  • 分类号G06F19/00;G06N3/12;

  • 代理机构杭州天勤知识产权代理有限公司;

  • 代理人胡红娟

  • 地址 310027 浙江省杭州市西湖区浙大路38号

  • 入库时间 2023-12-17 04:06:25

法律信息

  • 法律状态公告日

    法律状态信息

    法律状态

  • 2017-06-06

    授权

    授权

  • 2015-02-18

    实质审查的生效 IPC(主分类):G06F19/00 申请日:20141010

    实质审查的生效

  • 2015-01-21

    公开

    公开

说明书

技术领域

本发明涉及分类预测技术领域,具体涉及一种基于遗传算法和粗糙集 的属性约简方法及精神状态评估方法。

背景技术

决策支持系统是辅助决策者通过数据、模型和知识,以人机交互方式 进行决策的计算机应用系统。在计算机辅助决策过程中,常会遇到数据的 属性过多的问题,其中部分属性与对决策不重要或与决策无关,一方面, 获取这些属性会浪费人力和物力,另一方面,当这些冗余属性数据量较大 时,还会影响决策的效率和准确性。为提高决策效率,可删除这些冗余属 性,删除这些冗余属性即为属性约简

粗糙集(Rough Set)理论作为一种属性约简方法,也越来越被广泛地 使用。但现存的粗糙集的属性约简算法有的存在“组合爆炸”,很难在属 性数量较大时得到具体实施,有的算法只是局部寻优,达不到全局最佳约 简。

基于遗传算法的粗糙集属性约简方法通过模拟生物在自然环境中的 遗传和进化过程,基于逐次迭代法进行搜索、寻优,得到属性约简。具体 过程如下:

首先根据决策表生成初始解空间(即初始种群),再根据适应度函数 计算初始种群中各个染色体的适应度,从初始种群开始,根据各个染色体 的适应度进行遗传操作(包括选择、交叉和变异操作),生成新的种群,再 对新种群重新计算每个染色体的适应度和进行遗传操作,反复循环,直到 找到满足条件的种群为止,将最终得到的种群中适应度最大的染色体输出, 并将该染色体解码作为属性约简结果。

从遗传算法流程可以看出,适应度函数直接关系到最终得到的约简结 果的准确性以及该约简结果中包括的属性的个数,进而影响到得到的约简 结果的决策能力。现有遗传算法中采用的适应度函数F(x)通常如下:

F(x)=(1-card(X)card(C)+card(POSX(D))card(POSC(D)))

其中,C为条件属性集,D称为决策属性集,card(X)为表示染色体X 的所含的条件属性集的个数(即该染色体中为1的基因位对应的条件属性 集的个数),card(C)表示条件属性集的个数,POSX(D)表示染色体X的正 域,POSC(D)为决策属性集D对条件属性集C的正域,card(POSC(D))为 决策属性集D对条件属性集C的正域的集合中包含的元素个数, card(POSX(D))为染色体X的正域集合中包含的元素个数,表 明染色体X中包含的条件属性的区分能力。

利用该适应度函数进行粗糙集属性约简时,当染色体X的适应度大, 例如,设有两条染色体a和b,a所包含的条件属性的个数是4,b所包含 的条件属性的个数是3,当card(C)=10,card(POSC(D))=100, card(POSa(D))=86,card(POSb(D)=82时:

F(a)=(10-4)/10+86/100=1.46,

F(b)=(10-3)/10+82/100=1.52。

虽然f(a)<f(b),但是由于POSB(D)≠POSC(D),包含在染色体b中的 属性集并不是关于D的C的属性约简。因此可以看出,上述适应度函数 的适用范围有限,如当染色体X的适应度大时,无法得到正确的属性约简 结果。

发明内容

针对现有技术的不足,本发明提供了一种基于遗传算法和粗糙集的属 性约简方法及精神状态评估方法。

本发明的基于遗传算法和粗糙集的属性约简方法,包括:

(1)求决策表的属性核,基于得到的属性核初始化得到初始种群;

(2)根据适应度函数计算初始种群中每条染色体的适应度,所述的 适应度函数F(x)为:

F(x)=λ×(1-card(X)card(C)+)ϵ×card(POSX(D))card(POSC(D)),

其中,C为条件属性集,D称为决策属性集,POSX(D)表示染色体X 的正域,POSC(D)为决策属性集D对条件属性集C的正域,card(*)表示集 合*中包含的元素的个数,card(X)为表示染色体X的所含的条件属性集的 个数,card(C)表示条件属性集包含的元素个数,POSX(D)表示染色体X 的正域,POSC(D)为决策属性集D对条件属性集C的正域,card(POSC(D)) 为决策属性集D对条件属性集C的正域的集合中包含的元素个数, card(POSX(D))为染色体X的正域集合中包含的元素个数,λ为第一修正 因子,ε为第二修正因子,且:

λ=1card(POSC(D)),ϵ=1-λ;

(3)根据各个染色体的适应度对初始种群进行遗传操作生成新的种 群,反复对生成的种群中的每条染色体计算适应度和遗传操作,直至满足 终止条件后停止,并以最后一次遗传操作得到的种群作为最终种群;

(4)根据最终种群中适应度最大的染色体得到属性约简结果。

本发明的粗糙集属性约简方法中采用的适应度函数可以控制染色体 向最小约简的方向进化,越大,说明决策属性对条件属性的依 赖性越强,ε越大说明这种分类能力越重要。λ则根据数据计算所得,计 算方法更加客观。通过该适应度函数可以在决策属性对整体条件属性依赖 度不变的情况下找到所含条件属性最少的约简。

本发明中采用随机方式产生二进制编码初始化形成初始种群,在编码 时固定属性核对应的基因位为“1”或“0”。相应的步骤(4)中根据最终 种群中适应度最大的染色体得到属性约简结果,需要将最后得到的染色体 进行解码,将各个基因位映射为对应的条件属性。

初始种群的每一个个体通常都是通过随机的方法产生的,考虑到属性 核的特征,即属性核是所有属性约简的交集,每一种属性的约简都包括了 属性核,因此可以利用这一特点来对初始种群进行限制,减少随机产生的 初始值的盲目性,提高算法的效率"通过依赖关系求解决策表的核可以提 高简化效率。所述步骤(1)中根据属性依赖关系求决策表的属性核。

所述初始种群的大小为100~200。初始种群的大小直接关系到最后属 性约简结果的准确性和约简效率。

所述的遗传操作包括:

(3-1)根据各个染色体的适应度采用轮盘赌法则进行选择;

(3-2)采用单点交叉规则对选择得到的染色体进行交叉;

(3-3)根据启发式变异法对初始种群进行变异操作,且变异时保证 属性核对应的基因位不变。

步骤(3-2)中交叉时按照一定的概率选择个体参与交叉,对于参与 交叉的两个父代个体随机选取交叉点,然后对交叉后的部分子串进行交换, 产生下一代个体。

所述的终止条件为连续若干次遗传操作得到的种群中各个染色体的 平均适应度不变,或遗传操作的次数达到设定的阈值。

该终止条件的设置保证了最终解的可行性,使得搜索总在可行解范围 上进行,并在保证可行解的条件下尽量增大其适应度值。作为优选,连续 3~6次遗传操作(一次遗传操作对应一代)得到的种群中各个染色体的适 应度不变,所述的阈值为50~100次。进一步优选,连续5次遗传操作得 到的种群中各个染色体的平均适应度不变,所述的阈值为500次。

本发明还提供了一种基于上述属性约简方法的精神状态评估方法,包 括:

S1:采用粗糙集原理根据若干个训练样本构建决策表,其中以训练样 本的测试项目作为条件属性集,把训练样本的精神状态测试结果按照精神 状态评估标准转化为相应的精神状态级别,并以所有精神状态级别作为决 策属性集;

S2:基于遗传算法和粗糙集的属性约简方法对步骤S1构建的条件属 性集进行属性约简,提取用于进行精神状态评估的关键性指标;

S3:根据所述的关键性指标构建贝叶斯网络,并根据所述的关键性指 标简化各个训练样本,并以所有简化后的训练样本作为训练样本集,对所 述的贝叶斯网络进行训练,得到分类预测模型;

S4:获取待评估样本中关键性指标的测试数据作为测试样本,并利用 所述的分类预测模型对测试样本进行预测,获取评估样本的精神状态等级。

运用贝叶斯网络对训练样本集中的训练样本进行计算,获得关键性指 标之间和关键性指标与分类结果(即精神状态级别,可以根据实际应用情 况设定)之间的关联,构建关键性指标相对于分类按照一定概率关联的有 向无环图,即训练好的贝叶斯网络。

构建贝叶斯网络模型分为两个过程:结构学习和参数学习。结构学习 用来确定基本的贝叶斯网络结构,通过该网络结构可以得到变量之间的依 赖关系,而参数学习则是基于得到的网络结构进行计算得到其中的条件概 率值。

采用基于搜索评分的方法进行结构学习,就是对每种结构进行评分, 最后选择得分最高的网络结构,通过结构学习和参数学习过程,可以构建 出一个基于网络性能参数变量的贝叶斯网络结构模型。

本实施例中采用K2算法进行结构学习,K2算法要求先确定网络中节 点变量的次序,由于在K2算法中,节点的顺序是确定的,因此一个节点 的父节点只存在于排在这个节点前面的节点集合中,这样就确定了不同节 点的父节点集合可独立地进行计算,同时降低了构建贝叶斯网络的复杂性。 结构打分函数用来对所有可能的网络结构进行打分,最后分数最高的网络 结构为得到的最优解。在K2算法中结构搜索过程采用局部搜索的爬山算 法选择父节点。通过不断为每个节点增加父节点来增加局部结构的评分, 评分函数为:

P(Bs,D)=CΠi=1nmax[Πj=1qj(ri-1)!(Nij+ri-1)!Πk=1riNijk!],

其中Bs表示网络拓扑结构,C为约简后的条件属性集,D表示训练样 本集,n为贝叶斯网络中节点个数即条件属性的数量,ri为条件属性变量xi可能的取值数目,Nijk表示条件属性变量xi对应父节点xj时取值为k的总数 目;qj表示条件属性变量xj可能的父节点数目。

直到为每一个节点找到分值最高的父节点集后搜索停止。但是始终要 求在最大化每个节点父节点集的同时满足初始假定的节点顺序。

参数学习是在已经确定贝叶斯网络结构的基础上,通过对历史数据的 计算获得变量之间依赖关系的条件概率值。在参数学习过程中采用极大似 然概率的方法计算每个节点的概率依赖关系,对每个节点使用对数概率来 表示与其他节点之间的依赖关系。求解过程中采用以下定义计算概率值:

p[xi=k|pai=j]NijkNijmax>=1NΣi=1nΣDlogp(xi|Parent(xi),D)

式子中p表示条件概率值,pai为条件属性变量xi的父节点,Parent(xi) 为条件属性变量xi的父节点集合,可以看出计算过程中采用对数概率的方 式表示节点之间的依赖关系,Nijk为变量xi对应父节点xj时取值为k的总 数目,Nij为变量xi对应父节点xj时的总数目,N为总节点数,log的底数 是10。

所述步骤S1在构建决策表时,根据各个测试项目的测试数据的取值 范围,对测试数据进行离散化处理。

每个测试项对应的测试数据可以在值域上连续,经典的粗糙集理论不 能处理具有连续属性值的信息系统,在对数据处理之前,需要进行离散化 处理。离散化处理时,可以将整个值域划分为若干个区域,每个区域采用 特定的数字表示。如值域为0~100,可以平均划分为5个区域,各个区域 分别采用1,2,3,4和5表示。

所述步骤S3中删除训练样本中除关键性指标外的各个测试项目的测 试数据,完成对各个训练样本的简化。

通过简化大大提高了训练效率。根据简化的结果确定构建的贝叶斯网 络的参数,并完成训练。

本发明的基于遗传算法和粗糙集的属性约简方法及精神状态评估方 法,基于遗传算法和粗糙集完成了粗糙集属性约简方法中设定的适应度函 数,扩大了基于遗传算法和粗糙集的属性约简方法的适用范围;且进行精 神状态评估时,先构建贝叶斯网络,利用贝叶斯网络算法对训练数据集中 的样本数据进行计算,获得约简后各属性之间的关联,构建贝叶斯网络分 类器,提高了诊断的准确性,易于实施,对数据具有广泛的适应性。

附图说明

图1为实施例的精神状态评估方法的流程图;

图2本发明基于遗传算法和粗糙集的粗糙集属性约简方法的流程图。

具体实施方式

下面将结合附图和具体实施例对本发明进行详细说明。

如图1所示,本实施例中的精神状态评估方法包括:

S1:以训练样本的测试项目作为条件属性集,把训练样本的精神状态 测试结果按照精神状态评估标准转化为相应的精神状态级别,并以所有精 神状态级别作为决策属性集,采用粗糙集原理根据若干个训练样本构建决 策表,如表1所示(精神状态评估的原始数据集),C1到C37为精神评 估的测试项目,D为决策项(即测试结果),每一行为一个受试者的各项 得分,数据集的大小为334。

本实施例中得到的决策表即输入信息系统:(U,C∪D,V,f),其中 U是对象的非空有限集合,C是条件属性集,D是决策属性集;A是属性 的非空有限集合,且A=C∪D,V表示全体属性的值域, V=∪a∈AVa,Va表示属性a∈A的值域;f表示U×A→V的一个映射,称为 信息函数。

表1

为提高评估效率,步骤S1进一步还包括对构建的决策表进行离散化 处理,即根据各个测试项目的测试数据的取值范围,对测试数据进行离散 化处理,离散化处理后的决策表如表2所示。将连续的数据根据领域知识 进行离散化。如测试项目C37,得分小于10分为严重异常,记为A;10 分~15分是轻度异常,记为B;15分以上是正常,记为C。经过预处理之 后的数据集如表2所示,离散化后的决策表记为信息系统S。

表2

S2:基于遗传算法和粗糙集的属性约简方法对步骤S1构建的决策属 性集进行属性约简,将属性约简结果作为用于进行精神状态评估的关键性 指标。本实施例的基于遗传算法和粗糙集的属性约简方法,包括:

(1)根据属性依赖关系求决策表的属性核,求决策表的属性核,基 于得到的属性核初始化得到初始种群,初始种群大小为200;

属性依赖度的定义如下:对于信息系统S=(U,C∪D,V,f),条件 属性集C对决策属性集D的依赖程度定义为:

r(C,D)=|(POSC(D))|/|U|;

其中1|U|为决策属性集的训练样本的个数,|(POSC(D))|为决策属性 D在条件属性集为C时正域中的元素个数。根据该定义可知条件属性a关 于D的重要度定义为:

Sig(a,C,D)=r(C,D)-r(C-a,D),

其中,a∈C,C-a表示除去条件属性a后的条件属性集。

为提高遗传算法的收敛性,在初始化种群时,先计算决策表的属性核, 求决策表的核:

令逐个去掉一个条件属性c∈C,若γC-c≠γC,则 Core(C)=Core(C)∪{c},即核为Core(C);若γcore(D)=γc(D),则Core即 为最小相对约简。

本实施例中求得的属性核是{C11,C25,C26}。

初始化二进制种群组作为初始种群。二进制编码是遗传算法中经常使 用的编码方法,它是由二进制符号0和1组成,编码时使每一个条件属性 对应一个基因位。

本实施例中对应的基因位的值为0,则表示其对应的条件属性可以去 掉(即为冗余条件属性),如果在某个位置上其值为1,则表示其对应的条 件属性被选中。

基于得到的属性核初始化得到初始种群,这样是初始种群中每个属性 核对应的基因位为1,即令C11,C25和C26对应的基因位为1,基于测 试项目对应的基因位随机设定,且在遗传算法的运算中,C11,C25和C26 对应的基因位的值保持不变,始终为1。

(2)根据适应度函数计算初始种群中每条染色体的适应度,适应度 函数F(x)为:

F(x)=λ×(1-card(X)card(C))+ϵ×card(POSX(D))card(POSC(D)),

其中,card(x)为表示染色体x的所含的条件属性集的个数,card(C) 表示条件属性集的个数,POSx(D)表示染色体x的正域,POSC(D)为决策 属性集D对条件属性集C的正域,card(POSC(D))为决策属性集D对条件 属性集C的正域的集合中包含的元素个数,card(POSX(D))为染色体X的 正域集合中包含的元素个数,λ为第一修正因子,ε为第二修正因子,且:

λ=1card(POSC(D)),ϵ=1-λ.

本实施例中card(C)=334,card(POSC(D))=100,则:

λ=0.01,ε=0.99。

(3)根据各个染色体的适应度对初始种群进行反复遗传操作更新初 始种群,直至满足终止条件后停止,并以最后一次遗传操作得到的种群作 为最终种群。本实施例的终止条件为连续5次遗传操作得到的种群中各个 染色体的平均适应度不变,或遗传操作的次数达到500次。

遗传操作包括:

(3-1)根据各个染色体的适应度采用轮盘赌法则进行选择,具体如 下:

步骤1:设当前为第s代种群,,对该种群中的个体,按照适应度在整 个种群的个体适应度总和中所占的比例,采用轮盘赌方法进行选择。

步骤2:采取最优个体保存方法,设第i代种群(即第i次遗传操作 得到的种群)中a(t)为最优个体,又设A(t+1)为新一代群体(即种群),若 A(t+1)中的最优个体a(t+1)的适应度小于a(t)的适应度,则用a(t)来代替 A(t+1)中的最差个体。

(3-2)采用单点交叉规则对选择得到的染色体进行变异;

交叉操作釆用单点交叉,其主要的执行过程为:以一定的概率(本实 施例中为0.75)选择个体参与交叉,对于参与交叉的两个父代个体随机选 取交叉点,然后对交叉后的部分子串进行交换,即产生下一代个体。

(3-3)根据启发式变异法对初始种群进行变异操作,且变异时保证 属性核对应的基因位不变。

一般的变异算子是通过变异概率(本实施例中为0.03)随机反转某位 等位基因位的二进制字符值来实现。本发明将属性重要性作为启发式信息, 来描述变异算子,并且属性核对应的基因位不发生变异,对于给定的染色 体Si=a1a2…an,具体的操作过程如下:

ai=1-xi,δ=Max(Sig(a,C,D))xi,δ=Min(Sig(a,C,D))

其中i=1,2,…,n,生成新的个体(染色体)为Si′=a′1a′2…a′n。 xi是第i个基因位的值,δ为条件属性a的属性重要度。

(4)根据最终种群中适应度最大的染色体进行解码,以该染色体中 值为1基因位对应的条件属性作为属性约简结果。

本实施例中求得属性约简的结果为{C11,C15,C16,C17,C24,C25, C26,C29,C30,C31}。与未进行属性约简的数据集相比,数据项的约简 率为72.97%。有效地减少了条件属性数量,降低了信息采集的难度和精 神状态评估的工作量,有效提高了精神状态评估的效率。

S3:根据关键性指标构建贝叶斯网络,并根据该关键性指标,删除训 练样本中除关键性指标外的各个测试项目的测试数据,简化各个训练样本, 并以所有简化后的训练样本作为训练样本集,对构建的贝叶斯网络进行训 练,得到分类预测模型。

贝叶斯网络是一种表示变量之间依赖关系的有向无循环图模型。网络 结构中的节点表示参数变量,节点之间的有向弧表示节点之间的依赖关系。 有向弧连接的两个节点表示它们之间的父子关系,即弧线箭头的节点依赖 于前面的节点。

S4:获取待评估样本中关键性指标的测试数据作为测试样本,并利用 所述的分类预测模型对测试样本进行预测,获取评估样本的精神状态等级。 将约简后得到的关键性指标作为输入项,使用表2数据集训练,将贝叶斯 网络与其他常用分类算法进行比较,对比结果如表3所示。对于等级1和 等级3,所有这些分类器得到相似的分类性能,但是对于等级2,贝叶斯 网络的性能最好,敏感度和特异度都保持较高的水准。

表3

表4为以贝叶斯网络分类算法作为比较基准,本实施例的精神状态评 估方法与现有方法的不进行属性约简的精神状态评估方法的效果比较。可 以看出,从敏感度和特异度来看,除了等级3,其余2个等级的敏感度和 特异度都基本保持不变。

表4

以上所述的具体实施方式对本发明的技术方案和有益效果进行了详 细说明,应理解的是以上所述仅为本发明的最优选实施例,并不用于限制 本发明,凡在本发明的原则范围内所做的任何修改、补充和等同替换等, 均应包含在本发明的保护范围之内。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号