Multzokatze hierarkiko

Ikasketa automatikoa eta Datu-meatzaritza
Problemak Classification Multzokatzea Erregresioa Anomaly detection AutoML Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Ikasketa gainbegiratua Zuhaitzak Ensembles Bagging Boosting Random forest k-NN Karratu txikienen erregresio zuzen Naive Bayes Neurona-sareak Erregresio logistiko Perceptron Relevance vector machine (RVM) (SVM)
Multzokatzea BIRCH CURE Hierarkikoa k-means Expectation–maximization (EM)
Dimensionality reduction Faktore-analisi Korrelazio kanoniko ICA LDA NMF PCA t-SNE
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection k-NN Local outlier factor
Neurona-sare artifizial Autoencoder Ikaskuntza sakon DeepDream Multilayer perceptron RNN LSTM GRU) Restricted Boltzmann machine SOM Convolutional neural network U-Net
Reinforcement learning Q-learning SARSA Temporal difference (TD)
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine-learning venues NIPS ICML ML JMLR ArXiv:cs.LG
Glossary of artificial intelligence Glossary of artificial intelligence
Related articles List of datasets for machine-learning research Outline of machine learning
Txantiloi:Portal-inline
i e a

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.

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 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.

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).

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

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

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 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.

• 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.

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

• Multzokatze (estatistika)
• Dendrograma

• Datuak: Q1277447
• Multimedia: Hierarchical clustering / Q1277447