Multzokatze hierarkiko

Datu-meatzaritzan eta estatistikan, multzokatze hierarkikoa multzoen hierarkia bat sortzen duen multzoen analisirako metodo bat da. Sortutako multzoen hierarkia dendrograma baten bidez adierazten da. Multzokatzea modu hierarkikoan egiteko bi estrategia mota daude: ^[1]

• Pilatzaileak: Behetik gorako metodoak dira. Hasieran, elementu edo kasu bakoitzak multzo bat osatzen du eta gertueneko multzoak elkarri batuz, kasu guztiak multzo bakar batean multzokatzea lortzen da.
• Zatitzaileak: Goitik beherako metodoak dira. Hasieran, elementu edo kasu guztiek multzo bakar bat osatzen dute eta multzoa urratsez urrats bitan zatituko da, azkenean multzo bakoitzak kasu bakarra izango duen arte.

Multzoen bereizketa

Metrika

Multzokatze hierarkikoan, metodo pilatzaileek gertueneko multzoak batzen dituzte eta metodo zatitzaileek multzoa bitan zatitzen dute. Elkarri batuko diren edo zatituak izango diren multzoak algoritmoaren iterazio bakoitzean aukeratu behar dira. Aukeraketa hori egiteko irizpide bat behar da, erabiltzen den distantziaren arabera elkarri gertuen dauden multzoak desberdinak izan daitezkeelako. Metrika erabilienak honakoak dira: ^[2].

Distantzia	Formula
Distantzia euklidearra	${\displaystyle \|a-b\|_{2}={\sqrt {\sum _{i}(a_{i}-b_{i})^{2}}}}$
Manhattan distantzia	${\displaystyle \|a-b\|_{1}=\sum _{i}|a_{i}-b_{i}|}$
Distantzia euklidear karratua	${\displaystyle \|a-b\|_{2}^{2}=\sum _{i}(a_{i}-b_{i})^{2}}$
Distantzia maximoa	${\displaystyle \|a-b\|_{\infty }=\max _{i}|a_{i}-b_{i}|}$
Mahalanobisen distantzia	${\displaystyle {\sqrt {(a-b)^{\top }S^{-1}(a-b)}}}$ non S Kobariantza matrizea den

Testuetarako edo zenbakizkoak ez diren datuetarako, Hamming-en distantzia edota Levenshtein-en distantzia erabiltzen dira.

Osasunerako psikologian erabilitako multzokatze analisian egindako ikerketa batean, ohikoenak ziren distantziak Euklidearra eta Euklidear karratua zirela ondorioztatu zuten.^{[erreferentzia behar]}

Lotura irizpideak

Lotura irizpidearen arabera, multzoen arteko distantzia definitzen da. Multzoetako kasuen arteko distantzien kalkuluan oinarritzen dira multzoen arteko distantzia definitzen dute irizpideak.

A eta B multzoak izanik, hona hemen oso sarri erabili ohi diren lotura irizpide batzuk: ^{[3] [4]}

