Maksymalna i często zamykana - odpowiedź w zestawie

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.$X ∈ F$
• 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\}}$

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

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 .