Czy drzewa mogą podejmować decyzje?

Wstęp

Mówią, że drzewa i ryby głosu nie mają. Czy aby na pewno? Istnieje pewna rodzina drzew nazywana drzewami decyzyjnymi. Jak sama nazwa wskazuje - służą one do podejmowania decyzji.

Definicja

Drzewo decyzyjne to, używając matematycznego języka, graf nieskierowany, acykliczny i spójny, którego korzeń znajduje się na górze, a poszczególne gałęzie związane są z pewną decyzją. Łatwiej będzie to zrozumieć na przykładzie. Załóżmy, że pewien użytkownik wypracował sobie następujący algorytm głosowania w sieci Steem.

Algorytm ten został przedstawiony graficznie właśnie jako drzewo decyzyjne. Element na samej górze to korzeń (to pewna anomalia, charakterystyczna dla drzew decyzyjnych, że rosną one od góry, a nie od dołu). Elementy terminalne (nie mające już żadnych wychodzących połączeń) to liście. Tutaj, w każdym liściu przedstawiona została waga głosu z jaką wspomniany użytkownik zagłosuje, po udzieleniu odpowiedzi na pytania jakie znalazły się po drodze od korzenia do liścia.

Zastosowanie

Przykład wyżej, to wizualizacja pewnego schematu znanych decyzji. Jednak ciekawiej robi się wtedy, kiedy takie drzewo musimy zbudować na podstawie danych. Załóżmy, że chcemy stworzyć drzewo decyzyjne, które z dużą skutecznością pozwoli odróżnić zwykłego użytkownika od bid-bota.

Listę botów możemy pobrać ze strony https://steembottracker.com/. Daje nam to następującą listę:

peace-bot, noicebot, sunrawhale, weupvote, redwhale, getkarma,
singing.beauty, estream.studios, stef, sneaky-ninja, edensgarden, buildawhale,
t50, dlivepromoter, lrd, th3voter, honestbot, haveaheart,
tainika, oceanwhale, redlambo, voterunner, upyourpost, boinger,
cabbage-dealer, authors.league, aksdwi, ptbot, dailyupvotes, luckyvotes,
msp-bidbot, jerrybanfield, boomerang, bid4joy, rocky1, mercurybot,
lost-ninja, nado.bot, profitbot, alliedforces, brandonfrye, whalepromobot,
botox, upmewhale, isteemd, appreciator, flymehigh, profitvote,
booster, moneymatchgaming, sureshot, emperorofnaps, inciter, steembotup,
pushup, promobot, smartsteem, whalecreator, peoplesbot, pwrup,
therising, siditech, ecotrain, minnowvotes, bodzila, isotonic,
postdoctor, a-bot, proffit, mitsuko, spydo, postpromoter,
upme, chronoboost, onlyprofitbot, brupvoter, alfanso, megabot,
thebot, slimwhale, minnowhelper, joeparys, lovejuice, steembloggers,
estabond, brotherhood, shares, automation, votepower, ebargains, dolphinbot

---

Teraz kolej na listę użytkowników. Pobierzemy ją z bazy SteemSQL następującym zapytaniem:

SELECT DISTINCT author
FROM Comments (NOLOCK)
WHERE depth = 0
      AND (CONTAINS(json_metadata, 'pl-artykuly') AND json_metadata LIKE '%"pl-artykuly"%') AND
      created BETWEEN GETUTCDATE() - 30 AND GETUTCDATE()

---

Wybraliśmy użytkowników którzy dodali przynajmniej jeden post w tagu #pl-artykuly w ciągu ostatnich 30 dni. Lista zawiera 194 użytkowników, czyli około 2 razy więcej niż lista botów, ale to nie problem. Rzadko kiedy mamy do czynienia z danymi, które są równomiernie rozłożone na klasy.

Dla każdego konta wyznaczymy następujące atrybuty:

• liczba obserwujących
• liczba obserwowanych
• stosunek obserwowanych do obserwujących
• reputacja
• liczba użytkowników, którzy wyciszyli dane konto
• efektywny STEEM POWER (z delegacją)
• własny STEEM POWER (bez delegacji)
• stosunek efektywnego STEEM POWER do własnego STEEM POWER

W ten sposób powstaje następująca tabela:

                 name  followers  followings  foll. ratio  muters        rep       eff. sp        own sp    sp ratio  bid-bot?
