隐私保护的一站多表跨多表频繁项集挖掘

摘要：从多方合作挖掘分布存储在不同计算站点上多个数据库表而不泄露各方原始数据信息的目的出发，对于每个站点拥有多个数据表

>> 基于频繁项集发现的匿名隐私保护算法 基于差分隐私的频繁项集挖掘研究综述 挖掘正相关的频繁项集 频繁项集挖掘算法的研究 一种基于布尔矩阵的最大频繁项集挖掘算法 一种挖掘频繁闭项集的深度优先算法 基于矩阵的频繁项集挖掘算法 基于关联矩阵的频繁项集挖掘算法 基于格的快速频繁项集挖掘算法 基于FP树的最大频繁项集挖掘 基于间隔链表改进的频繁项集挖掘算法 快速挖掘频繁项集的并行算法 基于圈和树的频繁项集挖掘算法 最大频繁项集挖掘算法综述 一种基于Hadoop的多表链接策略 多表合一采集应用建设浅析 多表密码攻防战（一) 多表扬对学生的影响 基于Hadoop的频繁项集挖掘算法在图书借阅数据中的应用 基于滑动窗口的数据流频繁项集挖掘方法 常见问题解答 当前所在位置：）

原始PKDD99 Discovery Challenge金融数据库共包含有8个数据表，其中满足本文实验条件的数据表有5个，分别为account表、loan表、order表、disp表和trans表把account表和loan表分配到A站点，order表和disp表分配到B站点，C站点独自拥有trans表；在A站点以account表为主表、loan表为从表，在B站点以order表为主表、disp表为从表，C站点以trans表为主表3个站点A、B和C在站内及站间挖掘跨表频繁项集以属性account_id作为5个表的公共连接属性

本文测试一站多表的3站点跨5表频繁项集挖掘隐私保护算法（简记为算法MTCMPP）在确保3个站点隐私信息安全前提下的运行效率

图1给出了站点A中account表记录数为900、loan表记录数为600，站点B中order表记录数为1200、disp表记录数为500，站点C中trans表记录数为500，对于不同的最小支持度minsup，MTCMPP算法的运行时间

图1的实验结果表明：随着最小支持度的增大，MTCMPP算法所需的运行时间逐渐减少，算法具有较好的执行效率这是因为随着最小支持度的增大，3个站点生成的频繁项集数量在减少，站点间需要传送的站内频繁项集通信开销减少，同时参与三方安全协议计算的参数数量也相应减少，需要运行三方安全协议的次数变少，从而使得MTCMPP算法的运行速度加快

当最小支持度为0.001，A站点中account表记录数为4500、loan表记录数为682，B站点中disp表记录数为5369，C站点中trans表记录数为5000，在B站点主表order表记录数变化时，图2给出了MTCMPP算法的运行时间，图3给出了MTCMPP算法运行时站点连接表大小变化的情况

从图2中可以看到：MTCMPP算法的运行时间随着B站点主表order表记录数的增加而增加这是因为随着order表记录数的增加，B站点内公共连接属性account_id数目相应增加，B站点内主表和从表联合计算站内连接表大小的开销时间变大对于3站点计算5表的连接表大小开销增加更为明显，这是因为满足5表连接条件的参与三方安全协议计算的参数数量变大，执行三方安全协议的轮数增多，计算消耗时间随之增加另一方面，生成的站内和站间跨表频繁项集数也相应增多，增加了挖掘时间

图3给出了最小支持度为0.001，A站点中account表记录数为4500、loan表记录数为682，B站点中disp表记录数为5369，C站点中trans表记录数为5000，B站点主表order表记录数变化，MTCMPP算法运行时站点连接表大小变化的情况

图3的实验结果表明：随着order表记录数的增加，A站点站内连接表大小JoinSa变化没有产生影响，B站点站内连接表大小JoinSb则相应增加，全局3站点站间跨5表连接表大小Joinsize增加幅度较大这说明当构筑全局站间连接表大小、在站间挖掘跨表频繁项集数据时，order表数据对调节挖掘出站间跨表频繁项集结果起到决定性影响而需要表明的是，连接表大小为判断生成跨表频繁项集条件的一个决定性参数，在最小支持数固定的条件下，连接表大小越大，要满足条件：不小于Joinsize（或JoinSa或JoinSb）×minsup结果的跨表候选项集支持数就要越大，所以站间（或站内）连接表大小变化，对于生成跨表频繁项集数目以及站间执行三方安全协议次数具有很大的影响，从而影响算法所需的运行时间

当最小支持度为0.001，A站点中account表记录数为4500、loan表记录数为682，B站点中order表记录数为6471、disp表记录数为5369，C站点trans表记录数变化时，图4给出了MTCMPP算法的运行时间，图5给出了MTCMPP算法运行时站点连接表大小变化的情况