Lotura irizpidea	Formula
Distantzia maximoa	${\displaystyle \max \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Distantzia minimoa	${\displaystyle \min \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Batezbesteko distantzia	${\displaystyle {\frac {1}{|A|.|B|}}\sum _{a\in A}\sum _{b\in B}d(a,b).}$
Zentroideen arteko distantzia	${\displaystyle \|c_{s}-c_{t}\|}$ non ${\displaystyle c_{s}}$ eta ${\displaystyle c_{t}}$ s eta t multzoen zentroideak diren, hurrenez hurren.
Energia minimoa	${\displaystyle {\frac {2}{nm}}\sum _{i,j=1}^{n,m}\|a_{i}-b_{j}\|_{2}-{\frac {1}{n^{2}}}\sum _{i,j=1}^{n}\|a_{i}-a_{j}\|_{2}-{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}\|b_{i}-b_{j}\|_{2}}$

non d aukeratutako metrika den. Badaude beste lotura irizpide batzuk, baina erabilienak horiek dira.

Multzokatze hierarkikoan edozein distantzia mota erabil daiteke. Izan ere, multzoa osatzen duten kasuak edo elementuak izatea ez da beharrezkoa, haien arteko distantziez osatutako matrizea erabiltzen baita.

Algoritmoen konplexutasuna

Oro har, multzoen banaketa eta elkarketa horiek algoritmo irenskor baten bidez egiten dira.

Multzokatze hierarkikorako algoritmo arruntak ${\displaystyle {\mathcal {O}}(n^{3})}$-ko konplexutasun denbora du eta ${\displaystyle {\mathcal {O}}(n^{2})}$-ko memoria behar izaten du. Horrek, algoritmoa nahiko motela izatea eragiten du. Hala ere, ${\displaystyle {\mathcal {O}}(n^{2})}$ konplexutasuna duten metodo pilatzaile optimo eraginkorrak ezagutzen dira, zenbait kasu partikularretan erabil daitezkeenak: SLINK ^[5] distantzia minimoko multzokatzerako eta CLINK^[6] distantzia maximoko multzokatzerako.

Distantzia minimoko multzokatzea erabiltzen duten kasu partikular batzuetatik aparte, ez dago soluzio optimo bat aurkitu dezakeela bermatzen duen beste algoritmorik (${\displaystyle {\mathcal {O}}(2^{n})}$-ko bilaketa zehatza (exhaustiboa) izan ezik). Hala ere, ohikoa da azkarragoak diren hurbilpen algoritmoak erabiltzea, adibidez, partiziozko multzokatzea (ingelesez k-means).

Adibidea. Multzokatze pilatzailea

Demagun sei elementu ditugula {a}, {b}, {c}, {d}, {e} eta {f}. Haien arteko distantziak ezagunak dira (ikus irudia). Demagun distantzia euklidearra erabiliko dela.

Kasuak multzokatu gabe

Metodo pilatzailearen bidez multzokatze hierarkikoa egitea, urrats bakoitzean gertueneko bi multzoak bakar batean elkartzea izan da. Honako dendrogramak erakusten du prozesu osoa:

Kasuak hierarkikoki multzokatuta

Ikusten den bezala, hasieran elementu edo kasu bakoitzak multzo bat osatzen du. Hasierako urrats horretan, multzoen arteko distantzia elementuen arteko distantzia da. Gertueneko bi multzoak {b} eta {c} badira, haiek batu ondoren, {a}, {b, c}, {d}, {e} eta {f} multzoak lortzen dira. Multzokatze gehiago egin ahal izateko, multzoen arteko distantziak eguneratu egin behar dira; sortu berri den {b, c} multzotik gainerako multzoetarako distantziak kalkulatu egin behar dira. Horretarako, erabaki behar da zein lotura irizpideren arabera definituko den multzoen arteko distantzia.

Normalean distantzien taula bat eraikitzen da, non i. errenkadan eta j. zutabean dagoen elementuak i multzoaren eta j multzoaren arteko distantzia adierazten duen. Irizpide arruntenen kasurako, horrela kalkulatuko litzateke:

• Distantzia maximoa: Distantzia maximora dauden ${\displaystyle {\mathcal {A}}}$ multzoko ${\displaystyle x}$ elementuaren eta ${\displaystyle {\mathcal {B}}}$ multzoko ${\displaystyle y}$ elementuaren arteko distantziak definitzen du ${\displaystyle {\mathcal {A}}}$ eta ${\displaystyle {\mathcal {B}}}$ multzoen arteko distantzia.

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• Distantzia minimoa: Distantzia minimora dauden ${\displaystyle {\mathcal {A}}}$ multzoko ${\displaystyle x}$ elementuaren eta ${\displaystyle {\mathcal {B}}}$ multzoko ${\displaystyle y}$ elementuaren arteko distantziak definitzen du ${\displaystyle {\mathcal {A}}}$ eta ${\displaystyle {\mathcal {B}}}$ multzoen arteko distantzia.

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• Batezbesteko distantzia: Bi multzoetako elementu guztien arteko batezbesteko distantziak definitzen du ${\displaystyle {\mathcal {A}}}$ eta ${\displaystyle {\mathcal {B}}}$ multzoen arteko distantzia.

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}$

Prozesua amaituko da elementu guztiak multzo bakar batean daudenean. Urratsez urrats elkartu diren multzoak zein izan diren eta haien arteko distantzia zein den adieraziz eraikitzen da prozesu osoa adierazten duen dendrograma.

Multzokatze hierarkikorako metodoa aplikatzearen ondorioz lortu den multzokatzea zein den erabakitzeko, zuhaitza mailaren batean moztu behar da. Adibidean, dendrograma bigarren errenkadan moztuz, {a}, {b, c}, {d,e}, {f} multzokatzea lortzen da (4 multzo). Hirugarren errenkadaren ondoren moztuz, {a}, {b,c}, {d,e,f} multzokatzea lortzen da (3 multzo). Multzokatze horien artean egokiena zein den erabaki ahal izateko, ebaluazio irizpideren bat erabiltzea beharrezkoa gertatzen da.

Multzokatze zatitzailea

Multzokatze hierarkikorako metodo zatitzaileek DIANA (ingeleraz, "DIvisive ANAlysis Clustering") algoritmoan dteu jatorria. ^[7] Algoritmoaren hasieran, kasu guztiak multzo bakar batean daude eta algoritmoaren urrats bakoitzean multzo handiena zatitzen da, kasu bakoitza multzo bakar batean geratu arte.

Multzoak zatitzeko ${\displaystyle O(2^{n})}$ modu existitzen direnez, metodo heuristikoren bat behar da. Horretarako, DIANA algoritmoak batezbestean desberdintasun handiena duen azpimultzoa aukeratzen du, horiekin multzo berri bat sortzeko. Ondoren, gertuen dauden kasuak sartuko zaizkio.

Softwarea

Kode irekikoak

Iris lorearen datu multzoarekin lortutako dendrogramaren multzokatze hierarkikoa (R erabiliz). Iturria

• Octave, MATLAB-en parekoa GNU proiektuan.
• R lengoaiak multzokatze hierarkikorako funtzio asko ditu.
• SciPy liburutegiak multzokatze hierarkikoa eskaintzen du, Pythonen inplementatua. Oso eraginkorra den SLINK algoritmoa ere badu.
• Weka ingurunean multzokatze hierarkikoa erabili daiteke.

Inplementazio komertzialak

• MATLAB multzokatze hierarkikoa inplementatuta dauka.
• Mathematica programak multzokatze hierarkikorako pakete bat dauka.
• SPSS paketeak multzokatze hierarkikoa egiteko aukera ematen du.

Erreferentziak

1. (Ingelesez) Lior, Rokach; Maimon, Oded. (2005). "Clustering methods." Data mining and knowledge discovery handbook. Springer US.
2. (Ingelesez) SAS Institute.
3. (Ingelesez) The CLUSTER Procedure: Clustering Methods. in: SAS/STAT 9.2 Users Guide. SAS Institute.
4. (Ingelesez) «Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method» Journal of Classification 22 (2): 151-183.  doi:10.1007/s00357-005-0012-9..
5. (Ingelesez) «SLINK: an optimally efficient algorithm for the single-link cluster method» The Computer Journal (British Computer Society) 16 (1): 30-34. 2017-11-30  doi:10.1093/comjnl/16.1.30..
6. (Ingelesez) «An efficient algorithm for a complete-link method» The Computer Journal (British Computer Society) 20 (4): 364-366.  doi:10.1093/comjnl/20.4.364..
7. (Ingelesez) Finding Groups in Data - An Introduction to Cluster Analysis. A Wiley-Science Publication John Wiley & Sons. .

Ikus, gainera

• Multzokatze (estatistika)
• Dendrograma

Kanpo estekak