TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.5, May 2014, pp . 4071 ~ 40 7 8   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i5.4770          4071     Re cei v ed O c t ober 2 2 , 201 3; Revi se d Decem b e r  27, 2013; Accept ed Ja nua ry 1 8 , 2014   The New Algorithms of Weighted Association Rules  Based on Apriori and FP-Growth Methods      Ting Liu  Coll eg e of Information Sci enc e and T e chno l o g y , Z hengz ho u Normal U n iv ersit y ,   Hen an Z h e ngz hou, 45 00 44, Chin a   E-mail: ed uli u ti ng@ 163.com       A b st r a ct   In order to improve the freq uent  ite m sets  gen erate d  laye r-w ise efficienc y, the paper u s es the   Apriori  pro pert y  to reduc e the  search s pace.  F P -grow   algor ithm for  mini ng  freque nt patte rn steps  mai n ly  is   divid ed  into tw o steps: F P -tree a nd F P -tre e to constr uct  a recursiv e  mi nin g . Algor ith m  F P -Grow t h is to   avoi d the hi gh  cost of candi date it e m sets  gen eratio n, few e r, more effi cient scan n in g .  T he paper p u ts  forw ard the  ne w  algorit hms  of  w e ighte d  ass o ciatio n ru les  ba sed  on A p rior i  and  F P -Grow t h metho d s. In th e  same support, this  method  is  the  most effe ctive a n d  stabl e  max i mu m fr equ ent  ite m set s  mini ng  ca pa city   and  mi ni mu m  executi on ti me.  T h rough th eor etical a nal ys is and ex peri m en tal simul a tion o f  the performan c e   of the alg o rith m is disc usse d ,  it is proved t hat the alg o rith m is feasi b l e  a nd effective.      Ke y w ords :  F P -grow ,  apriori,  w e ighted  asso ciatio n rule     Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Data mi ning  asso ciation  rule mi ning  is an  impo rtant re se arch topic in t he field.   Asso ciatio n rules  can ge nerally be di vided  into  Boolea n a s so ciation  rul e   and  qua ntitative   asso ciation  rules. Ag ra wal  in 1993  mad e  Boolea n  a s so ciation  rule s is  pro p o s ed , after cla ssi cs  Apriori  and A p rio r i TID al g o rithm. Multi  valued attri b u t es are divide d into catego ries of attrib utes  and attribute, many  alg o rith ms  i n  solving  multi  va lued   attributes min i ng a s so ciatio n rules,  are th e  contin uou s  n u meri cal  di scriminatio n, ge t the  corr e s p o nding  fuzzy d e scriptio n, a n d its processi ng  method is  si milar to the Boolea n asso ci ation rule s mi ning.   As in  the  weighted  a s so ciation  rules ba sed  on   simultan eou s minin g  p o si tive and   negative associatio n rule s,  will pro d u c e  some co ntra diction s  and  meanin g le ss  rule s, therefo r e,  in the traditio nal su ppo rt, confid en ce framework,  introdu ced in thi r d pa ramete rs to remove t h e   redu nda nt ru les. Ba sed  o n  the  correl a t ion  between  positive  and  negat ive asso ciation rul e s  mining al gorit hm ba sed  on  intere st and  right: the po si tive and ne ga tive associ ation rul e s  mini ng   algorith m  ba sed on weight ed chi - squa re  test; t he posi t ive and nega tive asso ciati on rul e s mini ng   algorith m  [1]. Whe n  the d a taba se i s  very uneve n ly distrib u ted,  the above fo r the mini ng  of   asso ciation  rules is  not ef fective. Beca use  of  the  l o w  fre que ncy items who s e  sup port  i s  often  low, a nd the r efore  ra rely  be exh u med.  Aiming at th is p r obl em, t he  sup port  d egre e  m odel  for  different tran sa ction s  with  different min i mum su ppo rt  threshold, it is more effici ent use r  interest   rule s.  Weig hted a s so ciation  rule s with n egati v e supp ort a nd co nfiden ce of the cal c ulated by  introdu cin g  n egative set, suppo rt de gre e  and  conf id ence de gree  cal c ulatio n is facin g  a  sev e re   test  of  its se arch spa c e e x ponential growth.  Be cau s e data mi nin g  is the  obje c t of ma ss  d a ta,  and a s soci ation rule s a r e i n  focu s for th e proje c t of it.  Cla s s with A p riori  algo rithm  ba sed  on  FP-Gro wth  algo rithm; a cl ass  based o n  a  cl ass of   algorith m s. P r eviou s  re se arch at hom e and ab ro a d  have don e  a lot of work, their typi cal  algorith m s  are pro p o s ed i n  MINWAL (O) alg o ri thm  and MINWAL  (W) alg o rith m, the pro p o s e d   algorith m  Ne w-Ap rio r i 20 0 3 , in ad dition  to WA R al g o rithm  and t he M W QA R  algorith m . Th e   pape r puts fo rwa r d the ne w algo rithms  of weight ed a s soci ation rul e s ba sed o n  Apriori a nd F P - Growth methods .       Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  4071 – 40 78   4072 2. The Analy s is of Weig h t ed Associa t ion Rules Te chnolog y   With the  rap i d develo p m ent of comp uter  te chn o lo gy, the so ci ety has  ente r ed th e  informatio n a ge, esp e ci all y  the databa se an d data  colle ction te chnolo g y deve l opment, vari ous  indu strie s  sto r e a lot of d a t a, from the  origin al  file d a ta to the co mputer  stora ge. Beca use  the   databa se exp ansi on cap a city,  large  am ounts of  dat a  in datab ase, much  impo rtant inform ation   behin d , and i t  is the information is ext r acte d fr om t he datab ase, will create a  lot of potential  value. In the  face  of the  increa sin g  e x pansi on of  sea  of data,  the tra d ition a l data  analy s is  method s hav e been u nabl e to meet the need s of  the peopl e, as is  sho w n by Fig u re1.         Figure 1. Wei ghted Asso ci ation Rul e s T e ch nolo g y Diagra m       Since th e a ssociatio n rule s in d a ta mini n g , fi rst  by Agrawal  was put  forward, pe o p le o n   the asso ciati on rul e s i n  d a ta mining te chn o logy  research h a s  be en cond ucte d ,  in theory it on a   lot of very fruitful analysi s  and  re sea r ch, prac ti ce  also ma de  many effective algorith m s for   mining a s so ciation rul e s f r om the o ry to appl i c ation  foundation.  Here, ba sed  on data mi ning   asso ciation rules algo rith m  introd uctio n .  Associat io n rule  minin g  algorith m  cl assic  algo rith m is  Apriori  algo rit h m. The  alg o rithm i s  p r o posed by Ag rawal et al  i n  199 4, the  main  work i s  on  asso ciation rule freq uent  item set mini ng, esp e ci all y  for Boolea n asso ciation  rule s frequ e n t  itemset s  mini ng.  It can b e  a ttributed to  the followi ng  two  kind  o f  thought: o ne is the  a ttribute  discrimi nation ,  it is weighted, the proble m  is  tran sformed into a weighted Bool ean Asso ciati o n   rule s. The  other m e thod i s  the attri but e of dom ain  is divide d int o  overla ppin g  interval, th en  locate d n ear t he b oun dary   element  ma kes it  po ssible   to s i multaneous l y in the two intervals .  A s  a   result of these eleme n ts si multaneo usly  to t he two zone s betwee n  cont ributio n s , there m a y be   too much e m pha sis o n  the  role of these  element s.   The eig h t parameter  persp ective tran sfo r mati on m o d e l althoug h it can m o re a c curately   descri be th e  came ra' s   mo vement, but it s  comp utat io nal compl e xity greate r  d e g r ee.  Con s id ering   the accu ra cy with re al-time  requi reme nts, it is the six-pa ramete r af fine model of  came ra moti on   cau s e d  by the interface scene chang e modelin g [2]. When the scene rel a tive depth chang e is  not sig n ifica n t, the six-pa rameter  affine  model  can   well d e scri be  the rotatio n   of the ca mera ,  panni ng and t r an slation a l motion.  At present in the asso ci ation rul e s  a l gorit hm fo r  freque nt itemset s  discov ery, has  prod uced va rious  effective  method. G e nerally  spe a k ing, the s e  algorith m s  are to follow two  step s: one, t o  esta blish t he fre que nt item se ts  a ca ndidate  set; t w o, in th e ca ndidate  set  o u t  actually in clu des frequ ent item se t of all  sub s ets. In  asso ciation  rule metho d , Apriori m e tho d  is  most wi dely used. Th e Apri ori metho d  is  use d  as  a lay e r by layer se arch iterative  method, and i t   is usi ng the p r eviou s  iterati on of  the freq uent item sets a s  after on e is iteratio n  of the can d id ate   item sets, an d then gets th e final result prun e.  Whe r ein, ea ch  tran sa ction  is  a set of  T  i s   e a ch  tra n sa ction having an  ide n tifier TID.  Let  A  be  a set,  T  contai ns  A when  the asso ciation rule s are sha ped a s   A →  B impli c ation,  whi c h,  A I,  and  only whe n  the A  T B, I, A ∩  B= .  Rule A →   B   in transactio n  set  D su ppo rt s D  tra n sacti on  contai ns A →   B percenta g e ,  let menu s b e  the minim u m su ppo rt de gree, if  s  ≥ mi nsu p , call ed f o r  freque nt itemsets. Rule A →  B in transaction  set D  confid en ce le vel in C is co ntained in the  D A  transactio n  contain s  both the per ce ntag e of B, namely Support (A →  B )  = P  ( A   ∪ B), Confide n ce   (A →  B) = P (A|B), as is shown by Equat ion (1).  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The Ne w Alg o rithm s  of Weighted Asso ciation  Rule s  Based o n  Apriori and … (Ti ng Liu)  4073    00 0 0 0 ,= , , 1 ,                1 1 ( , ) 1 ( 1 , )                    1 ( , 1 ) ( 1 , 1 ) fu v f u v fu v f u v f uv f u v fu v f u v                                                                                 (1)     Weig hted fre quent itemsets do wn ward clo s ure  ch ara c ter in tra d itio nal asso ciatio n rule s  in tran sa ction ,  a lot of, thus creating  eno rmou s  sub s et , using  freq ue nt set the  do wn ward  closu r e   cha r a c ter, to  some  rule s p r unin g , for example, in  the  algorithm Ap riori, if {AB} a nd {BC} are  not  freque nt, then {ABC} an d { B CD} a r e n o t freque nt.   Improved  wei ghted a sso ci ation rule s al gorithm  an d Apriori al gorit hm the basi c  steps  like: first find  all weig hted  sup port d egree is not   sma ller than a u s er-sp e cifie d  minimum  sup port   degree  weig h t ed freq uent i t emset s , and  the freq uent  i t emset s  satisfying the mini mum weighte d   confid en ce of  all the rules.   A  set  of {AB} affairs wei ght   cal c ulatio n  f o r:  Fo r (k=2; L  k-1 = do  b e g in;  k++) Ck =Apri o ri- gen (L  k-1); For ea ch tra n s a c tion s t ∈∈ D For eac h  trans ac tions  t D {Ct s ubset (Ck ,  t); For each  c a nd id a t es  C  ∈ Ct {  c. n u m+ +;   c. weig ht =   Weig ht  (  c  );   /  /   cal c ul ation   of weig hted sup port   } Lk ={ c  ∈ Ck  | c.  weig ht × c .num/|D| ≥  minws u p }  }   r e tu rn  L=   ∪ K  Lk ; ITW (A, B )  =0.6  × 0 .9/ (0.6+ 0 .9)  = 0 .36.  Weig hted su pport data b a s e contain s  the proj ect a ffairs  cent rali zation value summary : WS (X)  =N X   ∈∈ Π ( [i[ w]  X] ) Ti [ik  [ w ]] n  Σ ( [i[ w]  X Ti [ik  [w]]  ] )K = 1  K = 1  |X |X  |.   Becau s e t he  data the b o d y  itself is not  too mu ch  sig n ifican ce, it is only a de scri ption of   what h app en ed, and  not for de ci sion -m akin g provid e  reliabl e ba si s; through  dat a analy s is to  find  out the relati onship betwe en the given  data, some   meanin g  and  relevan c e, it formed the  so- calle d info rm ation. Althou gh given  data  in some  mea n ingful thin gs, but it often  and p eopl e n eed   to c o mplete the tas k  without direc t   c o ntac t, als o   c ann o t  se r v e as   d e c is ion - ma k i n g  ba s i s ;  on ly th e  informatio n for furthe r pro c essing, to un derta ke  mo re  thoroug h an alysis, in ord e r to obtain  more   useful info rm ation, namely  kno w led ge, as is  sho w n b y  Equation (2 ) [3].                                                                                              (2)    Ho wever, the  amount of d a ta to the explosiv e g r o w t h  of now  ma ke s it difficult for the   use r  to like  b e fore relying  on expe rien ce, lar ge a m o unts of calcul ation and  hu man comma n d  to   find out abou t the artificial  data more comprehe nsiv e kno w le dge,  the kno w led ge hidd en in  the  data. Many  can be  found  and  us ed, the waste  of  resou r ce cau s ed  by data.  Many de ci si on  make rs from the databa se  mining the s e  pattern s ar e increa singly in tereste d  in, associ ation rul e s  mining  can  p r ovide  effecti v e de cisi on  suppo rt, wa s prom oted on  certai n  l e vel asso ciation   rules  mining techn o logy develo p ment.  The p r o b lem  of minin g   asso ciation  rules can  be  formali z e d   as foll ows: I } , is th e  collection of all items. I s  all   affairs D M  set (d ataba se ), each tran sa ction  T i s  the   numbe r  of ite m s  colle ction, T i n clu ded in I, each tran sa ct ion ca n  u s e  T I to identify a uniqu e ide n tifier. A D T.  Asso ciatio n  rules are  sha p ed a s  B  =!.  Rule a  B B I, B  I, and  A is a   set of thi n g s ,  T contain s  A  if  and only if A  B implication.   Hori zo ntal  weighted  a s so ciation  rul e s  mining  met hod  and  the  improved  weighted  asso ciation rules minin g  method com p arison re sults,  whe r ein,  sh ado w pa rt is the fre que nt item.  The  algo rithm  of minim u m  sup port  is re spectively  p r ov ided  with  15 %, 55%, 33% , to illust rate t he  weig hting fu nction in mi ning a s soci ation rule s [4]. Hori zontal  weig hted a s sociatio n rule s to   gene rate freq uent item pro c e ss i s  first calcul ated by cou n ting su p port deg ree,  namely a set  in   the data base  the p r op ortio n , and th en  u s e th e item  weig ht prunin g  by it. As yo u can  see  fro m   Table  1, ho ri zontal  wei ght ed a s soci atio n rul e s  mini ng meth od b e ca use of th e presen ce  of  freque nt item  sub s et s is  not frequ ent,  so it c an n o t maintain f r equ ent item,  as i s  sho w n  by  Equation (3).     1 1 [( ) ] [( ) ] , i k k kk i x x I X IX II LL LL                                                                                                   (3)  N M y x F y x R RMSE M i N j j i j i   11 2 )] , ( ) , ( [ Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  4071 – 40 78   4074 In thing s   set  D  wa s e s tabli s he d, with  th e supp ort of  s  whe r ein  s i s   D thin gs co ntains A!,  B (i.e., A and B two) perce ntage, it is the prob ability  P (B A!). Rule a B is  the percentag e of C, it  is the  con d itional p r ob abili ty P (B A |).  Namely: supp  ort (A B)  = P  (A B! ))  = P (A B D |) in thi n g s   with co nfiden ce C, if D co n t ains A affairs wh ile Pack: x [0, 1], called  the membe r ship deg ree.   A  colle ct ion  o f  it ems  called  it em s e t s   (I TE  set ) .   Cont ai ns  k it em  set   calle d k  m  se t .  A  set   of frequ en cy  of occu rren ce  is  c ontai ning  the item  set t r an sa ction  nu mber,  refe rre d to a s  a  set  of  freque ncy,  a  cou n t o r   cou n ting. If the it em  set i s  g r e a ter th an  or  equal  to the   freque ncy  of  M  in_sup an d D in the affairs  of the total nu mber  of  pro d uct, the item  set satisfie s the sm all sup port  M in_su p  as i s  sh own by Equation (4).          s s n n t s n s f t f ) 2 , ( ) , ( ~ ) (                                                                                    (4)     The  u s e   of vertical data mining  frequ ent  pattern a bove two  me thods are b a s ed  on   stand ard d a ta format as tran sa ction se t mining freq uent pattern s in the algorithm, also can  be  use d  in a vertical fo rmat  of data mining [5]. It is the core  of equivalen c e tra n sfo r m a tion   algorith m . Co mpared with  the Apfiofi algorithm u s e s  a hori z ontal  format data, this metho d  h a s  the follo wing  advanta g e s : 1)  Ca ndid a te ge neration p r o c e s s  doe s n o t p r odu ce th e d a ta  explosi on, produ ced o n ly a sma ll nu mb er of set s  of items.  2  Do n o t need to scan the datab ase   to determine  the (K  + 1 )  it em sets  (for  k  > = 1 )  of th e suppo rt d e gree.  The  use of differen c e set  techn o logy to  furthe r  redu ce th e  storag e of  lo ng  TID coll ectio n  ov erhe ad  and  the inte rsectio n   comp utation.   Asso ciatio n rule mining is one of the importa nt con t ent of data  mining field. But the  traditional  a s so ciation  rule s mi ning  is o ften ba sed  o n  such  co ndit i ons:  (1 ) T h e  datab ase  ea ch  item of importance a r e th e same; (2 )  The datab as e is uniforml y  distributed:  but the practical  appli c ation of  the databa se is not a n  id eal situat io n, but users on  variou s  proje c ts for  attention   degree i s  also different, a s  in ind u st ry sale s, so me  comm ercial p r ofits, so th e  mall ope rato rs to  pay cl ose att ention to  it in  it, for such  a  proje c t sho u l d   be   given greater wei ght. The weig hts are   introdu ce d to the mining of asso ciation rules.   Matrix of wei ghted a s so ci ation rul e s  mining al go rithm this i s  b u ilt on a d e scen din g   trimming  weights  ba sed   on 3 2  al go ri thms  de scrib ed in  ou r  F  -  R  - t  me thod b a sed  on  combi nation   weig hting m a trix of the  rul e s  of P  g  wh o o  model  in here n t cha r a c teri stic,  out  of the   diggin g  matri x  of weighte d  asso ciation  rules  algo rith m [6]. Propo sed alg o rithm  basi c  tho ught  is:  first stru cture  F. F digging process u s i ng P  tree in P tree weight ing desce ndi ng find frequ ent  itemset s  p r un ing. Th en  accordin g to  the  matrix weight ed  confid en ce a r e from th e fre quent  ite m   sets in a s so ci ation rule s to find exit, as is sho w n by Equation (5 ).     1 0 1 (, ) ( , ) n i i Vk t V k t n                                                                                                               (5)    Whe n  the d a t a is up dated  quickly ho w to improve t he alg o rithm,  nume r ical variabl e  pro c e ssi ng p r oble m , proje c t set in the  weighte d  ca se of asso ci ation rule mi ning metho d  of  ass o c i ation rules mining f i rs tly [7]. By  Ag.  W Imi e linski a nd S w ami p r op ose d  swe e t. Apriori  algorith m  by A.orawal an d Sr ikant propo sed "!, subsequ ently  it was  based  on the Apri ori   algorith m  ca rried   out a se ries of  imp r ov ements,   com pare d  to  the   well-kn own in clud e the  u s e  of  hash table t o  improve the efficie n cy  of mini ng  asso ciation  rules, u s e s  t he tran sa cti on  comp re ssion  technolo g y to the scan n ed tran sa ctio n set are co mpacte d, used the divisi on   techn o logy o n  tran sa ction  set segme n tation, usi ng  sampli ng te chnolo g y of mining an d u s i ng  dynamic item set co unting  method.   Asso ciatio n rule mining  h a s ma ny extensi o n s , incl uding m u ltilevel associ ation rul e s  mining, asso ciation rule  mining, mini ng asso ci ati on rule s ba sed o n  co n s traint s, peri odic  asso ciation  rules minin g , t he mi ning  of  weig hted  associatio n rule s, there  a r e  some  schola r s of  these al gorith m s. In additio n , associ atio n rule mi ni ng  technol ogy n o t only can b e  dire ctly use d   as  a  de cisi o n  supp ort to ol, ca n  also  be a pplie d t o  othe r  data  minin g  te ch nology,  su ch   as  asso ciation  rules  mining  tech nolo g y ca n be  used in   deci s io n tre e   indu ction a n d  analysi s   of time  seri es d a ta, classificatio n  in data mining  technol ogy.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The Ne w Alg o rithm s  of Weighted Asso ciation  Rule s  Based o n  Apriori and … (Ti ng Liu)  4075 3. The Res e a r ch of Aprior i and FP-Gro w t h  Me thod s   This pa pe r a nalyze s  the F P 2 tree is ap plied to the maximum pat tern minin g , can rea c h  a high er  efficiency in  1 th at the p r oble m  is  m a inly becau se  the  algorith m   ge nerate s  a  la rge  numbe r of ca ndidate m a ximum mod e , testing  w heth e r they are for maximum  mode n eed s  to  spe nd a lot of time 1 in order to solve t he pro b lem p u t forwa r d th e corre s p ondi ng improvem ent  measure, the s e  metho d s i n clu de  FP2 t r ee  orde ring,  re du ce  gen erate  candi d a te Max  scal e,  redu ce  the in spe c tion  scop e 1 we give t he imp r oved  SFP2Max alg o rithm, an d th e algo rithm  with  the improve d  algorith m  and  the MAF IA  FP 2Max befo r e the pe rformance co mp arison [8].  On the Ne w. Apriori al go rithm time com p lexi ty is too high an d the numbe r of ca ndidate   itemset s  i s  to o la rge, i s   ba sed  on  the  two p r uni ng  alg o rithm  WA RDM, give s th e related  the o rem   and its pro o f. WARDM alg o rithm in mini ng the dat ab ase, only nee ds to scan th e databa se o n ce  can g ene rate  all the weig h t ed frequ ent itemset s , can  redu ce th e d a taba se the  numbe r of visits,  and im prove   the efficien cy  of minin g . T h rou gh t w o ti mes  of pruni ng  can  effect ively redu ce t h e   numbe r of ca ndidate item sets, as  is  sho w n by Equati on (6 ).     2 11 1 (, ) ( , ) ( , ) MN kt k t xy M SE I I I x y I x y MN                                                                                  (6)     FP -gro w th algorithm for  mining freq ue nt patte rn ste p s mainly is  divided into two ste p s:   F P  2 t r e e a nd F P  2 t r e e  to   c o ns tr uc t a re c u r s ive  mini ng. Con s tru c tion of FP  - t r ee 1:  algo rith m  input: transa c tion data b a s e and the mi nimum supp ort thre shol d  to D m in_ sup. Outp ut: th e   freque nt patt e rn t r ee  FP  2tree. M e tho d : mainly  co nsi s ts  of two  step s: (1) Scan s tran sa ction  databa se  D, get the frequent 12  se t F and thei r su ppo rt co unt. Acco rdi ng to F sup port   desce nding  sort, get frequ ent item table L. (2) To  create the FP -tree to  the root node, labe led  as null " ag ai n to scan the  databa se, in  the D T ran  s ea ch tra n saction exe c ut es the follo wi ng  operation: ".  Extraction  of T ra n s freq u ent item a nd  pre s s L  ord e r so rting. To  sort after f r eq u ent  item table fo r [P P], where  p is the first  elemen t, a n d  P is th e rem nant of the  el ements of a  list.  Call the in SERT tree  ( [P P ], T ).   STL provide s  a  seri es of  cont aine rs an d  template  alg o rithm,  combi n ing th ese  co ntainers  and  algo rith ms  can  a c hie v e a vari ety of utility func t i on. At the p o int of  chai n  stru cture  will  link  them to have  the same ite m  _ nam e n ode. If the  P is not empty, _ recursive i n vocatio n  of in  SERT tree (P, N). Analys is : FP -tree c o ns truc tion  process of tran sa ction d a taba se scan  two  times, finally the databa se  comp re ssi on  storag e  into a tree, the tree co ntains f r equ ent patte rn  mining all th e informatio n .  FP-tree usually fo r long  mode and i n tensive d a taba se with h i gh  comp re ssion  ratio, but with  a larg e num ber of  sho r t p a ttern data b a s e  comp re ssi on pe rform a n c e   is su peri o r.       Figure 2. The  Apriori an d F P -Growth Me thods      In the FP-G ro w alg o rithm, t he main  data  st ru cture in cl ude s Item, Xiang T oubia o   Hea der  and FP  2 tree . Item head er table  and  FP-tree  elem ent , a sto r ag e  structu r e  by d e f ining a  cla s s  to  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  4071 – 40 78   4076 encap sulate t he related  Item data  mem bers, in cludi n g  a item  nam  e _, n ode  ch ain no de_  lin k,  sup po rt_ co un t suppo rt cou n t, the parent nod e ch ain parent t_ link and CH ILD child no de   chai n _ lin k, o ne child n ode  chai n for  set  contai ner  poi nter types. Ite m head er ta bl e is o ne by th e   sup port  cou n t  in descen d i ng order li ne ar table, d a ta  membe r s i n clud e item na me, calle d th e  _   node  chai n n ode_ lin k, as i s  sh own by Figure 2.   Therefore  th e existen c e   of Aprio r i alg o rith m i s   with the  same   defect. Aimin g  at the  defect s  of  th e Apri ori  alg o rithm, the  p r opo se d a   ki nd of  not  ge neratin g  can d idate ite m   set  algorith m  of FP-Growth, to avoi d the h i gh co st of candid a te item sets g ene rati on, fewe r, more   efficient scan ning. The r e is a numbe r of FP-Growt h al gorithm s ba sed multi level asso ciation rule   mining al gorit hm, the algo rithm in different deg r ee a nd improves  the mining ef ficien cy [9].  But  most of th ese alg o rithm s   can  only a c h i eve a laye r  within th e mi ning, u nable   to find differe nt  con c e p tual le vel asso ciatio ns am ong th e data it em s;  and some al gorithm ca n  realize  the cro ss  level mining, but it can not reflect the con c ept  hi era r chy of intrinsi c co nstraints rel a tion s,   resulting in th e FP heade r betwe en com p lex, can  effe ctively simplify the proce ss of mining.  Weig hted a s so ciation  rule s propo se d b y  Apriori al go rithm in mini ng freq uent it emset s   whe n  there a r e actu ally two  big hypoth e sis of the  ol d t: (1)  Of ea ch it em in the  dat aba se  with th e   same  natu r e  and fun c tion,  i.e. the sa me.  (2 ) Th e im p o r tance of  ea ch item in th e  databa se  of the  distrib u tion is uniform that is the freque ncy of oc currence of the same or simil a r [10]. Howev e r,  in reality worl d databa se o f  more than two hy pothe ses are not establis h ed. Wh en the datab ase   is in proj ect  of uneven di stributio n of frequ en cy  differen c e i s  larger, will cau s e the minimum   sup port  deg ree is hig h  wit h  low have  problem s in  t w o chess  su rfa c e, if  set too  high, the  mini ng  asso ciation  rules m a y not  involve sho w ed a lo we r  fre quen cy of pro j ect, as i s   sho w n by Equ a tion  (7).     ) 1 /( ] ) 4 / 1 ( ) 4 / 2 [( 2 2 ) ( 1 1 2 / 1 2 / 1 2 1 j j j X c df cf v j j                                                                                  (7)     In ord e r to  overcome th e  shortcomin gs  of Ap rio r i alg o rithm,  some  schola r s prop ose d  th e   mining of wei ghted a s soci ation rule s al gorithm, for e a ch item were weig hted, e ffective intere st to  solve the p r oject in the  databa se  with different  importan c e  to discu ss and analy s is of  rep r e s entativ e weig hted a s soci ation rul e s minin g  alg o rithm nam ed  New-Apri ofi algorith m .  Weig hted su pport mea s u r e is defined,  combi ned  with this algorith m , an improv ed Ne w- Apriori al go rithm is put forward, in whi c h the  item set  X weighted suppo rt mea s u r e is defin ed  as:  swoop  ( X  ) =max{hi, hE, h k }X ',  su p  ( X  ), where hi  is  ij wei ghts  [11] . Ne w, Apri ori  algo rithm  an d  OD alg o rithm  of Ap. Same idea, reali z e d  by tw o step s : first find all weighte d  su pport d egree  is  no less than  a user  spe c ified minimu m weighte d  sup port wmi n su p con s tra i nt all weight ed  freque nt itemsets, de noted  as L, then use a wei ghte d  freque nt itemset s  satisfyi ng the minim u m  weighted reli ability constraint of wminco nf all weighted association  rules.  In the minin g  of weighte d  asso ciatio n  ru le s al gorit hm New.Ap ri ori al gorithm  is the   cla ssi c  algo ri t h m;  it  ca n  ef f e ct iv ely  b e  w e ighte d   asso ciation  rules minin g . Based  on  the  Ne w.Apfiofi algorithm to p r odu ce a la rge  numbe r of ca ndidate  set of  options  and repeate d  scan s  the origi nal  databa se  de fects a r e im proved,  thi s  pape r p r op ose s  a n  im proved  algo rithm  WARDM alg o r ithm. Finally throug h the si mulati on exp e rime nts vali date the WA RDM al go rith m.      4.  Ne w  Alg o rithms  of Weigh t ed Associa t ion  Rules  Bas e d  on Aprior i and FP-Gr o w t h  Metho d s  Mining frequ ent itemsets  is the  cla s sical algo rithm  Apriori  algo rit h m an d FP - gro w th   algorith m . M o st oth e r alg o rithm s  a r e  the two  al gorithm varia n ts. Cla ssi c  alg o rithm  ha s t w o   default a s su mptions: th e  databa se  of  each item  i n   the same  dat aba se  and th e impo rtan ce  of  each item in  the distrib u tion is unifo rm , the frequen cy of occurre n ce of the  same or  simil a r.  Therefore, cl assical algo ri thm is equal  to the  consi s tent way of dealin g with databa se in t h e   databa se  proj ect. Ho weve r the actu al sit uation i s  not  the ca se, the  importa nce  of not the sa me   and un even  distrib u tion. In orde r to so lve the  first proble m , re se arche r s p u t forward wei g h t ed  asso ciation rules al gorith m .  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The Ne w Alg o rithm s  of Weighted Asso ciation  Rule s  Based o n  Apriori and … (Ti ng Liu)  4077 A priori  algo ri thm there  are  two maj o r p r em ise  hypoth e se s: 1 )  Data base items th e sa me   importa nce; 2 )  Databa se  of  ea ch item  in  the di st ributio n is unifo rm, t he fre que ncy  of the  same  o r   simila r. Howe ver, in the real worl d data base is  often  not so [12].  Whe n  the da tabase is in the  proje c t i s  n o t  uniform  in  distribution, freq uen cy differe nce  is large r ,  will le ad to  su pport  deg re e  of  rea s on able  setting, if high, discovere d  asso ci ation  rules mi ght  not involve sho w e d  a lo wer  freque ncy of proje c t, as is  sho w n by Eq uation (8 ).      ) , 0 ( 2 )) 0 ( ( )] , 0 ( ) 0 ( ) , 0 ( [ 2 1 ) , 1 ( 2 k x A I k x A k x x k                                                             (8)     The cu rre nt data  mini ng resea r ch  focus. With  wei ghting  a s so ci ation  rule s mining  i s   calle d weig ht ed asso ciatio n rule s minin g . Since  199 8, weighte d  asso ciation rule mining h a s   received exte nsive attentio n and stu d y, in the mi ning of weighte d  asso ciation  rules al go rithm   resea r ch at home and a b road, a lot of result s.   This p ape r a nalyze s  the  without ge nerati ng ca ndid a t e set dire ctly to generate freque nt  pattern  alg o rithm for FP  2Gro w th, its b a si c idea  is to the  e n tire  datab ase comp re ssi o n   rep r e s ente d   as tree  stru cture of FP  2 t ree, fr e quen t pattern mi n i ng p r o c e ss i n to re cu rsively  gene rating  co ndition s and  con d ition s  of sub Li brary  o f  FP 2tree, P Rio RI pe rfo r man c e  relati ve  to A seri es al gorithm  ha s a  larger imp r o v e. Be ca use  FP 2G ro w th   algorith m  d a ta st ru cture  u s ed  to achi eve m o re  com p lex, has certain   difficult y, and  obje c t-o r ient ed p r og ramm ing lan gua ge  C+  + the  STL  st anda rd te mpl a te library, wherei n the  d a ta structu r e  and  algo rith m for  pro g ra m  provide s   po werful  tool s. The FP  2 G ro w th al g o rithm d e scri p tion an d a nalysi s , and  then  discu s ses its  reali z ation m e thod.   In order to fu lly refle c t the  wei ghted  a s so ciation  rule s ta ke s  adva n tage  of a n   efficient  algorith m . Th e wei ghted  p r ocess  ca n n o t only di stin guish the im portant  deg re e of the mi ni ng  proje c t an d the re sult s be come m o re reasona ble,  a nd in some  case s al so  ca n gre a tly improve  the efficien cy of the algorith m , redu ce mi ning we ighte d  asso ciation  rule s re qui red  time. Becau s e   in the a s so ci ation rule s correlation  alg o rithm  to ge nerate   freq u ent  item sets,  stage will cost  algorith m ’s ru nning time.   The m a in  wo rks  are  a s  fo llows: the  Web d a ta mi ni ng a s so ciatio n rule s a nd  weig hted   asso ciation  rule theo ry is  studie d . For  a variet y of weig hted a s sociatio n rul e s algorithm fo r in- depth  re sea r ch, fo cu sing  on  analy s is of the  prop ose d  Apfiofi  algorith m  for the  Ne w.Ap fiofi  algorith m  time com p lexity is too hig h  an d the  numb e r of candi date  itemset s  exce ssive  sho r tag e ,  is  b a sed on   the  two pru n i ng  al go rithm WARDM,  giv e s th e  relate d theo rem  an d its proof, u s in g   synthetic d a ta sets TIO,  wIOOK an d T 4011 0D1 00K experim ent, and the analysi s  of  experim ental  result s. Experim ental a nalysi s  of environm ent: CPU Intel PE, 1GB memory,  Wind ows X P  operating  system ; al gorithm  usi n g Java l ang uage, in E c lipse  deb ug ging  developm ent platform.           Figure 3. The  Weighte d  Asso ciation  Rul e s Based on  Apriori a nd F P -Growth Me thods    Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  4071 – 40 78   4078 The pa pe r p u ts forwa r d t he ne w al gorithm s of  wei ghted a s so ci ation rul e s  b a se d on  Apriori  a nd  FP-Growth   method s. Alg o rithm i n  th e  ca ndid a te it em  sets Ck,  Lk.1  p r uni n g , to   reduce to  connect frequency (k.1 ). Thi s  reduce s the com b inatorial possi bilities, whi c h  reduce  circulatin g ju dgment time s, thereby re duci ng th e  conne cting  op eration,  and  to red u ce th e Ck  option set qu antity, improve the efficien cy of t he alg o rithm. If the large  datab ase  of the time   spe ndin g  on  data mining e fficiency is ve ry obvious.   The expe rime nts sh ow that  the algorithm  c an effective l y avoid singl e sup port s  mi nimum   weig hted su p port set too l o w num ber o f  rules is too  large a nd too  high can n o t effectively th e  probl em of  mining a s so ciation rule s.  The expe rim ental re sult s sho w  that, unde r the sa me   minimum wei ghted su ppo rt  thre shold   condition s,  the  WA RDM  alg o rithm  of wei ghted frequ e n t  itemset s  num ber le ss than  New.Apfiofi algorit h m ; WARDM alg o rit h m to generate a weight ed   freque nt itemsets u s in g time is less th an Ne w.Apfio f i algorithm: WARDM alg o rithm ha s g ood  stability and  expan sibility, in larg e am ou nts of d a ta  mi ning i s  mo re  high effici en cy. Therefo r e t he  WARDM alg o r ithm ha s better pe rform a n c e than  Ne w.Apfiofi algorit hm.      5. Conclusio n   The a s sociati on rule s in d a ta mining te chn o logy e s p e cially the weighted a s so ciation   rule s of the  system, com p reh e n s ive, detailed  a nal ysis an d re search, an d h a s ma de  certain  achi evement s. The  pap er  puts fo rward   the ne w al g o rithms of  weig hted a s soci ation rules ba sed   on Ap riori  an d FP-G ro wth  method s. In  orde r to  i m prove the frequ ent itemsets  gene rated  lay e r- wise efficie n cy, uses the  Apriori  prope rty to re d u ce  the search  spa c e. At th e sa me time,  the   algorith m   kee p s th e A P R  I O  RI  algo rith m of ex celle n t  pro pertie s , h a s  better time  co mplexity a nd  spa c e  com p l e xity. The experim ental re sults  sh ow  th at the perfo rmance of H a l gorithm, FP-gro w  faster than   Apriori  alg o ri thm by a n   orde r  of ma gnitude,  alth ough  freq ue nt pattern m i ning  algorith m  for some n on de nse d a taba se  is very effective.      Referen ces   [1]    Moham ad F a r han M o h a mad  Mohsi n , Moh d  He lm y  Ab d  W ahab, M ohd  F a iruz Z a i y ad i, Cik F a zi l a h   Hiba d u lla h. An  Investig ation  i n to Influ ence  Factor  of Stud e n t Programm i n g  Grade  Usi n g  Associati o n   Rule Mi ni ng.  AISS . 2010; 2(2):  19 ~  27.  [2]    Guo Hon g ji an.  A Novel F r eq uent Item-set Minin g  Metho d  based  on F r e que nt-pattern  List.  JDCTA .  201 1; 5(11): 18 2 ~  188.  [3]      Xia o ke  W u ,  Xi ongfe i   Li. Mi ni ng M a xima l F r equ ent S ubtre es b a se d o n  F u sio n  C o mpr e s s ion  an d F P - tree.  JDCTA .   201 1; 5(7): 191  ~  200.  [4]    Li Guod on g, Xia Ke w e n. An Improved D a ta  Mining T e chni que C o mbi n e d  Apriori Alg o rit h m  w i t h  Ant  Colo n y  Alg o rith m and its Appl i c ation.  JDCTA .  2011; 5(8): 2 4 1  ~  249   [5]    T H AIR A SAL IH. Performan c e Anal ys is of  Chaot ic C h ir p Sprea d  Spe c trum S y stem  in Multip ath   Enviro nment.  Journ a l of T heor etical a nd Ap pli ed Infor m atio n  T e chno logy . 2 010; 18( 2): 101 -108.   [6]    Usman B aba wuro, Zou Be iji.  Kno w l e d ge R epres entati on:  A Genera l  S u rve y  a nd T e chni ques for   Soun d Kno w l e dge Bas ed S y s t ems.  IJI I P . 2011; 2(4): 16 ~  22.  [7]    Mingc han g Li u, He w a ng L i u.  Rese arch o n  Applic atio n of Associati on R u le  Minin g  in C h in ese Athl ete s ’   Nutritio nal a nd  Bioch e mica l Inde xes Mo nitori ng.  JDCTA . 20 12; 6(7): 17 4 ~   180.   [8]    Cha ngj ian g   Li,  Xi anfe n g  Yan g .  T he Researc h  of  Recomm e ndati on S y ste m s  in E-Comm erce  B a sed   o n   Associati on Ru le Improve d -Ap r iori Alg o rithms .  IJACT . 2012; 4(21): 35 4 ~  36 1.  [9]    YiJie C h e n . T he Dev e lo pme n t  of the Comm odit y   F l o w   An a l y s is S y stem B a sed On Ass o ciatio n Ru le  Mining.  IJACT . 2012; 4(1 3 ): 4 30 ~  436.   [10]    CH Ca i, W C  F u  Ada, CH  Ch eng,  W W  K w o ng. Mini ng  ass o ciati on ru les  w i t h   w e ig hted i t ems. Proc. of  the Int’l  Data ba se Engi ne erin g  and App lic atio ns Symp osi u m . 1998; 68 ~ 77.   [11]    Char u C Agar w a l, Phil ip S Y u .  A  New   F r amew ork for Itemset Gen e rati on . Procee di n g s of  the 17th  ACM SIGACT -SIGMOD-SIGART  Sympos iu m on Pri n ci ple s  of Database  Systems (POD S ’ 98)  Seattle,   W a shin gton. ACM Press Publ isher. 19 98; 18 ~ 24.  [12]    Song YQ, Z hu YQ, Sun Z H ,  Che n  G. An algorit hm a nd its  updati ng a l gor ithm  base d  on  F P -T ree for   minin g  ma xim u m frequent ite m sets.  Journal of  Softw are . 2003; 14(9): 1 586 -159 2.         Evaluation Warning : The document was created with Spire.PDF for Python.