• Odkrywanie zbiorów częstych

  • algorytm apriori, miara wsparcia

  • znajomość reguł asocjacyjnych i naiwnego algorytmu ich konstrukcji, miara ufności

  • wielowymiarowe reguły asocjacyjne, co to jest, algorytm odkrywania

  • dyskretyzacja atrybutów ciągłych

    • Co z eliminacją na kracie?

    • 71?

• Klasyfikacja

  • znajomość problemu klasyfikacji

  • klasyfikator k-nn, obliczanie odległości pomiędzy obiektami o różnych rodzajach atrybutów

  • klasyfikator ID3

  • naiwny klasyfikator Bayesa

  • ocena jakości klasyfikatorów: zbiór trenujący i testujący, macierz pomyłek, walidacja skrośna, miary precision i recall

    • Co z pokryciem rekordów?

• Grupowanie

  • problem grupowania

  • hierarchiczny aglomeracyjny algorytm grupowania + miary odległości

  • algorytm k-means

Part 1.

Miara wsparcia.

Mamy regułę, na zasadzie: jeśli wystąpi A to wystąpi też B. Koniunkcja- wynikanie. [A->B].

Jeśli mamy zestawy typu ABCD/ADB/ADDA/ADDD. To sprawdzamy w których sytuacjach prawdą jest iż jeśli wystąpiło A to wystąpiło też B.

Mamy tu sytuację wystąpienia tej koniunkcji 2 razy, spośród 4ch. Zatem wsparcie to 2/4 = 50%.

Miara ufności

Jeśli jest poprzednik to jaka jest szansa na następnik. [A->B] Jeśli jest A to jaka szansa na B.

Mamy zestawy ACB/AEFB/TYOP/AX/.

W tych zestawach, 2 spełniają pełną koniunkcję czyli ACB/AEFB. Dodatkowo jedne spełnia poprzednik: AX.

Teraz w sumie mamy 3 zestawy. Pytanie brzmi jaką ilość spośród tych 3 zestawów stanowią te które spełniają koniunkcję. 2/3 = 66,{6} %.

Reguła silna – Taka dla której ufność lub wsparcie jest większe od zadanego progu minimalnego.

Naiwny algorytm

• Jest zbiór A,B,C,D.

• Wygeneruj wszystkie podzbiory (AB,CD,AC.. itd.).

• Oblicz wsparcie każdego podzbioru.

• Zostaw zbiory o wsparciu silnym.

• Są to zbiory częste.

• Z każdego zostawionego podzbioru utworzyć możliwe reguły asocjacyjne.

• Obliczyć ufność reguł i zostawić te > minconf.

Nie nadaje się do dużych zbiorów. Liczba podzbiorów to (2^n)-1, gdzie N to elementy zbioru.
Uwaga! Jeśli mamy. ABC i sprawdzamy ufność AC. To dla ABC jest 0. Nie ma tej samej kolejności liter.

Reguły asocjacyjne ( X jest podzbiorem Y )

• Monotoniczność- f(x) <= f(y)

  • Wsparcie nie jest monotoniczne

• Anytmonotoniczność f(x) >=f(y)

  • Wsparcie jest antymonotoniczne

Algorytm Apriori

Jeśli zbiór jest częsty (55-58) to jego pozdbiory też są częste.

Jeśli zbiór nie jest częsty (59-61, od piel ) to jego nadzbiory też są nieczęste.

• Przykładowo mamy produkty (ABCD). I listę koszyków z produktami.

• Obliczamy wsparcie dla każdego produktu, przyrównując do koszyków.

• Sprawdzamy czy te produkty spełniają min sup, jeśli nie to wywalamy.

• Tworzymy możliwe asocjacje (2 elementowe, to każdy z każdym)

• Sprawdzamy czy spełniają minsup, przyrównując do koszyków, jeśli nie to wywalamy.

• Tworzymy znowu asocjację, TYLKO TE same prefixy się kasują, nowy doklejamy na koniec, różnych prefixów nie używamy.

• Czyli (ABC, ABD,ACD) daje ABCD. Ale ACD nie ma z czym się skleić, bo używam 2ch pierwszy prefixów.

• Robimy tak aż nie będzie co sklejać na końcu

• Wypisujemy które asocjacje ( te pojedyncze też ) są częste, tj. spełniają minsup.

• Jeżeli w tym procesie powstanie np. ABCD, a wcześniej wykluczyliśmy BC, to skoro BC jest podzbiorem ABCD i jest nieczęste to całe ABCD jest nieczęste i je skreślamy.

Reguła wielowymiarowa- dane występujące w regule reprezentują różne dziedziny wartości(np. Id, wiek, płeć, dochód )

