人工免疫聚类（精选7篇）
人工免疫聚类 篇1
1、引言
聚类分析是一种无监督的学习方法, 根据输入样本数据之间的相似性度量, 将样本自动分类。在传统的聚类方法中[2], 基于目标函数的聚类算法把聚类问题归结为一个优化问题, 例如:K-均值聚类[1,3,5]、模糊C-均值聚类[4,6]等。但是这些方法要求聚类类别数和聚类原型的先验知识。同时, 对于优化聚类目标函数的算法, 一般都采用梯度法求解, 这样使得算法很容易陷入局部极小值。对初始化敏感是基于目标函数的聚类算法的又一严重缺点。为了解决局部极值问题, 研究者提出了基于GA的聚类方法[7], 尽管该方法能以高概率收敛到全局最优点, 但收敛速度慢, 而且易出现早熟现象。针对类别数未知的问题, William等提出采用自组织映射 (self-organization feature mapping, SOFM) 神经网络进行聚类[8], 虽然能解决预先设定类数问题, 但却无法解决多类原型的数据分析。
近年来, 随着人工免疫系统方法的兴起, 人们又提出了利用人工免疫网络来进行聚类分析[12,13,14], 实现了无监督分类, 同时解决了GA算法的早熟问题, 但该方法同样仅适合各样本子集边界清晰的情况, 若各子集间交集为非空, 或存在噪音时, 这些样本作为抗原, 能够极大的激活免疫网络, 引起抗体分泌, 使网络结构不再清晰, 从而不能正确的聚类。
本文基于独特性免疫网络理论, 结合自组织特征映射原理, 提出了一种动态免疫网络聚类算法, 该算法强调免疫网络拓扑结构对免疫记忆, 抗体竞争, 免疫耐受, 克隆变异等免疫机制的影响, 利用自组织特征映射原理, 改进克隆变异算子, 引入抗体合作机制。仿真实验结果表明, 该算法的聚类性能明显优于传统的聚类算法和aiNet[13]免疫网络算法。本文第2节介绍了我们的免疫网络算法中用到的一些基本概念和主要机制, 第3节介绍了我们提出的免疫网络聚类算法, 分析了算法的关键操作和过程, 第4节是仿真实验及结果比较, 第5节是结论。
2、基本概念与主要机制
2.1 SOM网络
自组织特征的映射 (self-organizing feature maps, 简称SOM) , 根据样本的内在联系, 能够对样本自动进行聚类。设网络输入模式为X=[x1, x2, ..., xm]T, M为输入样本的维数。SOM权值为wj=[wj1, wj2, ..., wjm]T, j=1, 2, ..., l, l为总的神经元个数。SOM算法的核心步骤为:
Step1:选择具有最小距离的节点j*作为获胜节点:
Step2:调整输出节点及其几何邻域内的节点所连接的权值:
易见, SOM学习算法在对竞争获胜的神经元及其邻域的调整时, 依赖于欧式距离||X-wj||。当样本在输入空间中分布不规则或呈高度线性不可分时, SOM网络聚类效果差, 且对噪声和野值点极为敏感。
2.2 重要的免疫概念
免疫网络理论是由Jerne在1974年最先提出的Leandro根据Jerne的免疫网络理论, 在2000年提出一种人工免疫进化网络 (Evolutionary Artificial Immune Network) [12].在我们的网络模型中, 假设抗原集AG={ag ag∈S}是待分析数据集, 其中agi=[agi1, agi2, …, agim]T表示第i个样本的m个特征值, agi表示形态空间Sm中的一个点, 将这个点作为抗原;设抗体集AB={ab|ab∈S};基于Mercer核函数, 定义非线性映射φ:X→φ (X) ∈F, 其中X∈R, R为样本集, F为特征空间。设p∈AB, q∈AB∪AG, 这样抗原-抗体及抗体-抗体之间的亲和力被定义为:
在我们的模型中, 不仅强调了抗体-抗体及抗体-抗原的群体影响, 而且突出了免疫网络结构的记忆、耐受和学习等免疫机制, 整个免疫网络拓扑采用树形结构, 树形拓扑具有很好的仿生性质, 它的生长过程能够较好的模仿免疫网络的进化过程, 可以很好的控制网络的动态性和可塑性。每一条拓扑连接的起点表示抗体父亲节点, 末端表示克隆产生的抗体儿子节点。受抗原刺激越大的抗体克隆产生更多的子孙抗体, 当免疫网络进化结束后, 再进行网络压缩, 最后得到的网络能较准确的对输入样本 (抗原) 聚类。
此外, 若抗体交互机制只存在竞争和抑制, 那么该机制仅能较好的控制抗体数量, 至多间接提高聚类效果。故, 抗体-抗体作用机制应是综合的交互机制, 一方面能控制抗体总数, 同时又能保证聚类质量。在模型中, 基于网络拓扑影响的抗体交互机制包括:抗体竞争、抗体合作和抗体抑制。需要注意的是, 在算法中, 抗体合作机制是通过抗体变异体现的, 变异机制采用了自组织映射原理 (SOM) , 变异信号由竞争获胜抗体发出, 通过网络拓扑路径向全网抗体节点传递, 信号随拓扑路径的长度衰减, 距离获胜抗体拓扑路径近的抗体节点, 有较相似的变异趋势, 距离远的抗体有相对独立的变异趋势。抗体的变异取决于三个因素:当前变异学习速度、当前窗口宽度和距获胜抗体节点的网络拓扑路径。
3、算法描述
3.1 动态免疫网络聚类算法
下面给出该免疫网络算法的具体描述:
算法1.动态免疫网络聚类算法
输入:待聚类抗原样本
输出:记忆抗体网络
Step1:随机产生初始抗体免疫网络;初始化各相关参数, 预设最大进化代数G。
Step2:随机选择样本抗原向免疫网络提呈, 选择具有最高亲和力的抗体作为获胜抗体;若该抗体是非记忆抗体则其受刺激度递增, 若该获胜抗体受刺激度低于刺激阈值σs或该抗体是记忆抗体则转至步骤 (Step4) 。
Step3:获胜抗体转变成记忆抗体;进行克隆选择, 抗体亲和力越高, 克隆抗体细胞越多;对克隆产生的抗体细胞进行以获胜抗体为中心的高斯多样化处理;建立克隆产生的抗体节点与获胜抗体节点的网络拓扑连接。
Step4:计算网络中每一个抗体节点与该获胜节点的拓扑距离, 进行以该获胜抗体节点为中心的免役网络的抗体细胞变异操作。
Step5:对每一对抗体, 若抗体-抗体间满足抑制条件, 则进行抗体抑制操作。
Step6:网络拓扑更新, 调节网络拓扑连接, 若抗体抗体间的连接强度低于连接阈值σu, 则断开网络连接;若记忆抗体的子孙节点数减为0, 则该记忆抗体转变成非记忆抗体。
Step7:更新当前各相关参数, 若未超过进化时限, 则转至步骤 (Step2) 。
Step8:进行网络抑制, 删除网络中当前所有非记忆抗体。
Step9:输出记忆抗体网络。
3.2 算法关键过程分析
在上述算法中, 只考虑抗原与抗体;其中抗体细胞又分为记忆抗体集和非记忆抗体集。免疫网络从初始的非记忆抗体网络开始进化, 每次选择与抗原具有最高亲和力的抗体, 将其转换成记忆细胞, 并进行克隆增生, 产生新的非记忆抗体细胞。该过程循环进行, 免疫网络以分层树形拓扑结构进化;最后进行网络压缩, 将所有非记忆抗体从网络中移除。此外, 尽管亲和力计算和细胞变异采用了基于Mercer核函数的新的距离度量标准, 但抗体竞争、克隆选择和抗体变异等仍然在原输入空间中进行, 核代入后只是改变了内积运算, 不需要知道非线性变化的具体形式, 并没有使算法复杂性随着维数的增加而增加.算法的整个学习过程依然在原空间中进行, 这样一方面保证了当样本数据空间分布比较混乱、重叠比较明显时的聚类效果, 另一方面又保持了整个聚类过程及结果在原空间中的直观刻画。
1、抗体竞争
当抗原提呈给免疫网络时, 所有的抗体参与竞争, 与抗原亲和力最高的抗体成为获胜抗体, 该抗体转变为记忆抗体, 进行克隆选择。根据亲和力计算公式:, 为了得到亲和力最高的抗体细胞, 需要最小化, 故我们对使用最速下降法, 得到抗体p的变异公式:
2、抗体变异
根据前面2.3节中的分析, 在算法中, 抗体变异采用了自组织映射原理 (SOM) 。由式 (6) , 我们得到网络中的抗体变异公式
di, best是获胜抗体与当前抗体abi的网络拓扑距离。η (n) ≤1是当前的变异速度, ρ (n) >0是当前窗口宽度, 并且有,
其中, 0<ηG<η0≤1, 0<ρG<ρ0, λ>0;λ用来控制η (n) 和ρ (n) 的收敛速度。
3、抗体抑制
通过抗体抑制来控制免疫网络中的抗体节点数量;当抗体-抗体间满足以下条件时, 则抑制发生:
(i) %抗体-抗体间无直系克隆关系, 即抗体-抗体间无直系祖父辈或直系子孙辈关系;
(ii) %抗体间亲和力大于自体免疫阈值σd;
当抗体抑制发生时, 以概率删除具有较少子孙节点的抗体及以该节点为根的整棵子树, 而以概率修改具有较少子孙节点的抗体双亲, 使另一抗体成为该抗体新的双亲。
4、网络拓扑更新
通过前面的分析, 我们知道, 每一条网络拓扑连接是建立在竞争获胜抗体与其克隆产生的抗体之间的, 所以拓扑连接两端的抗体具有较高的亲和力, 然而, 由于一些偶然因素的干扰, 在免疫网络的进化中, 并不能保证总是这样;我们需要不断的调节拓扑连接, 避免具有低亲和力的抗体对间具有直接的拓扑连接。设σu为连接强度阈值, 当具有直接拓扑连接的抗体对间的亲和力低于σu, 则断开该拓扑连接。该机制能够引起独立分支树的出现, 提高不同类簇的网络聚类精度。
3.3 聚类关键参数分析
这里的动态免疫网络进化, 大致可分为: (1) 网络生长期和 (2) 网络结构调节期两个阶段。在前期网络生长阶段, 概率较大, 抗体抑制发生时候, 主要进行删除抑制操作, 降低抗体冗余度, 而当进入到后期网络结构调节阶段, 较大, 抗体抑制主要进行抗体间的关系调整操作, 提高网络拓扑的聚类精度。所以, 自体免疫阈值σd太大, 会引起抗体冗于度过大;σd太小又会过度抑制抗体细胞, 导致网络拓扑结构的混乱;刺激阈值σs过大, 免疫网络的抗噪音能力强, 但会引起免疫过度耐受, 缺少足够的抗体细胞, σs太小, 又会产生免疫刺激过敏, 并降低抗噪音能力;此外, 连接阈值σu也需要准确设置, 太大导致过多的类簇分支, 太小又会丢失需要的类簇分支。在仿真实验中, 我们进行了大量的实验和尝试, 对实验中的各个相关参数进行了较为合适的设置。得到了令人满意的聚类效果。
4、实验结果及分析
4.1 IRIS数据集上的实验
实验1采用UCI机器学习库中的IRIS数据集, IRIS数据集包括3个类, 每个类由50个4维模式组成, 并且第2、3类是线性不可分的。显然, 不同的Mercer核函数代入会在原输入空间中产生不同的距离度量;在实验中, 采用高斯核, 参数σ=1.1, 令免疫网络最大进化代数G=1000, 克隆增生最大值k=3, 变异速度η0=0.5, ηG=0.01, 窗口宽度ρ0=32, ρG=0.6, 克隆增生阈值ζ=0.94, 收敛速度控制因子λ=0.3, 刺激阈值σs=2, 连接阈值σu=0.88, 自体免疫阈值σd=0.96;并且, 我们分别采用K-means算法、SOM聚类算法、aiNet网络算法和我们的算法对IRIS数据集进行聚类;每个算法均独立进行10次实验。表1给出了各个算法最后的聚类正确率。
通过表1中的实验结果说明, 我们的免疫网络算法的聚类正确率明显优于K-means算法和SOM算法, 特别是在输入2、3类样本间边界模糊, 仍然保持了较高的聚类正确率;这是因为引入核函数的因素;此外, 尽管aiNet网络算法的正确率接近我们的算法, 但在多数情况下, 它的聚类中心均偏离了理想的聚类中心位置。
4.2 DARPA入侵攻击数据集上的实验
实验2是对入侵检测系统产生的报警数据进行映射聚类, 采用入侵检测系统Snort[17]检测DARPA的分布式拒绝服务攻击 (DDOS) 数据[18], 所产生的报警数据集经过剔除与DDOS攻击无关的报警数据后, 共有60条报警数据。本文对数据集进行字符属性的数值化和所有属性的归一化, 并按照攻击流程选择聚类的类别数为4, 即端口扫描、缓冲区溢出、DDOS工具安装和DDOS攻击。对数据集应用该映射聚类方法, 采用高斯核 (实验参数同实验1) 。
结果只将原本属于缓冲区溢出的一条数据错误地聚为DDOS攻击数据, 另将端口扫描的两条数据错误地聚为DDOS工具安装数据, 聚类的正确率为95%。
5、结论和进一步研究
无监督聚类分析, 特别是当类间样本边界模糊时的聚类, 是聚类分析的主要研究问题之一;本文提出了一个动态免疫聚类网络, 利用免疫网络的良好特性, 结合了自组织映射和Mercer核函数的优点, 仿真实验证明了算法的有效性和良好的性能。由于不同的核函数代入会在原输入空间中产生不同的距离度量;如何针对具体问题选择合适的核函数及网络学习参数, 并使参数具有自适应性, 以及对免疫网络自身的收敛性和稳定性的证明, 是下一步的研究重点。
人工免疫聚类 篇2
入侵检测系统是一种主动的安全防护系统, 它通过对网络流量或主机运行状态的检测来发现对系统资源的非法授权访问与破坏行为, 并对各种恶意攻击做出响应。入侵检测方法主要分为异常检测和误用检测两种。当前的研究热点是异常检测技术。聚类分析是一种重要的异常检测方法。它利用某种相似性度量, 把一个未知类别的样本集组织成若干个有意义的子集, 要求相似度较高的样本尽量归为一类, 而不相似或相似度较小的样本则在不同的类中[1]。
由于在一般的网络环境内, 正常行为是主流, 而入侵则表现为个别现象, 因此获得的正常实例的规模远大于入侵行为的数目。入侵检测中的异常检测模型假定所有的入侵活动都是异常活动, 由于在合理的尺度条件下属于同样类别的数据实例在特征空间中互相接近, 而不同类别的数据实例则相互远离, 因此可以将聚类算法应用于入侵检测。通过这样的划分, 可将网络流量样本集中的正常流量和异常流量区分开来。
目前普遍采用的聚类算法是模糊C-均值聚类 (FCM) 算法。但是其主要缺点是对初始值过于敏感, 要求输入聚类的数目, 并且只能处理数值属性, 而网络中的数据不仅有数值属性, 还有分类属性。本文利用人工免疫网络aiNet算法能够自动生成聚类的优点, 提出基于人工免疫网络和模糊C-均值的AiNet_Fcm入侵检测方法。
1 FCM算法
假设给定数据集X={x1, x2, …, xn}, 模糊C均值算法把n个数据集对象划分为c个子类, 并给每个子类定义一个聚类中心, 然后根据数据集中的每个数据对象与聚类中心的距离, 形成一些具有相同性质的模糊子集, 每一个数据对象与聚类中心有一个隶属度, 并使得非相似性指标的目标函数达到最小。FCM采用模糊划分的方法, 使得每个给定数据对象用[0, 1]间的隶属度来确定其属于各个子类的程度。用uij表示数据集中的第i个样本隶属于第j个类的隶属度。设第j个类的聚类中心向量为vj, 则定义目标函数为:
其中m (m>1) 是模糊指数。该目标函数实际表征了各条样本到聚类中心的加权距离平方和, 其值越小, 表明各类中样本依附于它们的聚类中心就越紧密。聚类问题就是求使J (U, V) 最小的隶属度矩阵U = [ui j]n×c及类别中心v= (v1, v2, …vc) 。
计算隶属度uij:
更新聚类中心:
2 一种改进的AiNet算法[2]
AiNet 是由De Castro提出的一种人工免疫网络模型。该模型模拟生物免疫系统中抗体克隆和选择过程。aiNet实际上是一个加权图, 该图由一组不完全连接的称为抗体的节点组成, 每对节点产生一条边, 每条边上都赋有权值。aiNet模型的最终目的是建立一个记忆集合, 用来识别和表示数据结构组织, 它主要用于减少数据冗余等。
为了使抗体集合尽可能反映所有的抗原分布情况, 添加一步, 即在每个抗原作用于抗体集合时, 与该抗原有相同特征的抗体都有机会进入临时抗体集合中;并且为了获得稳定的抗体集合, 在变异过程中, 改用退火变异, 即随着循环次数的增加, 变异的概率逐渐降低。
3 基于AiNet和FCM的入侵检测算法
基于聚类的入侵检测方法建立在以下两个假设之上: (1) 正常行为的数目远远大于入侵行为的数目; (2) 入侵行为和正常行为差异非常大。该方法的基本思想就是由于入侵行为和正常行为不同并且数目相对较少, 它们在检测的数据中呈现出比较特殊的特性。
AiNet_Fcm入侵检测方法主要包括三部分。
3.1 aiNet_FCM聚类算法
FCM算法是通过对基于欧氏距离度量的目标函数的极小值而得到最终的分类结果, 但是这类基于目标函数的聚类算法存在的最大问题就是对聚类先验知识要求的增加, 因为在聚类分析之前, 必须给定聚类原型的类型以及聚类的类别数c, 否则将会对算法产生误导, 得到的聚类效果不好, 从而得不到数据集的正确划分。而AiNet模型模拟生物免疫系统中抗体克隆和选择过程, 引入了亲和度成熟、克隆和记忆机制, 并利用相应的算子保证了该算法能快速的收敛到全局最优解。在模型中, 把输入的数据集作为抗原, 最终输出的抗体作为聚类中心, 就能够得到数据集的一个较好的聚类中心和聚类数目。这样就弥补了FCM算法的缺点。
结合AiNet和FCM, 可得到基于人工免疫网络的模糊C均值 (AiNet_FCM) 聚类算法流程:
(1) 使用AiNet算法的到数据集的一个初始聚类中心和聚类数目。
aiNet算法将数据集X作为抗原集合, 生成的抗体集合则作为聚类结果。抗原与抗体之间, 以及抗体与抗体之间的亲和度由它们之间的欧氏距离决定, 距离越大, 亲和度越低。算法结束时, 以生成的抗体集合作为FCM算法的初始聚类中心, 抗体的数目作为聚类数目。
(2) 利用式 (1) 中的聚类中心和数目运行FCM算法, 得到最终的聚类中心和聚类。
3.2 标类算法[6]
在聚类生成之后需要对其进行标类。由算法的2个假设可以推测在最后生成的聚类中, 如果某个聚类为正常数据所聚集成的, 那么它包含的数据数目应该远远大于那些由入侵数据聚集成的聚类所包含的数据数目。因此, 可以将所有的类按其中包含的数据量大小排序, 并设定一个比例常数N (异常类比, 异常类在总聚类数目中的比例) , 那些位于N以下包含较少数据量的类被判定为异常, 其余的类为正常。假设Ci, i=1, 2, …, K为已生成的聚类, N∈ (0, 1) 为异常类比。标类算法的描述如下:
(1) Sort (Ci) , 按Ci中包含数据的多少降序排列;
(2) 对于每一个聚类Ci:
如果i<K× (1-N) , 则将Ci标为正常类;
否则将Ci标为异常类。
3.3 异常检测算法
异常检测算法的描述如下:
假设x是一个要检测的网络数据包:
(1) 将x进行预处理;
(2) 找出x与所有聚类中心Ci距离的最小值min_dist及所对应的Ci;
(3) 如果有min_dist大于某个检测阈值, 则认为此数据包为入侵数据包, 报警;
(4) 若Ci为正常数据类, 则x为正常数据包, 否则为入侵数据包, 报警。
4 实验及结果分析
为评价基于AiNet_FCM的入侵检测方法的性能, 本文采用KDD CUP99[3]数据集进行了测试实验。该数据集包含四大类入侵类型, 即Probing、R2L、U2R和DoS。为了满足检测算法的两个假设的需要, 需要对KDD CUP99数据集作一些过滤。所以, 从整个数据集中提取10100条记录作为训练样本集, 其中含有入侵数据100条, 符合检测算法的第1个假设的要求。在整个训练集中入侵类型及数目如表1所示。
在测试样本集的选取中, 共选取了3组数据:第一组测试样本集选自训练样本集。第二组和第三组则选自KDDCUP99数据集中除去训练样本集以外的数据, 并且在选择时特意选择了不在训练样本集中的入侵数据, 即这两组测试样本集包含有未知的入侵。
因为KDD CUP99数据集中每条记录有41个属性, 既包括数值属性, 又包括分类属性。并且数值属性的度量标准不同, 直接进行聚类处理将产生不真实的结果, 所以要对它们进行数据的预处理。
4.1 属性的选取
数据集中每条记录有41个属性, 其中数值属性34个, 分类属性7个。但是并不是每个属性都对检测结果有贡献, 文献[4]中用支持向量机方法通过实验指出KDD CUP99数据集中有13个属性最为重要, 其中11个数值属性, 2个分类属性。实验采用了该属性选取方案。
4.2 分类属性处理
在选取的13个属性中, 有2个分类属性, 由于FCM算法不能直接处理分类属性, 因此, 可以把分类属性转换成数值属性, 处理方法是对其进行编码, 对于有m种不同取值的分类属性, 用m bit对其进行编码, 当且仅当属性取值为第i种值时, 其码字中的第i bit为1, 其余bit 为0[5]。如属性protocol_type有3种取值, 则可编码为:tcp 001, udp 010, icmp 100。但是另一个分类属性有66种取值, 若直接编码, 则带来输入矢量过大的问题, 因此, 本文选取取值最多的3个编码:ecr_i 0001, private 0010, http 0100, 其他的所有都编码为1000。
4.3 数值属性的处理
对于数值属性来说, 不同的数值属性有不同的度量标准, 如果直接对原始数据不进行预处理就有可能产生大数吃小数的问题。为了解决这一问题, 要对数值属性进行一些规范化处理。
4.3.1 标准化
其中
4.3.2 正规化
正规化变换的公式为:
其中x′ij标准化后的第i个数据的第j个属性,
对于网络中的每个数据包, 都按照上述方法对它的属性进行计算, 并得到新的数据计算欧氏距离, 可避免数值属性度量标准不同带来的影响。
4.4 实验结果及分析
在实验中, 为了评价算法的性能, 对相关统计量做如下定义:
异常类比N 异常类在总聚类数目中的比例;
检测率D 检测出入侵的数目与测试集中总的入侵数目的比值;
误警率E 检测为异常的正常数目与测试集中所有正常数目的比值。
检测率和误警率是入侵检测系统最重要的性能指标, 检测率与误警率总是紧密相关的, 增加检测率常常要以误警率的增加为代价, 而误警率偏高使系统对原本不是攻击的事件产生了错误的警报, 将导致入侵检测系统的性能降低, 因此只能在两者之间取折衷的选择。表2是对不同的异常类比N的实验结果。
由表2可以看出, 当异常类比为25%时, 算法的整体性能较好, 因此, 本文固定此阈值测试算法对未知攻击的检测性能。当异常类比为25%时, AiNet_Fcm算法对于测试集的平均检测率和误警率为82.9%和1.62%。此外可以使用普通的FCM聚类算法进行异常检测实验, 数据的预处理采用本文的方法处理, 得到的平均检测率和误警率为67.8%和3.17%。通过比较可知, 在入侵检测上, AiNet_Fcm算法比普通的FCM算法结果更为理想。
表3显示了当N=25%时算法在测试集2和测试集3上对已知和未知攻击的检测情况。所谓已知攻击是指在测试集和训练集中都包含的攻击类型 (表1中列出的入侵类型) , 未知攻击是指在测试集中包含但训练集中没有的攻击类型。
从表3可以看出, 算法对DoS和Probing入侵的检测效果较好, 但是对于U2R和R2L的检测效果不是很理想, 主要原因有两个:
(1) R2L、U2R攻击, 不像DoS、Probing那样在短时间内对一些主机发出很多连接, 它们嵌入到包中, 正常情况下只存在于一个连接中, 无法对其进行足够的特征描述。
(2) Probing、DoS攻击相对来说比较固定, 而R2L、U2R类攻击种类较多, 且有很多的R2L入侵伪装合法用户身份进行攻击, 这就使得其特征与正常数据报比较类似, 造成算法的检测率偏低。但总体来说, 算法对未知攻击的检测率在40%以上, 说明其能够比较有效的检测未知攻击。
5 结 论
本文分析了基于人工免疫网络和模糊C-均值的异常检测的可行性, 给出了该检测方法的流程和混合型属性的数据与处理方案, 并利用KDD CUP99实验数据集进行了仿真实验, 证明该方法能取得较高的检测率与较低的误警率, 尤其是在对DoS、Probing攻击的检测中取得了满意的检测结果。但是算法对其他两种攻击类型的检测效果不理想, 异常类比N需要人工干预, 因此下一步的研究重点是如何提高U2R和R2L两种类型的检测率和如何自动找到合适的参数N。
参考文献
[1]Jiawei Han.Micheline Kamber Data Mining:Concepts and Techniques[M].Morgan Kaufman, 2005.
[2]钟将, 吴开福, 吴开贵, 等.基于人工免疫网络的动态聚类算法[J].电子学报, 2004, 32 (8) :1268-1272.
[3]http://kdd.ics.uci.edu/database/kddcup99/kddcup99.html.
[4]Mukkamala S, Janoski G, Sung AH.Intrusion Detection Using SupportVector Machines and Neural Networks[C].Washington DC Proc.of theIEEE Int’l Joint Conf.on Neural Networks, 2002:1702-1707.
[5]黄斌, 史亮, 姜青山, 等.基于孤立点挖掘的入侵检测技术[J].计算机工程, 2008, 34 (3) :88-90.
人工免疫聚类 篇3
基于人工免疫机制的入侵检测系统不仅能识别已知的攻击,而且能识别未知的攻击,近年来已成为一个新的研究热点[1,2]。然而传统的基于免疫机理的入侵检测算法是基于监督学习的算法,需要足够的训练数据以生成具有良好的泛化性能的检测模型,需要完善的自体集以完成自我耐受[3,4]。然而,在网络环境中,要获得足够的标记数据作为训练集是困难的,代价高昂。非监督学习方法根据数据的相似性进行分组[5],克服了监督学习方法中需要标记数据的不足。但是,非监督检测算法的检测精度明显低于有监督的异常入侵检测方法[6]。在现实应用中,获得少量的标记数据是可能的,因此,利用少量的标记数据进行有指导的半监督学习技术[7,8,9,10]正在被广泛应用到入侵检测领域。
在基于人工免疫的入侵检测方法中,产生的初始抗体的质量很重要,要能覆盖大部分非我,而且不能匹配自我。若抗体规模不够,则可能大部分入侵都识别不出来,都会被当作正常样例给放行。而抗体的质量取决于训练样例的数量,在网络环境中,获得足够的标记数据作为训练样例集是困难的,故本文将半监督聚类技术应用到基于免疫的入侵检测系统中,利用少量的已标记样本来获得大部分未标记数据的类别,不断改善抗体的质量,从而提高检测率。
1 相关定义
定义1 抗原与抗体
设Ag代表抗原集合,Ab代表抗体集合。用一个实数坐标M=<m1,m2,…,mL>表示抗原或抗体,将其看作L维实数空间中的一个点M∈SL⊂RL ,其中S表示形态空间,L表示其维数,mi(i=1～L)均为实数,抗原、抗体的表示方式完全一样。
定义2 抗原与抗体的亲和力
设抗原Agi的坐标由<Agi1,Agi2,…,AgiL>给定,抗体Abj的坐标由<Abj1, Abj2,…, AbjL>给定,则它们之间的亲和力用如下公式表示:
DAgi-Abj表示抗原与抗体间的Euclidean距离,可见距离越小,亲和力越大。Agin、Abjn分别代表抗原与抗体集中的两个样本,它们都有L个属性。
定义3 自我集的中心及识别半径
假定第i个自我集Self(i)=(Si1,Si2,…,Sim)表示拥有m个自我的聚类,其中心Sc(i)表示为:
其中,Xik表示聚类i的第k个属性值,Scik表示聚类中心的第k个属性的取值。
自我集的识别半径用聚类内所有向量之间的距离的平均值来表示,公式如下:
其中,Si,Sj为自我集内的两个向量。
定义4 抗体的识别半径
根据自我集的中心及识别半径导出第i个抗体的识别半径,具体公式如下:
Abi.radious=min{DAbi-Scj-R(Scj)|j=1,2,…,s} (4)
其中s表示自我集聚类的数目。
2 基于半监督聚类技术的免疫入侵检测算法
2.1 算法思想
在传统的基于人工免疫技术的入侵检测算法中,抗体的生成方式通常是:在训练阶段随机产生检测器,经历自体耐受后成为成熟抗体,然后再参与检测。随机产生检测器由于随意性较大,需经历自体耐受,若自体规模较大,则训练时间很长;若自体规模不够,则产生的抗体可能会覆盖自我,会导致误判。因此,本文借助于聚类技术,将免疫方法与聚类方法结合起来,提出了一种半监督的免疫入侵检测算法SCIID,充分利用少量的已标记数据来指导抗体的生成过程,可大大缩短抗体的耐受时间。
SCIID算法分三个阶段:抗体产生阶段,首先对自我样本进行聚类,获得自我样本的聚类中心及识别半径,这里聚类中心是聚类内所有样本的几何中心,识别半径是聚类中所有样本之间的平均距离。然后根据训练数据集中非我与自我聚类中心的距离进行克隆扩增,产生初始抗体;最后根据式(4)计算每个抗体的识别半径,相当于进行阴性选择,至此抗体产生完毕。这里,计算抗体的识别半径时,不必计算跟每个自我的距离,而只需计算跟自我聚类中心的距离即可,大大缩短了计算时间。
入侵检测阶段:新抗原到来后,计算新抗原与抗体及自我聚类中心的距离,能被谁识别,则进入相应的聚类,相应的标签标为聚类所在类的类标签。这样可实现利用少量标记类数据获得其他大部分数据的标记类。对于有些抗原,如果都不能被当前已知类别识别,可考虑使用K-近邻法,通过投票决定其属于什么类别,如果经过投票方法后依然不能确定其所属的类别,则产生一新的类别,由用户参与决定是自我还是非我,同时产生该聚类相应的抗体。
抗体更新阶段:经过一段时间后,由于新的抗原的加入,使得类的分布发生了变化,自我可能发生变化,非我也可能发生变化,故需调整聚类中心。具体做法是,将新出现的抗原散列到各个聚类当中,重新计算聚类中心和聚类半径,同时更新抗体中心及识别半径,不断改善抗体的质量。若抗体数目超过一定数目,则去除最近最久未参与识别的抗体,以此来保证抗体种群的规模在可控范围之内。
2.2 算法描述
输入:训练样本集T=Tself∪Tnonself(已标记类别),未知类别样本集U。
输出:未知样本x∈U所属的类别(正常或入侵)。
Step1 对自我样本Tself={S1,S2,…,Sm}进行聚类,得到自我集的s个聚类。
Step2 根据式(2)、式(3)计算每个自我聚类的中心Sci及识别半径。
Step3 for (每个非我NSj∈nonself)计算非我与自我聚类中心的距离D=DNSj-Sci根据距离D进行克隆变异,生成一定数目的抗体。
Step4 根据式(4)计算抗体的识别半径。
Step5 计算距离D=Dx-Sci及Dx-Abj,若D<R(Sci),则x的类别标记为正常;若D<Abj.radious,则x的类别标记为入侵。x进入相应的聚类,更新其中心及半径。
Step6 若仍未能判断所属类别,则调用K-近邻法,采用投票机制决定x所属类别。
Step7 经过Step5、Step6,依然无法判断x所属类别,则产生一新的类别,同时产生能识别该抗原的抗体。
Step8 重复Step5～Step7直到未知样本集U为空。
Step1～Step4为抗体产生阶段,Step5～Step8为入侵检测阶段。检测过程中对初始未能正常识别的抗原采用了投票方法,增大了其被识别的概率,同时也可发现新的类别。
3 仿真实验及结果分析
实验数据选用KDD99数据集,该数据库由大量真实的正常和攻击网络连接数据组成,每个连接数据是一个42维向量,前41维代表连接数据的特征,最后一维表示该连接所属的类别。
从KDD99数据集中随机抽取 10 000条网络数据记录,对其中200条数据(包含正样本和负样本)进行标记,作为初始的已标记样本集。为便于比较,候选抗体的产生都是直接将负样本作为候选抗体,所不同的是经历的阴性选择方式不同。
SCIID算法中抗体产生阶段对自我集进行了聚类操作,抗体的识别半径据此得出,由此会大大减少计算量。在检测阶段,SCIID算法对无法准确判断类别的抗原增加了投票机制。检测过程中调用的K-近邻算法中设置K为50,取10次运行算法所得到结果的平均值作为检测结果。
实验一 SCIID算法与单纯的基于免疫的算法的比较
图1、图2给出了SCIID算法的检测率与误检率,并与单纯的基于免疫的算法进行了比较,结果如图1、图2所示。
从图1、图2中可看出,已标记样本数目越多,自我聚类越精确,越能反应出当前网络状况,生成的抗体拟合自我的可能性越小,抗体的质量越高,故误检率较低,检测率较高。SCIID算法对暂时无法判断其类别的新来抗原,增加了一种投票机制,增大了新抗原被识别的概率,故检测率高于单纯基于免疫的算法。
实验二 已标记样本中正负样本的比例对检测结果的影响
该实验测试已标记样本中正负样本比例对检测结果的影响,结果如图3所示。从图3可看出,正负样本比例越大,正样本越多,生成的自我聚类越能反映当前网络状况,由此产生的抗体拟合自我的可能性越小,误判率越低。正样本如果很少的话,不能准确反映正常网络状况,会使产生的抗体覆盖的范围过大,容易造成误判,故误判率较高。
实验三 SCIID算法对已知和未知入侵的检出率比较
已知入侵指的是在训练样本和测试样本中都包含的入侵,未知入侵指的是在训练样本中不包含而在测试样本中新加入的入侵,该实验主要测试SCIID算法对未知入侵的检测程度,结果如图4所示。
从图4可看出,在已标记样本数目一定的情况下,SCIID算法对已知入侵的检出率要高一些,达到了83%以上,对未知入侵的检出率稍低一些,但都在60%以上,可见SCIID算法能发现新的攻击类型。
4 结 语
本文针对通常的入侵检测系统中需要大量的标记数据,而网络环境下获得足够的标记数据比较困难这一问题,将成熟的聚类技术与免疫方法结合起来,提出了一种基于半监督聚类技术的免疫入侵检测算法SCIID,并给出了算法描述。在抗体生成阶段及更新阶段利用聚类技术大大减少了计算量,在入侵检测阶段利用聚类技术可快速获取未标记数据的类别。将SCIID算法与单纯基于免疫的算法在检测率与误检率方面以进行了比较,并专门测试了SCIID算法对未知入侵的检测程度。实验结果表明,SCIID算法具有更优的检测性能,同时实现了利用少量的标记数据来获得大多数未标记数据的类别,而且能发现新的攻击类型。该算法为实现海量数据的入侵检测提供了一种新思路。
摘要：传统的基于免疫的入侵检测系统需要足够的标记数据才能够生成具有良好泛化性能的抗体,而网络环境中获得充足的标记数据是困难的。为克服这一难题,对无监督聚类技术及免疫方法进行深入研究,并将二者结合起来,提出一种半监督的免疫入侵检测算法SCIID(Semi-supervised cluster based Immune Intrusion Detection)。在抗体产生阶段通过对自我样本进行聚类,大大缩短了阴性选择的时间;在入侵检测阶段采用聚类技术可快速获取未标记数据的类别,进而指导后续的学习过程,达到提高检测率的目的。仿真结果表明,该算法在仅有少量标记数据的情况下,可以获得大部分未标记数据的类别,而且能发现新的攻击类型,同等训练样例数目条件下检测率高于单纯基于免疫的方法。
关键词：半监督,聚类,人工免疫,入侵检测,检测子
参考文献
[1]Junqwon K,Bentley P J.Towards an artificial immune system for net-work intrusion detection:an investigation of clonal selection with a neg-ative selection operator[C]//Proceedings of the Congress on Evolu-tionary Computation(CEC-2001).Seoul,South Korea:IEEE Press,2001:244-1252.
[2]Kim J,Bentley P,Aickelin U,et al.Immune system approaches to in-trusion detection-a review[J].Natural Computing,Springer,2007,6(4):413-466.
[3]Laurentys C A,Ronacher G,Palhares R M,et al.Design of an artificialimmune system for fault detection:A negative selection approach[J].Expert Systems with Applications,2010,37(7):5507-5513.
[4]Dipankar D,Fabio G.An immunity-based technique to characterize in-trusions in computer networks[J].IEEE Transactions on EvolutionaryComputation,2002,6(3):281-291.
[5]Wagstaff K,Cardie C,Rogers S,et al.Constrained k-means clusteringwith background knowledge[C]//Proceedings of International Confer-ence on Machine Learning,San Francisco,USA,2001.
[6]李昆仑,曹铮,曹丽苹,等.半监督聚类的若干新进展[J].模式识别与人工智能,2009,22(5):735-742.
[7]Zhong S.Semi-supervised model based document clustering:a compara-tive study[J].Machine Learning,2006,65(1):3-29.
[8]Chapelle O,Scholkopf B,Zien A.Semi-supervised learning[M].Cam-bridge,Mass:MIT Press,2006.
[9]Zhou Z H,Li M.Semi-supervised regression with co-training style algo-rithms[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(11):1479-1493.
[10]Pedrycz W,Waletzky J.Fuzzy clustering with partial supervision[J].IEEE Trans on Systems,Man,and Cybernetics,Part B,1997,27(5):787-795.
人工免疫聚类 篇4
聚类分析[2,3]是多元统计分析的一种，也是非监督模式识别的一个重要分支，它把一个没有类别标记的样本集按某种准则划分成若干个问题子集，使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同的类中。聚类分析的研究过程中，出现了一批经典的聚类算法，如k-means聚类算法、FCM聚类算法等。随着聚类算法对相关数据进行聚类时，聚类中心在迭代的过程中很容易陷入局部极值点，而无法发现该类型数据集的正确聚类，因此，对聚类算法可靠性，稳定性方面亟待加强。人工免疫系统[4]是借助高等脊椎动物免疫机理及医学免疫学原理建立和发展一种新颖、有效的现代计算智能方法，并已成功的应用于解决工程实际中的复杂问题。如组合优化问题，数值优化，智能控制等。
本文提出了一种免疫克隆选择聚类算法的TSP问题求解，本文针对大规模TSP问题，利用K均值动态聚类法对TSP进行邻域分区，免疫克隆选择算法对群内细分的TSP进行精确优化，后根据K重心邻域连接方法进行全局连接以快速得到大规模TSP问题满意解。实验结果表明文中提出的算法是有效的，可行的。
1 免疫聚类克隆选择算法
1.1 K-means算法的数学思想
K_means算法[5]的核心思想如下：算法把n个向量xj(1,2…,n)分为c个组Gi(i=1,2,…,c)，并求每组的聚类中心，使得非相似性(或距离)指标的价值函数(或目标函数)达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时，价值函数可定义为：
这里是组i内的价值函数。这样Ji的值依赖于Gi的几何特性和ci的位置。
一般来说，可用一个通用距离函数d(xk,ci)代替组I中的向量xk，则相应的总价值函数可表示为：
为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为(1)式。划分过的组一般用一个c×n的二维隶属矩阵U来定义。如果第j个数据点xj属于组i，则U中的元素uij为1;否则，该元素取0。一旦确定聚类中心ci，可导出如下使式(1)最小uij:
重申一点，如果ci是xj的最近的聚类中心，那么xj属于组i。由于一个给定数据只能属于一个组，所以隶属矩阵U具有如下性质：
且
另一方面，如果固定uij则使(1)式最小的最佳聚类中心就是组I中所有向量的均值：
这里|Gi|是Gi的规模或。
1.2 K-means算法步骤
1)从n个数据对象任意选择k个对象作为初始聚类中心;
2)循环(3)到(4)直到每个聚类不再发生变化为止
3)根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;
4)重新计算每个(有变化)聚类的均值(中心对象)。
1.3 免疫克隆选择算法
1958年，Burnet等人最先提出了克隆选择学说，其核心思想为：抗体是天然产物，以受体的形式存在于细胞表面，抗原可与之选择性地反应。抗原与相应抗体受体相互刺激可导致细胞克隆性增殖。该群体具有相同的抗体特异性，其中某些细胞克隆分化为抗体生成细胞，另一些形成免疫记忆细胞以参加以后的再次免疫应答。在此过程中，主要借助克隆使其激活、分化和增殖，以增加抗体的数量，通过进行免疫应答最终清除体内抗原。因此，克隆选择是生物免疫系统自适应抗原刺激的动态过程，在这一过程中所体现出的学习、记忆、抗体多样性等生物特征，正是人工免疫计算所借鉴的。根据Burnet的抗体克隆选择学说，De Castro以及Kim等人从不同的角度模拟上述生物学抗体克隆选择机理，相继提出了不同的克隆选择算法模型[6]。并给出De Castro提出的基本克隆选择算法流程。如图1所示。
1)首先生成候选解P,P是有记忆单元(M)和保留种群(Pr)组成，即：P=Pr+M;
2)根据亲和度计算，选择n个个体(Pn);
3)复制(克隆)种群中n个最好的个体，生成一个克隆临时种群(C)，克隆规模和抗体—抗原的亲和度成正比;
4)对克隆临时种群进行高频变异，这里高频变异和抗体，抗原的亲和度相对应，由此获得了一个变异后的抗体群(C*);
5)从C*中重新选择改进的个体组成记忆单元M.P中的一些个体也被C*中其他改进的个体所取代;
6)利用新产生的抗体代替d个旧抗体(引入多样性)，亲和度低抗体更容易被取代。
1.4 免疫聚类克隆选择算法流程
图2为算法流程图。
2 实验测试
实验仿真环境：windows XP系统，AMD处理器，1.90GHZ 448MB内存，仿真软件MATLAB 7.0。
2.1 数据仿真测试
运行结果(初始为聚3类，可自定义)及仿真数据源如图3，一共有32个坐标对象。
运行之后输出聚类结果如图4。
由仿真图形4可以看出可以看出其中第一类有11个对象，第二类14个对象，第三类7个对象，合计32个对象。图4画出了中心点，坐标依次为C1(2.6364,1.9091),C2(6.0714,5.8571),C3(12.143,1.429)。
2.2 TSP实例测试
为了验证本文算法的有效性性，采用国际上用的TSP测试实例库。
实例一：对ch130(城市规模130)进行10次操作，抗体种群规模m=130，输入重心点为4。本文算法获得最优值一次6110.8438，得到的最优数据优于TSPLIB提供的最优路径长度6110.9最大值为6238.8255，平均值6183.1417，偏离最优值的误差为0.0118。
实例二：对tsp202(城市规模202)进行10次测试，抗体种群规模m=202，输入重心点为4。根据本算法获得。得到最大值为496.9347，最优值489.8321。得到的最优数据优于TSPLIB提供的最优路径长度490.67，得到平均值为493.2675。
表1中平均百分误差
其中STi是第i次的最短路径，S0是已知最短路径。NGA与IDIA的求解数据均来自文献[7]。
3 小结
本章提出了一种面向组合优化经典NP难TSP问题的免疫聚类克隆选择算法，针对大规模TSP问题，利用K均值动态聚类法对TSP进行邻域分区，免疫克隆选择算法对群内细分的TSP问题进行局部精确优化，后根据K重心邻域连接方法进行全局连接以快速得到大规模TSP问题满意解。通过实验仿真可知，大部分结果优于或接近标准TSPLIB提供的已知最优路径距离S0，全局搜索能力更强，收敛速度更快。
参考文献
[1]Michalewicz Z,Fogel D.How toSolve It:Modern Heuristics[M].Berlin,Germany:Springer-Ver-lag,2000.
[2]LeFevre K,DeWitt D,Ramakrishnan R.Mondrian multidimensional k-anonymity[C]//Liu L,Reuter A,Whang KY,Zhang JJ,et al.Proc of the22nd Int'l Conf.on Data Engineering.Los Alamitos:IEEE Computer Society,2006.
[3]戴东波,汤春蕾,熊赟.基于整体和局部相似性的序列聚类算法[J].软件学报,2010,21(4):702-717.
[4]戚玉涛,刘芳,焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报,2008,19(6):1265-1273.
[5]汪中,刘贵全,陈恩红.一种优化初始中心点的K-means算法[J].模式识别与人工智能,2009,22(2):299-304.
[6]De Castro L N,Zuben F J V.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Com-putation,2002,6(1):239-251.
人工免疫聚类 篇5
1 零件设计参数聚类分析
零部件的设计参数信息可通过直线的方式来表达, 如果将规约为“线”的设计参数作为聚类原型, 则可通过对聚类原型的聚类分析来完成零部件的设计缺陷辨识。
令S={S1, S2, …, Sn}表示n个零件的数据集, Si=[li1, li2, …, lim]T为第i个零件的m个设计参数值, 将n个零件数据集划分为满足k种设计要求的子集, 从而判断出各子集中设计的优差。将零件设计参数中的“线”作为聚类原型, 如果已知一直线l1上的两点v1, v2与一直线l2上的两点v3, v4, 则可通过计算两直线之间的距离及两直线的方向矢量的点乘来验证设计参数之间关系, 其计算式为
式中:dl1, l2分别为l1到l2的距离, τ0=阈值, 如果验证两直线的同轴度, 则τ0=0, 如果验证平行度, 则τ0=设计值, ni为方向矢量, α为两直线夹角。
如果将零件设计参数用直线上点来表示, 则Si=[li1, li2, …, lim]T可写成m维的直线向量Si=[ (v11, v21) , (v12, v22) , …, (v1m, v2m) ]T, 将式 (1) 、式 (2) 作为约束条件, 零件设计参数聚类分析的目标函数定义为
式中:S为样本;μ为S的划分矩阵;V为聚类原型;d2ij为零件i第k维直线与零件j第k维直线的距离;vik为第i个零件第k维直线上的点;nij为单位方向向量。
由式 (3) 计算得到, <vik-vjk, nij>为2个向量的内积, μ2ij为第i个零件对第j个样本的隶属度函数, 其满足以下条件
式中:为第i零件距离第j个聚类中心的距离, k为聚类中心个数, 随着d2ij的增大, 第i零件属于第j类的可能性降低。
如果不可规约为线性关系的设计参数也作为聚类原型, 则零件设计参数的聚类分析将转化为具有混合数据特征集的聚类分析, 对于非线性设计参数的目标函数定义为
式中:plj为第j个零件的第l维非线性设计参数值, l取值从t+1开始, 前t个为线性数据, t+1后为非线性数据, xlc为第c个聚类中心的第l维非线性设计参数值, τlc为第c个球壳的半径值。
综合考虑零件设计参数之间的线性与非线性约束关系, 零件i种方案对应的设计参数可写为, 将式 (4) 与式 (7) 合并可得到混合数据类型集的目标函数为
式中:d2si, sjΣΣ为相异性测度, 当d2si, sjΣΣ取最小时, 得到n个零件的最优划分。
2 零件设计参数的免疫聚类算法
为了避免分析结果为局部最优解, 文中采用免疫聚类算法对设计参数进行优化, 并通过设定阈值来剔除那些较差的设计, 因此需求解下式
式中:τij, τlj为零件设计参数的阈值, α为零件的第i条直线单位方向向量与聚类中心第j条直线的单位方向向量容许的最小夹角, 如果验证垂直度, α的取值为90°, 验证平行度与同轴度为0°或180°。
依据式 (10) 可知零件的设计参数目标函数越小, 聚类效果越优, 零件设计参数的亲和度函数定义为
零件设计参数的设计缺陷免疫聚类算法步骤。
1) 将零件设计参数编码为具有M维基因段的抗体, 将设计的N个零件组成原始抗体库, 设定交叉概率pc, 变异概率pm, 死亡概率pd, 算法终止条件SC;
2) 依据式 (12) 计算亲和度值, 选择值较大的抗体进行克隆操作, 被选中进行克隆概率为
式中:fSi为抗体群中第i个抗体的亲和度值;为所有抗体的亲和度值的均值;fmax为抗体库中最大的亲和度值。
本文只将亲和度值较大的抗体进行克隆操作, 亲和度值较小将作为死亡个体, 克隆后的抗体组成子代抗体群, 克隆的规模为
式中:Nc为亲和度值大于的抗体的数量;IntΣxΣ为大于x的最小整数。
3) 以pc对亲和度值较大抗体的线性基因位与非线性基因位进行交叉, 基因交叉不破坏原有的抗体基因结构, 交叉操作如下
4) 以Pm对抗体进行变异操作, 变异操作只对非线性设计参数基因位有效, 由于多数标准件的参数为整数, 与其配合的轴径也应取整数, 因此采用取整的规则对非线性设计参数进行变异操作。
5) 计算所有抗体与聚类中心的亲和度值, 将值较小的抗体以概率pd执行死亡操作, 并将死亡的抗体并入死亡抗体库, 抗体的死亡操作如下
式中:pd为抗体的死亡概率, S'i为第i个抗体, T0为聚类中心, 为抗体与抗原的相异性测度, 由式 (10) 计算得到, dτ为约定的阈值。
6) 由步骤2到4产生的子代抗体取代父代, 保持原始抗体的数目不变。如果SC不满足, 返回步骤2;如果满足, 则停止聚类。
3 结论
将具有不同类型的设计参数统一编码, 利用抗原与抗体基因变异的特性实现了机械产品设计缺陷的辨识, 提出了新的交叉变异方法, 使抗体的各基因位达到最优。
参考文献
[1]毕锦烟, 李巍华.基于半监督模糊核聚类的齿轮箱离群检测方法[J].机械工程学报, 2009, 45 (10) :48-52.
[2]徐超, 张培林.基于改进半监督模糊C-均值聚类的发动机磨损故障诊断[J].机械工程学报, 2011, 47 (17) :55-60
人工免疫聚类 篇6
水环境质量评价作为环境质量评价的重要组成部分, 是进行环境管理决策的依据。目前, 海洋环境部门采用较多的仍是单项因子评价法。单项因子评价法对于有针对的治污具有清晰明了的优势, 却很难反映不同海域的整体水质状况。综合评价法体现各个评价因子对水质的整体影响程度。目前, 水质综合评价主要有综合指数法、多因子综合评价法、属性识别法、模糊数学法、灰色理论法和人工神经网络法等。考虑到在环境质量评价中, 有限的时空监测数据所提供的信息是不完全的, 污染物与环境之间存在着复杂多变的联系, 这种联系往往带有一定的不确定性, 实际上构成了灰色系统的基本特征。本文主要采用灰色聚类法和具有很强的非线性映射能力和并行性、自适应、容错性及自学习能力的人工神经网络分别对水质进行评价, 将两种方法做一比较。
2 改进的灰色聚类法
灰色聚类法自创立以来广泛应用于环境评价的各个领域, 发展较为成熟, 模型具有数据分辨力高的优点, 在多因子的综合评价中有独到的优势。经典的灰色聚类法采用直线型白化函数, 使得某些数值权重为零, 这是明显不合理的[1], 本文采用改进的灰色聚类法进行计算。
2.1 水质聚类样本的构成
设有k个样本 (测点) k=1, 2, …m, 且各有i个指标 (污染物) i=1, 1, 2, …n, 每个指标有j个灰类 (环境质量等级) , 则由k个样本的i个指标的白化数构成矩阵为C= (Cki) m×n。
2.2 数据的标准化处理
为了对各样本指标进行综合分析和使聚类结果具有可比性。首先要对给出的白化函数和灰类进行无量纲处理, 本文采用标准化处理, 对于数值越大污染越严重的污染因子计算公式如下:
式中:dki为第k个样本第i个指标的标准化值;Cki为第k个样本第i个指标的实测值;Coi为第i个指标 (污染因子的) 参考标准, 本文取二类海水水质标准对于数值越大水质越好的因子如溶解氧, 则采用标准值比实测值。
2.3 灰类的标准化处理
为了使原始白化数与灰类之间比较分析, 仍用Coi进行灰类的无量纲化处理, 具体如下:
rij第i个指标第j个灰类Sij的标准化处理值;Sij指标灰数;Coi第i个指标 (污染因子的) 参考标准。
2.4 白化函数的确定
白化函数反映了聚类指标对灰类的亲疏关系, 经典的灰色聚类法采用直线型白化函数, 导致某些数值的权重为零。本文采用指数型白化函数[2], 从而使得任意一个实际监测数据与某等级的一个非零权重值之间存在一一对应, 更全面地体现了因子的影响作用。对于第i个指标第j个灰类可以用白化函数曲线或关系式表达 (图1) 。各个指标的白化值分别对j个灰类的亲疏关系如下。
i个指标灰类1的白化函数为:
i个指标灰类j (2≤j≤h-1) 的白化函数为:
第i个指标灰类j=h的白化函数为:
2.5 求聚类权
聚类是衡量各个指标同一灰类的权重, 其计算公式如下:
式中:wij是第i个指标对j个灰类的权值;rij是第i个指标对j个灰类的标准化处理值。
2.6 求聚类系数
聚类系数通过灰数白化函数的生成而得到, 反映了聚类样本对灰类的亲疏程度。设有k个样本, 每个样本分别对j个灰类的聚类系数用εkj表示, 计算公式如下:
εkj是第k个样本对j个灰类的聚类系数;fij (dki) 第k个样本对i个指标的第j个灰类的白化函数。
3 BP神经网络法
环境质量评价本质上属于模式识别, 这正是ANN的特长所在。对某区域的水环境质量的综合评价一般涉及到较多的评价因素, 且各因素与区域环境整体质量关系复杂。而在建模过程中BP网络本身存在收敛速度慢, 目标函数存在局部极小点的情况, 这些问题一般通过附加动量项和变速率学习的方法来解决 (图2) 。
3.1 样本数据的输入与输出
BP网络的水质评价不同于一般的预测的主要问题在于预测一般都有较长的样本, 而水质评价的样本主要来源于水质标准。对于海水水质标准四个等级来说, 只有四个样本。用四个样本训练出来的模型去评价复杂多变的水质状况, 显然不合理。本文通过采用matlab中unifrnd函数随机生成样本的方法在每个因子水质标准等级之间增加50例样本。增加的200例样本和水质标准共204个样本共同构成训练样本 (表1) , 将训练样本和待评价样本用下式进行初始化。
考虑到sigmoid函数的线性映射范围为0~1, 为了避免极值处微分为0, 将样本的初始化在[0.1 0.9]之间。输出值为相应的水质标准, Ⅰ、Ⅱ、Ⅲ、Ⅳ类水分对应输出值为0.2、0.4、0.6、0.8。
3.2 网络拓扑结构的确定
选择输入层-隐含层-输出层的结构, 输入层节点数为5个评价因子, 输出层节点数为1, 隐含层节点数的选择采用黄金分割试验点法确定。即若神经网络的输入层和输出层的节点数分别为I和J, 则理想的隐含层节点数L一般在如下范围:
在[a, b]范围内分别以取g1=0.618× (b-a) +a和g2=0.382× (b-a) +a, 若g1节点时网络输出误差小于g2节点的网络输出误差则舍去[a, g2) , 留下[g2, b], 反之留下[a, g1], 若g1、g2节点的网络输出误差一样, 则留下[g1, g2]。在[g1, g2]区间内重复上述步骤, 直到确定最优节点[7]。依次记录a, b, g1, g2……的网络输出误差, 取输出误差最小的节点数, 确定模型结构为7层。
3.3 网络训练参数的确定
BP人工神经网络所采用的算法是LevenbergMarquardt动量项法 (即L-M法) 来实现。输入层与隐含层之间采用tansig型传递函数, 隐含层和输出层之间选用logsig函数。最大循环次数1000次, 目标误差0.001, 动量常数0.001, 学习速率0.1。
3.4 模型的检验
为了对所建立的BP神经网络模型进行检验, 采用随机生成几个样本, 对样本进行评价 (表2) 。
经过插值扩充训练样本后, 增加了训练样本的连续性, 网络变得更为稳定, 评价结果表明, 网络已经充分对样本进行了学习。
4 两种方法的结果对比
参照GB3097-1997《海水水质标准》, 分别采用灰色聚类法和BP人工神经网络对表3中的水质进行评价, 评价结果见表3。
mg/L
通过随机生成训练样本的方式大大缩短了网络训练的时间。由评价结果 (表4) 表明改进的灰色聚类法和BP神经网络的评价并不完全符合。改进的灰色聚类法白化函数的确定对评价结果影响较大。BP网络其评价结果直接取决于网络训练的好坏, 通常来说样本越多代表性越好训练出的网络越好。
5 结语
灰色聚类法经过长时间的发展较为成熟, 其不足之处在于庞大的计算量, 并且白化函数的选择具有一定的主观性。灰色聚类法概念明确, 并不要求有庞大的样本来支持, 适合于环境评价的各个领域。近年来改进的灰色聚类法较多, 主要都是对白化函数的改进。不同的白化函数导致不同的评价结果, 但是确定白化函数的聚类模型其评价结果的稳定性是BP网络所难以媲及的。
BP神经网络的计算通过程序或软件实现, 工作量相对较小。神经网络具有很强的非线性映射能力和并行性、自适应、容错性及自学习能力, 特别适用于解决因果关系复杂的非确定性推理、判断、预测和分类等问题。水质评价方式看似和一般的预测一样, 其实不然。由于预测允许一定的误差, 是估计未发生的状况, 而评价则是对发生的状况的判别, 要求有一定的稳定性及统一的标准。此外, 即使确定了最优BP神经网络在做评价过程中仍然会遇到如下问题。
(1) 通过随机生成样本, 使样本容量和样本的连续性都有增加, 大大缩短了训练时间。但是随机增加的样本单个评价因子严格满足各级水质标准, 对于复杂多样的水质状况来说, 并没有很好的代表性。
(2) 网络的泛化能力和预测能力仍然存在矛盾, 通过最小误差确定的的网络仅仅是达到了对样本的最优拟合, 评价的结果未必最优。
(3) 网络结构和误差的大小的人为规定的, 致使BP神经网络的评价结果仍然存在一定的主观性。
摘要：探讨了两种水质综合评价方法:改进的灰色聚类法和人工神经网络法。通过采用增加训练样本和黄金分割的隐含层节点优化算法建立了人工神经网络模型, 将两种水质综合评价方法进行了比较, 结果表明:改进的灰色聚类法计算量较大, 主观性较强, 评价结果稳定。BP人工神经网络进行水质综合评价具有客观性, 但网络训练较为繁琐, 通过插值生成训练样本, 极大地增强了网络的稳定性。但扩充后的训练样本, 不能代表复杂的水质实况, 使评价结果受到一定影响。
关键词：灰色聚类,人工神经网络,水质,评价
参考文献
[1]孟宪林.灰色理论在环境质量评价中的应用与完善[J].哈尔滨工业大学学报, 2002, 34 (5) :700～702.
[2]徐卫国, 张清宇.基于修正灰色聚类模型计算污染物排放阈值[J].生物数学学报, 2007, 22 (1) :164～170.
[3]刘金生, 周焕银, 刘金辉.基于BP神经网络的抚河水环境质量评价研究[J].东华理工大学学报:自然科学版, 2008 (1) .
[4]蒋佰权, 王万森, 温香彩.改进算法的BP神经网络水质评价模型[J].计算机系统应用, 2007 (9) .
[5]娄申, 干晓蓉.基于BP神经网络的水质评价[J].中南民族大学学报:自然科学版, 2007 (2) .
[6]刘坤, 刘贤赵, 李希国, 等.模糊概率神经网络模型在水质评价中的应用[J].水文, 2007 (1) .
[7]夏克文, 李昌彪, 沈钧毅.前向神经网络隐含层节点数的一种优化算法[]J.计算机科学, 2005 (10) .
[8]邹志红, 王学良.基于随机样本的BP模型在水质评价中的应用[J].环境工程, 2007 (1) .
[9]劳期团.灰色聚类法在海水水质评价中的应用[M].北京, 中国环境出版社, 1994:63～75.
人工免疫聚类 篇7
中医舌诊因其在疾病的诊断和治疗中的显著作用,在临床医学和生物医学上引起了广泛的关注和重视。但是,舌诊也有其自身不可避免的缺点,这些缺点阻碍了舌诊的应用和发展。如舌诊的临床诊断能力取决于医生的知识和经验,诊断结果依赖医生的主观分析,因此,诊断结果往往因人而异等。将现代计算机技术与舌诊相结合,提取并分析舌象特征参数,从而实现诊断的自动化具有非常重要的现实意义[1]。实现中医舌诊诊断的自动化包括舌图像的特征参数的提取和根据舌象特征参数进行辨识两个方面。本文介绍用神经网络方法实现舌象特征参数的辨识。为提高神经网络的学习速度和泛化能力,本文构建的中医舌诊智能诊断系统采用了一种改进的基于免疫聚类的RBF神经网络学习算法,通过将每个病例的舌象特征参数作为训练样本集进行学习,从而得出相应病证。
1 舌象识别的神经网络模型
图1是构建中医舌诊智能诊断系统的神经网络模型。模型前端部分为输入样本的“数据归一化”处理。后端部分为给出识别结果部分。它是根据输出层各节点的输出值,利用最大值准则给出识别结果,即哪类节点的输出值最大则相应的输出为1,其它节点相应的输出为0。模型中的中间部分是改进的基于免疫聚类的RBF神经网络,分为二个阶段,第一阶段用人工免疫聚类算法来确定RBF网络隐层的聚类中心C的位置和数量。第二阶段对输入样本集进行学习、训练,求出输出层的权值W。
1.1 数据归一化处理
将样本数据转化在区间[-1,1]之间,可避免出现“奇异输入样本”,可使网络的权值和阈值在较短的时间内易于修改,并有足够的变化量[2]。对于数值变量,采用比例归一法,如式(1)。对于定性变量,先依次编号,再采用比例归一法进行转换[3]。如表1中证型包括正常、肝瘀痰阻、气虚血瘀、气滞血瘀、湿热瘀滞五种,可相应转化为-1,-0.5,0,0.5,1。
式中,x为原始数据,xmin、xmax分别为原始数据中的最小值与最大值,x*为归一化后的数据。
1.2 改进的基于免疫聚类的RBF神经网络学习算法
RBF网络即径向基函数神经网络,它具有全局逼近性质,且不存在局部最小问题,计算量小,学习速度快等优点,已经广泛应用于模式分类、系统辩识、函数逼近等[4]方面。基于聚类分析的RBF神经网络能够克服以往RBF网络存在的学习训练的难题:高维数据问题。因此,基于聚类分析的RBF网络可用于大数据、多样本、无明确函数关系的复杂问题。
在基于人工免疫原理的聚类分析中,把要分类的数据对象视为抗原,把聚类中心看作是免疫系统中的抗体,数据对象的聚类过程就是免疫系统不断地产生抗体,识别抗原,最后产生了可以捕获抗原的最佳抗体过程[5,6]。
改进的免疫聚类算法的思路:每个抗体能识别其临近空间的抗原,即抗原能否被抗体识别,就看其两者的亲和力是否大于某个阈值,大于则说明识别成功,否则,选择其最优的抗体,克隆N个,根据式(2)进行变异,得到新的抗体集:
c′k=ck-βk(ck-xi) k=1,2,…,N (2)
式中,βk为变异率。
这一过程实际在最大亲和力的数据中心附近进行搜寻,以得到可能更优的中心。再在新抗体集中择其最优的抗体进行识别。还是不能成功识别,则再选择其最优抗体克隆、变异、择优识别……循环K次,还是不能识别,则直接将抗原作为一个新的抗体。直到学习完所有的输入样本集,免疫聚类算法结束。
算法详细描述如下:
Step1 以一个确定数量N随机或根据已有经验初始化聚类中心集合C。
Step2 对于每一个样本xi,
1) 计算xi与C中所有中心的亲和力;
2) 如果亲和力最大值大于等于阈值。
则:转Step3,否则:
(a) 克隆:将与xi亲和力最大的中心克隆N个放入C′中;
(b) 变异:对C′中N个相同数据中心根据式(2)进行变异;
(c) 重新计算xi与C′中所有数据中心的亲和力;
(d) 选择与xi亲和力最大值aij,其对应的聚类中心c′j ;
(e) 如果 aij>ρ (阈值),则:
①将中心c′j 作为一个新的聚类中心,添加到C中;
②更新N,C的中心数量N加1,转Step3。
否则: 如果循环次数小于K次,
则:转(a),否则:
①将xi作为一个新的聚类中心,添加到C中;
②更新N,C的中心数量N加1,转Step3。
Step3 判断输入数据是否全部学习完,未完,转Step2。
Step4C为所求的聚类中心,N为聚类中心的数量。
Step5 构建RBF网络,计算权值矩阵。聚类中心C为RBF的“基”,聚类中心数N为隐层节点数,样本分类数为输出层节点数。
2 实 验
以肝病病证诊断进行仿真,采用上述算法,建立基于免疫聚类的RBF网络中医舌诊智能诊断模型。
将每一个病例的舌象特征参数作为一个输入样本。选取4类病证共200例舌象特征参数的样本数据作样本集。每个样本包括证型、舌象、主干形态、主干充盈度、质红、质绿、质蓝、舌下R、舌下G、舌下B等33项舌象特征参数作为输入样本的属性。样本数据分四类为:正常50例,肝癌50例,肝硬化50例,乙肝50例。
对于4类病证各取30例数据共120例数据作为训练样本,最后用80例数据进行测试。
首先对200例数据进行数据归一化处理,将所有数据的值转化在[-1,1]之间[3]。
采用Visual C++作为开发平台,基于上述的学习算法,经第一阶段人工免疫算法的训练,120例训练样本被分为32组,产生32个聚类中心,其中,阈值ρ=0.3,变异率用(2)式计算。即隐层节点数可取32个。
因实验结果要求分为4类,输出节点数设为4。输出为(1,0,0,0)、(0,1,0,0)、(0,0,1,0)、(0,0,0,1)分别表示识别为正常、肝癌、肝硬化、乙肝,所以构建基于免疫聚类的RBF学习算法的RBF网络结构为33-32-4结构。
实验运行结果如表2所示。将120例训练样本输入到基于免疫聚类的RBF神经网络进行训练,当训练次数为3923次时,网络的收敛误差为0,程序结束。将80例样本数据进行测试,得到的识别率很高(平均约91%)。其中有某些样本数据不能被正确识别,其原因是由于对舌图像提取特征参数时存在人为造成的误差,致使样本的特征量产生“失真”,影响识别的正确率。因此,从实验结果来看,该模型能有效地学习输入样本数据,对于高维数、大数据能快速地聚类。因此,具有收敛速度快、识别能力较强、泛化能力强等特点。
3 结 论
用一种改进的基于免疫聚类的RBF神经网络构建中医舌诊智能诊断模型。旨在对大数据、高维数样本能快速聚类,以提高收敛速度和确定最优的聚类中心集,保证整个RBF网络具有良好的泛化能力。实验结果表明该模型能有效地学习输入样本数据,对于高维数、大数据样本能快速地聚类。具有诊断能力强、收敛速度快,泛化能力强等特点。
摘要：研究基于人工免疫聚类的RBF(Radial-Basis Function)神经网络应用于中医舌诊诊断,构建一个中医舌诊智能诊断的神经网络模型,旨在提高模型的诊断能力和收敛速度。对输入样本集进行数据归一化处理,采用改进的基于免疫聚类的RBF算法进行学习、训练。以肝病病证诊断进行仿真,结果表明:该中医舌诊智能诊断系统具有诊断能力强、收敛速度快,泛化能力强等特点。因此,基于人工免疫聚类的RBF神经网络应用于中医舌诊诊断的研究是可行的,有效的。
关键词：人工神经网络,舌诊,人工免疫聚类,径向基函数神经网络
参考文献
[1]刘春雨.基于纹理特征的舌象分类研究及应用[D].哈尔滨工业大学,2006.
[2]王炳和,相敬林.基于神经网络方法的人体脉象识别研究[J].西北工业大学学报,2002,20(3):454-457.
[3]冯定.神经网络专家系统[M].北京:科学出版社,2006:66-69.
[4]朱大奇,史慧.人工神经网络原理及应用[M].北京:科学出版社,2006:133-136.
[5]刘韬,王耀才,王致杰.一种基于人工免疫系统的聚类算法[J].计算机工程与设计,2004,5(11):2051-2053.