《1 前言》

1 前言

许多知识发现系统需要从规律性变化的数据中准确挖掘信息。在这样的系统中,无论是频繁的还是偶然的数据更新都有可能改变先前发现的知识或规则的状态。因此,知识的维护和更新就成为知识发现研究中要解决的问题之一。

目前,知识发现研究采用增量更新、数据快照和时间戳等方法对知识进行动态维护和及时更新。以关联规则为例,D. W. Cheung 等研究了一系列维护更新问题[1];何炎祥等在此基础上提出应用抽样技术的算法 SEA[2];冯玉才等提出 IUA /PIUA[3] 算法; 宋余庆、杨明、吉林根等先后提出了几种关联规则更新算法[4 ~6] 。这些算法基于动态库和交互方式,以数据量增加后规则的维护算法居多,这样的动态挖掘算法一般称为增量式挖掘算法。一般来说,增量式数据挖掘的研究是以静态挖掘为基础的。如上述算法其本质都是以 Apriori 算法[7] 为基础,考虑数据库的动态性或者约束条件的改变,以有效减少数据库扫描次数和候选项目集为目标,实现增量式关联规则的更新维护,得到比较精确的结果。

但是这类算法存在几方面问题。一方面,在结果分析上,由于挖掘是在新的时间断面上进行,所以不可避免会造成一次数据中随机因素的增大,对生成或者丢弃的规则和知识产生扰动。另一方面,由于大型数据库中海量数据的出现,使得原来的数据挖掘算法存在实现上的困难。再一方面,虽然在数据库的数据积累过程中,知识库的结构具有一定的稳定性,但它也在随着数据的积累不断变化。因此, 有必要整体考察知识库中的知识随时间动态变化的特点和规律,不再简单地以一次挖掘结果来决定知识的取舍。

根据数据库和知识库动态变化特性,引入免疫进化方法以解决上述问题,因为免疫进化计算适合于直接解决动态问题,其核心思想就是利用进化历史中获得的信息指导搜索或计算。

《2 基于数据增量的动态挖掘进程概念》

2 基于数据增量的动态挖掘进程概念

简单地说,动态数据挖掘是“运动的”挖掘,即在静态挖掘的基础上,动态地考察每次挖掘的结果, 综合给出对知识的评价。实际上,动态数据挖掘就是从知识的演化角度,综合评价知识的类型,给出对知识的取舍。它要求知识发现系统不仅要考虑基于动态数据库的增量式挖掘,而且要考虑基于动态知识库的动态挖掘算法。

在动态数据挖掘中,作为挖掘结果的知识主要受以下几个方面的环境因素影响:a. 动态变化的数据库;b. 动态变化的知识库;c. 动态变化的用户感兴趣度;d. 挖掘相关领域的时空变迁;e. 论域与阈值的变化等,其中最重要的是时变数据、背景知识和用户兴趣。

定义 1 动态数据挖掘的环境空间是 5 元组 Ω = (UV RS T) ,其中,U 表示动态数据库,V 表示动态知识库,R 表示用户感兴趣度论域;S 表示变迁的时空域;T 表示论域与阈值集。

对于时序数据库,数据会随着一定的时间间隔不断地加入数据库。在考虑其增量数据添加后知识发现中的动态挖掘问题时,首先规定一定的时间间隔,对挖掘的数据库 DB 采用如下的分库方案。

方案 1 如果数据库的字段中包含时间属性 T, 则根据 Ti 将数据库逻辑地划分成 n 个 DBi ,使每个 DBiTi 对应。其中,Ti = { tractimei , tractimej }为一时间区间,且满足:如果 i <j,那么 tractimei <tractimejij =1, 2, …,

方案 2 如果数据库的字段中不包含时间属性,那么将数据库 DB 逻辑地分成 n 个 DBi ,满足当 i <j 时,DBi <DBj,且 DBn =DB。

在此分库方案的基础上,提出了动态挖掘进程的概念。

