Maksimal & tertutup sering - Jawaban Termasuk

10

My  dataset:
1:A,B,C,E
2:A,C,D,E
3:     B,C,E
4:A,C,D,E
5:    C,D,E
6:    A,D,E

Saya ingin mengetahui set item sering maksimal dan set item sering tertutup .

  • Set item yang sering adalah maksimal jika tidak memiliki superset sering.XF
  • Set item yang sering X ∈ F ditutup jika tidak memiliki superset dengan frekuensi yang sama

Jadi saya menghitung terjadinya setiap set item.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

{A,B} = 1; {A,C} = 3; {A,D} = 3; {A,E} = 4; {B,C} = 2; 
{B,D} = 0; {B,E} = 2; {C,D} = 3; {C,E} = 5; {D,E} = 3

{A,B,C} = 1; {A,B,D} = 0; {A,B,E} = 1; {A,C,D} = 2; {A,C,E} = 3; 
{A,D,E} = 3; {B,C,D} = 0; {B,C,E} = 2; {C,D,E} = 3

{A,B,C,D} = 0; {A,B,C,E} = 1; {B,C,D,E} = 0

Min_Support disetel ke // Sangat penting. Terima kasih steffen untuk mengingatkan hal itu.50

Apakah maksimal = ?{A,B,C,E}

Apakah ditutup = ?{A,B,C,D} and {B,C,D,E}

Mike John
sumber

Jawaban:

5

Saya menemukan definisi yang sedikit diperluas dalam sumber ini (yang mencakup penjelasan yang baik). Berikut adalah sumber (diterbitkan) yang lebih andal: CHARM: Algoritma yang efisien untuk penambangan itemset tertutup oleh Mohammed J. Zaki dan Ching-jui Hsiao .

Menurut sumber ini:

  • Itemet ditutup jika tidak ada superset langsung yang memiliki dukungan yang sama dengan itemset
  • Set item maksimal sering jika tidak ada superset langsungnya sering


Beberapa komentar:

  • Hal ini diperlukan untuk mengatur min_support (dukungan = jumlah set item yang mengandung subset minat dibagi dengan jumlah semua itemet) yang mendefinisikan itemset mana yang sering . Set item sering terjadi jika dukungannya> = min_support.
  • Berkenaan dengan algoritma, hanya itemset dengan min_support dipertimbangkan ketika seseorang mencoba untuk menemukan itemset maksimal dan tertutup maksimal.
  • Aspek penting dalam definisi ditutup adalah, bahwa tidak masalah jika superset langsung ada dengan lebih banyak dukungan, hanya superset langsung dengan dukungan yang sama persis yang penting.
  • maximal frequent => closed => frequent, tetapi tidak sebaliknya.

Aplikasi untuk contoh OP

catatan:

  • Tidak memeriksa jumlah dukungan
  • Katakanlah min_support = 0,5. Ini terpenuhi jika min_support_count> = 3
{A} = 4; tidak ditutup karena {A, E}
{B} = 2; tidak sering => abaikan
{C} = 5; tidak ditutup karena {C, E}
{D} = 4; tidak ditutup karena {D, E}, tetapi tidak maksimal karena misalnya {A, D}
{E} = 6; ditutup, tetapi tidak maksimal karena misalnya {D, E}

{A, B} = 1; tidak sering => abaikan
{A, C} = 3; tidak ditutup karena {A, C, E}
{A, D} = 3; tidak ditutup karena {A, D, E}
{A, E} = 4; ditutup, tetapi tidak maksimal karena {A, D, E}
{B, C} = 2; tidak sering => abaikan
{B, D} = 0; tidak sering => abaikan
{B, E} = 2; tidak sering => abaikan
{C, D} = 3; tidak ditutup karena {C, D, E}
{C, E} = 5; ditutup, tetapi tidak maksimal karena {C, D, E}
{D, E} = 4; ditutup, tetapi tidak maksimal karena {A, D, E}

{A, B, C} = 1; tidak sering => abaikan
{A, B, D} = 0; tidak sering => abaikan
{A, B, E} = 1; tidak sering => abaikan
{A, C, D} = 2; tidak sering => abaikan
{A, C, E} = 3; sering maksimal
{A, D, E} = 3; sering maksimal
{B, C, D} = 0; tidak sering => abaikan
{B, C, E} = 2; tidak sering => abaikan
{C, D, E} = 3; sering maksimal

{A, B, C, D} = 0; tidak sering => abaikan
{A, B, C, E} = 1; tidak sering => abaikan
{B, C, D, E} = 0; tidak sering => abaikan
steffen
sumber
Tautan sumber rusak, hanya memberi tahu Anda. Dan ya min_support sangat penting, saya menggunakan .50
Mike John
1
Maaf untuk itu, sudah diperbaiki.
steffen
1
mengubah min_support = 0,5 <=> min_support_count = 3 dan mengubah aplikasi menjadi contoh yang sesuai.
steffen
Gunakan APRIORI, dan Anda dapat menghemat banyak penghitungan dan pembuatan itemet ...
Memiliki QUIT - Anony-Mousse
@ Anony-Mousse Saya tahu APRIORI ... Saya melangkahi itemset secara manual untuk menjelaskan konsep itemset tertutup dan maksimal sesering mungkin, karena ini adalah sumber kebingungan OP (IMHO).
steffen
1

Anda mungkin ingin membaca tentang algoritma APRIORI. Ini menghindari itemset yang tidak perlu dengan pemangkasan yang cerdas.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

B tidak sering, hapus.

Bangun dan hitung dua item (belum ada sihir, kecuali yang Bsudah keluar)

{A,C} = 3; {A,D} = 3; {A,E} = 4; 
{C,D} = 3; {C,E} = 5; {D,E} = 3

Semua ini sering terjadi (perhatikan bahwa semua itu Btidak mungkin sering terjadi!)

Sekarang gunakan aturan awalan. HANYA menggabungkan itemet dimulai dengan item n-1 yang sama. Hapus semua, di mana subset tidak sering. Hitung itemet yang tersisa.

{A,C,D} = 2; {A,C,E} = 3; {A,D,E} = 3; 
{C,D,E} = 3

Perhatikan bahwa {A,C,D}tidak sering. Karena tidak ada awalan bersama, tidak mungkin ada itemset yang lebih sering!

Perhatikan betapa sedikitnya pekerjaan yang saya lakukan!

Untuk itemset maksimal / tertutup, periksa subset / superset.

Perhatikan bahwa misalnya {E}=6, dan {A,E}=4. {E}adalah himpunan bagian, tetapi memiliki dukungan yang lebih tinggi, yaitu ditutup tetapi tidak maksimal. {A}juga tidak, karena tidak memiliki dukungan yang lebih tinggi daripada {A,E}, yaitu berlebihan .

Memiliki QUIT - Anony-Mousse
sumber