基于分布式系统下的改进矩阵算法应用研究★ 郑金彬 （龙岩学院数学与计算机科学学院．龙岩３６４０１２） 摘 要：在分布式数据库中，采用集中的数据挖掘技术来发现有用的模式并不总是可行的．因为从 不同的站点来合并数据集会导致庞大的数据通信量。为此．提出一种基于分布式系统下的 改进矩阵算法。实验结果表明，该算法既可计算局部的支持计数，又可减少扫描分区数据库 的时间。 关键词：分布式系统；关联规则；Ａｐｒｉｏｒｉ算法；矩阵算法 ０ 引言 众所周知．Ａｒ，ｒｉｏｒｉ算法是大多数现有的并行和分 Ｉ＝｛ｉ ，ｉ ，…，ｉ ｝是项集，其中ｉｋ（ｋ＝１，２，…，ｎ１）可以是购物 篮中的物品．也可以是保险公司的顾客。设任务相关的 数据Ｄ是事务集，其中每个事务Ｔ是项集．使得Ｔ Ｉ。 设Ａ是一个项集．且Ａ Ｔ 关联规则是如下形式的逻辑蕴涵：Ａ Ｂ，Ａ ＣＩ。 布式算法的核心．直接编写一种Ａｐｒｉｏｒｉ算法不能显著 提高频繁项目集的生成。在分布式数据挖掘中．信息传 递是同步的．因此能否实现信息的同步传递就成为通 信优化的目标．而对于分布式数据库来说．数据如何分 解是非常重要的『ｌ１。因此．具有较好性能的分布式数据 ＢｃＩ．且ＡｎＢ＝ 性： 关联规则具有如下两个重要的属 挖掘所主要面临的挑战之一是如何找到一种较为优越 的数据分解策略．以实现各节点的负载平衡，并尽量减 （１）支持度（Ｓｕｐｐｏ￣）：Ｐ（ＡＵＢ），即Ａ和Ｂ这两个 项集在事务集Ｄ中同时出现的概率 少数据通信量 分布式算法的主要思想是根据分布在各个领域的 （２）可信度（置信度）（Ｃｏｎｆｉｄｅｎｃｅ）：Ｐ（ＢＩＡ），即在出 现项集Ａ的事务集Ｄ中．项集Ｂ也同时出现的概率嘲。 数据集以形成一定的挖掘规则。与其将不同领域的数 据集合并在一个集中领域．不如生成统一的关联规则． １．２基于分布式系统的关联规则挖掘 设有一个分布式数据库系统Ｓ，由１１个站点Ｓ；（ｊ＿１． …所以这种算法必须尽可能减少数据通信量 关联规则 挖掘过程主要包含两个阶段：第一阶段必须先从资料 集合中找出所有的高频项目组（Ｆｒｅｑｕｅｎｔ Ｉｔｅｍｓｅｔｓ），第二 阶段再由这些高频项目组中产生关联规则（Ａｓｓｏｃｉａｔｉｏｎ ，ｎ）组成。ＤＢ＝ＤＢ１ＵＤＢ２Ｕ…ｕＤＢ ，则ＤＢ称为全局 数据库，ＤＢ；称为局部数据库。 定义１设Ｘ．ｓｕｐ和Ｘ．ｓｕｐｉ分别表示Ｘ在ＤＢ和 ＤＢｉ上的支持数。如果Ｘ．ｓｕｐｉ＞ｍｉ￣ｎｓｕｐｘＤｉ，则称Ｘ为站 点Ｓｉ上的局部频繁项目集；如果Ｘ．ｓｕｐ＞Ｉｍｉｎｓｕｐ￣Ｄ，则 Ｘ为全局频繁项目集 定义２若Ｘ既是站点Ｓ 的局部频繁项目集．又是 全局频繁项目集，则Ｘ称为站点Ｓｉ的重频繁项目集。 显然站点Ｓ；的重频繁项目集包含于其局部频繁项目集 中【引 Ｒｕｌｅｓ）．面临的主要问题有：工作负载平衡、通信的最小 化、同步、数据布局状况、数据分解、磁盘Ｉ／Ｏ负载等。 １ 分布式系统的关联规则概述 １．１关联规则描述 关联规则挖掘的一个典型例子是购物篮分析。设 ★基金项目：福建省教育厅基金资助项目（Ｎｏ．ＪＡ０８２２９） 收稿Ｅｌ期：２０１０—０７—１２ 修稿日期：２０１０－０８－１２ 作者简介：郑金彬（１９７５一），男，副教授，硕士，研究方向为数据挖掘、算法设计与分析 ④ 现代计算机２０１０．０９ １．３ Ａｐｆｉｏｆｉ算法核心思想 为了生成所有频集．使用了递推的方法。其核心思 想简要描述如下： Ｌｌ＝｛ｌａｒｇｅ １－ｉｔｅｍｓｅｔｓ｝； ｆｏｒ（ｋ＝２；Ｌｋ－ｌ≠ ；ｋ＋＋）ｄｏ ｂｅｇｉｎ 种解决方案还降低了平均交易的规模和数据集的大 小．从而导致减少了扫描分区数据库的时间。它最大限 度地减少了候选集的数量、局部和全局信息交换所需 的修正量 通过使用Ｌ型压缩矩阵方法来减少扫描分 区数据库的时间。从而得到所需的支持度。这是一种非 常有效的策略 找出一个中心点用以管理其他所有的 ／，新的候选集 Ｃｋ＝ａｐｒｉｏｒｉ—ｇｅｎ（Ｌｋ—１）；信息交流点以获取所有全局频繁项目集．其时间复杂 度为Ｏ（ｎ）。Ｌ型矩阵算法具有优异的运行效率、低廉的 ｏｒ ａｌｌｆ ｔｒａｎｓａｃｔｉｏｎｓ ｔＥＤ ｄｏ ｂｅｇｉｎ 通信成本．为序贯算法在分布式数据库中的直接应用 ／／事务ｔ中包含的候选集 Ｃｔ＝ｓｕｂｓｅｔ（Ｃｋ，ｔ）； 提供了更强的可扩展性 Ｌ型矩阵是一个压缩结构的对象变量。事务数据 库是由一个二进制数码矩阵构成的．其中行代表事务． 列代表警报 将分区数据库数据转换成局部Ｌ型矩阵 时．只需扫描一次就行了．所以只需从局部Ｌ型矩阵读 取数据就可获取相关的支持度．而不是一次又一次对 分区数据库中的数据不断扫描．因此这种策略将节省 大量内存空间。 ｏｒ ｆａｌｌ ｃａｎｄｉｄａｔｅｓ Ｃ∈Ｃｌ ｄｏ ｃ・ｃｏｕｎｔ＋＋； ｅｎｄ Ｌｋ＝｛Ｃ∈Ｃｋ Ｉｃ．ｃｏｕｎｔ≥ｍｉｎｓｕｐ｝ ｅｎｄ ａｎｓｗｅｒ＝－Ｕ ｋｈ； Ｃ 中的每个元素需在交易数据库中进行验证来决 定其是否加入ＩＪｋ，这里的验证过程是算法性能的一个 瓶颈 这个方法要求多次扫描可能很大的交易数据库。 即如果频集最多包含ｌ０个项．那么就需要扫描交易数 据库１０遍．这需要很大的Ｉ／Ｏ负载 可能产生大量的候 选集．以及可能需要重复扫描数据库．是Ａｐｒｉｏｒｉ算法 的两大缺点 ． ２．２ Ｌ型矩阵算法执行策略 现在以一超市的例子来说明该算法的可行性实施 策略。假定超市现有五种商品类别是咖啡、茶、牛奶、面 包和黄油，分别用Ａ、Ｂ、Ｃ、Ｄ和Ｅ来表示。现假设有如 下三种事务：第一个事务涉及咖啡、茶和牛奶：第二个 事务涉及咖啡、茶、面包和黄油；第三个事务涉及咖啡、 ２ 改进矩阵算法 同其他许多关于数据挖掘课题一样．挖掘关联规 则的关键也是设计出一种用于挖掘频繁项目集的高效 牛奶和黄油 商品的Ｌ型矩阵数据和事务表如图１所 示。 然后。我们只需统计图ｌ中Ｌ型矩阵的第１列中 ‘１’的计数值就获取对应商品Ａ的支持度为３ 同样． 可统计出介于Ａ和Ｃ之间同时为‘１’的计数值为２．也 就是说ＡＣ的支持度为２ 算法，并实现之 有效的办法是使用前缀树结构用于存 放频繁项目集的压缩信息。例如ＦＰ－树。许多实验结果 表明．这些算法是很有效的．为了很大程度上减少需要 遍历的ＦＰ一树．本文采用了一种新型的ＦＰ阵列技术． 它可以显著提高ＦＰ一树算法的性能．这种阵列技术对 于稀疏数据集是非常有效的问 为此．笔者提出一种改 进的算法，它可用于所有的极大化的、关闭了的频繁项 『Ｉ １ １ １ ０ ０ ｌ １ ０ ｌ １ 【１ ０ １ ０ １ ｊ 图１商品的Ｌ型矩阵和事务表 目集的数据挖掘。实验结果表明，这种算法相对其他算 法而言是最快的。当处理稀疏数据集且最小支持度也 较低时．即便可能会消耗较多内存资源．但该算法也是 最快的 ２．３改进的矩阵算法描述 根据定义２以及上面的提出的算法思想．给出具 体的算法描述．设关系数据库中数据的预处理工作已 完成。 ２．１ Ｌ型矩阵算法的优越性 Ｌ型矩阵算法可以最大限度地减少通信开销。这 （１）在局部站点Ｓｉ处计算频繁项目集算法： 输人：ＤＢｊ（ｉ＿１，…，ｎ），在站点Ｓ。的分支数据库 现代计算机２０１０．ｏ９ 囝 输出：ＬＬｉ㈦中的候选元 ｆｏｒ ｋ＝ｌ ｔｏ ｎ ｄｏ ｂｅｇｉｎ ｉｆ ｋ＝ｌ ｔｈｅｎ ，Ｉ’ｉ“）＝ｇｅｔ＿ｈｅａｖｙ＿ｉｔｅｍｓ（Ｓｉ， ，１）； ｅｌｓｅ ｂｅｇｉｎ Ｃｋ＝ａｐｒｉｏｒｉ—ｇｅｎ（Ｌｋ—１）；，／新的候选集 ｉｆＣＫ－￣ｔｈｅｎ Ｅｘｉｔ； ／／算法终止 （ｋ）＝ｒｅａｄ（ＬＭａｔｒｉｘ，Ｃｂｉ）；，，从Ｌ矩阵剩余的候选数 据集中读取局部支持计数 ｅｎｄ ｆｏｒ＿ａｌｌＸ∈ｒＩ’ｉ（ｋ）ｄｏ ｂｅｇｉｎ ｉｆ Ｘ．ｓｕｐｉ＜Ｓ Ｄ ｔｈｅｎ ｐｒｕｎｅ（Ｘ，Ｘ．ｓｕｐｉ）；，／若候选的最大值小于Ｓ＊Ｄ， 则进行局部修正后存放到ＩＬ（ ）中 ｅｎｄ ｆ０ｒ ａｌｌ ｒｅｑｕｅｓｔ ｉｔｅｍ Ｘ ｆｒｏｍ ｇｌｏｂａｌ＿ｓｉｔｅ ｄｏ ｉｆ ｒｅｃｅｉｖｅ（ｃｅｎｔｅｒ＿ｓｉｔｅ）∈Ｓ； ／／若项目集Ｘ 的计数是从中心站点获取的．则重新从ＬＬ矩阵中读取，且将 局部剪正值存放回中心站点 ｂｅｇｉｎ ㈦＝ｒｅａｄ（ＬＭａｔｒｉｘ，ＣＫ＇ｉ）； ｐｒｕｎｅ（Ｘ，Ｘ．ｓｕｐｉ）ｉｎｔｏ Ｕ （ｋ）； ｅｎｄ ｅｌｓｅ ｆ０ｒ．ｊ＝１ ｔｏ ｎ ｄｏ ｒｅｃｅｉｖｅ （”ｆｒｏｍ ｇｌｏｂａｌ＿ｓｉｔｅ；，，获 取全局频繁项集及其支持度 ｋ＝ｋ＋１： ｅｎｄ （２）在中心点处计算全局频繁项目集算法： 输入：各个站点Ｓｉ的ＬＩＪｉ（ｋ）； 输出：取得Ｌｋ ｏｆｒ ｉ＝ｌ ｔｏ ｎ ｄｏ ｂｅｇｉｎ ｆｏｒ ｋ＝ｌ ｔｏ ｍ ｄｏ ｂｅｇｉｎ ＝ ； ｒｅｃｅｉｖｅ ＥＬｉ㈤ｆｒｏｍ ｐａｒｔｉｔｉｏｎｓｉｔｅｓ；／，从各个站点Ｓｉ ＿的读取数据集ＬＬ ｉｆ ＥＬｉ（ｋ）＝ ｔｈｅｎ ０ 现代计算机２０１０．０９ ． ｉｆ ｉ＝ｎ ｔｈｅｎ Ｅｘｉｔ：，／一旦所有站点候选数据集 ＬＬ。（ｋ】＝ ，算法终止 ｅｌｓｅ ｃｏｎｔｉｎｕｅ； ｆｏｒａｌｌ Ｘ∈ＬＩＪｉ㈦ｄ。 ｂｅｇｉｎ ｉｆ ａｌｌ ｐａｒｔｉｔｉｏｎ—ｓｉｔｅ∈Ｘ ｔｈｅｎ ＝ＩＪｋｕＸ ，／若Ｘ中 包含了所有的分区站点，则将候选集Ｘ加入到 ｅｌｓｅ ｂｅｇｉｎ Ｘ．ＭａｘＣｏｕｎｔ＝Ｘ．ｓｕｐｉ； ｉｆ Ｘ．ＭａｘＣｏｕｎｔ＜Ｓ Ｄ ｔｈｅｎ ＬＬ（ｋ￣＝Ｌｋ（ｋ）－Ｘ：／／计算 出候选集Ｘ的最大值，若候选的最大值小于Ｓ＊Ｄ，则进行局 部修正后存放到ＬＬ（ｋ）中 ｏｆｒｊ：：１ ｔｏ ｎ ｄｏ ｂｅｇｉｎ ｉｆｊ≠ｉ ｔｈｅｎ ｓｅｎｄ ｒｅｑｕｅｓｔ ｔｏ ｓｊ； Ｘ．ＭａｘＣｏｕｎｔ＝Ｘ．ＭａｘＣｏｕｎｔ＋Ｘ．ｓｕｐｊ；，，累加支持 数得到Ｘ的全局支持数 ｅｎｄ ｅｎｄ ｋ＝ ＵＸ； ，／将Ｘ．ＭａｘＣｏｕｎｔ≥Ｓ￥Ｄ的Ｘ并入 到ＩＪｋ ｋ＝ｋ＋１： ｅｎｄ －＿ｉ＋ｌ： ｅｎｄ ｒｅｔｕｒｎ ３ 实验结果与算法性能分析 以上述实例为证：从Ａ、Ｂ、Ｃ、Ｄ、Ｅ五个商品类别中 任选取一项作为项目．在这商品事务中每种项目个数 均以１数值递增。然后任选取一项目组合，且与其相应 的事务假定为：若商品在候选项目集中则以ｌ计数递增 且将其加入该项目集．其余小于事务的最小支持数的 商品则从列表中删除。 图２中．基于分布式系统下，依据不同最小支持度 和不同的数据库容量大小来测试，着重从扫描分区数 据库的时间来说明：改进的Ｌ矩阵算法较Ａｐｒｉｏｒｉ算法 在执行效率方面有一定程序的提高．其中Ａ曲线代表 Ｌ矩阵算法执行效率．Ｂ曲线代表Ａｐｒｉｏｒｉ算法执行效 ．率 硒蜜与 发 ／ 图２基于分布式系统下Ｌ矩阵算法和Ａｐｒｉｏｒｉ算法比较 ４ 结语 参考文献 『１１Ａ．Ｓｃｈｕｓｔｅｒ，Ｒ．Ｗｏｌｆ．Ｃｏｍｍｕｎｉｃａｔｉｏｎ—Ｅｆｆｉｃｉｅｎｔ Ｄｉｓｔｒｉｂｕｔｅｄ Ｍｉｎｉｎｇ ｏｆ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅｓ．Ｐｍ ．ｏｆ ＡＣＭ Ｓｉｇｍｏｄ Ｉｎｔ＇ｌ Ｃｏｎｆ． Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ．ＡＣＭ Ｐｒｅｓｓ．２ｏ０ｌ 综上所述．该Ｌ矩阵算法用于分布式数据库的挖 掘关联规则是一种行之有效的算法．不仅大大减少了 数据通信成本．它还具有通过网络传递数据信息以缩 小规模的优势 通过构造Ｌ矩阵．从中获取计数值直接 减少了扫描分区数据库的时间。此外．该改进算法可应 用于统计大型集中数据库的关联规则挖掘所分割的分 布式数据库系统的节点．当其中数据集较大且采用贯 序挖掘策略时．这种方法就显得特别有效 【２】朱喜梅．关联规则挖掘综述【Ｊ】．电脑知识与技术，２００６（０５） 【３】刘独玉，杨晋浩，钟守铭．关联规则挖掘研究综述【Ｊ】．成都 大学学报（自然科学版）．２００６（０１） 『４１Ｍ．Ｚ Ａｓｈｒａｆｉ，Ｍｏｎａｓｈ Ｕｎｉｖｅｒｓｉｔｙ ＯＤＡＭ：Ａｎ Ｏｐｔｉｍｉｚｅｄ Ｄｉｓ— ｔｒｉｂｕｔｅｄ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅ Ｍｉｎｉｎｇ Ａｌｇｏｒｉｔｈｍ，ＩＥＥＥ Ｄｉｓｔｒｉｂｕｔ— ｅｄ Ｓｙｓｔｅｍｓ Ｏｎｌｉｎｅ １５４１—４９２２．２ｏｏ４．Ｐｕｂｌｉｓｈｅｄ ｂｙ ｔｈｅ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｖｏ１．５ Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｉ ｍｐｒｏｖｅｄ Ｍａｔｒｉｘ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍ ＺＨＥＮＧ Ｊｉｎ—ｂｉｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｌｏｎｇｙａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｌｏｎｇｙａｎ ３６４０１２） Ａｂｓｔｒａｃｔ：Ｃｅｎｔｒａｌｉｚｅｄ ｄａｔａ ｍｉｎｉｎｇ ｔｏ ｄｉｓｃｏｖｅｒ ｕｓｅｆｕｌ ｐａｔｔｅｒｎｓ ｉｎ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａｂａｓｅｓ ｉｓｎ＇ｔ ａｌｗａｙｓ ｆｅａｓｉｂｌｅ ｂｅｃａｕｓｅ ｍｅｒｇｉｎｇ ｄａｔａ ｓｅｔｓ ｆｒｏｍ ｄｉｆｆｅｒｅｎｔ ｓｉｔｅｓ ｉｎｃｕｒｓ ｈｕｇｅ ｄａｔａ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｏｕｎｔｓ．Ｐｒｏｐｏｓｅｓ ａｎ ｉｍｐｒｏｖｅｄ ｍａｔｉｒｘ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｉｓｔｒｉｂｕｔｅｄ ｓｙｓｔｅｍ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｃａｎ ｃａｌｃｕｌａｔｅ ｌｏｃａｌ ｓｕｐｐｏｒｔ ｃｏｕｎｔｓ，ａｌｓｏ ｒｅｄｕｃｅ ｔｈｅ ｔｉｍｅ ｏｆ ｓｃａｎｎｉｎｇ ｐａｒｔｉｔｉｏｎ ｄａｔａｂａｓｅ． Ｋｅｙｗｏｒｄｓ：Ｄｉｓｔｉｂｕｔｅｄ Ｓｙｓｔｅｍ；Ａｓｓｏｃｉｒａｔｉｏｎ Ｒｕｌｅｓ；Ａｐｉｏｒｉ Ａｌｇｏｒｉｔｈｍ；Ｍａｔｉｒｘ Ａｌｇｏｒｉｔｈｍ 现代计算机２０１０．０９ ０