Maximal & häufig geschlossen - Antwort enthalten

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

Ich möchte die maximal häufigen Objektgruppen und die geschlossenen häufigen Objektgruppen herausfinden .

  • Die häufige Objektmenge ist maximal, wenn keine häufigen Obermengen vorhanden sind.XF
  • Die häufige Objektmenge X ∈ F wird geschlossen, wenn keine Obermenge mit derselben Frequenz vorhanden ist

Also habe ich das Vorkommen jedes Item-Sets gezählt.

{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 auf // Sehr wichtig. Danke steffen, dass du daran erinnert hast.50

Ist maximal = ?{A,B,C,E}

Hat geschlossene = ?{A,B,C,D} and {B,C,D,E}

Mike John
quelle

Antworten:

5

Ich habe in dieser Quelle eine leicht erweiterte Definition gefunden (die eine gute Erklärung enthält). Hier ist eine zuverlässigere (veröffentlichte) Quelle: CHARM: Ein effizienter Algorithmus für das Mining geschlossener Objekte von Mohammed J. Zaki und Ching-jui Hsiao .

Nach dieser Quelle:

  • Eine Elementmenge wird geschlossen, wenn keine ihrer unmittelbaren Obermengen dieselbe Unterstützung wie die Elementmenge hat
  • Eine Itemset ist maximal häufig, wenn keine ihrer unmittelbaren Supersets häufig ist


Einige Anmerkungen:

  • Es muss ein min_support festgelegt werden (support = die Anzahl der Objektgruppen, die die interessierende Teilmenge geteilt durch die Anzahl aller Objektgruppen enthalten), die definiert, welche Elementmenge häufig ist . Ein Itemset ist häufig, wenn seine Unterstützung> = min_support ist.
  • In Bezug auf den Algorithmus werden nur Itemsets mit min_support berücksichtigt, wenn versucht wird, die maximal häufigen und geschlossenen Itemsets zu finden.
  • Der wichtige Aspekt bei der Definition von geschlossen ist, dass es keine Rolle spielt, ob eine unmittelbare Obermenge mit mehr Unterstützung existiert, sondern nur unmittelbare Obermengen mit genau derselben Unterstützung.
  • maximal häufig => geschlossen => häufig, aber nicht umgekehrt.

Anwendung auf das Beispiel des OP

Hinweis:

  • Die Anzahl der Unterstützungen wurde nicht überprüft
  • Angenommen, min_support = 0,5. Dies ist erfüllt, wenn min_support_count> = 3 ist
{A} = 4; wegen {A, E} nicht geschlossen
{B} = 2; nicht häufig => ignorieren
{C} = 5; wegen {C, E} nicht geschlossen
{D} = 4; nicht geschlossen wegen {D, E}, aber nicht maximal wegen zB {A, D}
{E} = 6; geschlossen, aber nicht maximal aufgrund von zB {D, E}

{A, B} = 1; nicht häufig => ignorieren
{A, C} = 3; wegen {A, C, E} nicht geschlossen
{A, D} = 3; wegen {A, D, E} nicht geschlossen
{A, E} = 4; geschlossen, aber aufgrund von {A, D, E} nicht maximal
{B, C} = 2; nicht häufig => ignorieren
{B, D} = 0; nicht häufig => ignorieren
{B, E} = 2; nicht häufig => ignorieren
{C, D} = 3; wegen {C, D, E} nicht geschlossen
{C, E} = 5; geschlossen, aber aufgrund von {C, D, E} nicht maximal
{D, E} = 4; geschlossen, aber aufgrund von {A, D, E} nicht maximal

{A, B, C} = 1; nicht häufig => ignorieren
{A, B, D} = 0; nicht häufig => ignorieren
{A, B, E} = 1; nicht häufig => ignorieren
{A, C, D} = 2; nicht häufig => ignorieren
{A, C, E} = 3; maximal häufig
{A, D, E} = 3; maximal häufig
{B, C, D} = 0; nicht häufig => ignorieren
{B, C, E} = 2; nicht häufig => ignorieren
{C, D, E} = 3; maximal häufig

{A, B, C, D} = 0; nicht häufig => ignorieren
{A, B, C, E} = 1; nicht häufig => ignorieren
{B, C, D, E} = 0; nicht häufig => ignorieren
steffen
quelle
Der Quelllink ist defekt und lässt Sie nur wissen. Und ja, min_support ist sehr wichtig, ich benutze .50
Mike John
1
Entschuldigung, behoben.
steffen
1
min_support = 0.5 <=> min_support_count = 3 geändert und Anwendung entsprechend auf Beispiel geändert.
steffen
Verwenden Sie APRIORI, und Sie können viel Zählen und Erstellen von
Itemsets
@ Anony-Mousse Ich kenne APRIORI ... Ich ging manuell über die Itemsets, um das Konzept der geschlossenen und maximal häufigen Itemsets so detailliert wie möglich zu erläutern, da dies die Quelle der Verwirrung des OP (IMHO) war.
steffen
1

Vielleicht möchten Sie sich über den APRIORI-Algorithmus informieren. Es vermeidet unnötige Objektgruppen durch cleveres Beschneiden.

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

B ist nicht häufig, entfernen.

Konstruiere und zähle zwei Itemsets (noch keine Magie, außer das Bist schon raus)

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

All dies ist häufig (beachten Sie, dass alles, was hatte, Bnicht häufig sein kann!)

Verwenden Sie nun die Präfixregel. Kombinieren Sie NUR Itemsets, die mit denselben n-1 Items beginnen. Entfernen Sie alle, wenn eine Teilmenge nicht häufig ist. Zählen Sie die verbleibenden Artikelgruppen.

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

Beachten Sie, dass dies {A,C,D}nicht häufig ist. Da es kein gemeinsames Präfix gibt, kann es kein größeres häufiges Itemset geben!

Beachten Sie, wie viel weniger Arbeit ich getan habe!

Überprüfen Sie für maximale / geschlossene Elementmengen Teilmengen / Obermengen.

Beachten Sie, dass zB {E}=6und {A,E}=4. {E}ist eine Teilmenge, hat aber eine höhere Unterstützung, dh sie ist geschlossen, aber nicht maximal. {A}ist auch nicht, da es keine höhere Unterstützung als hat {A,E}, dh es ist redundant .

Hat aufgehört - Anony-Mousse
quelle