Tujuan Pembelajaran

Mahasiswa dapat menganalisis, menginterpretasikan data dan informasi serta mengambil keputusan yang tepat berdasarkan pendekatan analisis asosiasi (CPMK1, CPMK2, KUE, KKB). - Analisis Afinitas - Algoritma Apriori di R Studio - Pertumbuhan FP di R Studio

Algoritma FP Growth

Algoritma yang sama dengan Apriori, FP-Growth mulai dengan menghitung item tunggal sesuai dengan jumlah kemunculan item yang ada didalam dataset. Setelah proses penghitungan selesai maka akan dibuat struktur pohon pada tahap kedua. Pohon yang dibuat mulanya kosong yang nanti akan diisi dengan hasil dari dataset yang telah didapat sebelumnya. Kunci untuk mendapatkan struktur pohon yang bisa didapatkan dengan proses lebih cepat untuk mencari item set yang besar menjadi sedikit dengan di urutkan secara descending dari frekuensi yang ada dataset tersebut. Masing-masing item yang tidak mencapai kebutuhan minimum dari threshold tidak dimasukkan kedalam pohon, tapi dikeluarkan secara efektif dari dataset.

FP-Tree merupakan struktur penyimpanan data yang dimampatkan. FP- Tree dibangun dengan memetakan setiap data transaksi ke dalam setiap lintasan tertentu dalam FP-Tree. Karena dalam setiap transaksi yang dipetakan, mungkin ada transaksi yang memiliki item yang sama, maka lintasannya memungkinkan untuk saling menimpa. Semakin banyak data transaksi yang memiliki item yang sama, maka proses pemampatan dengan struktur data FP-Tree semakin efektif. Kelebihan dari FP-Tree adalah hanya memerlukan dua kali pemindaian data transaksi yang terbukti sangat efisien. Adapun FP-Tree adalah sebuah pohon dengan definisi sebagai berikut: a. FP-Tree dibentuk oleh sebuah akar yang diberi label null, sekumpulan berupa pohon yang beranggotakan item-item tertentu, dan sebuah tabel frequentheader. b. Setiap simpul dalam FP- Tree mengandung tiga informasi penting, yaitu label item, menginformasikan jenis item yang direpresentasikan simpul tersebut, support count, merepresentasikan jumlah lintasan transaksi yang melalui simpul tesebut, dan pointer penghubung yang menghubungkan simpul-simpul dengan label item sama antar-lintasan, ditandai dengan garis panah putus-putus.

Tahapan Algoritma FP Growth

Algoritma FP-Growth Proses perhitungan association rule terdiri dari beberapa tahap adalah sebagai berikut :

  1. Membuat Header Item Header dalam hal ini selain sebagai header suatu item ke FP-Tree juga sebagai jenis item dasar yang memenuhi minimum support. Setelah mendapatkan item dan nilai support-nya, maka item yang tidak frequent dibuang dan item diurutkan berdasarkan nilai support-nya. Header untuk item, disiapkan pada suatu array tertentu dan ditambahkan ketika membuat FP-Tree.

  2. Membuat FP-Tree FP-Tree dibangun dengan mencari item sesuai urutan pada item yang frequent. Data transaksi tidak perlu diurutkan, dan untuk tiap item yang ditemukan bisa langsung dimasukkan ke dalam FP-Tree. Sesudah membuat root, tiap item yang ditemukan dimasukkan berdasarkan path pada FP-Tree. Jika item yang ditemukan sudah ada, maka nilai supportitem tersebut yang ditambahkan. Namun jika path belum ada, maka dibuat node baru untuk melengkapi path baru pada FP-Tree tersebut. Hal ini dilakukan selama item pada transaksi masih ada yang qualified, artinya memenuhi nilai minimum support. Jadi, item-item yang ditemukan dalam transaksi akan berurutan memanjang ke bawah. Dalam struktur FP-Tree, diterapkan alur path dari child hingga ke root. Jadi, suatu path utuh dalam FP-Tree adalah dari child terbawah hingga ke root. Tiap node pada FP-Tree memiliki pointer ke parent, sehingga pencarian harus dimulai dari bawah.

  3. Pattern Extraction Pattern extraction dilakukan berdasarkan keterlibatan item pada suatu path. Di setiap path, diperiksa semua kombinasi yang mungkin dimana item tersebut terlibat. Di iterasi berikutnya dilakukan dengan melibatkan item berikutnya, tanpa melibatkan item sebelumnya, sehingga pattern yang sama tidak akan ditemukan dua kali pada path yang sama. Bila item pertama suatu hasil kombinasi bukan item terakhir sebelum root, maka kombinasi itemset tersebut masih bisa dikembangkan lagi.

  4. Memasukkan setiap pattern yang ditemukan ke dalam PatternTree Setelah mengolah FP-Tree menjadi pattern-pattern, diperlukan proses akumulasi pattern-pattern yang ditemukan mengingat pattern yang sama dapat ditemukan pada path yang berbeda. Untuk itu digunakan struktur data Pattern Tree lihat Gambar 2.5. Setiap node di Pattern Tree merepresentasikan dan menyimpan frekuensi suatu pattern. Pattern Tree terdiri atas Pattern TreeNode yang menyimpan nilai item, nilai support dan dilengkapi dengan dua pointer yaitu untuk horisontal dan vertikal. Misalnya pada node d:1 di atas, berarti terdapat pattern a-c-d bernilai support 1. Kemudian bila ada pattern a-c-d lagi bernilai support n yang ditemukan dari FP-Tree maka nilai support 1 tersebut menjadi n+1. Contoh hasil lengkap dari PatternTree tersebut: 1. a:5 menggambarkan bahwa ada pattern a sebanyak 5 2. b:4 menggambarkan bahwa ada pattern a-b sebanyak 4 3. c:4 menggambarkan bahwa ada pattern a-b-c sebanyak 4 4. d:3 menggambarkan bahwa ada pattern a-b-c-d sebanyak 3 5. c:2 menggambarkan bahwa ada pattern a-c sebanyak 2 6. d:1 menggambarkan bahwa ada pattern a-c-d sebanyak 1 7. d:3 menggambarkan bahwa ada pattern a-d sebanyak 3

  5. Mengurutkan dan Menyeleksi Pattern Gambar 2. 4 Pattern Tree Pattern yang tidak memenuhi minimum support, dihapus dari daftar pattern. Pattern-pattern yang tersisa kemudian diurutkan untuk memudahkan pembuatan rules.

