aturan keterhubungan.ppt

7/23/2019 Aturan Keterhubungan.ppt

http://slidepdf.com/reader/full/aturan-keterhubunganppt 1/21

Association Rules

(Aturan Asosiasi)



Overview

• Masalah Association Rule

• Aplikasi• Algoritma Apriori

• Menentukan Association Rules

•



Association Rule Problem

• Dibarikan database transaksi:

• Menemukan semua association rules:



Applications

• Analisa keranjang pasar (Market Basket Analysis):terdapat database transaksi customer , dimana setiap transaksiadalah sekumpulan item/barang dengan tuuang menemukanserangkaian item dimana sering diberli sercara bersamaan

• Telecommunication• Medical Treatments



• I !"i1, i2, ###, in$: seluruh items/barang

• %ransaksi T : sekumpulan item sehinga T ⊆ I

• %ransaksi Database D: sekumpulan transaksi

• %ransaksi T ⊆ I berisi X ⊆ I dengan beberapa

item , ika X ⊆ T • Association Rule: adalah impliksi dari bentuk t X

⇒ Y , dimana X , Y ⊆ I

Association Rule De&initions



• 'ekumpluan items/barang dikenal dengan itemset# 'uatu

itemset (ang berisi k items din(atakan dengan k )itemset#

• Support s dari itemset X adalah percentase dari transaksi

dalam database transaksi D (ang berisi X #• 'upport dari rule X ⇒ Y dalam database transaksi D adalah

support dari items X ∪ Y dalam D#

• Confidence dari rule X ⇒ Y dalam databse transaksi D

adalah ratio atau perbandingan dari umlah transactions dalam D (ang berisi X ∪ Y terhadap umlah transaksi (ang berisi X

dalam D#

Association Rule De&initions



A

• Support : Suatu ukuran yang menunjukkan

seberapa besar tingkat dominasi suatu

item/itemset dari keseluruhan transaksi. Ukuran

ini akan menentukan apakah suatu item/itemset layak untuk dicari confidence-nya (misal, dari

seluruh transaksi yang ada, seberapa besar

tingkat dominasi yang menunjukkan bahwa item

A dan dibeli bersamaan! dapat juga digunakanuntuk mencari tingkat dominasi item tunggal



• Confidence : suatu ukuran yang

menunjukkan hubungan antar " item

secara conditional (misal, seberapa sering

item dibeli jika orang membeli item A!.



Association Rule Problem

• *iven:+ item)tiem I

+ Database D dari transaksi+ minimum support s

+ minimum con&idence c

• -ind:+ semua association rules X Y dengan minimum

support s dan con&idence c#



.# Mencari semua items (ang memiliki

minimum support &re0uent itemsets1

2# Menggunakan &re0uent itemsets untuk

menghasilkan rule)rule (ang diharapkan

2 3angkah penting44



%he Apriori Algorithm

• Karakteristik Frequent Itemset :

Himpunan bagian dari freuent itemset

dala! freuent"• Contrapositive:

If an itemset is not freuent# none of its

supersets are freuent"



-re0uent 5temset Propert(



%he Apriori Algorithm

• $k : 'atu set &re0uent itemsets ukuran k dengan min

support1

• % k : 'atu set calon itemset k potentiall( &re0uent itemsets1

$1 ! "&re0uent items$for k ! . $k 6!∅ k 771 do

% k&1 ! calon/itemset (ang dihasilkan dari $k

for each transaksi t dalam database do

"menghitung ban(akn(a kanditat dari masingdari itemset % k&1 (ang ada dalam transaksi t$

$k&1 ! kandidat dalam % k&1 dengan

min8support

return ∪k $k



%he Apriori Algorithm 9 ;ample

'can D

itemset sup.#$% "

#"% &

#&% &

#'% $

#(% &

% 1itemset sup.

#$% "

#"% &

#&% &

#(% &

$1

itemset sup

#$ &% "

#" &% "

#" (% &

#& (% "

$2

itemset sup

#$ "% $

#$ &% "

#$ (% $

#" &% "

#" (% &

#& (% "

% 2 itemset

#$ "%

#$ &%

#$ (%

#" &%#" (%

#& (%

% 2'can D

% ' itemset

#" & (%

'can D $' itemset sup

#" & (% "

)*+ *tems

$,, $ & '

",, " & (

&,, $ " & (

',, " (

Database D

Min support =50%



<agaimana untuk menentukan

kandidatInput: $i1 : satu set &re0uent itemsets ukuran i1

utput: % i :satu set kandidat itemset ukuran i

% i empt* set+

for setiap itemset , dalam $i1 do

for setiap itemset - dalam $i1 sehingga# -./ , do

if i2 dari element dalam , dan - sama then

if semua subsets dari " - ∪ , $ dlm $i1 then

% i % i ∪ " - ∪ , $

return % i



• $'"abc# abd# acd# ace# bcd $

• Menentukan % 0 dari $'

= abcd dari abc dan abd

= acde dari acd dan ace

• Pruning:

= acde dihapus karena ade tidak dalam $'

• % 0!"abcd $

>ontoh



Menemukan Rules

Misalkan ?)itemset "5., 52, 5@$:

5. ∧ 52 ⇒ 5@

5. ∧ 5@ ⇒ 52

52 ∧ 5@ ⇒ 5.

5. ⇒ 52 ∧ 5@

52 ⇒ 5. ∧ 5@

5@ ⇒ 5. ∧ 52



S&, ing /iu, U* $

Step ": 0enerating rules 1rom

1re2uent itemsets

• 3re2uent itemsets association rules

• 4ne more step is needed to generateassociation rules

• 3or each 1re2uent itemset X ,3or each proper nonempty subset A o1 X , 5 /et B 6 7 - A

5 A→ is an association rule i1 • on1idence(A→ ! 8 mincon1,

support(A→ ! 6 support(A∪! 6 support(7!

con1idence(A → ! 6 support(A ∪ ! 9 support(A!



$

0enerating rules: an e;ample

• Suppose #",&,'% is 1re2uent, with sup6< 5 =roper nonempty subsets: #",&%, #",'%, #&,'%, #"%, #&%, #'%, with

sup6<, <, ><, ><, ><, >< respecti?ely

5 )hese generate these association rules:

• ",& → ', con1idence6$<• ",' → &, con1idence6$<

• &,' → ", con1idence6@><

• " → &,', con1idence6@><

• & → ",', con1idence6@><

• ' → ",&, con1idence6@><

• All rules ha?e support 6 <



Alternative Measures &or Association

Rules

• %he confidence o& X ⇒ Y in database D is the ratio o& thenumber o& transactions containing X ∪ Y to the number o&transactions that contain X # 5n other words the con&idence is:

• <ut, when Y is independent o& X : pY 1 ! pY X 1# 5n this case i&

pY 1 is high weBll have a rule with high con&idence thatassociate independent itemsets6 -or e;ample, i& pCbu* milk 1 !EFG and Cbu* milk is independent &rom Cbu* salmon, then therule Cbu* salmon ⇒ Cbu* milk will have con&idence EFG6

11

1

1

1

1 X Y p X p

Y X p

D

X numTrans D

Y X numTrans

Y X conf =∧=

∪

=→



A

• A text document data set

doc $: Student, )each, School, ducation

doc ": Student, School, ducation

doc &: )each, School, ity, 0ame,ducation

doc ': aseball, asketball, Sportdoc : asketball, =layer, Spectator, Sport

doc @: aseball, oach, 0ame, )eam, Sport

doc >: asketball, )eam, ity, 0ame, SportB

minsup 6 "< and minconf 6 @<

)ugas : uat aturan keterkaitan ( association rules!

aturan keterhubungan.ppt

Documents