定义 2 基于数据增量的动态挖掘,通过对数据库的划分方案对逻辑子库依据时间顺序不断挖掘知识,综合每次挖掘结果给出对知识的评价过程,称为动态挖掘进程。

动态挖掘进程与增量式挖掘既相互联系又有所区别。一方面,动态挖掘进程融合了增量式挖掘。它不仅依靠增量式挖掘方法实现当前的挖掘,而且要利用每次挖掘结果进行动态分析,剔除不确定因素对数据造成的影响,指导每次挖掘。另一方面,基于数据增量的动态挖掘进程不同于单纯的增量式挖掘。增量式挖掘注重具体算法的研究,在当前挖掘中尽量利用前一次挖掘的结果,使当前挖掘的算法复杂度降低,以求算法的高效性和有效性。而基于数据增量的动态挖掘进程不仅针对变化的数据库, 在每次挖掘时选用具体的增量式挖掘算法,以求得一次挖掘的结果;而且它在对知识的评价运用上,不是依据前一次挖掘的结果,而是根据每一次挖掘结果,综合地历史地对挖掘的规则进行评价。在使用动态挖掘进程进行知识发现时,甚至可以不注重具体的挖掘结果,而通过对知识或者规则的跟踪性研究,使用户挖掘出自己感兴趣的知识。这种历史地、综合地跟踪性研究可以很好地避免一次挖掘中数据的随机因素对挖掘结果造成的干扰。

按照哈肯的协同学思想,如果把每次挖掘的结果看成一个个微观层次的子系统,那么整个动态挖掘进程就是在已有的结果基础上再进一步地给予宏观上的研究,形成整体地对知识或者规则的认识和评价,有效地防止上一次挖掘的结果的不确定性所带来的影响。动态挖掘进程的这种动态性特点使得利用生物系统的免疫进化解决其中问题成为可能。

《3 知识发现中的免疫进化机制内涵》

3 知识发现中的免疫进化机制内涵

《3.1 生物免疫进化过程》

3.1 生物免疫进化过程

在生物免疫系统中,一切免疫反应均源于抗原的入侵。其机理是通过外部抗原的入侵产生免疫应答,引起免疫细胞对抗原的识别,将抗原信息传递给免疫活性细胞;再通过抗体与抗原的匹配(以亲和度度量) ,对抗体进行选择、变异,促使相应抗体的增殖、分化;之后,引起炎症反应,浆细胞合成并分泌抗体,产生体液免疫。生物免疫系统还可以产生免疫记忆,当再次遇到相同抗原分子时能作出迅速反应,给出更快更强的应答。

生物免疫系统的上述特点成为人们解决工程实际问题的灵感来源。基于生物医学研究对自然免疫系统的不同机理的认识,人们设计出许多利用免疫进化机制处理各种问题的方法。 De Castro 和 Von Zoben 开发了基于免疫网络亚动力学的数据分析和数据简化算法[8] ,并检验了免疫系统内克隆选择机制的作用[9] 。该方法继续扩展和应用到数据聚类, 产生了 aiNet 算法。实验表明,把进化人工免疫网络与传统统计方法结合,能够有效实现从数据集中提取有用的信息聚类[10] 。此外,Timmis 提出了一种资源有限人工分类器[11] , 并很好地改进了其效率 [12] 。 J. Twycross 提出了基于免疫阴性选择原理的 Web 文本分类算法[13]

尽管人工免疫系统中的各种模型采用了自然免疫系统的不同机理,但最主要的还是抗原与抗体的亲和作用。对抗体与抗原的亲和作用进行建模几乎在所有的模型和技术中采用。

《3.2 动态挖掘进程与生物免疫进化过程的相似性》

3.2 动态挖掘进程与生物免疫进化过程的相似性

综合分析知识发现的动态挖掘进程,发现它与生物免疫进化过程有很多相似之处。在此,赋予生物免疫系统的基本概念在动态挖掘进程中新的含义。

1) “抗原”对应动态挖掘中新增的数据;

2) “抗体”对应挖掘得到的知识;

