基于图像映射的关联规则数据挖掘方法

针对大多数关联规则数据挖掘算法难以适应支持度或数据集的变化问题,提出一种基于图像映射的关联规则数据挖掘算法Pix—DM。该算法利用图像在操作系统中的显示及存储特点,结合数据挖掘理论,通过映射有效地将数据挖掘过程在线性空间中实现,提高了算法对支持度或数据集变化的适应能力。实验证明,Pix—DM算法是有效且可行的。

第3 4卷第 2期 1V 1 4 o. 3

计

算

机

工

程

20年 1月 08 1No e b r 2 0 v m e 0 8

No 2 .l

Co p t rEn i e rn m u e gn e i g

软件技术与数据库

文章编号；lo_ 4808 1 7— 2文献标识码： o 32(o)— 01 2 2 A

中图分类号tT1 P8

基于图像映射的关联规则数据挖掘方法王晗，孔令富，练秋生(. 1燕山大学经济管理学院，秦皇岛 0 6 0;2燕山大学信息科学与工程学院，秦皇岛 0 6 0 ) 604 . 604

摘

要：针对大多数关联规则数据挖掘算法难以适应支持度或数据集的变化问题，提出一种基于图像映射的关联规则数据挖掘算法

PxD该算法利用图像在操作系统中的显示及存储特点， i M。—结合数据挖掘理论，过映射有效地将数据挖掘过程在线性空间中实现，通提高了算法对支持度或数据集变化的适应能力。实验证明，P— M算法是有效且可行的。 iD x 关健诃：数据挖掘；关联规则；图像；映射

Da aM i i gAp r a h o s c a i n Ru e s d 0 m a eM a p n t n n p o c f As o i to l sBa e n I g p i gWA n, NG Ha KONGL n . L A u se g igf, I N Qi. n u h( . c o l f c n mi Ma a e n, a s a iest, n u n d o0 6 0; 1 S h o o o c n g me tY n h nUnv ri Qih a g a 6 0 4 oE y

2 S h o f o ue fr t nadE gn eigY nh nUnvri, n u n d o0 6 0 ) . c o l mp t I omao n n ie r, a sa iest Qih ag a 6 0 4 oC rn i n y

[ src]Mot aa nn loi ms f soit nrls a o d p lt e hn e f u p radd tst T ip pr rp ss o e Abta t sdt igag rh sca o ue nn t at lOt ag s p ot n a es hs ae o oe n vl mi t oa i c a we h c os a . p aa g ih b s d o ma e ma pi g n me y Pi— l or m a e n i g

p n, a l x DM . i g t e p i t fi g sd s l y n n t r g n o e ai g s se a d c mb n ng t e t By usn h o n so ma e i p a i g a d so a e o p r t y t m, n o i i h n me h d o aa mi i g tc r i s o tt r c s f d t i i g i i e r s a e a d i r e h e i ii f t e s p o ta d d t s t h n e . t o f d t n n,i a re u he p o e so aa m n n n a l a p c n mp ov s t e f x b lt o h u p r n a a e s c a g s n l y T x e i n n r a a a e sp ov st t x DM se f c i e a d f a i l . hee p rme t e l t s t r e — o d ha Pi i fe t n e sb e v

[ ywo d]d t miig asc t nrl;mae ma pn Ke r s a nn; soi i e i g; p ig a ao u

1概述在所有的关联规则数据挖掘算法中，数据结构不同会带来不同的挖掘效率。在 F—e Pt e算法”的基础上，已涌现出 r 一

T P:具体的事务模式及其所有子模式。 0:每种模式的支持数的累计操作。 定义 2对于事务数据库 D中每个事务对应的模式 P及其子模式 P u,如果其在所有事务模式中的数量不小于用户 sb指定的最小支持数 misp nu,则称该模式是频繁的。

些不同数据结构的高效算法，如 S PMa算法 J F— x、

MA B G算法。可见，采用适当的数据结构可以使算法 R PL

在计算机中的执行效率更高。当然，数据结构的不同对于具体实现是有利有弊的，针对具体问题采用适当的结构才是数据挖掘方法解决实际问题的良策。本文利用计算机中图像 J的表示特点提出了一种基于图像映射的数据挖掘方法。该方法可以有效地在线性空间中实现数据挖掘过程，并有利于事务数据库的更新及增加。

性质 1设事务数据库 D中的事务丁都是依次加入的，则由于某个事务模式 P 1 7加入而获得的频繁模式一定是该事务模式 P的子模式。 一

证明当某个事务模式被加入时，所有子模式对应的支其

持数都加 1。那些达到用户指定的最小支持数的模式都成为频繁模式。因此，性质 1得证。

2问题描述一

推论当事务数据库中所有事务都依次加入完毕，即获得最大频繁模式。

般的数据挖掘方法不会保留所有的中间项目集，这主

要是为了节省内存占用、提高算法效率。但在某些情况下则限制了算法的适应性，如：事务数据集更新，事务数据集增加，支持度改变。在计算机处理器速度、内存和硬盘速度及

定义 3所有项目模式集合 A到图像( Xm行大小)素 f !中像集合 S i p为图像中像素的位置) p( i S存在映射关系 A p。—S i集合 A与集合 S i非空集合。对于每一个模式 P p是 cA,

容量成倍增长的前提下，利用硬件性能提高软件适应性的方法是可取的。

在图像中都有一个唯一的像素(像素点坐标为<,> 0≤ y (≤, 0 v )≤_≤ )与之对应。因此，存在映射关系 A-S i - p。+ 性质 2映射娓从 A到 S i p的双射。 证明 () 1由于存在 oA= p, ()S i因此劝从 A到 S i p的满射。() 2因为当DP )oP ) ( 1= (2时必有 P=P ( 1 P∈A,以劝从 I 2P, 2 )所

操作系统本身就可以支持图像在计算机中的显示，尤其是一些标准的图像格式，且通用性很强。而图像在计算机中

的表示是以像素矩阵的形式存在的，每个像素一般被表示为2 i或 3 i的真彩色，且可以进行随机存取。这就提出一 4bt 2 t b

A到 s i p的单射。概是满射又是单射，因此，劝从 A到 s i p的双射。性质 2得证。基金项目：国家“6”计划基金资助项目( 0 A 0 Z 1) 83 2 6 A 4 2 2 0

个问题，是否可以借助图像本身的特点为数据挖掘的实现带来便利。

3主要定义及有关性质定义 1关联规则挖掘的空间可以用一个三元组 J丁， P尸，D来刻画。其含义如下： )

作者简介：王晗( 7一)男， 1 7,博士研究生， 9主研方向：智能控制，数据挖掘；孔令富，教授、博士、博士生导师；练秋生，副教授、博士

P:所有可能的 k项目模式(:,, n集合。 1…, 2 )

收稿日期：2 0—21 0 7 1-3

E m i a g a@yu d . - al:w nh n s. u n e c一

71 —