离散化算法范文-盘古文库

离散化算法范文

来源：莲生三十二

作者：开心麻花

2025-09-19

离散化算法范文（精选8篇）

离散化算法第1篇

自Zadeh教授发表论文“Fuzzy sets and information granularity”以来, 研究人员对信息粒和粒计算产生了浓厚兴趣[1]。Zadeh教授认为信息粒广泛存在于自然界, 只是在不同的领域其表现形式不同, 信息粒化是人类对现实世界的一种抽象, 是人类存储和处理信息的一种方式。粒计算对于解决实际问题具有非常重要的意义, 特别是对于复杂的大型问题, 通过粒划分可以转化为若干个简单的问题进行处理, 从而降低问题的求解难度[2]。粒计算包括两个基本问题:粒化和基于粒化的计算, 即如何构造粒化模型以及根据这个模型进行计算。连续数值属性的离散化是应用粗糙集等粒计算理论的重要步骤, 下面我们将粒计算引入连续数值属性的离散化, 融合熵理论来控制粒化过程, 建立了基于粒计算的连续数值属性的离散化算法;以入侵检测领域的经典数据集:KDDcup99为处理对象, 就算法对于离散化对象即初始数据集的敏感性进行研究, 同时应用于入侵检测系统并对其应用效果进行分析和评价。

1 离散化问题的粒度描述

在粒计算理论的应用过程中常采用一种特殊的知识表达系统:决策表对知识进行表达和处理。决策表可以表示为四元组S= (U, A, V, f) , 其中U是非空对象的有限集合, 称为论域;A是属性的非空集合, A=C∪D, C∩D=Φ;其中C={a1, a2, , am}称为条件属性集;D={d}具有唯一的决策属性 (也称为类别属性) , 称之为决策属性集;V=a∈∪AVa, Va是属性a的值域;f:UAV是一个信息函数, 它为对象的每个属性赋以一个值, 即:a∈A, x∈U, f (x, a) ∈Va。

假设对于a∈C, 属性a的值域是实值区间, 我们将该区间定义为一个区间粒;令Pa是对区间粒Va的细分, 即对于某一正整数ka, 有;这样将属性a的取值分成ka个较细的区间粒, 每个区间粒可以看作为一个等价类, 其中的每个cia (0ika) 称为属性a在其值域Va上的一个断点。显然, 离散化的目的就是按照一定的粒化准则对由条件属性所构成的粒空间进行细分, 进而确定各个连续属性的最佳断点集;此时有:, 即细分后的每个区间粒对应一个离散值;这样经过离散化后, 原来的决策表就被新的决策表所替代, 而且要求这个新的决策表的决策能力保持不变。

2 连续数值属性的离散化

连续数值属性的离散化在粗糙集等粒计算理论出现前就已经得到研究。粒计算理论出现后, 广大研究者对已有的离散化算法进行引用或者改进以解决本领域中的相关问题。

离散化算法常分为无监督算法和有监督算法[3,4]。无监督算法不考虑属性与类别之间的关系, 在离散化时往往需要人为地设定一些参数, 而这些参数某种程度上带有一定的主观性, 因而很难获得理想的离散化效果。有监督算法要考虑样本数据的类别属性, 它比无监督算法更科学。有监督算法主要包括基于信息熵的离散化算法, 如Patterson-Niblett、IEM等;基于统计的离散化算法, 如Chi Merge、Chi2等;基于属性类别关联度的离散化算法, 如CADD、CAIM等。

从粒计算角度看, 离散化存在自顶向下的逐步细化和自底向上的逐步粗分两种实现方式。自顶向下方式首先将待离散化的样本数据集看成一个完整的区间粒, 然后按照一定的粒化方法在区间中选择一个最佳断点将整个区间粒细分成两个子区间粒;以后在每个子区间粒上重复上述过程, 直到满足一定的粒化准则;这种算法的典型代表是由Fayyad和Irani提出的决策树离散化算法[5]。该算法采用样本集的类别熵作为粒化准则, 选择使得分割成两个子区间粒的类别熵最小的断点作为最佳断点, 然后依此递归, 直到算法满足由最小描述长度决定的终止条件时为止;这种算法每次确定一个断点, 离散化过程所需时间较长, 而且决定终止条件的最小描述长度常常难以确定。基于自底向上的离散化算法用样本集中所有不同的观测值构成初始区间粒分布, 然后按照一定的粒化准则选择相邻的两个区间粒进行合并, 得到新的区间粒分布, 然后重复上述过程, 直到得到的区间粒分布满足一定的终止条件, 这种算法的典型代表是Chi Merge算法[6,7]。该算法基于数理统计中的χ2测试作为粒化准则, 在选择相邻区间粒进行合并时依次计算各相邻区间的χ2值, 并将χ2值最小的相邻区间粒合并为一个粗的区间粒;这样依此循环, 直到所有相邻区间粒的χ2值都小于规定的阈值时为止。这种算法由于每次仅能归并相邻的两个区间粒, 当样本数据集规模较大时算法的速度较慢。

显然, 无论哪种算法在离散化过程中都应尽量保证系统的粒度不发生太大的变化, 以保证无论是粒的细化还是变粗, 系统的决策能力应保持不变。

3 基于粒计算的连续属性离散化算法

如前所述, 对于自底向上实现方式, 连续属性离散化的本质就是利用选取的若干个断点对条件属性所构成的粒空间进行划分, 并根据一定粒化准则将区间粒进行聚类合并的一个粗分过程。首先根据条件属性X的值对样本空间S由小到大进行排序, 设X中的不同观察值由小到大依次为x1, x2, , xn, 构造n个初始区间粒I1, I2, , In如下:

其中, 每个初始区间粒只包括一个观察值。

然后对相邻的区间粒进行合并, 直到满足一定的粒化准则;此时得到的每个区间粒即对应一个离散值, 从而实现了连续属性的离散化。

为了提高区间粒合并的速度, 对于初始化得到的区间粒I1, I2, , In, 若某些相邻的区间粒具有相同的分类属性则将它们合并为一个区间粒, 从而减少初始区间粒的个数。

假设每次考虑将m个相邻区间粒Ip+1, Ip+2, , Ip+m进行合并, 可能存在多段这样的区间粒, 那么优先选择哪一段区间粒进行合并呢?下面通过信息熵来定义另一个概念:粒度损失, 它描述了相邻区间粒合并前后的粒度变化, 并将它作为粒化准则来选择优先合并的相邻区间粒。

现考虑将m个相邻区间粒Ip+1, Ip+2, , Ip+m合并为一个区间粒I, 则合并前区间粒I的粒度定义Grbefore (I) 为:

其中, |Ip+i|和|I|分别表示属性X的值位于区间粒Ip+i和I上的样本数, E (Ip+i) 为区间粒Ip+i的分类信息熵。而合并后区间粒I的粒度定义Grafter (I) 为:

其中p (Di, I) 是指区间粒I中类别属性值为Di的样本的概率。

有了上述概念, 定义区间粒合并前后的粒度变化为粒度损失Gr_Loss (I) , 具体如下:

显然, 区间粒的粒度描述的是系统的分辨能力, 随着区间粒的合并粒将逐渐变粗, 系统的分辨能力也将会变差, 理想的情况是合并前后的粒度损失能够达到最小。下面以粒度损失作为粒化准则, 选择粒度损失最小的那些区间粒进行合并, 并以当前步的粒度损失大于前一步的n倍作为终止条件。具体的离散化算法如下:

Input:具有连续数值属性X和分类属性D的样本数据集S, 每次合并的区间粒个数m, 参数n

Output:具有离散数值属性X和分类属性D的样本数据集

Begin

s1:将集合S中的样本按照属性X的值由小到大排序;

s2:按照式 (1) 形成初始区间粒, 然后将具有相同分类属性值的相邻区间粒合并为一个区间粒, 得到初始区间粒序列I1, I2, , In;

s3:依次选择m个相邻的区间粒, 按照式 (2) -式 (4) 计算这些相邻区间粒合并前后的粒度损失;

s4:选择具有最小粒度损失的相邻区间粒进行合并, 得到新的区间粒序列;

s5:if当前步的粒度损失不大于前一步的n倍goto s3;else执行s6;

s6:将样本的X属性值离散化, 令位于区间粒[a, b) 或者[a, b]内样本的X属性值=int ( (a+b) /2) , 从而得到新的样本集;