3) “记忆库”对应知识库;

4) “免疫细胞的产生”意味着随机产生或从记忆库中提取知识或规则构成初始群体;

5) “抗原与抗体的相遇”意味着新数据到来后知识的演化;

6) “抗体识别抗原”意味着以知识或者规则的相关值作为个体浓度的适应度,进行抗体适应性的评价,其实,这就是抗体对抗原的结合强度;

7) “抗体的繁殖”意味着基于上一步的计算结果对抗体群体进行选择、变异操作得到新群体;

8) “免疫记忆”意味着把与抗原能够很好匹配的抗体作为规则保存到数据库,以备知识展示或者下一次数据到来前生成初始种群。

图 1 说明了生物免疫进化过程与知识发现系统中动态挖掘进程之间的相似性。

《图 1》

图 1 生物免疫进化过程与动态挖掘进程的相似性比较

Fig.1 A comparison between the evolutionary immune process and dynamic mining process

《3.3 知识发现中的免疫进化机制内涵》

3.3 知识发现中的免疫进化机制内涵

综观知识发现的动态挖掘进程与生物免疫进化过程在过程原理上的相似性,并根据实际处理问题的需要, 在基于内在认知机理知识发现理论 KDTICM 中的双库协同机制、双基融合机制、信息扩张机制的基础上[14] ,提出知识发现系统的免疫进化机制,其基本特征的非形式化描述如下:

1)把新增加的数据作为抗原,已有的知识作为抗体,通过抗体对抗原的识别,依据其结合强度的大小,实现抗体的增殖、分化、变异,通过记录知识的持续数,表征知识的衰减和保持;

2) 结合利用双库协同机制中的启发式协调器 [14] ,把常识、用户以及专家知识作为疫苗,实现对抗体的接种,形成定向挖掘,提高抗体的适应性以及获取新的知识的能力;

3)对获得的新规则不急于作为记忆保存,而是先评价,期望去除矛盾知识,但是重复或冗余的知识要记忆,在形成新的应答抽取初始抗体群时,重复的知识被抽取的可能性更大,宜于实现知识库(记忆库)的实时维护和奉行。

针对动态挖掘进程,展开基于免疫进化机制的知识发现系统的研究极具意义。它通过识别新数据,利用历史挖掘的知识及其参数,实现快速有效的挖掘。利用免疫记忆的原理,对以前经常挖掘出的知识,在一次挖掘中不因为其不能满足参数阈值要求就随意抛弃,而是加以保护(但持续数降低) ,这避免了由于数据的随机分布而带来对挖掘结果的过大影响。

《4 应用》

4 应用

为了验证知识发现系统中免疫进化机制在解决实际问题中应用的有效性,以时序模式挖掘为例,进行了相关的实验。

将时序数据挖掘看成是一个动态挖掘进程,即在静态时序挖掘的基础上,动态地考察、综合每次挖掘的结果,给出知识的评价;从知识演化的角度,综合地评价知识的类型,给出对知识的取舍。针对随时间变化的时序数据库,在每次挖掘的时候,选用具体的增量式挖掘算法,求得一次挖掘的结果;并利用每次挖掘结果进行动态分析,剔除不确定因素对数据造成的影响,从而改进挖掘结果,指导每次挖掘。

《4.1 几个定义》

4.1 几个定义

1)规则持续数。

定义 3 对一个规则 R,取 0 <<1,称

为规则 R 相对第 i 个参数的持续数。

规则持续数反映了规则 R 相对第 i 个参数来说能够持续的强度。实际应用中可以根据需要设定的值。由于 0 <<1,所以随着挖掘次数的增加, →0, 说明以前挖掘的结果对现在的影响逐渐减弱。

定义 4 在动态挖掘进程中,如果当前是第 n 次挖掘,那么前 n -1 次挖掘得到的规则持续数定义为

反映了到目前为止,规则应有的持续程度。在考虑知识的传承和淘汰问题时,可以事先设定规则持续度阈值,然后依据持续度阈值,决定规则的持续还是淘汰。

