Maksymalna i często zamykana - odpowiedź w zestawie

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

Chcę znaleźć maksymalne zestawy częstych przedmiotów i zamknięte zestawy częstych przedmiotów .

  • Zestaw częstych elementów jest maksymalny, jeśli nie ma żadnych częstych ustawień superset.XF
  • Zestaw częstych pozycji X ∈ F jest zamknięty, jeśli nie ma nadzbioru o tej samej częstotliwości

Więc policzyłem występowanie każdego zestawu przedmiotów.

{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 ustawiony na // Bardzo ważne. Dzięki steffen za przypomnienie tego.50

Czy maksymalna = ?{A,B,C,E}

Czy zamknięte = ?{A,B,C,D} and {B,C,D,E}

Mike John
źródło

Odpowiedzi:

5

W tym źródle znalazłem nieco rozszerzoną definicję (która zawiera dobre wyjaśnienie). Oto bardziej wiarygodne (opublikowane) źródło: CHARM: Wydajny algorytm do wydobywania zamkniętych przedmiotów przez Mohammeda J. Zaki i Ching-jui Hsiao .

Według tego źródła:

  • Zestaw przedmiotów jest zamknięty, jeśli żaden z jego bezpośrednich nadzorów nie ma takiego samego wsparcia jak zestaw przedmiotów
  • Zestaw przedmiotów jest maksymalny często, jeśli żaden z jego bezpośrednich supersetów nie jest częsty


Kilka uwag:

  • Konieczne jest ustawienie min_support (wsparcie = liczba zestawów przedmiotów zawierających podzbiór będący przedmiotem zainteresowania podzielona przez liczbę wszystkich zestawów przedmiotów), który określa, który zestaw przedmiotów jest częsty . Zestaw przedmiotów jest częsty, jeśli jego wsparcie> = min_support.
  • W odniesieniu do algorytmu, tylko zestawy przedmiotów z min_support są brane pod uwagę, gdy próbuje się znaleźć maksymalne częste i zamknięte zestawy przedmiotów.
  • Ważnym aspektem w definicji zamkniętej jest to, że nie ma znaczenia, czy istnieje bezpośredni nadzbiór z większym wsparciem, tylko bezpośrednie nadzbiory z dokładnie takim samym wsparciem mają znaczenie.
  • maksymalna częstość => zamknięte => częste, ale nie odwrotnie.

Zastosowanie do przykładu PO

Uwaga:

  • Nie sprawdziłem liczby wsparcia
  • Powiedzmy, że min_support = 0,5. Jest to spełnione, jeśli min_support_count> = 3
{A} = 4; nie zamknięty z powodu {A, E}
{B} = 2; niezbyt często => ignoruj
{C} = 5; nie zamknięty z powodu {C, E}
{D} = 4; nie zamknięty z powodu {D, E}, ale nie maksymalny z powodu np. {A, D}
{E} = 6; zamknięte, ale nie maksymalne z powodu np. {D, E}

{A, B} = 1; niezbyt często => ignoruj
{A, C} = 3; nie zamknięty z powodu {A, C, E}
{A, D} = 3; nie zamknięty z powodu {A, D, E}
{A, E} = 4; zamknięte, ale nie maksymalne z powodu {A, D, E}
{B, C} = 2; niezbyt często => ignoruj
{B, D} = 0; niezbyt często => ignoruj
{B, E} = 2; niezbyt często => ignoruj
{C, D} = 3; nie zamknięty z powodu {C, D, E}
{C, E} = 5; zamknięte, ale nie maksymalne z powodu {C, D, E}
{D, E} = 4; zamknięte, ale nie maksymalne z powodu {A, D, E}

{A, B, C} = 1; niezbyt często => ignoruj
{A, B, D} = 0; niezbyt często => ignoruj
{A, B, E} = 1; niezbyt często => ignoruj
{A, C, D} = 2; niezbyt często => ignoruj
{A, C, E} = 3; maksymalna częstość
{A, D, E} = 3; maksymalna częstość
{B, C, D} = 0; niezbyt często => ignoruj
{B, C, E} = 2; niezbyt często => ignoruj
{C, D, E} = 3; maksymalna częstość

{A, B, C, D} = 0; niezbyt często => ignoruj
{A, B, C, E} = 1; niezbyt często => ignoruj
{B, C, D, E} = 0; niezbyt często => ignoruj
steffen
źródło
Link źródłowy jest zepsuty, po prostu dając ci znać. I tak, min_support jest bardzo ważny, używam .50
Mike John
1
Przepraszamy za to naprawione.
steffen
1
zmieniono min_support = 0,5 <=> min_support_count = 3 i odpowiednio zmieniono aplikację na przykład.
steffen
Zastosowanie APRIORI, a można zaoszczędzić dużo liczenia i konstruowaniu itemsets ...
zrezygnował - anony-Mousse
@ Anony-Mousse Wiem APRIORI ... Przeszedłem ręcznie przez zestawy przedmiotów, aby wyjaśnić pojęcie zamkniętych i maksymalnych częstych zestawów przedmiotów tak szczegółowo, jak to możliwe, ponieważ było to źródłem pomieszania OP (IMHO).
steffen
1

Możesz przeczytać o algorytmie APRIORI. Pozwala uniknąć niepotrzebnych zestawów przedmiotów poprzez sprytne przycinanie.

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

B nie jest częste, usuń.

Stwórz i policz dwa zestawy przedmiotów (jeszcze nie ma magii, z wyjątkiem tego, że Bjuż jest)

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

Wszystkie są częste (zauważ, że wszystko, co Bnie mogło być częste!)

Teraz użyj reguły przedrostka. Łącz TYLKO przedmioty zaczynające się od tych samych przedmiotów n-1. Usuń wszystko, gdy jakikolwiek podzbiór nie jest częsty. Policz pozostałe zestawy przedmiotów.

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

Pamiętaj, że {A,C,D}nie jest to częste. Ponieważ nie ma wspólnego prefiksu, nie może istnieć częstszy zestaw przedmiotów!

Zauważ, ile mniej pracy wykonałem!

Aby uzyskać maksymalne / zamknięte zestawy elementów, sprawdź podzbiory / nadzbiory.

Należy pamiętać, że na przykład {E}=6, i {A,E}=4. {E}jest podzbiorem, ale ma większe wsparcie, tzn. jest zamknięty, ale nie maksymalny. {A}nie jest, ponieważ nie ma większego wsparcia niż {A,E}, tzn. jest zbędny .

Ma ZAKOŃCZENIE - Anony-Mus
źródło