Eksperimen Algoritma FP GRowth

Loading DATA

library(arules)
## Loading required package: Matrix
## 
## Attaching package: 'arules'
## The following objects are masked from 'package:base':
## 
##     abbreviate, write
library(arulesViz)
library(grid)
data(Groceries)
class(Groceries)
## [1] "transactions"
## attr(,"package")
## [1] "arules"
inspect(head(Groceries, 3))
##     items                 
## [1] {citrus fruit,        
##      semi-finished bread, 
##      margarine,           
##      ready soups}         
## [2] {tropical fruit,      
##      yogurt,              
##      coffee}              
## [3] {whole milk}

Item Yang Sering Muncul

frequentItems <- eclat (Groceries, parameter = list(supp = 0.07, maxlen = 15)) # calculates support for frequent items
## Eclat
## 
## parameter specification:
##  tidLists support minlen maxlen            target  ext
##     FALSE    0.07      1     15 frequent itemsets TRUE
## 
## algorithmic control:
##  sparse sort verbose
##       7   -2    TRUE
## 
## Absolute minimum support count: 688 
## 
## create itemset ... 
## set transactions ...[169 item(s), 9835 transaction(s)] done [0.01s].
## sorting and recoding items ... [18 item(s)] done [0.00s].
## creating sparse bit matrix ... [18 row(s), 9835 column(s)] done [0.00s].
## writing  ... [19 set(s)] done [0.00s].
## Creating S4 object  ... done [0.00s].
inspect(frequentItems)
##      items                          support    count
## [1]  {other vegetables, whole milk} 0.07483477  736 
## [2]  {whole milk}                   0.25551601 2513 
## [3]  {other vegetables}             0.19349263 1903 
## [4]  {rolls/buns}                   0.18393493 1809 
## [5]  {yogurt}                       0.13950178 1372 
## [6]  {soda}                         0.17437722 1715 
## [7]  {root vegetables}              0.10899847 1072 
## [8]  {tropical fruit}               0.10493137 1032 
## [9]  {bottled water}                0.11052364 1087 
## [10] {sausage}                      0.09395018  924 
## [11] {shopping bags}                0.09852567  969 
## [12] {citrus fruit}                 0.08276563  814 
## [13] {pastry}                       0.08896797  875 
## [14] {pip fruit}                    0.07564820  744 
## [15] {whipped/sour cream}           0.07168277  705 
## [16] {fruit/vegetable juice}        0.07229283  711 
## [17] {newspapers}                   0.07981698  785 
## [18] {bottled beer}                 0.08052872  792 
## [19] {canned beer}                  0.07768175  764
itemFrequencyPlot(Groceries, topN=10, type="absolute", main="Item Frequency") # plot frequent items

Aturan Rekomendasi Produk