2)知识的编码。免疫进化机制要求对数据及知识进行必要的编码。对抗原抗体采用实数编码的方式。

设事务数据库有 s 个属性,如果记其第 i 个属性为 Xi ,对应的数值域是 Di ,其中 i =1, 2, …, s, 则数据库中一条记录就是一个 s 维向量,其每一维上的分量取值对应于相应属性的数值域。它的一个正则划分数值子域为 , …,,定义一个映射为 jj =1, 2, …, ti

由此映射就可以对一条记录进行如下的编码: 如果这条记录的第 i 个属性取 ,那么其编码的第 i 位就取得 j 值;如果这条记录的第 i 个属性值取空值,则该位置取 0。这样,一条记录其编码的第 i 位就是 0, 1, …,ti 中的某一个确定的值了,即一条记录的编码第 i 位的值域是{0, 1, …,ti } ,记为 Vi ,即 Vi = {0, 1, …,ti } 。

定义 5 称事务数据库 X 对应的所有属性,其对应的编码值域 Vi 的笛卡尔积

为抗原的形态空间。

对于抗体(频繁项目集或者候选项目集) 的编码可以采用同样的编码原则,因为频繁项目集或者候选项目集的长度一般都小于记录的属性个数,这样只要把空缺位置填 0,把项目集对应属性位的值对应于相应的编码就可以得到抗体的编码。

3)抗体与抗原的结合强度和抗体对抗原的刺激水平。计算抗体与抗原的结合强度的一般方法包括:海明空间的海明距离、 Eucilidean 形态空间的 Eucilidean 距离和 Manhattan 形态空间的 Manhattan 距离等。根据知识发现系统的动态挖掘进程的特点,结合上述的抗原、抗体的编码形式,定义抗体、抗原的结合强度如下:

定义 6 如果抗原的编码是 Ag = ( ag1, ag2, …, agL) , 抗体的编码是 Ab = ( ab1,ab2, …, abL) ,取

其中 i =1, 2, …, L,那么,抗体 Ab 与抗原 Ag 的结合强度为

D =1 时,抗体与抗原就是完全匹配的。

定义 7 把对一个抗体与所有抗原的结合强度相加,得到的值称为所有抗原对抗体的刺激水平。刺激水平可以决定对抗体的取舍。

定义 8 假设有两个时间序列 A1 ={ x1 1x1 2 , …, x1 n }和 A2 ={ x2 1x2 2 , …, x2 n } ,其模式分别为 { }和{ } ,如果满足 dA1A2 pc,则称时间序列 A1A2 是在给定误差 pc 允许下的相似时序模式。

相似关系一般应该满足传递性,但上述定义的相似模式不满足传递性,为相似关系的处理带来了不便。另外,考虑到下一步编码的方便,给出了相似模式的改进定义。

定义 9 把 -90°到 90°之间 n 等分。如果一条线段对应的编码等于 i,则它相似于角度 -90°+ 180°/2n +i ×180°/n 对应的模式。如果 2 条线段对应的编码相等,则它们相似。

定义 9 满足相似关系的传递性,即相似于同一模式的 2 个线段,本身也相似,从而具有传递性,为处理相似关系带来方便。该定义也为编码带来方便。编码采用十进制,一个线段模式对应的编码就是它最接近的中心角的编码值,一个序列的模式就可以定义为它的每一个线段对应的编码序列。然后,把要找的候选模式作为抗体,把时间序列对应的窗口序列集中的序列作为抗原,并根据式(4 ) 将抗体与抗原之间的结合强度进一步定义如下:

定义 10 如果抗原的编码是 Ag =(ag1,ag2, …,agL) , 抗体的编码是 Ab = ( ab1,ab2, …,abL) ,取

这里 i =1, 2, …,L,那么,抗体 Ab 与抗原 Ag 的结合强度为

W =1 时,抗体与抗原完全匹配,在计算结合强度时,可以作为该序列的支持度。

《4.2 算法》

4.2 算法

