Multzokatze hierarkiko

Wikipedia, Entziklopedia askea
Jump to navigation Jump to search

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[aldatu | aldatu iturburu kodea]

Metrika[aldatu | aldatu iturburu kodea]

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
Manhattan distantzia
Distantzia euklidear karratua
Distantzia maximoa
Mahalanobisen distantzia 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[aldatu | aldatu iturburu kodea]

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
Distantzia minimoa
Batezbesteko distantzia
Zentroideen arteko distantzia non eta s eta t multzoen zentroideak diren, hurrenez hurren.
Energia minimoa

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[aldatu | aldatu iturburu kodea]

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

Multzokatze hierarkikorako algoritmo arruntak -ko konplexutasun denbora du eta -ko memoria behar izaten du. Horrek, algoritmoa nahiko motela izatea eragiten du. Hala ere, 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 (-ko bilaketa zehatza (exhaustiboa) izan ezik). Hala ere, ohikoa da azkarragoak diren hurbilpen algoritmoak erabiltzea, adibidez, partiziozko multzokatzea (ingelesez k-means).

Adibidea. Multzokatze pilatzailea[aldatu | aldatu iturburu kodea]

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 multzoko elementuaren eta multzoko elementuaren arteko distantziak definitzen du eta multzoen arteko distantzia.
  • Distantzia minimoa: Distantzia minimora dauden multzoko elementuaren eta multzoko elementuaren arteko distantziak definitzen du eta multzoen arteko distantzia.
  • Batezbesteko distantzia: Bi multzoetako elementu guztien arteko batezbesteko distantziak definitzen du eta multzoen arteko distantzia.

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[aldatu | aldatu iturburu kodea]

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 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[aldatu | aldatu iturburu kodea]

Kode irekikoak[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

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

Erreferentziak[aldatu | aldatu iturburu kodea]

  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 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[aldatu | aldatu iturburu kodea]