图4的实验结果表明：MTCMPP算法的运行时间随着C站点trans表记录数的增加而增加

图5给出了最小支持度为0.001，A站点中account表记录数为4500、loan表记录数为682，B站点中order表记录数为6471、disp表记录数为5369，C站点trans表记录数变化， MTCMPP算法运行时站点连接表大小变化的情况

从图5可以看到：随着C站点trans表记录数的增加，对A站点站内连接表大小JoinSa和B站点站内连接表大小JoinSb变化不产生影响，对全局3站点站间跨5表连接表大小Joinsize变化呈亚线性增长，这也说明了C站点trans表数据对于构筑全局站间连接表大小、调节挖掘出站间跨表频繁项集结果影响大

本文给出的MTCMPP算法执行三方安全协议计算站间跨表项集支持数，使得三方中的任何一方都不能获知其他两方的敏感数据，确保3站点间隐私信息得到安全保护，并且高效地挖掘出一站多表3站点跨5表的频繁项集结果

4 结语

已有的隐私保护频繁项集挖掘算法不能满足多个数据表分布在不同计算站点上的多方安全联合获取知识的需求对于每个站点拥有多个数据表的分布式计算环境，基于三方安全协议，采用随机数扰乱方法，本文设计实现了一站多表的3站点跨多表频繁项集挖掘隐私保护算法，该算法高效并且能够保护各方私有数据的安全下一步将研究算法效率和隐私保护没有受到减弱的同时，将算法扩展到拥有更多参与方的情形

参考文献：

[1]VAIDYA J， CLIFTON C. Privacy preserving association rule mining in vertically partitioned data [C]// KDD02： Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2002： 639-644.

[2]GOETHALS B， LAUR S， LIPMAA H， et al. On private scalar product computation for privacypreserving data mining [C]// ICISC04： Proceedings of the 7th Annual International Conference in Information Security and Cryptology， LNCS 3506. Berlin： SpringerVerlag， 2004： 104-120.

[3]华蓓，钟诚，黄肇明，等.通过计算影响权值实现敏感序列模式隐藏[J].小型微型计算机系统，2010， 31（8）： 1647-1651.

[4]GONG Q Y， LUO J Z， YANG M. AIM： a new privacy preservation algorithm for incomplete microdata based on anatomy [C]// Proceedings of the 7th International Conference on Pervasive Computing and Applications （ICPCA） and the 4th Symposium on Web Society， LNCS 7719. Berlin： SpringerVerlag， 2013： 194-208.

[5]GORAWSKI M， JURECZEK P. Optimization of privacy preserving mechanisms in mining continuous patterns [C]// Proceedings of the 8th International Conference on Dependability and Complex Systems， AISC 224. Berlin： Springer Verlag， 2013： 183-194.

[6]贡晓静，钟诚，华蓓.基于等距变换的聚类挖掘敏感信息保护方法[J].计算机工程，2011，37（19）：122-125.

[7]HUA B， ZHONG C， YANG L， et al. Collusionresistance privacypreserving distributed sequential pattern mining [J]. International Journal of Advancements in Computing Technology， 2012， 4（21）： 204-212.

[8]SHE R， WANG K， FU A W， et al. Computing join aggregates over private tables [C]// Proceedings of 9th International Conference on Data Warehousing and Knowledge Discovery， LNCS 4654. Berlin： Springer Verlag， 2007：78-88.

[9]DU W. A study of several specific secure twoparty computation problems [D]. West Lafayette， Indiana： Purdue University， 2001： 1-159.

[10]林瑞，钟诚，李效鲁.隐私保护的跨多表频繁项集挖掘[J].计算机工程与应用，2012，48（2）：66-68.

[11]JANGRA A， BALA R. PASA： privacyaware security algorithm for cloud computing [C]// Proceedings of the International Symposium on Intelligent Informatics， AISC 182. Berlin： SpringerVerlag， 2013： 487-497.

[12]YUAN J W， YU S C. Privacy preserving backpropagation learning made practical with cloud computing [C]// Proceedings of the 8th International Conference on Security and Privacy in Communication Networks， LNICST 106. Berlin： SpringerVerlag， 2012： 292-309.

[13]PANG X Q， YANG B， HUANG Q. Privacypreserving noisy keyword search in cloud computing [C]// Proceedings of the 33rd International Conference on Information Systems， LNCS 7618. Berlin： SpringerVerlag， 2012： 154-166.

[14]WAQAR A， RAZA A， ABBAS H， et al. A framework for preservation of cloud users data privacy using dynamic reconstruction of metadata [J]. Journal of Network and Computer Applications， 2013， 36（1）： 235-248.

[15]CANETTI R， FEIGE U， GOLDREICH O， et al. Adaptively secure multiparty computation [C]// STOC 96： Proceedings of the Twentyeighth Annual ACM Symposium on Theory of Computing. New York： ACM， 1996： 639-648.