频繁情景并行挖掘算法研究

频繁情景可用于挖掘蕴藏在事件序列数据库中的知识,为了提高算法的时间性能,提出了一种挖掘频繁情景的并行算法PRE。研究了局部频繁情景与全局频繁情景的关系;通过研究频繁情景挖掘中事件可删除的条件,提出了逐步缩减数据库的技术,使得算法在迭代过程中需要扫描的数据库大小逐渐减少。数据实验表明,仅采用数据库缩减技术时算法PRE的时间性能比算法WINEPI提高25%,并行挖掘时算法PRE的并行效率与处理器个数近似成线性关系。

A Parallel Algorithm for Mining Frequent Episodes

To our knowledge,there is no paper in the open literature concerning parallel algorithm for mining frequent episodes.We now present an algorithm,called PRE(parallel algorithm using database reduction technique for mining frequent episodes) by us,that is more efficient than the existing WINEPI algorithm because:(1) PRE utilizes the efficiency of parallel computing and(2) the size of database can be gradually reduced during mining.In the full paper,we explain PRE algorithm in detail;in this abstract,we just add some pertinent remarks to listing the three topics of explanation:(1) the important properties in parallel mining episodes of frequent occurrence;(2) the database reduction techniques in parallel mining frequent episodes;and(3) the iterative procedure of PRE algorithm;in topic 1,we give Theorems 1,2,and 3 in the full paper that make clear the relations among global frequent episodes and local frequent episodes under various conditions;in topic 2,we give Theorems 4 and 5 in the full paper for reducing the database gradually during mining;in topic 3,we give a four-step iterative procedure.Finally we give some numerical examples,whose results,shown in Figs.1,2,and 3 in the full paper,show preliminarily that,by using the database reduction techniques alone,algorithm PRE is faster than WINEPI about 25%.The experiment results also show that algorithm DRE has good speedup performance.