Binaryzacja danych (83) . Jeśli mamy np. wiek to tworzymy przedziały (dysretyzacja)

• Wiek [1-20] 0/1

• Wiek [ 21-40] 0/1

• I wpisujemy w te pola gdzie dane Id spełnia dany zakres (1 lub 0 )

W przypadku np. kolorów to każdy kolor jest osobnym atrybutem

• Red [0/1]

• Black [0/1]

Dyskretyzacja statyczna- przedziały mają równą szerokość/gęstość Np.:

Równy zakres dla zarobku [0-200] [201-400].
Gęstość- [11,30,40] [ 45,10,300] Po tyle samo elementów.

Dyskretyzacja dynamiczna­- rozkład wartości atrybutu.

Part 2

Klasyfikacja- Znalezienie zbioru danych –funkcji klasyfikacji-(deskryptorów/atrybutów opisowych) które odwzorowują każdy rekord w klasę(etykieta klasy/atrybut decyzyjny)

Deskryptor: Łysy, powolny, podparty, zmęczony, stary

Klasa: staruszek

Funkcja klasyfikacji­- służy do przewidywania atrybutów decyzyjnych. Podaje się zbiór uczący i sprawdza na testowym.

Kiedy przestać dzielić:

• wszystkie przykłady w podzbiorze są jednej klasy

• wykorzystano wszystkie podziały

• wartość wszystkich atrybutów w zbiorze są takie same

• liczba przykładów w podzbiorze< zadany próg

• inne

