集群系統中基于MPI的關聯規則快速挖掘算法

安立奎 錢偉懿 韓麗艷

(1.渤海大學數學系,遼寧錦州 121003;2.渤海大學公共計算機教研部,遼寧錦州 121003)

集群系統(cluster)也稱機群系統指“利用高速通用網絡將一組高性能工作站或高檔PC機,按某種結構連接起來,在并行程序設計及可視化人機交互集成開發環境支持下,統一調度,協調處理,實現高效并行處理的系統”(王鼎興,董春雷.可擴展并行機群系統.From CCW,1997-04),由于其具有開發周期短,性能高,投資風險小,可擴展性好等優點,已經成為并行計算中的熱點.MPI提供了基于消息傳遞方式的并行程序設計,是目前發展較快,使用面廣的一個公共消息傳遞庫.關聯規則是數據挖掘的一個重要研究領域,它能發現不同商品之間的聯系,發現顧客購買行為方式,有利于有效設計商品貨架,對用戶分類等.關聯規則的挖掘算法主要有[1]Agrawal等提出的基于Apriori算法的頻集方法.為了提高關聯規則的挖掘效率,研究人員又提出了并行挖掘算法,主要包括:[2-5]Agrawal等人提出的CD算法,Park等人提出的PDM算法,Chueng等人提出了FDM和DMA算法.這些算法雖然具有速度快、容易實現等優點,但也存在著可擴性較差、候選項集大、規則合成難度高等缺點.

本文參照了文獻[6]的算法,給出了一種在集群系統中用MPI實現的基于二進制的關聯規則算法,該算法具有實用性強,并行可擴展性好,實現難度低和高效率等優點.

1 基本概念

1.1 關聯規則并行挖掘問題描述

設I={i1,i2,…,im}是項的集合,事務T是I的子集.設事務數據庫DB是由事務組成的集合,數……