s7:输出离散化的样本数据集。

end

4 实验及其结果分析

实验采用主频2.0GHz双核处理器、2GB内存的计算机, 用C++0编程;以入侵检测数据集KDDcup99中10%的数据集为处理对象, 该数据集包括近50万条记录, 每条记录包括41个条件属性 (包括34个数值属性和7个符号属性) 和1个分类属性;分类属性又分成5大类:Normal、DOS、Probing、R2L和U2R, 分别对应正常状态和4类网络攻击;对于41个条件属性, 通过分析各数值属性取值的分布发现34个数值属性中有13个属性仅取有限的几个离散值, 故将这13个属性和符号属性一样看作离散量, 其他21个属性为连续数值属性。由于原始数据比较庞大, 所以在研究过程中常常随机选出若干条记录作为决策分析的依据。下面从21个连续数值属性出发, 探讨基于粒度损失的离散化算法对样本数据集的敏感性以及对入侵检测系统的影响。

为了分析离散化算法以及对入侵检测系统的影响程度, 首先引入信息增益的概念[8]。设S是样本数据的集合, 其类别属性D存在k个不同的取值, 其第i个值记为Di, 则样本集S的分类信息熵E (S) 为:

其中p (Di, S) 是指样本集S中某个样本的类别属性值为Di的概率。

假设X是样本空间上的一个条件属性, 即X∈C, X将S分为不相交的n个子集, 即S=ni=∪1Si, 当i≠j, Si∩Sj=Φ, 其中:

式中, value (X) 是属性X取值的集合, 则S被属性X划分所得到的分类信息熵E (X, S) 可表示为:

条件属性X相对于样本集S的信息增益IG (X, S) 定义为:

根据式 (5) -式 (7) , 可以计算每个条件属性对于某个样本集的信息增益。依据信息论的观点, 信息增益IG (X, S) 表示属性X及其属性值对决策系统分类能力的贡献程度。显然, 对于一个连续的数值属性, 当样本数据足够多时, 其不同样本子集对决策系统分类能力的贡献程度应相同或者相近, 即说明该属性在不同样本子集上经离散化后所得到的信息增益应一致或者相近。下面采用信息增益作为测度来评价基于粒度计算的离散化算法对于不同样本子集的敏感程度。

实验过程中随机选取9个数据集, 每个数据集各包括3万条记录;选取数据时适当控制使得这些数据集的交集尽可能地小, 以使方法具有普适意义。离散化时每次选择3个相邻区间 (即m=3) 进行合并以加快速度;分别对21个连续数值属性进行离散化, 然后计算各个属性在不同样本集上的信息增益。为了使在不同样本集上计算的信息增益具有可比性, 采用式 (8) 对每个样本集上得到的信息增益进行归一化, 式中的A表示全部条件属性的集合。

图1给出了信息增益变化较为明显的几个连续数值属性在9个不同样本集上进行离散化时的变化情况。从图中可以看出, 离散化过程敏感于样本数据的有6、24、30、35、36、37、38号属性, 其中6、35、38号属性的信息增益变化较为明显, 其他属性的信息增益的变化较为平缓。上述实验结果说明本文所提出的离散化算法在部分条件属性上敏感于样本数据集, 在不同的样本集上进行离散化时损失的信息量有一定差别, 可能要影响系统的决策能力。

在上述离散化的基础上根据文献[9]提出的方法分两种情况将该算法应用于入侵检测。其一是采用41个属性直接建立SVM模型;其二是先进行属性约简, 得到约简后的条件属性集合为{3, 5, 23, 24, 29, 32, 33, 34}, 然后建立相应的SVM模型;进而分析离散化算法在不同情况下对检测模型的影响。实验时随机选择1万条记录作为训练数据, 再选择另外完全不同的1万条记录作为测试数据, 分别得到两种模型下DOS攻击的检测率为99.26和98.57, probing攻击的检测率为99.81和99.19, U2R和R2L攻击的检测率分别保持为99.97和99.74附近, 几乎没有变化。显然, 尽管两种模型下均含有离散化过程敏感于样本集的属性 (约简后仅包括24号属性) , 但是对于各种类型攻击的检测率几乎保持不变, 充分说明本文所提出的离散化算法尽管部分数值属性的离散化敏感于样本数据, 但对入侵检测能力的影响很小, 充分说明该离散化算法具有较强的鲁棒性。

5 结语

连续数值属性的离散化是应用粗糙集等粒计算理论的一个重要环节, 而寻求最优的离散化过程已被证明属于NP完全问题。本文对目前各种离散化算法进行了分类分析, 采用粒计算对连续数值属性的离散化过程进行了描述, 提出了基于粒计算的离散化算法, 并就算法对于样本集的敏感性以及是否影响入侵检测效果等方面进行了分析。实验结果表明该离散化算法对于部分属性敏感于样本数据, 但是无论使用原始的41个属性还是经过约简后的8个属性, 尽管都含有敏感于样本集的部分条件属性, 所建立的入侵检测模型均具有较高的分类能力, 所以基于粒计算的离散化算法具有较强的鲁棒性, 适合应用于入侵检测等决策系统。

参考文献

[1]王国胤, 张清华, 胡军.粒计算研究综述[J].职能系统学报, 2007, 2 (6) :8-26.

[2]张钹, 张铃.粒计算未来发展方向探讨[J].重庆邮电大学学报, 2010, 21 (5) :538-540.

[3]刘业政, 焦宁, 姜元春.连续属性离散化算法比较研究[J].计算机应用研究, 2007, 24 (9) :28-31.

[4]花海洋, 赵怀慈.一种新的无监督连续属性离散化方法[J].计算机工程与应用, 2011, 47 (6) :208-210.

[5]Fayyad U, Irani K.Multi-interval discretization of continuous-valued attributes for classification learning[C]//Proceedings of the 13th International Joint Conference on Artificial Intelligence.San Mateo:Morgan Kaufmann Publisher, 1993:1022-1027.

[6]刘磊, 闫德勤, 桑雨.连续属性离散化的Bayesian-Chi2算法[J].计算机工程与应用, 2008, 44 (18) :39-41.

[7]Kerber R C.Discretization of Numeric Attributes[C]//Proceedings of the 10th National Conference on Artificial Intelligence.MIT Press, 1992:123-128.

[8]李刚, 李霁伦.WILD:基于加权信息损耗的离散化算法[J].南京大学学报:自然科学版, 2001, 37 (2) :148-152.

离散化算法第2篇

在过程化教学考核体系中，考核阶段的划分，成功激励机制的效用以及不同的考核方式的实施是关键点，在过程化教学考核体系中，应体现“以应用为目的，培养兴趣，重视实践”的原则。

2.1 考核方式的选择

离散数学传统的考核方法是笔试，通过试卷，能比较全面地考核学生掌握数学课程的情况，然而，一考定分的方式不能充分发挥学生的主观能动性，难以启发学生的创造性思维。新的考核体系中，采用了探索问题 + 编程实现的方式进行阶段考核，提高了学生的学习热情和积极性，培养了学生的创新能力。