ID3- atrybuty opisowe muszą być nominalne, podział zawsze grupuje przykład wg. Wartości atrybutu (np. wzrost: rozgałęzia się na „niski, wysoki”. Do wyboru atrybutu stosuje się miarę zysku informacyjnego.

• Wybieramy atrybut decyzyjny wg. Którego będziemy obliczać dane deskryptory

• Deskryptor może być atrybutem decyzyjnym

Liczymy outlok wg. play(klasy).

• Wypisjemy wszystkie możliwe stany outlook czyli 3.

• Piszemy ile ogólnie mamy przykładów (x)

• Piszemy ile spośród całość wynosi dana wartość (x/y)
  gdzie y to wartość np. rainy, sunny

• Piszemy ile stanów przyjmuje na yes i No (s1/s2)

• Piszemy jaka to część ze wszystkich stanów (p1/p2)=0.x (dziesiętnie)

• Obliczamy E(outlook)= Xo/Yo I(S1,S2)+Xr/Yr I(S1,S2)+Xs/Ys I(S1,S2)
  tj. E(outlook)=
  Xo/Yo (-p1log^2p1-p2log^2p2)
  Xr/Yr (-p1log^2p1-p2log^2p2)+
  Xs/Ys (-p1log^2p1-p2log^2p2)

• Obliczmy I

• Do tego piszemy ile przykładów mamy w ogóle (P)

• Które z nich przyjmują dane wartość decyzyjne ( tutaj, yes/no Si1/ Si2)

• I=
  -[(S1/p)log2(S1/p)]-[(si2/p)log(Si2/p)]

• Gain= I- E

Entropia- miara stanu nieuporządkowania układu. Entropia rośnie gdy podział jest równy np. 2x A 2x B. Daje entropie 1. AAAA Entropia 0. AAAB ~0,25

Przeuczenie klasyfikatora:

• Złe przykłady uczące

• Sprzeczne przykłady

• Za mało przykładów

  • W drzewie mogą pojawić się gałęzie będące reakcją na punkty odstające

  • Po zakończeniu budowy drzewa, wycina się osobliwe gałęzie dla poprawy

Klasyfikator Bayesa: Przydziela obiektowi najbardziej prawdopodobną klasę.

• Wypisać ile jest przykładów (S), podzielić na wartości atrybutu decyzyjnego (S1/S2), zapisać dziesiętnie (S1/S) (S2/S).

• Wypisać wszystkie wartości atrybutów z podziałem na klasę ( atrybut decyzyjny)
  Ooutlock ( rainy 3x yes, 2 x no | sunny 2x yes 3x no) inne też

• Obliczyć Jaką częścią wszystkich YES jest rainy yes(P), Jaką częścią NO jest rainy no (P) i adekwatnie do tego reszte.
  Jeśli wyjdzie 0 to zastąpić niewielką liczbą.

• Teraz jeśli dostaniemy coś do zaklasyfikowania to sprawdzamy czy atrybut pasuje do No/yes. W tym celu dla YES mnożymy
  S1/S *P/s1*p2/s1*p3/s1 itd. Zamieniamy to na dziesiętne.
  Na No też robimy to samo.

• To co da większą wartość to większe prawdopodobieństwo wpasowania

Miary odległości kNN:

• Atrybuty nominalne: współczynnik Jaccarda/ Odległość Hamminga

Współczynnik Jaccarda- oblicza prawdopodobieństwo między obiektami binarnymi

Odległość Hamminga- oblicza prawdopodobieństwo między obiektami nominalnymi

• Jeśli porównamy 2 wartości które będą takie same to piszemy 0.

  • Np. Kawa = Kawa 0

• Jeśli będą różne to piszemy 1

  • Np. Kawa<>herbata 1

Używanie funkcji na bezpośrednich danych może powodować przekłamania. Nie wszystkie atrybuty mają taką samą skalę. Np. Temp Ciała i miesięczne zarobki. Trzeba nadać wagi, standaryzować wartości atrybutów.

Mapowanie atrybutów porządkowych: niski= 0 / średni=1/ Duży=2/ Gigant=3

Normalizacja atrybutów porządkowych-np: mamy oceny:

• A=0

• B=1

• C=2

• D=3

• E=4

• M= Ile jest ocen? M=5

• Min które uznaliśmy że ma być osiągnięte to B=1. Czyli mapowane na pozycji 2. Min=2

• Max które jest dopuszczalne to E=4. Mapowane na pozycji 5. Max=5.

  • Normalizajca = {[Dana wartość] –Jej dopuszczalne min.}/[dop. Max- dop.min]

  • Jest zawsze dodatnia. Wywalamy minusa jeśli powstanie.

Odległość między obiektami liczbowymi(Normalizowanymi !!): np. porównujemy średnie ocen które normalizowaliśmy na str. 149. Porównujemy ocenę 1 z 3. To odejmujemy te wartość od siebie. Od 1ej odejmujemy 3ą.
W przypadku wartości mapowanych- Wartość bezwzgl. Z różnicy wartości. Dzielone, przez (ilość mapowanych wartości)-1.

Gdy już poobliczamy prawdopodobieństwa i odległości różnych wartości:

• Trzeba obliczyć odległość ostateczną zgodnie z metryką Minkowskiego (3 typy)

• Euklidesowa

  • Pierwiastek 2stopnia z (Suma wszystkich wartości podniesionych do ^2)

• Manhatan

  • To po prostu suma wszystkich wartości

• Chebychew

  • To po prostu największa wartość z tych które wyszły

Ocena Jakości klasyfikatorów: podaje się zbiór uczący i testujący. Klasyfikator buduje się z uczącego a testującym sprawdza się poprawność. Wynikiem testu jest macierz pomyłek.

Macierz pomyłek: przedstawia w jaki sposób faktycznie zaklasyfikowano dane klasy

Preccision / F-means/ recall:

• F measure- średnia charmoniczna

• Recall- jaki % z [x] zakwalifikowano faktycznie jako [x]

Walidacja skrośna- ocenia algorytm klasyfikacji i jego parametry. Dzielimy zbiór danych na kilka części, z reguły (10). Wybieramy 1n element który będzie testujący. Pozostałymi częściami uczymy i budujemy klasyfikator. Sprawdzamy zbiorem testującym. Powtarzamy to dal wszystkim elementów.

Part 3

Grupowanie-zbiór obiektów o podobnych cechach

Podobne-odległość dwóch dowolnych obiektów klastra jest < od dowolnego obiektu w klastrze i dowolnego obiektu poza klastrem.

Proces grupowania:

Miary odległości: bardzo często są to metryki (Minkowskiego);

STR 224-244; + dodatkowe materiały;

Grupowanie AHC

• Mając daną tabelę, trzeba stworzyć macierz czyli tabelę kombinacji na zasadzie każdy z każdym czyli, np. tabela ma 4 rzędy. To robimy tabele kombinacji 11,12,13,14, 21,22,23,24

1	21	42
2	32	2
3	21	2
4	56	1

	1	2	3	4
1	0		1.3=pierw.2(21-21)^2+(42-2)^2
2		0	Itp.
3			0
4				0

• 

K-Means

Najpierw ustalamy na ile grup będziemy dzielić, wybieramy jakieś losowe :K ( 1-5 np. )

Wybieramy jakieś początkowe środki grup, np. punkty o zadanych współrzędnych.

Odległość punktów w układzie współrzędnych:

Nowe środki obliczy na zasadzie

(1/n)*(E(x,y)

[gdzie n, to liczba lepszych dopasowani, np. 4 wyniki są lepsze w rzędzie]

[E(x,y) to suma współrzędnych tych punktów które mają lepsze dopasowanie]

Przy czym w każdej kolumnie wybieram [n] takie które jest najlepsze ze wszystkich rzędów.