rules <- apriori (Groceries, parameter = list(supp = 0.001, conf = 0.5)) # Min Support as 0.001, confidence as 0.8.
## Apriori
## 
## Parameter specification:
##  confidence minval smax arem  aval originalSupport maxtime support minlen
##         0.5    0.1    1 none FALSE            TRUE       5   0.001      1
##  maxlen target  ext
##      10  rules TRUE
## 
## Algorithmic control:
##  filter tree heap memopt load sort verbose
##     0.1 TRUE TRUE  FALSE TRUE    2    TRUE
## 
## Absolute minimum support count: 9 
## 
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[169 item(s), 9835 transaction(s)] done [0.01s].
## sorting and recoding items ... [157 item(s)] done [0.00s].
## creating transaction tree ... done [0.00s].
## checking subsets of size 1 2 3 4 5 6 done [0.03s].
## writing ... [5668 rule(s)] done [0.00s].
## creating S4 object  ... done [0.01s].
rules_conf <- sort (rules, by="confidence", decreasing=TRUE) # 'high-confidence' rules.
inspect(head(rules_conf)) # show the support, lift and confidence for all rules
##     lhs                      rhs                    support confidence    coverage     lift count
## [1] {rice,                                                                                       
##      sugar}               => {whole milk}       0.001220132          1 0.001220132 3.913649    12
## [2] {canned fish,                                                                                
##      hygiene articles}    => {whole milk}       0.001118454          1 0.001118454 3.913649    11
## [3] {root vegetables,                                                                            
##      butter,                                                                                     
##      rice}                => {whole milk}       0.001016777          1 0.001016777 3.913649    10
## [4] {root vegetables,                                                                            
##      whipped/sour cream,                                                                         
##      flour}               => {whole milk}       0.001728521          1 0.001728521 3.913649    17
## [5] {butter,                                                                                     
##      soft cheese,                                                                                
##      domestic eggs}       => {whole milk}       0.001016777          1 0.001016777 3.913649    10
## [6] {citrus fruit,                                                                               
##      root vegetables,                                                                            
##      soft cheese}         => {other vegetables} 0.001016777          1 0.001016777 5.168156    10
rules_lift <- sort (rules, by="lift", decreasing=TRUE) # 'high-lift' rules.
inspect(head(rules_lift)) # show the support, lift and confidence for all rules
##     lhs                         rhs                  support confidence    coverage     lift count
## [1] {Instant food products,                                                                       
##      soda}                   => {hamburger meat} 0.001220132  0.6315789 0.001931876 18.99565    12
## [2] {soda,                                                                                        
##      popcorn}                => {salty snack}    0.001220132  0.6315789 0.001931876 16.69779    12
## [3] {flour,                                                                                       
##      baking powder}          => {sugar}          0.001016777  0.5555556 0.001830198 16.40807    10
## [4] {ham,                                                                                         
##      processed cheese}       => {white bread}    0.001931876  0.6333333 0.003050330 15.04549    19
## [5] {whole milk,                                                                                  
##      Instant food products}  => {hamburger meat} 0.001525165  0.5000000 0.003050330 15.03823    15
## [6] {other vegetables,                                                                            
##      curd,                                                                                        
##      yogurt,                                                                                      
##      whipped/sour cream}     => {cream cheese }  0.001016777  0.5882353 0.001728521 14.83409    10

Mengontrol Jumlah Aturan di Keluaran