问题的设置必须针对应用型本科专业人才培养模式，充分把握离散数学在专业课程体系中的定位，从离散数学的重要性入手，引导学生去探索问题的答案。例如，在离散数学的第一次课中，给学生讲解“计算思维”和离散数学的联系。留给学生的探索性问题是“离散数学在计算机应用领域发挥什么样的作用？”“计算机专业课程中哪些内容将用到离散数学知识？”学生将以小论文或者调研报告的形式来探索问题，极大地激发了学生的求知欲望。通过设置这样的`探索问题，有利于学生快速掌握课程知识体系，启发学生将离散数学内容与相关课程结合，应用于相关课程，有利于帮助学生理解课程。

2.2 成功激励机制的作用

学习积极性不高是当前大学生存在的普遍现象，但他们渴望成功和自己的付出被认可。因此，采用适当的激励机制能够很好地调动学生的学习积极性，采用课堂课后多种激励方式，让学生积极主动参与到教学活动中，并以此为过程化考核的重要依据。

针对离散数学课程特点，课程组提出以成功激励为主的过程化考核方式。离散数学的课程内容分为四部分：数理逻辑、集合论、代数结构及图论。这四部分内容相对来讲能够各自独立成篇，耦合性弱，课程组采用模块化的方式进行考核，各个模块独立进行测试的方式使得学生在刚学习完本模块内容时进行考核，对其知识点记忆得较好，这时考核必将取得较好效果，这也是对学生的一种公正客观的考核，考核过程也贯穿了整个教学过程。

课程组还采用了平时作业、奖励题、实验环节的编程实践等考核方式，让学生在完成的过程中得到成就感。尤其是奖励题和实验环节的编程实践，根据学生的不同能力特点，布置有一定难度的奖励题，采用直接将考核成绩计入学生期末成绩的方式，使得学生在学习过程中的表现成为成绩评判的重要依据，极大地调动了学生的学习积极性。对同一门课程采取不同的考核方式，这既符合应用型人才培养目标，又可以对学生的成绩评定提供一个客观的评价。

3 建立任课教师教学质量反馈机制

在教学的过程中，尽管教学的内容相同，但实际上不同教师面对不同班级的学生，教学的体验是不同的，而课堂教学的体验是对于教学质量的重要反馈，如何用科学的机制采集、分析教师对课堂效果的评估，激发教师对教学工作的主动性和创造性，建立有效的教学质量反馈机制，将有效的教学经验进行总结与分享具有重要意义。笔者根据离散数学教学过程，建立教师对课堂教学的反馈采集机制，对不同层面的教学信息反馈特点进行深入分析，并研究实施教学信息反馈的作用及关键环节。实现针对离散数学课程的重点内容，教师能够获得可靠的反馈信息，并能够明确自身具体努力方向，促进任课教师，尤其是青年教师投入教学工作的积极性、主动性和创造性。

教学质量反馈机制采用具体的指标，如表 1 所示，由于教学质量反馈与评估存在着模糊性，很难严格界定等级的标准，单一的等级分类是主观意识的结果，因此适合采用模糊评价法。

离散化代数重建的全变差算法改进第3篇

ART算法改进的关键是加快迭代收敛速度和减少迭代次数。影响ART算法的因素有以下几点:投影系数的求取、投影次序的访问顺序、松弛因子以及先验知识的影响等[5,6]。实际医学CT中的图像通常仅由两种或几种已知的灰度值组成,利用这些先验知识便可降低重建条件,从更少的投影数据,或相同投影数据下迭代次数少时,更精确地重建图像。近年来,由K.J.Batenburg等人[7,8]提出的离散迭代算法(Discrete Algebraic Reconstruction Technique,DART)就是利用该先验知识,在加快了迭代收敛速度和减少迭代次数方面取得了显著效果,但DART算法受到噪声影响会使得图像边缘比较模糊,本文提出的DART改进算法就是基于有限灰度值的先验知识快速重建图像,并利用全变差(Total Variation,TV)最小化约束[9,10]进一步抑制噪声,使得图像边缘更加清晰。

1 算法理论

1.1 ART算法原理

设f(x,y)为待重建图像,将一个n×n的方形网格叠加到f(x,y)上,每个网格内的f值均为常量,如图1所示。

扫描射线可由式xcosθ+ysinθ=t表示,其中θ为射线与x轴所夹的角,t为原点到射线的距离。射线宽度为δ。投影值函数,即Radon变换可由式(1)表示

在ART重建过程中,设射线数目为M,所得到的投影数据p={p1,p2,…pM},pi为第i条射线的投影值。wij为第i条射线与第j个像素网格所交的面积,称为投影系数

投影值向量和原图像的关系可由式(3)的代数方程组表示

W(M×N)称为投影系数矩阵。式(2)的矩阵形式如下

ART迭代算法最初于1937年由Kaczmarz[11]提出。其基本思想是松弛法,首先设定一列初值F(0),然后代入式(5)进行迭代

其中,i=0,1,2,…,M,k为当前迭代次数,j∈(1,N),λ为松弛因子。经过反复迭代式(5),不断修正重建值来获取较精确的重建图像。

1.2 DART算法原理

由于实际医学重建或工业无损检测中,被测图像通常仅由一个或有限个灰度值组成,因此图像重建问题可简化为离散断层成像(Discrete Tomography,DT)。近年来,由K.J.Batenburg等人[7,8]研究的基于ART迭代的DART重建算法有显著的效果。

设原图像的灰度值取值范围为V={v1,v2,…v1},定义临界值υ={υ1,υ2,…υ1},其中

通过上述定义设函数T对图像像素值进行离散化

以二值图像为例,DART算法的具体步骤如下:

(1)首先对待测图像进行ART迭代获得初始迭代值F(0);

(2)通过式(7)对F(0)进行离散化,得到离散像素值S(0)=TF(0);

(3)根据8连通域方法将图像分割为边缘像素点集合B和平滑区域集合I(若像素点与其8邻域中至少有一个像素点的像素值不同,则称其为边缘像素点,否则为平滑区域);对F(0)做如下处理

(4)以处理后的F(0)作为初始值重新利用式(5)进行ART迭代得到F(1),更新F(1),保持平滑区域I值不变,即

(5)重复步骤(2)到步骤(4)。

1.3 全变差(TV)原理

实际图像重建过程中,会不可避免地受到噪声影响,因此去噪问题非常重要。由Rudin等人提出的全变差(TV)图像去噪模型[12,13]已在图像复原领域得到广泛的应用和研究。目前,有诸多方法可用来最小化全变差图像去噪模型的能量函数[14,15]。

去噪模型可表示为

式(10)与式(4)是对应的。由式(10)可知,求解min‖F‖TV是关键。而实际min‖F‖TV不能直接计算得到,一般均是通过用范数L1来求解

式(11)中,,DxF,DyF是梯度算子,对于图像上的像素点(x,y),其梯度计算跟F(x,y)和F(x,y)附近的像素值有关

L1范数是图像所有像素点的像素值之和,可通过梯度下降法获取,过程如下

其中,ε=10-8。通过上式可求得min‖F‖TV。

2 算法改进

本文在上述算法的基础上提出DART+TV算法,在DART算法迭代过程中加入TV约束,抑制噪声,使得图像边缘更加清晰。

在DART+TV算法的实现过程中:首先利用DART对图像像素迭代值进行离散化,并通过比较八邻域像素值区分边缘区域B和平滑区域I,若像素点属于平滑区域I,则其像素值赋值为离散化后的值,否则其像素值保持迭代值不变,将处理后的整幅图像像素值重新进行ART迭代,只更新边缘区域B的值保持平滑区域I内的值不变,然后用全变差(TV)最小化约束条件对图像像素值进行处理,然后对此图像进行下一步DART迭代处理,直至像素值满足约束条件则循环结束。算法步骤如下:

算法流程图如图2所示。(1)首先对待测图像进行ART迭代获得初始迭代值F(0);(2)通过式(7)对F(0)进行离散化,得到离散像素值S(0)=TF(0);(3)根据8连通域方法将图像分割为边缘像素点集合B和平滑区域集合I(若像素点与其8邻域中至少有一个像素点的像素值不同,则称其为边缘像素点,否则为平滑区域);对F(0)做如下处理;(4)以处理后的F(0)作为初始值重新利用公式进行ART迭代得到F(1),更新F(1)),保持平滑区域I值不变;(5)利用式(12)对F(1)通过梯度下降法求导,进行最小化约束;;(6)重复步骤(2)~步骤(5)。

3 实验结果

接下来给出3组实验,用于对传统ART算法和DART算法和利用全变差(TV)约束处理的DART改进算法进行比较,以说明改进后的算法的优势,在每组实验中,投影角度均每隔取值。

(1)第1组实验。在这组实验中,使用的原图像是分辨率为的正方形二值模型,如图3(a)所示。图3中分别列出了传统ART算法与DART算法和DART改进算法迭代后的结果。

如图3(a)是原始图像,图3(b)是直接进行ART迭代的实验结果,图3(c)是进行DART迭代的实验结果,图3(d)图是进行DART改进算法迭代的实验结果。

实验中,本文用峰值信噪比(PSNR)值来定量评价重建图像与原始图像的误差,客观评价出重建图像的质量。表1显示了3种算法的实验参数指标对比,参数PSNR值越大说明图像噪声越小,图像质量越好,k为迭代次数。

从表1的实验结果可看出,本文算法和传统ART算法和DART算法相比均有所改进。

(2)第2组实验。在这组实验中,使用的原图像是分辨率为的正方形四灰度值模型。I=zeros(100,100);I(10:30,10:30)=1;I(10:30,60:80)=2;I(60:80,10:30)=3;I(60:80,60:80)=1。

图4分别列出了传统ART算法、DART算法和DART改进算法迭代后的结果。

图5中画出了3种算法的PSNR值随迭代次数的变化曲线图。

(3)第3组实验。在这组实验中,使用的原图像是分辨率为的Shepp-Logan模型,如图6(a)所示。

图6中分别列出了传统ART算法与DART算法和DART改进算法迭代后的结果。

图7为3种算法的PSNR值随迭代次数的变化曲线图。

(4)实验分析。在以上3组实验中,第1、2组采用的是灰度级较少的两幅图像,而第3组采用的是较为复杂的图像。从这3组实验的PSNR值变化曲线可看出,使用改进的DART算法能比传统的ART算法和DART算法较快地达到较好的质量,改进后的算法在前几次迭代时重建质量提高得比较快,一般迭代5、6次后PSNR值趋于平稳。

尤其从1、2组的比较中可明显看出,当原图像的灰度值较少时,使用DART改进后的算法在重建效果方面有大幅提高。

4 结束语

图像重建领域追求的是重建质量和重建速度这两个指标。本文利用一般待重建图像灰度级较少的先验条件,对迭代初值进行离散化分割,将重建问题简单化,并利用全变差约束条件,改善边缘模糊的情况,且在仿真实验中证实了其相对于传统ART算法和DART算法的优势,即重建质量提高了、更少的迭代次数就能达到较好的质量,这正契合了改进的目标。

摘要：文中提出一种离散化代数重建的全变差改进算法,主要针对离散化的代数重建算法易受到噪声等因素的影响而使图像边缘较为模糊的问题,利用全变差最小化的约束条件,提出一种改进的DART重建算法。实验表明,该算法与传统ART算法相比,能较快重建出图像,与DART算法相比,改善图像边缘模糊的情况,具有较好的抗噪性。

离散化算法第4篇

对于数据挖掘和机器学习而言, 数值属性离散化具有非常重要的意义。由于许多算法只能处理离散型信息系统, 因此数值属性离散化是应用这类算法的前提.此外, 有效的离散化能够减少算法的时间和空间开销, 提高系统对样本的聚类能力, 增强系统抗数据噪音的能力, 提高算法的学习精度[1]。然而, 实际的数据库中含有大量的数值属性, 为了得到更加简洁且有效的规则, 常常需要对数值属性进行离散化。但是, 最优离散化问题已经被证明是一个NP完全问题[2]。并且对信息系统的离散化方法不同, 得到的结果也往往存在差异。

粗糙集理论是一种新型的处理模糊和不确定知识的数学工具, 但它不能直接处理数值属性。因此, 在应用粗糙集时, 必须先对数值属性进行离散化。基于粗糙集理论的最优离散化[1]要求在保证信息系统的实例分辨关系的前提下, 用最少的断点对信息系统进行离散化。基于粗糙集理论框架的表格逻辑数据分析软件Rosetta是采用Naive Scaler算法和Semi Naive Scaler算法作为数值属性离散化算法。但是, Naive Scaler算法还存在缺陷。本文将对现有的基于粗糙集理论的数值属性离散化算法进行研究, 客观地评价它们的优缺点, 并在此基础上针对Naive Scaler算法及其现有的改进算法的不足, 提出一种新的改进算法, 最后通过算法示例进行验证。

2、基本概念及离散化问题的描述

定义1 (离散化问题的描述[3]) 。设S=<U, A∪{d}, V, f>为一决策表。其中:U称为论域;A和{d}分别称为条件属性集和决策属性集;是属性的取值范围构成的集合,

是属性a∈A∪{d}的值域;f:U×A∪{d}→V是信息函数, 它指定U中每一个对象各个属性的取值.假设对于a∈A, 值域va=[sa, la]奂R (R为实数集) 。属性a的值域va上的一个断点可以记为有序对 (a, pa) .其中:a∈A, pa∈R (R为实数集) 。值域va=[sa, la]上的任意一个断点集合{ (a pÁÁ) (a pÂÁ) (a pÁÂÁ) }定义了va上的一个划分pa, 即对于某一整数ka:则所有条件属性的划分

就定义了一个新的决策表SP=<U, A∪{d}, Vp, fp>, 对于坌u∈U, a∈A, i∈{0, …, ka}, fp (u, a) =i圳f (u, a) ∈[pia, pai+1], 即把含有数值属性的决策表S转换成离散化的决策表Sp。

定义2.给定决策表S, 如果对于任意的实例uj与uj (i≠j) , 当d (ui) ≠d (uj) 时, 一定存在a∈A, 使得a (ui) ≠a (uj) , 则称S为一致决策表[4]。否则, 称S为不一致的.。

3、基于粗糙集理论的数值属性离散化算法

基于粗糙集理论的数值属性离散化算法大致可以分为两类:一类基本上很少或者不考虑粗糙集理论的特性。其中, 等宽区间法[3]和等频区间法[3]计算简单, 一次可以得到所有的断点值, 但需要预先给定参数, 而且可能会改变原信息系统的不可分辨关系.Naive Scaler算法[3]和Semi Naive Scaler算法[3]都不需要额外的参数, 但离散化后得到的信息表可能引入新的冲突, 改变原信息表的一致性。

另一类算法采用了与粗糙集理论相互结合的方法来解决离散化问题, 能够保证信息系统的分辨关系.其中, 将布尔逻辑运算与粗糙集理论相结合的算法[1]能够求出给定信息系统所有可能的结果断点集, 但却具有NP时间复杂度.贪心及其改进算法[2,5]得到的断点数较少, 但是时间复杂度较高, 且改进算法存在一定的缺陷.基于属性重要性的离散化算法[6]可以减少学习实例的空间维数, 且时间复杂度较小, 但得到的断点个数较多.基于信息熵的全局离散化算法[7]具有多项式级的复杂性, 它不改变决策表的相容性, 但是当决策属性的类别较多时, 计算时间明显提高.基于聚类的离散化算法[8]可以合理地反映出实例的分布情况, 能够得到较好的断点集, 但计算代价较高。

4、关于Naive Scaler算法的进一步改进

4.1 Naive Scaler算法的不足

Naive Scaler算法的思想是对每个属性, 根据属性值从小到大的顺序对决策表中的实例进行排序, 如果相邻两个实例的属性值和决策值都不同, 则取这两个相邻的属性值的平均值作为断点值.该算法的优点在于不需要额外的参数, 时间复杂度较小, 并且能够保证所选的断点不破坏原信息系统的分类关系。但是, 该算法也存在缺陷。

以决策表S (见表1) 为例, 说明Naive Scaler算法存在的不足.按照上述算法思想进行离散化, 可以得到属性a的一个结果断点集pa={0.9, 1.5}, 属性b的一个结果断点集pb={0.75}。最终离散化后的决策表如表2所示。其中, 实例3、4、5、7存在冲突, 破坏了原决策表的一致性。此外, Naive Scaler算法还会随着数据库本身数据的排列情况的不同, 而得到不同的断点集。例如, 对属性b的属性值进行排序时, 对调属性值相等的实例的位置, 可能得到不同的结果断点集, 如pa={0.75, 2.5}, 或者pa={0.75, 1.5, 2.5}。用断点集pa={0.75, 2.5}进行离散化依然会产生冲突样本, 而用pa={0.75, 1.5, 2.5}离散化后的决策表没有产生冲突样本, 但却存在冗余断点。

4.2 现有的Naive Scaler算法的改进算法

Semi Naive Scaler算法是Naive Scaler算法的改进算法, 该算法得到的断点个数较少, 但可能会产生冲突样本, 破坏原决策表的一致性.文献[4]提出了一种Naive Scaler算法的改进算法.该算法可以保证离散化前后的决策表具有相同的不可分辨关系, , 以及保持原决策表的一致性。但是利用该算法离散化后的决策表各属性的属性值个数与未离散化时是相同的, 不能体现离散化的优点和作用。文献[9]也提出了一种改进算法.该算法从整个属性空间的角度来考虑剔除候选断点集中冗余的断点, 不产生冲突样本, 不改变原决策表的一致性。但该算法在剔除冗余断点时, 所选择的候选断点的顺序不同, 得到的离散化结果可能不同。

4.3 Naive Scaler算法的改进算法

针对Naive Scaler算法及其现有的改进算法的不足, 本文提出了一种新的Naive Scaler算法的改进算法.该算法的基本思想是首先判断每个属性的每个候选断点的两个相邻属性值所属的等价类的决策值的集合是否相等.若两个集合相等, 则不选取此断点, 否则选取此断点.为了进一步减少断点的个数, 再次扫描每个属性, 考虑每个属性中每一个断点存在的必要性。

为了更直观地反映出每个属性的每个候选断点的两个相邻属性值所属的等价类的决策值的集合是否相等, 特别构造了属性的初始区间与决策属性的列联表.初始区间即候选断点对该属性的值域进行划分后的区间.然后, 计算该属性的初始区间关于决策属性的频数, 形成该属性的初始区间与决策属性的列联表.如果列联表中相邻两个区间对应着相同的决策值类别, 可以合并相邻的两个区间, 去掉冗余的断点.在构造初始区间前, 应该在不改变原决策表的不可分辨关系的前提下, 尽量去除冗余的属性值.

本文提出的Naive Scaler算法的改进算法具体描述如下:

输入:决策表S=<U, A∪ (d) , V, f>。

输出:离散化后的决策表.

步骤1:对每个条件属性构造初始区间, 形成初始区间与决策属性的列联表。

步骤2:合并区间:如果相邻两个区间对应着相同的类别, 即在列联表中相邻两个区间上对应的决策值的频数或者都为0或者都不为0, 则合并相邻的两个区间, 去掉冗余断点。

步骤3:用合并后的区间对决策表S进行离散化。

步骤4:进一步判断断点存在的必要性。依次对每个属性的每个断点进行如下操作:把与该断点相邻的两个属性值的较小值改为较大值, 如果决策表不引起冲突, 则去掉这个断点;否则, 把修改过的属性值还原。

4.4 算法示例

利用本文提出的Naive Scaler算法的改进算法对表1所示的决策表S进行离散化.属性a的候选断点为{0.9, 1.15, 1.35, 1.5}, 形成属性a的初始区间与决策属性的列联表 (见表3) .经过区间合并, 得到属性a的区间为。同理, 形成属性b的初始区间与决策属性的列联表 (见表4) 。经过区间合并, 得到属性b的区间为。用合并后的区间对决策表S进行离散化 (见表5) .进一步删除冗余断点, 从属性a开始, 把属性值0改为1, 决策表不引起冲突, 但把属性值1改为2或者把属性值2改为3都会引起冲突。说明只存在一个冗余断点, 即断点0.9.同理, 在属性b中, 断点0.75为冗余断点.所以, 最终的结果断点集为pa={1.15, 1.5}, pb={1.5}.可见, 得到的结果断点集是唯一的, 不会随着数据库本身数据的排列情况的不同而发生变化.最终离散化后的决策表 (离散值从0开始标记) 如表6所示, 不存在冲突样本, 可以保持原决策表的一致性.并且最终得到的结果断点集是较优的, 不存在冗余断点.

5、结论

本文客观地评价了现有的基于粗糙集理论的数值属性离散化算法的优缺点, 并针对Naive Scaler算法及其现有的改进算法的不足, 提出了一种新的改进算法。最后通过算法示例验证表明, 本文提出的Naive Scaler算法的改进算法不需要额外的参数, 能够根据信息系统或数据库本身进行离散化处理, 而且可以有效地克服Naive Scaler算法的不足, 能够使最终离散化后的决策表不产生冲突样本, 保持原决策表的一致性, 结果断点集的断点个数较少, 并且得到的结果断点集不会随着数据库本身数据的排列情况的不同而发生变化。可见, 本文提出的Naive Scaler算法的改进算法是有效、可行的。本课题的研究将对发展新的数值属性离散化技术或为特定应用选择合适算法具有一定的参考价值。

摘要：在机器学习和数据挖掘领域, 数值属性离散化是一个重要的研究课题.本文对现有的基于粗糙集理论的数值属性离散化算法进行了较深入的研究, 客观地评价它们的优缺点, 并在此基础上针对Naive Scaler数值属性离散化算法及其现有的改进算法的不足, 提出了一种新的Naive Scaler算法的改进算法, 最后通过算法示例验证了该算法的有效性和可行性.

关键词：数值属性,离散化,粗糙集,Naive Scaler算法

参考文献

[1].赵军, 张显跃.基于粗集理论的数据离散化技术研究[J].重庆邮电学院学报, 2006, 18 (6) :752-757.

[2].Nguyen H.S., Skowron A.Quantization of real values attributes, rough setand boolean reasoning approaches[A].Proc of the 2nd Joint Annual Confer-ence on Information Sciences[C].Wrightsville Beach:[s.n.], 1995.34-37.

[3].王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社, 2001.99-114.

[4].陈东升.保持不可分辨关系的离散化方法[J].郑州轻工业学院学报 (自然科学版) , 2007, 22 (1) :87-91.

[5].赵军, 王国胤, 吴中福, 等.基于粗集理论的数据离散化方法[J].小型微型计算机系统, 2004, 25 (1) :60-64.

[6].刘凌霞.基于粗糙集理论属性重要性的离散化算法[J].广西轻工业, 2007, 23 (10) :75-76.

[7].沈永红, 王发兴.基于信息熵的粗糙集属性离散化方法及应用[J].计算机工程与应用, 2008, 44 (5) :221-224.

[8].Charlotte Bean, Chandra Kambhampati.Autonomous Clustering Using Rough Set Theory[J].International Journal of Automation and computing, 2008, 5 (1) :90-102.

一种离散傅里叶算法的新算法第5篇

离散傅里叶变换 (Discrete Fourier Transform, 缩写为DFT) , 是傅里叶变换在时域和频域上都呈离散的形式, 将信号的时域采样变换为其DTFT的频域采样离散傅立叶变换 (DFT) , 在继电保护系统中, 离散傅里叶变换是应用最广泛的算法, 当测量量中只包含基波和整数次谐波时, 传统的DFT算法只需要一个周期便可以测量, 但电压电流中通常包含衰减直流分量在很大程度上影响了DFT算法的计算量以及计算速度[2], 传统DFT算法通常需要花费4个周期[3], 这在对于时效要求特别严格的电力系统中是非常不利的。本文提出了一种DFT算法的修改算法, 能够在滤除信号衰减直流分量的同时, 保证算法的精确度以及减少计算量, 提高计算速度。

1 传统离散傅立叶算法

有限长序列的傅里叶变换称为离散傅里叶变换。DFT可以按3个步骤由DFS推导出来:

(1) 将有限长序列延拓成周期序列;

(2) 求周期序列的DFS;

(3) 从DFS中取出一个周期便得到有限长序列的DFT

将x (n) 延拓成周期为N的周期序列:

X (n) 的第一个周期, 即n=0到N-1的序列称为主值序列, n=0到N-1的范围称为主值区间。

上式可表示为:X (n) =x ( (n) ) N, x (n) =X (n) RN (n)

其中RN (n) 是矩形序列。符号 ( (n) ) N表示n对模N的余数, 即:

n=kN+ ( (n) ) N, 0≤ ( (n) ) N≤N-1这里k是商。

由此便可以得出有限长序列的离散傅里叶变换 (DFT) 的表示式为:

由此可见, 有限长序列x (n) 的DFT即X (k) 仍是有限长序列。

一般情况下, X (k) 是一个复量, 可表示为:

2 滤除衰减直流分量的新算法

其中b是幅度, τ是直流衰减的时间常数, N个样本, 一个周期后, 第K个样本信号如下:

利用DFT算法

实部:

虚部:

算式中第二部分是基本频率相量的真实部分, 第三部分是衰减直流相量。

其中 (2) 式中的第三部分

变量∧只依靠衰减直流时间常量, 变量φ取决于衰减直流分量的大小与时间常量对于一个给定的传输线路, 衰减直流时间常量只取决于阻抗参数的大小, 如线路电阻, 故障位置, 故障阻抗, 且大部分阻抗参数是可知的。所以变量时间常量可以很容易的被限定在一个给定的边界内, 如1.5到5个周期内, 但是衰减电流大小取决于参数大小, 比如发生故障时的信号幅度 (未知的) 所以衰减直流的幅度是不可知的。

为了计算 (4) 式, 只需要计算出 (5) 式中的实部。 (5) 式中基本频率向量如下所示:

通过 (6) , (7) 式,

样本采样点在 (8) , (9) 式中只需要一个样本的采样周期。

3 仿真计算

为了验证算法的准确性及精度, 以下面的信号作为输入, 利用算法对x (t) 中的各整数次波进行计算, 并且与传统的DFT算法进行比较。

其中:ω=100π, 分别取τ=10msτ=30ms

(表1、表2)

通过仿真结果来看, 算法对于分量的提取效果很明显, 与传统DFT算法相比, 新算法的幅值更加接近实际值, 且需要的样本周期相对较短。在以上的推到式中是假定输入信号中含有衰减直流分量, 整次谐波分量, 如果输入信号中还含有大量非整次谐波分量, 用以上推倒算法仍会产生一定的误差。

4 结语

本文分析了传统离散傅里叶算法 (DFT) , 并提出在输入信号包含衰减直流分量时, 传统DFT算法因为衰减直流分量的影响, 计算的精确度和计算效率都有很大程度的降低, 在此基础上提出了一种传统DFT算法的新算法, 通过有效滤除衰减直流分量, 并且相比传统DFT算法, 提出的新算法只需要一个周期的计算窗口, 大大提高了计算效率, 精确度也有所提高。并且在输入信号中不含衰减直流分量时, 新算法相比传统DFT算法, 计算效率和精确度也都有一定程度的提高。S

摘要：当输入信号中包含衰减直流分量时, 传统的离散傅里叶算法的计算精度和计算效率都有所降低, 提出了一种传统离散傅里叶算法的新算法, 通过仿真对比可以看出, 提出的新算法不但能够有效滤除衰减直流分量, 而且相比传统离散傅里叶算法需要4或以上的采样周期, 且新离散傅里叶算法只需要一个采样周期, 大大提高了计算的效率。

关键词：传统傅立叶算法,衰减直流分量,采样周期

参考文献

[1]陈洁, 何志勤, 叶青.微机保护中滤除衰减直流分量的全周波傅氏算法的仿真比较[J].继电器, 2007, 35 (3) .

[2]李洪生.几种滤除衰减非周期分量影响的傅里叶算法[J].现代电子技术, 2005, 8.

逆变器双环控制策略及其数字离散化第6篇

关键词：逆变器,双闭环控,数字化实现

0 引言

风能、太阳能等新能源发电系统具有环境污染小、调节灵活等优点受到了越来越多的关注。逆变器作为新能源发电系统中电能并网的重要接口, 其工作性能的优劣直接影响到并网电流的质量, 逆变器的控制环节决定了并网电流最终的波形、总谐波失真、功率因数、跟踪误差、动态响应速度等性能, 因此对并网电流控制技术也显得十分重要。逆变并网系统的控制目标为稳定直流母线电压和单位功率因数并网, 其逆变侧采用双闭环控制策略的系统结构框图如图1 所示, 电流内环用于控制并网电流, 电网电压同步信号用于锁相, 从而实现单位功率因数并网, 电压外环稳定逆变器的母线电压, 为逆变器提供稳定并网条件。

1 逆变器双闭环调节器设计

逆变器电流内环为BP调节器, 其在基波频率处增益较大, 基波频率以外增益逐渐衰减, 即使电流指令中引入谐波, 但BP调节器对应的闭环系统只响应电流中的基波频率分量, 通过闭环反馈输出电流中谐波含量大大降低, BP调节器表达式设计为:

电流内环作为并网侧的单位闭环反馈环节, 追求反馈电流与指令电流的精准跟踪。根据系统闭环设计可知, 作为单位闭环反馈系统其可以等效为增益近似为1 的一阶惯性环节, 惯性时间常数 τ 可认为为系统闭环传递函数的-3d B频带的倒数。

将电压环设计为近似典型II型系统, 电压调节器Gv (s) 的传递函数设计为

式中τv1是电压调节器的一阶微分时间常数, τv2是电压调节器一阶惯性时间常数, kpv为电压调节器比例系数。

为了满足系统性能指标, 电压环截止频率 ωcv设计为100rad/s。根据系统典型II型电子最佳设计有, 为了电压环响应速度快, 第一转折频率离截止频率较远, 第二转折频率离截止频率较近。则电压调节器为:

2 双闭环的数字离散化

采用双线性变换法分别对电流调节器进行离散化, 双线性变化法代换算式为:

式 (5) 中T为采样时间。根据电流环系统频带与实际工程应用经验, 离散化采样时间T取200μs, 代入式 (5) 之后得离散化的BP调节器为:

式中E (z) 为BP调节器输入误差, U (z) 为BP调节器输出。式 (6) 中离散化结果保留了三位小数位, 写成微处理器可实现的递推方程形式如下式:

电压调节器也采用双线性变换法离散化, 并将离散化时间T=50μs带入 (4) 式, 得出的电压调节器的递推表达式为

3 结论

本文采用电流内环、电压外环的双闭环控制方式, 具有控制结构清晰, 系统设计容易的优点, 采用带通 (BP) 调节器可以解决母线电压波动对并网电流产生的畸变, 实现单位功率因数并网, 电压外环可以对有效的稳定母线电压, 并给出了在控制器中易于实现的数字离散化处理过程。

参考文献

[1]熊健, 周亮, 张凯等.一种高性能的单相逆变器多环控制方案[J].电工技术学报, 2006, 21 (12) :78-82.

[2]杨会敏, 宋建成.基于双环控制的单相电压型PWM逆变器建模与仿真[J].电气传动自动化, 2009, 31 (01) :15-18.

离散化算法第7篇

随着移动互联网、大数据、云计算等新一代通信技术的发展,视频、图像等数字资源在互联网上的应用越来越广泛,对于这些资源的非法拷贝以及攻击行为导致的知识产权保护等问题日益凸显[1]。作为数字版权保护的一种有效手段,数字资源中嵌入水印(Digital Watermarking)技术作为保护版权及产权的一种有效手段得到了广泛的研究和应用。该技术的主要思路是通过一定的算法将版权信息(水印)隐藏在受保护的视频及图像中,也可以通过间接表示的方法(修改特定区域的结构)嵌入受保护内容中,嵌入后不影响受保护数字资源的使用价值,也不容易被非法探知和再次修改,通过隐藏的水印内容来保护版权[2]。一旦发生版权纠纷,该水印可以被版权拥有者识别和辨认,以证明版权所有者的身份和版权归属,确认版权的创建者、购买者,判断受保护内容是否被篡改等。该技术对视频版权及作者合法权益的保护具有积极意义,是保护信息安全、实现知识产权防伪的有效办法,是信息隐藏技术的重要研究和应用方向。

数字水印算法需考虑隐蔽性、鲁棒性、抗篡改性、容量大小、安全性和可靠性等,主要的水印嵌入算法包括空域算法、Patchwork算法、压缩域算法、NEC算法和变换域算法。本文主要针对变换域算法进行分析,针对现有算法的不足,提出一种基于块内系数自适应优化的水印嵌入算法。

1 变换域算法

基于变换域的水印算法主要包括基于离散余弦变换DCT的数字水印和基于离散小波变换的数字水印算法。基于DCT的算法中,最经典的是Cox等人提出的基于全局图像变换的数字水印算法,该算法主要基于信号的频谱扩展,也就是3G移动通信中广泛使用的扩频通信技术。算法主要原理如下:首先将正态分布的伪随机序列叠加到图像的DCT变换后的视觉系数中。嵌入水印信息的时候不是嵌入到低频系数上,而是嵌入到中频参数上,用以实现水印的鲁棒性与隐藏能力之间的折衷;其次,根据待隐藏的水印信息类型(可以是图像、语音、文字、数据等),对其进行相应的编码处理,根据隐藏信息量的大小及安全性要求,选择某些类型的频域系数参数;再次,通过一定的数学方法,用待隐藏的水印信息数据去调制承载对象的频域系数;最后,将嵌入水印后的图像信息从频域变换到空间域,进行发布、传输等。

2 基于 DCT变换的视频水印嵌入算法

基于离散余弦变换的数字水印嵌入算法在水印嵌入算法中很重要。E Koch、J Zhao等人最早提出了基于分块DCT变换的水印嵌入算法,该方案中,图像被分成8×8的子块,并由一个随机密钥选择其中的一些子块,通过DCT变换得到图像的频域系数,通过改变中频上的三元组得以隐藏二进序列信息。之所以选择中频分量叠加信息,是因为若在高频分量编码,该水印容易被破坏,鲁棒性不高;而在低频分量编码,由于人的视觉对低频分量非常敏感,若改变低频分量会导致视频质量的下降,用户感知度差。由于分块的选择对未经授权者而言具有随机性,因此,未经授权者并不知道嵌入水印的区域,从而难以检测和攻击。另外,该水印算法对图像的压缩处理具有良好的鲁棒性,由于频率参数选择的是中频分量,使得水印嵌入后中频系数的方差较小,因此抗噪声和抗攻击的能力比较好。文献[3]提出了一种基于MPEG-2的DCT自适应水印算法,该算法将水印信息嵌入到承载MPEG-2图像的中频参量上,达到了很好的隐藏水印信息的目的,但缺点是鲁棒性较弱。文献[4]提出一种将原始水印信息进行卷积编码、随机加密处理,然后进行水印的DCT嵌入方法。这种方法提高了水印的鲁棒性,但是算法较复杂。文献[5]提出一种基于DCT的阈值自适应视频数字水印嵌入算法,算法具有良好的水印隐藏特性和鲁棒性,能较好地抵抗不同类型的压缩攻击。

本文提出一种新视频水印嵌入算法,设计思路如下:首先读取视频信息,截图并进行部分解码;然后对解码的截图信息提取其I帧的亮度分量Y,并进行8×8的分块DCT变换;再读取水印图像,并对其进行扩频,生成为包含0和1的序列,并将此作为水印嵌入到视频中;最后,将嵌入水印的视频进行离散余弦逆变换,写入视频码流。对于水印提取或者验证而言,算法思路即为视频嵌入算法的相反过程。

3 仿真实验

实验仿真采用MATLAB软件,通过构建数字水印仿真平台来验证所提算法的有效性。实验参数设置为:视频Football,水印图像采用如图1所示的指纹图像。

3.1 水印隐藏能力分析

峰值信噪比值(PSNR)用来分析水印的隐藏能力,通常定义为原始图像和叠加水印后图像的均方误差对数值,该值越大则水印的隐藏能力越好,也就是说嵌入水印后对原图像的影响越小,嵌入的效果越好。表1列出了嵌入水印的视频序列Football帧的画面及嵌入后的PSNR值,从PSNR值可以看出,算法满足了水印的隐藏能力要求。

3.2 水印鲁棒性分析

如何描述图像中嵌入水印抵抗外部恶意攻击的能力,这是分析水印鲁棒性的关键所在,通常情况下是通过分析不同攻击类型、不同攻击强度下提取出水印和原始水印的相似度进行验证。本算法对视频序列采用压缩攻击,不同攻击强度下提取出的NC值如表2所示。

表2给出了不同的压缩攻击强度下,本文所提算法嵌入水印后提取出水印与原水印的相似度。仿真结果证明,在遭受了上述不同类型的压缩攻击后,所提取到的水印与原水印相似度值均高于0.75,这充分说明所提算法对于JPEG和MPEG压缩具有较强的抗攻击性,鲁棒性好。

4 结语

离散化算法第8篇

关键词：支持向量机,离散化,支持向量机集成

集成学习通过训练和组合多个准确而有差异分类器,可以显著提高学习系统的泛化能力,是年来机器学习领域的研究热点之一。目前,国内以神经网络、决策树等为基分类器的集成学习研已经取得了很大的进展。文献[1]提出训练多个经网络并将其结果按照一定的规则进行组合,取了显著的效果;文献[2,3,4,5]提出了多种集成学习法,例如Breiman[2]的Bagging方法、Schapire[3,4]出的Boosting方法、Zhou等[5]提出的GASEN方。目前,集成学习算法仍在不断涌现。对于支持量机集成,HyunChulKim等人已在文献[6]中将成方法应用于支持向量机,文献[7]则通过交叉选和控制样本特征属性的策略提高支持向量机成的性能,支持向量机集成已在模式识别与机器习领域备受关注,其学习性能仍在不断提高之中。

集成学习的研究表明,只有当组成学习系统的各基分类器具有一定的差异性,即基分类器之间的关联性较低时,集成学习的效果才明显[1]。本文从构造有差异的基分类器出发,采用基于粗糙集与布尔推理的离散化算法(Rough Set and Boolean Reasoning Approach, RSBRA)[8]处理训练样本集,提出基于RSBRA的支持向量机集成学习算法,有效地提高了集成学习的分类性能。

1RSBRA离散化方法

数据离散化是一个将连续属性转化为离散属性的过程。虽然支持向量机可以直接处理连续数据属性,但是在数据离散化过程中,如果选取的断点集合不同,会产生不同的离散化结果。因此,可以采用不同的离散化数据训练支持向量机,构造有差异的基分类器。

离散化的实质是将数据空间划分为有限个区域,每个区域中的对象具有相同的类别。一个典型的离散化过程包括确定候选断点、从候选断点中选择实际断点、以及利用实际断点对初始数据离散化三个部分。设决策表T=(U,C∪D,V,f),其中U为非空有限对象集、C∪D为非空有限属性集、C为条件属性、D为决策属性、V是各属性值域的并集、f为信息函数。对于∀a∈C,值域Va=[la,ra),Pa为Va上的一个划分,即:

Pa={[c $_{0}^{a}$ ,c $_{1}^{a}$ ),[c $_{1}^{a}$ ,c $_{2}^{a}$ ),,[c $_{k}^{a}$ ,c $_{k + 1}^{a}$ )} (1)

(1)式中la=c $_{0}^{a}$ <c $_{1}^{a}$ <<c $_{k + 1}^{a}$ =ra,Va=[c $_{0}^{a}$ ,c $_{1}^{a}$ )∪[c $_{1}^{a}$ ,c $_{2}^{a}$ )∪∪[c $_{k}^{a}$ ,c $_{k + 1}^{a}$ )。c $_{i}^{a}$ (i=1,2,,k)称为一个断点,Ca={c $_{1}^{a}$ ,c $_{2}^{a}$ ,,c $_{k}^{a}$ }为Va的断点集,每一个断点集Ca唯一确定了一个划分。任意的P={Pa:a∈C∪D}定义了一个新决策表 $Τ^{Ρ} = (U, C^{Ρ} \cup D, V^{Ρ}, f^{Ρ})$ ,这称为T的P离散化。这样,离散化问题可以描述为如下的决策问题。

1.1k最小划分问题

给定决策表T和整数k,寻找满足 $| Ρ | < k$ 的T不可约划分;

1.2最优划分问题

给定决策表T,寻找T最优划分。

Nguyen等指出,k最小划分问题是NP完全问题,而最优划分问题是NP难问题,但可以通过构造有效的启发式算法来获得次优断点集[8]。基于粗糙集和布尔推理的离散化方法(RSBRA)是一种有效的启发式监督离散化算法,它采用最大分辨能力启发式方法(Maximal Discernibility Heuristics,MD-heuristic)直接实现。MD-heuristic是一种启发式全局离散化算法,完全基于数据本身进行离散化,其描述如下:

输入:一致决策表T;

输出:实际断点集P;

步骤:

(1)根据决策表T构建表T*,T*的行由所有来自不同类别的两个样本对构成,列为候选断点,表中数据为“1”或“0”,分别代表列对应的断点的值是否介于行对应的两个样本的属性值之间。那么,每一列“1”的数量即为该断点分辨来自不同类别样本的能力。删除最后一行,令T**=T*;

(2)从表T**中选择“1”的数量最多的列,即选择具有最大分辩能力的断点,将该列对应的断点增加到实际断点集P中;

(3)从表T**中删除第2步选择的列和该列值为“1”的行;

(4)若表T**为空表,则算法结束,否则转第2步。

RSBRA的直接实现复杂度很高。设n为样本数目,为条件属性数目,则有, $| Τ^{*} | n (n - 1) k, | U^{*} | n (n - 1) / 2$ 。对∀c∈T*,计算能被c分辨的样本对需要O(n2)步,因此确定一个断点的时间复杂度和空间复杂度分别是O(kn3)和O(kn2)。在实际应用中,必须采用RSBRA的高效实现算法,它可将时间和空间复杂度降低到O(kn),适用于大数据集的离散化。

在r类分类问题中,给定样本子集X⊆U,对于某一断点c $_{m}^{a}$ ,a∈C,1mna,na为样本子集的样本数目,令

$l_{j}^{X} (c_{m}^{a}) = | {x \in X | [a (x) < c_{m}^{a}] \land [d (x) = j]} |$ (2)

$r_{j}^{X} (c_{m}^{a}) = | {x \in X | [a (x) > c_{m}^{a}] \land [d (x) = j]} |$ (3)

其中j=1,2,,r,则c $_{m}^{a}$ 能分辨的X中的样本数为

$W^{X} (c_{m}^{a}) = \sum_{j = 1}^{r} l_{j}^{X} (c_{m}^{a}) \cdot \sum_{j = 1}^{r} r_{j}^{X} (c_{m}^{a}) - \sum_{i = 1}^{r} [l_{i}^{X} (c_{m}^{a}) r_{i}^{X} (c_{m}^{a})]$ (4)

对于集合内的所有子集,c $_{m}^{a}$ 能分辨的总的样本数为

WP(c $_{m}^{a}$ )=WX1(c $_{m}^{a}$ )+WX2(c $_{m}^{a}$ )++WXn(c $_{m}^{a}$ ) (5)

其描述如下:

输入:一致决策表T;

输出:实际断点集P;

步骤:

(1)令决策表集L={U},X=L,实际断点集P=Φ(空集)。将L中属性按属性值a(x)大小排序,得序列v $_{1}^{a}$ <v $_{2}^{a}$ <<v $_{n_{a}}^{a}$ ,其中{v $_{1}^{a}$ ,v $_{2}^{a}$ ,,v $_{n_{a}}^{a}$ }={a(x)|x∈U},na为样本数目,则a上所有得候选断点可取为属性值的平均值:

${\frac{v_{1}^{a} + v_{2}^{a}}{2}, \frac{v_{2}^{a} + v_{3}^{a}}{2}, \dots, \frac{v_{n_{a} - 1}^{a} + v_{n_{a}}^{a}}{2}}$ (6)

即候选断点集为

$C_{1} = \cup_{a \in C} C_{a} = \cup_{a \in C} {c_{i}^{a} = \frac{v_{i}^{a} + v_{i + 1}^{a}}{2}, 1 i n_{a} - 1}$ (7)

(2)对∀c∈C1,计算WP(c);

(3)选择WP值最大的候选断点cmax加入到P中,并从C1中删除该断点;

(4)对于X∈L,若cmax将X分割为X1和X2,那么从L中删除X,并将X1和X2加入到L中;

(5)若对于∀Xi∈L,Xi中的所有样本均属于同一类别,则算法结束,否则转到第(2)步。

2基于RSBRA的支持向量机集成

粗糙集软件包ROSETTA[9]中给出了RSBRA算法的直接实现,并可基于最小碰集(Minimal Hitting Set)控制断点数以降低计算量。但是,减少断点数可能会导致离散化数据出现原始数据并不存在的数据冲突。因此,本文采用RSBRA的高效实现算法对数据进行离散化。

由上一节可知,RSBRA算法的输出是一个次优的断点集,而为了构造支持向量机集成,则需要多个训练集。本文通过选取不同的断点集,产生不同的离散化数据来形成不同的训练集合。由于RSBRA算法在每选择一个实际断点都重新计算各剩余断点的分辨能力,但算法结束时,剩余断点的分辨能力都为0。因此,可根据一个断点的分辨能力和一个预设的基本概率,来确定该断点增加到实际断点集的概率。在产生断点集时,以剩余断点对原始决策表的分辨能力为依据结合基本概率进行断点集选择,从而产生不同的断点集。

基于RSBRA的SVM集成算法(RSBRA Ensemble,RSBRAEN)描述如下:

输入:

训练集S={(xi,yi)},i=1,2,,m;

学习机L;

基分类器数目T;

剩余断点的基本选择概率p;

输出:

集成结果N*;

步骤:

(1)采用RSBRA算法对原始数据集S进行离散化,获得实际断点集P $_{p r a c}^{0}$ ,剩余断点集P $_{r}^{0}$ ,剩余断点的分辨能力WP0r;

(2)从原始数据S中删除在P $_{p r a c}^{0}$ 中无实际断点的属性,记为S*;

(3)计算剩余断点的选择概率:ps=pWP0r/max(WP0r);

(4)对 t=1,2,,T

a.以概率ps从剩余断点集P $_{r}^{0}$ 中选择断点组成集合Padd加入到断点集P $_{p r a c}^{t - 1}$ 中,即:

P $_{p r a c}^{t}$ =P $_{p r a c}^{t - 1}$ ∪Padd (8)

b.采用P $_{p r a c}^{t}$ 离散化数据集S*,得新的数据集S**;

c.删除S**中的重复样本;

d.采用S**训练支持向量机:Nt=L(S**);

(5)采用多数投票法组合基分类器: $Ν^{*} (x) = \underset{y \in Y}{a r g m a x} \sum_{t : Ν_{t} (x) = y} 1$ 。

3实验结果与分析

实验采用三个基准数据集对本文算法进行性能研究,并与支持向量机方法、Bagging和Adaboost集成学习算法进行了对比实验。使用的三个基准数据集包括UCI数据仓库[10]中的Wisconsin Breast Cancer Database(简称数据集Breast)、Glass Identificaition Database(简称数据集Glass)和Statlag[11]中的Heart Disease Database(简称数据集Heart)。表1给出了这三个数据集的基本信息,其中Breast数据集删除了16个属性值不全的样本。

实验共采用了单个SVM、Bagging、Adaboost以及RSBRAEN四种方法进行对比研究,其中Bagging、Adaboost以及RSBRAEN各包含了21个SVM作为基分类器,并都采用多数投票法对基分类器进行组合。每个SVM的参数C和γ通过对训练集进行网络搜索和5倍交叉验证确定,C和γ的搜索范围分别取为[-4,14]和[-14,4],搜索步长为2。剩余断点的基本选择概率设为0.3。实验在三个数据集上分别进行十次,每次随机选择70%的样本作为训练集,其余的作为测试集。各方法分别将十次实验的平均测试值作为最后的结果,如表2所示。

从表2的实验结果可以看出,Bagging和Adaboost两种集成算法并没有获得优于单个SVM的分类准确度,其中Bagging方法仅在Glass数据集上略优于单个SVM,而在其余两个数据集上都比单个SVM差,Adaboost方法则在三个数据集上都比单个SVM差。RSBRAEN方法充分挖掘了原始数据集的内在信息,通过特征选择和删除不相关的属性,有效地提高了集成学习的性能,在三个数据集上的分类准确度都远优于其他三种方法。

4结论

基分类器的差异性能广泛提高集成学习的性能。本文在数据离散化的理论基础上,提出了基于RSBRA的支持向量机集成学习算法。该算法灵活运用RSBRA数据离散化方法,通过构造不同的断点集以生成有差异的多个基分类器训练集,有效地提高了集成学习的性能。实验结果表明,本文方法明显优于单个支持向量机以及Bagging、Adaboost等集成学习算法。

参考文献

[1]Hansen L K,Salamon P.Neural network ensembles.IEEE Transac-tions on Pattern Analysis and Machine Intelligence,1990;12(10):993—1001

[2]Breiman L.Bagging predictors.Machine Learning,1996;24(2):123—140

[3]Schapire R E.The strength of weak learnability.Machine Learning,1990;5(2):197—227

[4]Schapire R E.The boosting approach to machine learning:an over-view.Proceedings of MSRI Workshop Nonlinear Estimation and Clas-sification,2002

[5]Zhou Zhihua,Wu Jianxin,Tang Wei.Ensembling neural networks:many could be better than all.Artificial Intelligence,2002,17(12):239—263

[6]Kim HC,Pang S,Je H M,et al.Constructing support vector ma-chine ensemble.Pattern Recognition,2003;36(12):2757—2767

[7]李青,焦李成.利用集成支撑矢量机提高分类性能.西安电子科技大学学报(自然科学版),2007,34(1):68—70,105

[8]Nguyen HS,Skowron A.Quantization of real value attributes:rough set and boolean reasoning approach.Proceedings of the Second Joint Annual Conference on Information Sciences,Society for Information Processing,1995:34—37

[9]Rosetta O A.Technical reference manual.Knowledge Systems Group,Department of Computer and Information Science,Norwegian University of Science and Technology(NTNU),Trondheim,Norway,2001

[10]Newman D J,Hettich S,Blake C L,et al.UCI Repository of ma-chine learning databases.Irvine,CA:University of California,De-partment of Information and Computer Science,1998