Scribd Logo
Upload

Welcome to Scribd!

  • 35 views

    Lecture Notes: Data and Text Mining

    Uploaded by

    Ajeng Dyahayu Windani
    The document discusses mining frequent patterns, associations, and correlations from data. It covers basic concepts like frequent itemsets and association rules. It also describes algorithms for finding frequent itemsets like Apriori and FP-growth. Apriori is an iterative algorithm that uses candidate generation to find frequent itemsets level by level. FP-growth avoids candidate generation by building a compact FP-tree structure to directly mine patterns from the data. Finding frequent itemsets is important for applications like market basket analysis and can reveal useful associations between items.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture Notes: Data and Text Mining

    Uploaded by

    Ajeng Dyahayu Windani
    35 views10 pages
    The document discusses mining frequent patterns, associations, and correlations from data. It covers basic concepts like frequent itemsets and association rules. It also describes algorithms for finding frequent itemsets like Apriori and FP-growth. Apriori is an iterative algorithm that uses candidate generation to find frequent itemsets level by level. FP-growth avoids candidate generation by building a compact FP-tree structure to directly mine patterns from the data. Finding frequent itemsets is important for applications like market basket analysis and can reveal useful associations between items.

    Original Title

    20200427151512_ISYS6333-LN4-W4-S5-R1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses mining frequent patterns, associations, and correlations from data. It covers basic concepts like frequent itemsets and association rules. It also describes algorithms for finding frequent itemsets like Apriori and FP-growth. Apriori is an iterative algorithm that uses candidate generation to find frequent itemsets level by level. FP-growth avoids candidate generation by building a compact FP-tree structure to directly mine patterns from the data. Finding frequent itemsets is important for applications like market basket analysis and can reveal useful associations between items.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    35 views10 pages

    Lecture Notes: Data and Text Mining

    Uploaded by

    Ajeng Dyahayu Windani
    The document discusses mining frequent patterns, associations, and correlations from data. It covers basic concepts like frequent itemsets and association rules. It also describes algorithms for finding frequent itemsets like Apriori and FP-growth. Apriori is an iterative algorithm that uses candidate generation to find frequent itemsets level by level. FP-growth avoids candidate generation by building a compact FP-tree structure to directly mine patterns from the data. Finding frequent itemsets is important for applications like market basket analysis and can reveal useful associations between items.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 10

    LECTURE NOTES

    Data and Text Mining

    Week ke - 4

    Mining Frequent Patterns, Associations, and


    Correlations: Basic Concepts and Methods

    ISYS6333 – Data and Text Mining


    LEARNING OUTCOMES

    LO 2: Using data mining models to solve problems by extracting knowledge from data

    OUTLINE MATERI :
    Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods
     Basic Concepts
     Frequent Itemset Mining Methods
     Apriori Algorithm with Python

    ISYS6333 – Data and Text Mining


    ISI MATERI

    1. Basic Concepts
    a. What Is Frequent Pattern Analysis?
    Frequent Pattern adalah itemset, subsequences, atau substructures yang muncul dalam
    kumpulan data dengan frekuensi tidak kurang dari batas yang ditentukan pengguna.

    b. Why Is Freq. Pattern Mining Important?


    Frek. pattern: Sifat intrinsik dan penting dari dataset
    Dasar terpenting dari Pattern mining:
    – Association, correlation, and causality analysis
    – Sequential, structural (e.g., sub-graph) patterns
    – Pattern analysis in spatiotemporal, multimedia, time-series, and stream data
    – Classification: discriminative, frequent pattern analysis
    – Cluster analysis: frequent pattern-based clustering
    – Data warehousing: iceberg cube and cube-gradient
    – Semantic data compression: fascicles
    – Broad applications

    c. Basic Concepts: Frequent Patterns


    Itemset: Satu set satu atau lebih item k-itemset X = {x1, ..., xk} (absolut) dukungan,
    atau, jumlah dukungan X: Frekuensi atau kemunculan itemet X (relatif) dukungan, s,
    adalah pecahan transaksi yang mengandung X (yaitu, probabilitas bahwa transaksi
    mengandung X). Itemet X sering terjadi jika dukungan X tidak kurang dari ambang
    batas menit

    d. Basic Concepts: Association Rules


    Temukan semua aturan X  Y dengan dukungan dan keyakinan minimum

    ISYS6333 – Data and Text Mining


    dukungan, s, kemungkinan bahwa transaksi mengandung X  Y
    confidence, c, conditional probability, probabilitas bersyarat bahwa transaksi
    memiliki X juga mengandung Y
    Let minsup = 50%, minconf = 50%
    Freq. Pat.: Beer:3, Nuts:3, Diaper:4, Eggs:3, {Beer, Diaper}:3

    e. Definition: Frequent Itemset


    1. Itemset
    a. A collection of one or more items
    i. Example: {Milk, Bread, Diaper}
    b. k-itemset
    i. An itemset that contains k items
    2. Support count ()
    a. Frequency of occurrence of an itemset
    b. E.g. ({Milk, Bread,Diaper}) = 2
    3. Support
    a. Fraction of transactions that contain an itemset
    b. E.g. s({Milk, Bread, Diaper}) = 2/5
    4. Frequent Itemset
    a. An itemset whose support is greater than or equal to a minsup threshold

    f. Definition: Association Rule


    Association Rule
    Ekspresi implikasi dari bentuk X  Y, di mana X dan Y adalah itemset
    Rule Evaluation Metrics
    – Support (s)
    Fraksi transaksi yang mengandung X dan Y
    – Confidence (c)

    ISYS6333 – Data and Text Mining


    Mengukur seberapa sering item dalam Y muncul dalam transaksi yang
    mengandung X

    g. Algorithms to find frequent pattern


    Apriori: menggunakan pendekatan generate-and-test - menghasilkan itemset kandidat
    dan tes jika mereka sering
     Generasi itemset kandidat mahal (baik dalam ruang maupun waktu)
     Penghitungan dukungan mahal
    o Pengecekan subset (secara komputasi mahal)
    o Beberapa pindaian Basis Data (I / O)
     FP-Growth: memungkinkan penemuan frequent itemset tanpa calon
    generasi. Dua langkah:
    o 1.Buat struktur data yang kompak yang disebut FP-tree, 2 melewati
    database
    o 2.extracts frequent itemsets secara langsung dari FP-tree, Lintasi
    melalui FP-tree

    2. Frequent Itemset Mining Methods


    Apriori adalah algoritma seminal yang diusulkan oleh R. Agrawal dan R. Srikant pada
    tahun 1994 untuk mining frequent itemset untuk aturan asosiasi Boolean [AS94b]. Nama
    algoritme didasarkan pada fakta bahwa algoritme menggunakan pengetahuan sebelumnya
    tentang properti itemset yang sering, seperti yang akan kita lihat nanti. Apriori menggunakan
    pendekatan iteratif yang dikenal sebagai pencarian tingkat-bijaksana, di mana k-itemset
    digunakan untuk mengeksplorasi .k C 1 / -itemet. Pertama, set 1-itemset yang sering
    ditemukan dengan memindai basis data untuk mengumpulkan hitungan untuk setiap item,
    dan mengumpulkan barang-barang yang memenuhi dukungan minimum.

    ISYS6333 – Data and Text Mining


    3. Apriori Algorithm with Python
    Problem: Retail stores are looking into the rules of association between six items, to find out
    which items are most often bought together so they can store items together to increase sales.

    ISYS6333 – Data and Text Mining


    ISYS6333 – Data and Text Mining
    SIMPULAN

    Penemuan pola, asosiasi, dan hubungan korelasi yang sering di antara sejumlah besar
    data berguna dalam pemasaran selektif, analisis keputusan, dan manajemen bisnis. Area
    aplikasi yang populer adalah market basket analysis, yang mempelajari kebiasaan membeli
    pelanggan dengan mencari itemset yang sering dibeli bersama (atau berurutan).
    Association rule mining terdiri dari temuan pertama frequent itemsets (set item, seperti A
    dan B, memenuhi ambang batas dukungan minimum, atau persentase tupel tugas yang relevan),
    dari mana aturan asosiasi yang kuat dalam bentuk A) B dihasilkan. Aturan-aturan ini juga
    memenuhi ambang batas keyakinan minimum (yang ditentukan sebelumnya probabilitas
    memuaskan B di bawah kondisi bahwa A puas). Asosiasi dapat dianalisis lebih lanjut untuk
    mengungkap aturan korelasi, yang menyampaikan korelasi statistik antara itemsets A dan B.
    Banyak algoritma yang efisien dan skalabel telah dikembangkan untuk frequent itemset
    mining, dari mana aturan asosiasi dan korelasi dapat diturunkan. Algoritma ini dapat
    diklasifikasikan ke dalam tiga kategori: (1) Apriori-like algorithms, (2) frequent
    pattern growth–based algorithms such as FP-growth, and (3) algorithms that use the
    vertical data format.
    Apriori algorithm adalah algoritma seminal untuk mining frequent itemset untuk aturan
    asosiasi Boolean. Ini mengeksplorasi properti penambangan bijak tingkat Apriori itu semua
    subset tidak mengikat dari frequent itemset juga harus sering. Pada k iterasi k (untuk k ≥ 2), ia
    membentuk kandidat k-itemset yang sering berdasarkan pada .k - 1 / -itemsets, dan memindai
    database sekali untuk menemukan set lengkap k-itemsets, Lk.
    Frequent pattern growth adalah metode penambangan frequent itemset tanpa calon
    generasi. Ini membangun struktur data yang sangat kompak (sebuah FP-pohon) untuk
    mengompres database transaksi asli. Berarti daripada menggunakan strategi generate-and-test
    dari metode Apriori, itu berfokus pada pola yang sering (fragmen) pertumbuhan, yang
    menghindari generasi kandidat yang mahal, menghasilkan efisiensi yang lebih besar.

    ISYS6333 – Data and Text Mining


    Mining frequent itemsets menggunakan format data vertikal (Eclat) adalah metode yang
    mengubah set data tertentu dari transaksi dalam format data horizontal TID itemset ke dalam
    format data vertikal dari set item-TID. Ini tambang data yang berubah ditetapkan oleh TID
    mengatur persimpangan berdasarkan properti Apriori dan teknik optimasi tambahan seperti
    diffset.
    Tidak semua aturan asosiasi yang kuat menarik. Oleh karena itu, kerangka kerja
    dukungan-kepercayaan harus ditambah dengan ukuran evaluasi pola, yang mempromosikan
    penambangan aturan yang menarik. Ukuran adalah null-invariant jika nilainya bebas dari
    pengaruh null-transactions (yaitu, transaksi yang tidak mengandung salah satu itemset yang
    sedang diperiksa). Di antara banyak langkah-langkah evaluasi pola, kami memeriksa angkat,
    χ2, all confidence, max confidence, Kulczynski, dan cosine, dan menunjukkan bahwa hanya
    empat yang terakhir yang nol-invariant. Ukuran Kulczynski, bersama dengan rasio
    ketidakseimbangan, untuk menyajikan pola hubungan antar itemset.

    ISYS6333 – Data and Text Mining


    DAFTAR PUSTAKA

    Han, J., Kamber, M., & Pei, Y. (2012). Data Mining: Concepts and Techniques. 03.
    Morgan Kaufmann Publishers. San Fracisco. ISBN: 978-0123814791.

    ISYS6333 – Data and Text Mining

    You might also like