rules <- apriori(Groceries, parameter = list (supp = 0.001, conf = 0.2, maxlen=3)) # maxlen = 3 limits the elements in a rule to 3
## Apriori
## 
## Parameter specification:
##  confidence minval smax arem  aval originalSupport maxtime support minlen
##         0.2    0.1    1 none FALSE            TRUE       5   0.001      1
##  maxlen target  ext
##       3  rules TRUE
## 
## Algorithmic control:
##  filter tree heap memopt load sort verbose
##     0.1 TRUE TRUE  FALSE TRUE    2    TRUE
## 
## Absolute minimum support count: 9 
## 
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[169 item(s), 9835 transaction(s)] done [0.00s].
## sorting and recoding items ... [157 item(s)] done [0.00s].
## creating transaction tree ... done [0.00s].
## checking subsets of size 1 2 3
## Warning in apriori(Groceries, parameter = list(supp = 0.001, conf = 0.2, :
## Mining stopped (maxlen reached). Only patterns up to a length of 3 returned!
##  done [0.01s].
## writing ... [9958 rule(s)] done [0.00s].
## creating S4 object  ... done [0.01s].
#summary of rules
summary(rules)
## set of 9958 rules
## 
## rule length distribution (lhs + rhs):sizes
##    1    2    3 
##    1  620 9337 
## 
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   1.000   3.000   3.000   2.938   3.000   3.000 
## 
## summary of quality measures:
##     support           confidence        coverage             lift        
##  Min.   :0.001017   Min.   :0.2000   Min.   :0.001118   Min.   : 0.8028  
##  1st Qu.:0.001220   1st Qu.:0.2439   1st Qu.:0.003762   1st Qu.: 1.8658  
##  Median :0.001627   Median :0.3077   Median :0.005287   Median : 2.3603  
##  Mean   :0.002554   Mean   :0.3452   Mean   :0.008272   Mean   : 2.6338  
##  3rd Qu.:0.002542   3rd Qu.:0.4194   3rd Qu.:0.008236   3rd Qu.: 3.0742  
##  Max.   :0.255516   Max.   :1.0000   Max.   :1.000000   Max.   :35.7158  
##      count        
##  Min.   :  10.00  
##  1st Qu.:  12.00  
##  Median :  16.00  
##  Mean   :  25.12  
##  3rd Qu.:  25.00  
##  Max.   :2513.00  
## 
## mining info:
##       data ntransactions support confidence
##  Groceries          9835   0.001        0.2
##                                                                               call
##  apriori(data = Groceries, parameter = list(supp = 0.001, conf = 0.2, maxlen = 3))
# Inspect rules
#inspect(rules)
#inspect top 5 rules by highest lift
inspect(head(sort(rules, by ="lift"),5))
##     lhs                               rhs                     support    
## [1] {bottled beer, red/blush wine} => {liquor}                0.001931876
## [2] {hamburger meat, soda}         => {Instant food products} 0.001220132
## [3] {ham, white bread}             => {processed cheese}      0.001931876
## [4] {bottled beer, liquor}         => {red/blush wine}        0.001931876
## [5] {Instant food products, soda}  => {hamburger meat}        0.001220132
##     confidence coverage    lift     count
## [1] 0.3958333  0.004880529 35.71579 19   
## [2] 0.2105263  0.005795628 26.20919 12   
## [3] 0.3800000  0.005083884 22.92822 19   
## [4] 0.4130435  0.004677173 21.49356 19   
## [5] 0.6315789  0.001931876 18.99565 12
# Visualization of rules
#Plotting rules
plot(rules)
## To reduce overplotting, jitter is added! Use jitter = 0 to prevent jitter.

# Two key plot
plot(rules , shading="order", control=list(main="two-key plot"))
## To reduce overplotting, jitter is added! Use jitter = 0 to prevent jitter.

RulesBev1 <- subset(rules, subset = rhs %ain% "soda")
summary(RulesBev1)
## set of 699 rules
## 
## rule length distribution (lhs + rhs):sizes
##   2   3 
##  64 635 
## 
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   2.000   3.000   3.000   2.908   3.000   3.000 
## 
## summary of quality measures:
##     support           confidence        coverage             lift      
##  Min.   :0.001017   Min.   :0.2000   Min.   :0.001322   Min.   :1.147  
##  1st Qu.:0.001220   1st Qu.:0.2390   1st Qu.:0.004067   1st Qu.:1.371  
##  Median :0.001627   Median :0.2807   Median :0.005592   Median :1.610  
##  Mean   :0.002408   Mean   :0.2994   Mean   :0.008989   Mean   :1.717  
##  3rd Qu.:0.002440   3rd Qu.:0.3415   3rd Qu.:0.009049   3rd Qu.:1.958  
##  Max.   :0.038332   Max.   :0.7692   Max.   :0.183935   Max.   :4.411  
##      count       
##  Min.   : 10.00  
##  1st Qu.: 12.00  
##  Median : 16.00  
##  Mean   : 23.68  
##  3rd Qu.: 24.00  
##  Max.   :377.00  
## 
## mining info:
##       data ntransactions support confidence
##  Groceries          9835   0.001        0.2
##                                                                               call
##  apriori(data = Groceries, parameter = list(supp = 0.001, conf = 0.2, maxlen = 3))
inspect(head(sort(RulesBev1, by ="lift"),5))
##     lhs                              rhs    support     confidence coverage   
## [1] {coffee, misc. beverages}     => {soda} 0.001016777 0.7692308  0.001321810
## [2] {pastry, misc. beverages}     => {soda} 0.001220132 0.6315789  0.001931876
## [3] {chicken, waffles}            => {soda} 0.001220132 0.5714286  0.002135231
## [4] {tropical fruit, canned beer} => {soda} 0.001728521 0.5666667  0.003050330
## [5] {bottled water, cake bar}     => {soda} 0.001016777 0.5555556  0.001830198
##     lift     count
## [1] 4.411303 10   
## [2] 3.621912 12   
## [3] 3.276968 12   
## [4] 3.249660 17   
## [5] 3.185941 10
plot(Groceries[1:30], method="graph")
## Warning in plot.itemMatrix(Groceries[1:30], method = "graph"): Use image()
## instead of plot().

plot(Groceries, method="paracoord")
## Warning in plot.itemMatrix(Groceries, method = "paracoord"): Use image() instead
## of plot().