0           nwacrypto        190          56     0.294737       0  39.626951  1.503422e+01      0.106194  141.572849         0
1              mastek        404          88     0.217822       4  52.211475  4.703563e+01    129.228725    0.363972         0
2        minnowhelper       4986           0     0.000000      38  54.167403  9.583000e+03   4293.335044    2.232064         1
3             booster      14706          13     0.000884      97  62.981797  1.028846e+06  11194.474322   91.906578         1
4                upme       7430           3     0.000404      45  48.911318  1.528846e+06  18600.885957   82.192119         1
5               pwrup        209           0     0.000000       1  30.637104  4.586465e+03    141.533885   32.405421         1
6           upmewhale       4640          10     0.002155      33  62.494684  9.514844e+05   5477.134376  173.719382         1
7        czekolatka22        189           5     0.026455       0  26.873284  1.507292e+01      0.198682   75.864492         0
8           bitcoinpl        213           1     0.004695       0  38.847017  1.517073e+01      0.272541   55.663959         0
9            shogunma        441         285     0.646259       1  52.514156  1.678035e+02    167.803466    1.000000         0
10      lynxialicious        248          71     0.286290       0  47.139451  1.508179e+01      0.100545  149.999882         0
11             wadera        453         240     0.529801       2  53.804437  3.656898e+02    346.743081    1.054642         0
12             ocisly        485          12     0.024742       1  57.049338  2.379411e+02    237.941102    1.000000         0
13            inciter        831           1     0.001203       5  26.577300  7.892722e+04   1229.580684   64.190354         1
14          minprawdy        466          21     0.045064       1  52.328351  3.545774e+01     60.636043    0.584763         0
15       verticallife        192          16     0.083333       0  43.087868  1.500313e+01      3.695172    4.060196         0
16        arabson1990        322         108     0.335404       1  54.460320  2.003903e+02    200.390324    1.000000         0
17             debski        202           6     0.029703       0  46.532757  1.322173e+01     13.221731    1.000000         0
18            marszum        986          41     0.041582       5  58.807664  2.488636e+01    386.221484    0.064435         0
19         czcibor360        274          42     0.153285       1  45.457077  6.038543e+01     15.528881    3.888588         0
20            tomosan        399          70     0.175439       0  50.512015  3.331150e+01     34.317865    0.970675         0
21           bartalke        166           3     0.018072       0  31.677634  1.508592e+01      0.100573  149.999833         0
22         saunter-pl        350          39     0.111429       1  53.809061  4.817920e+01     48.179197    1.000000         0
23       ciekawefbhpl        199          16     0.080402       0  43.629908  1.500020e+01      4.529806    3.311444         0
24        denyswielki        272          28     0.102941       0  45.467470  1.509815e+01      3.032004    4.979593         0
25           fatesick        231           6     0.025974       4  50.514631  6.017471e+01     60.174710    1.000000         0
26            katayah        441         134     0.303855       0  54.182795  7.454937e+02    595.106715    1.252706         0
27         sunrawhale        415           0     0.000000       9  36.434167  1.576457e+03    160.229086    9.838768         1
28         smartsteem       8705         840     0.096496      30  66.416996  2.859221e+06  44224.413403   64.652556         1
29              daisu        318          15     0.047170       0  41.525401  1.756675e+01     17.566747    1.000000         0
..                ...        ...         ...          ...     ...        ...           ...           ...         ...       ...

---

Czego możemy się spodziewać? Poniżej moje przypuszczenia:

• bid-boty są częściej wyciszane
• bid-boty mają wyższy efektywny STEEM POWER
• większość STEEM POWER botów pochodzi z delegacji
• bid-boty mają niższą reputację (bo rzadko kiedy dodają posty)

Sprawdźmy więc jak wyglądają średnie wartości dla poszczególnych atrybutów.

Atrybut	Średnia dla użytkowników	Średnia dla bid-botów
Obserwujący	368.232	2337.769
Obserwowani	81.289	204.297
Obserwowani / Obserwujący	0.213	0.164
Wyciszenia	1.165	14.725
Reputacja	48.483	46.215
Efektywny SP	566.560	236722.202
Własny SP	421.190	13192.904
Efektywny SP / własny SP	33.047	218.076

Widzimy, że faktycznie są spore różnice w średnich wartościach. Spójrzmy jeszcze na dokładniejsze wizualizacje wybranych par atrybutów (dla lepszej czytelności wykresów, punkty, które bardzo odstawały zostały pominięte).

Obserwowani + Obserwujący:

Reputacja + Wyciszenia:

Efektywny SP / własny SP + Obserwowani / Obserwujący:

Teraz pora na zbudowanie klasyfikatora - drzewa decyzyjnego. Na samym początku musimy podzielić dane (X - atrybuty, y - klasa decyzyjna) na zbiór treningowy i testowy. Zrealizujemy to poniższym kodem (cały skrypt znajduje się na dole artykułu):

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

---

Tworzymy obiekt drzewa decyzyjnego:

clf = tree.DecisionTreeClassifier()

---

Trenujemy je (korzystając ze zbioru treningowego):

clf = clf.fit(X_train, y_train)

---

Sprawdzamy jaka jest skuteczność tak wytrenowanego drzewa:

y_pred = clf.predict(X_test)

---

W tym celu wyświetlimy macierz konfuzji, która zlicza klasyfikacje. Na przekątnej znajdują się poprawne klasyfikacje (czyli użytkownik zaklasyfikowany jako użytkownik oraz bid-bot zaklasyfikowany jako bid-bot), poza przekątną niepoprawne klasyfikacje (czyli użytkownik zaklasyfikowany jako bid-bot oraz bid-bot zaklasyfikowany jako użytkownik).

cm = confusion_matrix(y_test, y_pred)
plt.figure(figsize = (6, 6))
sns.heatmap(cm, annot=True, cmap="Greens")

Widzimy, że mamy 80 poprawnych klasyfikacji oraz 6 błędnych, co daje skutecznośc na poziomie 93%.

A jak wygląda wizualizacja samego drzewa decyzyjnego?

Parametr samples określa ile rekordów trafiło do danej odnogi. Pierwsza wartość na liście value to liczba kont zaklasyfikowanych jako użytkownik, a druga wartość to liczba kont zaklasyfikowanych jako bid-bot.

Całość kodu można zobaczyć tutaj.

---

Artykuł jest zgłoszeniem do pierwszego tematu konkursu TemaTYgodnia: Drzewa klasyfikacyjne.