从数学规划的角度重新表述了单维布尔型频繁项挖掘问题，利用新定义的加法和数乘及范数运算将其归结为一个非线性0－1规划问题，并利用遗传算法进行求解。在分析频繁项挖掘问题困难原因的基础上，提出了利用原数据库记录确定初始种群的方法，并在IBM公布的ticeval2000数据库上进行了数值实验。实际计算结果表明，该方法一般在几代内即可找到一批长频繁模式。张军:基于遗传算法的频繁项挖掘算法008,44(12)163α)‖顶。冋时,频繁项挖掘问题之所以复杂主要是因为由此非于所有数据记录的子串。但即便这样搜索空间也是非常大的:线性项带来的不对称性:即仝局能够决定局部,但局部不能决如果每条记录的平均长度为l,共有m条记录,则根据定理1定全局。可以知道,整个搜索空间约有m2个元素。n. sup采用FP-增长算法的减小搜索空间的思想,令初始和群中aa= min_sup aa 0a1‖≥ nin slp(5)含有大量的原数据库记录同时为了保让遗传算法收敛到全局lax,‖≥ mun_ sep最优解,仍然加入部分随机产生的均匀分布的初始样本。式(5决定」我们无法从h-1频繁项的信息推测出k频繁初始种样的确定方法:项的信息,而恰恰是前者较后者更容易计算,这是频繁项挖掘(1)确定种样数量N和染色体编码长度n以及原始数据问题困难的根本原因。如果没有很好地解决‖④(x8x)的比例reD,1,令1,=1。数据库Am=(a)m共有m条记录初始种群为CA=(C;)。¨不对称’性,就不可能有非常快速的挖掘算法。(2)如果iP则结束;否则如果;P转(4),否则转(3)4,2初始种群的确定(3)产生随机数e∈[0,1].令c,=4m,=+1,j=j+1,转(2)。先考察在关联规则领域取得大成功的FP算法的构造(4)产生随机0,1上均匀分布向量6=e1e2…e,且e过程,由此推出初始种样的确定方式。FP-增长方法将发现长1e>0.5频繁模式的问题转换成递归地发现·些短模式,然后连按后,·1,2,…n,令e≤05/=1,2,…,m,令+,(2)缀。它通过构造FP树的形式避免了产生大量候选集,并只需实际计算表明,初始种群的选择对整个求解过程有显著的要扫描2次数据库。影响,r值越接近于1,收敛速度越快,但也更容易收敛于局部给定图1(a)的个数据库,构造的FP树如图(b)。最优解。同时,科群数量N显著地影响繁衍的代数,大的种群a df数量可以在很少的儿代里就收敛到最优解。ac ded8 deae:8-1h dna245.区5+-广b 7 d b利用定理2,可以没计出合适的算法使得遗传算法在繁衍b c d代时只访问次数据库A=(an)就能计算出所有个体的2 d b适应度值,从而使整个求解过程访问数据库的次数减少到可以1 c接受的程度(a)数据库(b)FP-树43算法设计图1给定的·个数据库FP-树本文在实现遗传算法时,采取了目前通用的算法结构,其染色体编码、评价函数确定和交叉、变异等操作如上所述。具体可以看到,HP-树实际上把数据库的每个记录依次压入树算法概述如下中,而所有的频繁模式只能是这棵树上的路径,从而只能是数(1)确定编码位数n和迭代最大次数L,生成初始样本空间」据库所有记录的一个子部分。做如下定义:(2)以第3章提到的交叉、变异运算形成新的样本空间。定义4给定两个字符串1和2,1=(n,12,…,wu),2(3)通过式(4)计算各样本的适应度。2)且wg∈{0,1},=1,2,=1,2,…,m,如果有:2≤(4)以转轮盘法选择进行优胜劣汰操作,使适应度大的样}=1,2,…,n,则称:2是1的子串,记作2≤o1本遗传到下一代的样本空间中去定理1令u1=(ln,t,…,l1n)且l1∈{0,1},i=1,2,…,n,(5)判晰最优个体的适应度是否满足条件及迭代次数是否若‖1l‖=l,则v共有2个子串大于L证明只要在v1的所有是1的位上任意取0或1即可形是:转(6成子串,由于|wl‖ll故1共有l位1,从而有2个子串。证毕否:迭代次数累加一次,转(2)。(6)输出最大频繁项和所有频繁项定理2给定数据库Am=:|=a,an,…,a1和0-1字其中第(3)步需要精细设计以达到只访问一次数据库的效果。有了定理2的支持,式(4)的计算可以等价于累计个体与符串x=(x1,2,…,x),若令A=(41,△2,…,△n)且A=数据库记录相比成为子串的次数。可以优化样本适应度函数的0其它1x)有:1(x8x)=|△‖。确定算法x=(-x1,x2,…,(1)令 index=1,Cm=(cn)m为当代种群,m为数据库记录总证明根据定义3容易看出,‖④(x⑧ar)‖表示x这个模数,6=(61,,…,)为各个体的适应度向量。式在数据库A中出现的次数;而根据定义4知,△=1表示1x(2)如果 index>m,转(4);否则转(3)。是数据库第讠条记录的子串,即包含x这个模式(取否是因为(3)读取数据库Aa=(a1)m的第indx条记录,记为 record.x=1表示没有第j项,而a=1表示含有第j项的原因),故|△如果(ηca,-ca,…,-cm)< record则8=+1,i=1,2,…,P。冋样也表示∫x这个模式在数据库A中出现的次数。故有,转(2)。4)对i=1,2,…,P:如果8≥min_s则8=‖(ca,ca,(x区a,)‖=‖△‖。证毕。cm);否则δ=n+B,返回8作为科群所有个体的适应度值。P-増长算法的一个优点就是只扫描2次数据库,这其实是以牺牲内存为代价的,它将整个数据库的信息都压缩到了5计算实例卜P树种。FP-增长算法的另一个优点就是它的搜索空问只限在实际计算中,选用的数据库为1BM公布的 literal21642008,44(12)mpuler Engineering and Applic: (in.计算机工程与应用(数据厍1:含84项,4000个记录)和Tl0I4D100K(数据库2:繁项时,初始种群选择方式对结果影响是极其显著的。含999项,1024个记录)。计算过程在如下平台上实现: IntelBest: 44 mean: 52385Pentium4630/3.0GCPU、1024M内存、 WinXP操作系统Mallaby7.0程序语言环境Mean fitn上述结果的最小支持度为200,得到图2的结果花费了348782sCPU计算时间;得到图3的结果花费了3553004sCPU计算时间。可以看到,相较于图2的结果,大容量的种群数量可以使算法快速地收敛,并达到全局最优值(得到了长度为40的频繁项,并且发现∫600个平均长度为32的频繁模式)。其实,45++++++++4++++++4+++4++++++图3所示结果中,在第30代就已经可以停止了,从而大大减小40510152025303404550计算时间。图5数据库1中取最小攴持度为200(5%)的结果最终最佳个体适应度:48(初始种群数量为200,且全部为数据厍记录)最终种群平均适应度:63.433在数据库I上逐步地抽岀子数据库进行频繁项挖掘计算,种群中最佳个体适应度种群中平灼适应度每次计算选取200的种群量、200的最小支持度、强制繁衍50代,随着抽出的项目数増加,本文提岀的算法计算时间随项目数变化的趋势如图6。与其他算法不同,基于遗传算法的最优扌卡化问题的求解时问随着变量増加基本昰现线性增长的趋势。这55是本文算法的最大优势,即在挖掘含更多顼的数据库频繁模式时,算法计算消耗时间的增长是线性的。0)20304)50)6070890100种群繁衍代数(种群数量:60数据库记录4000,迭代50代,最小支持度200图2挖掘数据厍1上频繁项的结果350(种群数量60,最小支持度200)300最终最佳个体适应度:44最终种群平均适应度:52936790种群屮最佳个体适应度80种群屮平均适应度回士100605512030450607080中时中数据库所含项数图6本文算法计算时间随数据库项日种辟繁衍代数(种群数量:6000数量增长的变化趋势图3挖掘数据库1上频繁项的结果图7为数据库2上挖掘最大频繁模式的计算情况,得到的(种群数量600,最小支持度200最大频繁模式为:图4中共花费349.704sCPU计算时间,与图2的计算时={87175108242438486684766958间相近,说明算法对最小支持度的取值不敏感,这是本文算法其中a()長示最大频繁模式中含第n(;)项。相较于其他算法的一个优势。种群最优个体适应度:989种群个体平均适应度:109768最终最佳个体适应度:53100种群最佳个体适应度最终种群平均适应度:591667种祥个体平均适应度901060种群中最佳个体适应度11040种群中平均适应度l0201000种群繁衍代数(种群数量:250)102030405060708090100图7在数据库2上的挖掘结果种样繁衍代数(种祥数量:60)(最小支持度为5(0.5%)图4数据库1中取最小支持度为1000(25%)的结果由于数据库2的记录本身非常稀疏(平均记录长度为9,图5的结果显示了如果选择合适的初始种群,本文算法惊每项最多记录为16),故算法很快收敛并趋于单一化(大部分人地在2代以后就收敛了,达到了只需要访问2次数据库即可个体都不是频繁)。稀疏的数据记录会使大部分长频繁模式得到结果的FP-增长算法同样的效果,却只消耗了很少的内存都不存在,造成遗传算法在繁衍时大部分个体都是不合法的,(20行、84列的0-1矩阵)。这充分说明利用遗传算法挖掘频故无法繁衍岀最优解,如何处理这样的情况是需要进一步研究张军:基于遗传算法的频繁项挖掘算法008,44(12)165的问题。16 Pasquier N, Bastide Y, Taouil R, et al. Discovering frequent closeditem sets for association rules[C/CDT'99, Israel, 1999: 398-4166结语[7 Han Jid-wei, Kamber M Dala mining: concepls and Lechniques [MI本文从数学规划的角度重新表述了单维布尔型频繁项挖S.J: Morgan Kaufmann Publishers, 2001掘问题,并利用新定义的加法和数乘及范数运算将其归结为[8 Pasquoer N, Bastide Y, Taouil R Efficient mining of association个非线性O-1规划问题,更加清晰和严格地描述了烻繁项挖掘rules using closed itemset lattices[J] Information System, 1999, 24冋题。通过对频繁项挖掘问颙困难原因的讨论,确立了以薮据库记录作为初始种群,直接以0-1变量作为是否包含项目的变 eral r do, cubero, arin \tBA; an efficient method for量,利用遗传算法进行求解的方法。实际计算结果表明,该方法associalion rule mining in relational databases[J]. Dala& knowledge般在几代内即可找到一批长频繁模式。Engineering, 200137: 47-64对初始种群选择的深入研究、对遗传算法中适应数据挖掘卩0皮德常,秦小麟,工宁牛.基于动态剪枝的关联规则挖掘算法肌小的新个体产生的方法的深入研究是将来的研究方向。型微型计算机系统,2004(10):1850-1852[11] Borgelt CEfficient implementationg of Apriori and Eclat[C]proc参考文献:of Ist IEEE ICDM Workshop on Frequent Item Set Mining Implementations(FIMI 2003, Melbourne, FL), CEUR Workshop Pro[刘同明数据挖掘技术发其应用[M]北京:国防工业出版社,2001ceedings 90, Aachen, Germany, 20032]张云涛,龚玲数据挖掘凉理与技术M北京:电子工业出版社,12张禾瑞赫炳新高等代数Ⅵ3版北京:高等教育出版社,1992004.[3]史忠植知识发现M]北京:清华大学出版社,20023 Agrawal R, Imielinski T, Swami A Mining association rules betweensels of items in large database[Cy/proe of the ACM SIGMOD Intl[14] Synthelic dala generation code for associations and sequentialConf on management of Data. Washington d. 1993: 207-216patterns. Intelligent Information Systems, IB Almaden Research[4] Park J S, Chen M S, Yu P SAn effective hash based algorithm forCenterhttp://www.almaden.ibm.com/software/quest/resources/indexmining association rules[C]/ACM SIGMOD International ConferenceshtmlManagement of Data, 1995: 175-186[15] Zaki M J Scalable algorithms for associalion mining.IEEE Trans5 Savasere A Omiecinski E, Navathe SAn efficient algorithm for rainactions on Knowledge and Data Engineering, 2000, 12(3):372-390ing association rules in large database(Cp/proc o2 nd intl conf on[6刘淳安解非线性规划的多日标传算法及其收敛性U计算机工Very large database, Zurich, Swaziland, 1995 432-443程与应用,2006,.42(25):27-29(上接126贝)tology: Proc Eurocrypt 1991.[L]: Springer, 1991: 490-497里假设(K1,S1),(K2,S2),…,(K。,S〃)是消息M(i=1,…,n)[5] Chen x, Zhang F,KimK. a new id- based group signature scheme的代理盲签名,M1对应同一个代理授权证书W,进行批量验证from bilinear pairing[eb/olj-2006.htTp: /eprint. iacr. org/2003/116.pdf时只需要验证以下等式是否成立[6] Lin W D, Jan J K A security personal learning tools using a proxyblind signature scheme C/proceedings of International Conferencee(∑sP)=(∑K+(∑HM|K")P),FK+K)on Chinese language Compuling, Illinois, USA, 2000: 273-277如果对n个签名进行逐一验证,那么将需要消耗的计算代7谭作文,刘卓车,唐春明基于离散对数的代理盲签名软件学报价为2nP+nP+nA,而进行批量验证时,计算代价仅为2P+2003,14(11):1931-19358]王蜀洪,王贵怵,鲍丰,等对一个基」离散对数代理盲签名的密码IP+(3n-1)Ajc分析J软件学报,2005,16(5):911-915.19 Awasth I AK, Lal S Proxy blind signature scheme[J]JFCR Transac7结束语tion on Cryptology, 2005, 2(1): 5-11本文针对基于身份的代理盲签名方案不能有效抵抗伪造10 Sun H m, Hsieh B T On the security of some proxy blind signa--攻击和不具有不可链接性等缺陷,利用双线性对构造了·种新ture schemes[j/ol]-[2003]. Http: //eprint. iacr. org/2003/68型的基于证书的代理育签名方案,通过比较分析,本方案具有[11 Zheng D, Huang z, Chen KF.ID- based proxy blind signature[C]//更高的安全性和效率等优点。ANNA 2004, EEE Compuler Society, 2004, 2: 380-383[12] L ang WM,Tan Y M, Yang 7. K.A new efficient ID-hased proxy参茅文献:blind signature scheme[C)/Iscc 2004, IEEE Computer Society[1 Shamir A Identity-based cryptosystems and signature schemes[Cy/2004,1:407-411LNCS 196 Crypto 1984, Berlin, 1984: 47-53[3]张学军,王育民高效的基于身份的代理盲签名计算机应用,[2] Gentry C. Cerlificale-based encryptiOn and the certificale revocation2006,26(11):2586-2588problem CVLNCS 2656: Advances in Cryptology -EUROCRYPT 2003. [14] Juels A, Luby M, Ostrovsky R Security of blind digital signatures(Cy/[S.L. ] Springer-Verlag, 2003 272-293LNCS 1294: Advances in Cryptology -Crypto 97. S.L.: Springer[3 Al-Riyami SS, Paterson K G Certificateless public key cryptograverlag,1997:150-164.phy[C]/LNCS 2894: Advances in Cryptology -ASIACRYPT 2003. [15] Ahe M, Okamoto T Provably secure partially blind signatures[C]Berlin: Springer-Verlag, 2003: 452-473LNCS 1880: Advances in Cryptology -Crypto 2000.[S1. Springer-I Girault MSelf-certified public keys(/LNCS 434: Advances in Cryp-Verlag,2000:271-286