基于免疫进化机制的时序模式发掘算法:

输入 n(把 -90°到 90°等分为 n 份) ;窗口 ;时间序列 A ={ x1x2,……, xn } ;

输出时序模式。

Step1 先由时间序列和窗口 值,得到对应的序列集 Ws) ={ s1s2,…, sn -w +1 } ;

Step2 计算序列集中每一个序列的模式作为抗原 Ag,得到编码;

Step3 随机取若干个抗原作为抗体,产生初始抗体种群 Abs, 放入记忆矩阵 M

Step4 亲和度计算,根据抗原对抗体的刺激水平,计算当前抗原 Ag 和 M 中每个抗体 Ab 的结合强度,统计支持度;

Step5 克隆选择,选择具有高结合强度的抗体进行克隆,规模正比于结合强度;

Step6 抗体成熟度,抗体进行变异,规模反比于结合强度,接种疫苗;

Step7 重新选择:计算每个 Ab 和当前抗原 Ag 的结合强度,重新选择具有较高支持度的抗体,将具有较低支持度的抗体作为当前抗原;

Step8 重复执行 Step5 ~Step7,直到满足规定的执行次数;

Step9 if 第一次计算 then 转 Step11;

Step10 进行抗体抑制,对新出现的支持度超过最小支持度的抗体,到原来数据中进行检查;

Step11 分类记忆结合强度高的抗体,以及抗体持续数;

Step12 展示支持度大于最小支持度的模式;

Step13 监视直到新数据的到来;

Step14 将新数据结合原来的数据,生成新的窗口序列集合 Ws) ={ s1s2,…, sn -w +1 } (抗原) ;

Step15 由记忆抗体集产生新的初始抗体种群 Abs,放入矩阵 M,转入 Step4;

Step16 重复执行 Step4 ~Step15,直到满足结束条件;

Step17 结束。

《4.3 实验分析》

4.3 实验分析

取某股票 8 个月中每天的平均价作为实验数据 (见图 2) 。取 =4, 观察连续 4 天股价的变化形态。取 n =9,允许最大偏差为 20°,支持度取 0.15。

先取 3 个月数据运行程序,分析得到 2 个模式 (见图 3)。模式显示出股价以上涨和调整为主。然后,增加 2 个月的数据,系统很快显示这 2 个模式仍为频繁模式,说明股价仍以上扬为主。又增加 3 个月数据后,系统显示这 2 个模式仍是频繁模式,但是同时出现另外一个下降模式(见图 4)。考虑到下降模式出现较晚,并且其持续度比上升模式持续度较低, 所以总的来说可以认为股价呈现上扬调整的态势。

《图 2》

图 2 某股票 8 个月每天交易的平均价格走势

Fig.2 The average price trend for a certain stock

《图 3》

图 3 第一次、第二次显示模式

Fig.3 Patterns shown at the first and second runtime

《图 4》

图 4 第三次显示模式

Fig.4 Patterns shown at the third runtime

由此可见,基于数据增量的动态挖掘进程利用已有模式及其变异进行发现,不仅可以较快发现新的模式,而且它在对知识的评价运用上,不是依据前一次挖掘的结果,而是根据每一次挖掘结果,综合地历史地对挖掘的规则进行评价。这种历史地综合地跟踪性研究能够避免一次挖掘中数据随机因素对挖掘结果造成的干扰,说明利用免疫进化机制解决动态挖掘问题的方法是有效的。

《5 结语》

5 结语

在阐明数据挖掘中动态挖掘进程与生物免疫进化机制之间相似性的基础上,提出知识发现系统中的免疫进化机制内涵,并通过时序模式挖掘验证了新机制的有效性和先进性。由于生物免疫进化机制是复杂的,所以一般应用系统都是从某一特定角度出发利用它来解决实际工程问题。今后,一方面要继续跟踪生物免疫进化方面的新研究进展,另一方面要扩充和完善现有的知识,发现系统中免疫进化机制的理论基础,将其应用到更多类型的数据挖掘进程中。