Ang pamamaraan ng clustering ay ang gawain ng pagpapangkat ng isang hanay ng mga bagay sa paraang ang mga ito sa parehong grupo ay mas magkapareho sa isa't isa kaysa sa mga bagay sa ibang mga industriya. Ito ang pangunahing gawain ng data mining at isang pangkalahatang diskarte sa pagsusuri ng istatistika na ginagamit sa maraming larangan, kabilang ang machine learning, pattern recognition, image recognition, information retrieval, data compression, at computer graphics.
Problema sa pag-optimize
Ang clustering method mismo ay hindi isang partikular na algorithm, ngunit isang pangkalahatang gawain na kailangang lutasin. Maaari itong makamit sa iba't ibang mga algorithm na malaki ang pagkakaiba sa pag-unawa kung ano ang bumubuo sa isang grupo at kung paano ito mahahanap nang mahusay. Kasama sa paggamit ng clustering method para sa pagbuo ng metasubjects ang paggamit ng pangkat na maymaliliit na distansya sa pagitan ng mga miyembro, siksik na rehiyon ng espasyo, pagitan, o ilang partikular na distribusyon ng istatistika. Samakatuwid, ang clustering ay maaaring buuin bilang isang multi-objective na problema sa pag-optimize.
Ang naaangkop na paraan at mga setting ng parameter (kabilang ang mga item gaya ng function ng distansya na gagamitin, ang threshold ng density, o ang bilang ng mga inaasahang cluster) ay nakadepende sa indibidwal na set ng data at sa nilalayong paggamit ng mga resulta. Ang pagsusuri sa gayon ay hindi isang awtomatikong gawain, ngunit isang umuulit na proseso ng pagtuklas ng kaalaman o interactive na multi-layunin na pag-optimize. Kasama sa pamamaraang ito ng clustering ang mga pagsubok na pagsubok at error. Kadalasang kinakailangan na baguhin ang preprocessing ng data at mga parameter ng modelo hanggang sa makuha ng resulta ang mga gustong katangian.
Bilang karagdagan sa terminong "clustering", mayroong ilang mga salita na may katulad na kahulugan, kabilang ang awtomatikong pag-uuri, numerical taxonomy, bothryology at typological analysis. Ang mga banayad na pagkakaiba ay madalas na nakasalalay sa paggamit ng pamamaraan ng clustering upang bumuo ng mga relasyon sa metasubject. Habang sa pagkuha ng data ay interesado ang mga nagreresultang grupo, sa awtomatikong pag-uuri ito na ang kapangyarihan sa diskriminasyon na nagsasagawa ng mga function na ito.
Ang Cluster analysis ay batay sa maraming gawa ni Kroeber noong 1932. Ito ay ipinakilala sa sikolohiya ni Zubin noong 1938 at ni Robert Tryon noong 1939. At ang mga gawaing ito ay ginamit ni Cattell mula noong 1943 upang ipahiwatig ang pag-uuri ng mga pamamaraan ng clustering sa teorya.
Term
Hindi tiyak na matukoy ang konsepto ng "cluster." Isa ito sa mga dahilan kung bakit napakaraming pamamaraan ng clustering. Mayroong isang karaniwang denominator: isang pangkat ng mga bagay ng data. Gayunpaman, ang iba't ibang mga mananaliksik ay gumagamit ng iba't ibang mga modelo. At bawat isa sa mga paggamit na ito ng mga pamamaraan ng clustering ay nagsasangkot ng iba't ibang data. Malaki ang pagkakaiba ng konseptong makikita ng iba't ibang algorithm sa mga katangian nito.
Ang paggamit ng clustering method ay ang susi sa pag-unawa sa mga pagkakaiba sa pagitan ng mga tagubilin. Kasama sa mga karaniwang cluster pattern ang:
- Centroid s. Ito ay, halimbawa, kapag ang k-means clustering ay kumakatawan sa bawat cluster na may isang mean vector.
- Connectivity model s. Ito ay, halimbawa, hierarchical clustering, na bumubuo ng mga modelo batay sa distance connectivity.
- Modelo ng pamamahagi s. Sa kasong ito, ang mga cluster ay na-modelo gamit ang clustering method upang bumuo ng metasubject statistical distributions. Gaya ng multivariate normal separation, na naaangkop sa expectation maximization algorithm.
- Density model s. Ito ay, halimbawa, DBSCAN (Spatial Clustering Algorithm with Noise) at OPTICS (Order Points for Structure Detection), na tumutukoy sa mga cluster bilang mga konektadong siksik na rehiyon sa espasyo ng data.
- modelo ng subspace c. Sa biclustering (kilala rin bilang co-clustering o dalawang mode), ang mga grupo ay namodelo na may parehong mga elemento at may naaangkop na mga katangian.
- Modelo s. Ang ilang mga algorithm ay hindipinong ugnayan para sa kanilang pamamaraan ng clustering upang makabuo ng mga resulta ng meta-subject at magbigay lang ng pagpapangkat ng impormasyon.
- Modelo batay sa mga graph. Isang pangkat, iyon ay, isang subset ng mga node, na ang bawat dalawang koneksyon sa gilid na bahagi ay maaaring ituring bilang isang prototype ng hugis ng cluster. Ang paghina ng kabuuang demand ay kilala bilang quasi-cliques. Eksaktong parehong pangalan ang ipinakita sa HCS clustering algorithm.
- Mga neural na modelo s. Ang pinakakilalang unsupervised network ay ang self-organizing map. At ang mga modelong ito ang kadalasang mailalarawan bilang katulad ng isa o higit pa sa mga pamamaraan ng clustering sa itaas para sa pagbuo ng mga resulta ng meta-subject. Kabilang dito ang mga subspace system kapag ipinatupad ng mga neural network ang kinakailangang anyo ng principal o independent component analysis.
Ang terminong ito ay, sa katunayan, isang hanay ng mga naturang pangkat, na karaniwang naglalaman ng lahat ng mga bagay sa hanay ng mga pamamaraan ng pag-cluster ng data. Bilang karagdagan, maaari nitong ipahiwatig ang kaugnayan ng mga kumpol sa isa't isa, tulad ng isang hierarchy ng mga system na binuo sa bawat isa. Maaaring hatiin ang pagpapangkat sa mga sumusunod na aspeto:
- Hard centroid clustering method. Dito, ang bawat bagay ay kabilang sa isang pangkat o nasa labas nito.
- Soft o malabo na system. Sa puntong ito, ang bawat bagay ay nabibilang na sa isang tiyak na lawak sa anumang kumpol. Tinatawag din itong c-means fuzzy clustering method.
At posible rin ang higit pang mga banayad na pagkakaiba. Halimbawa:
- Strict partitioning clustering. Ditobawat bagay ay nabibilang sa eksaktong isang pangkat.
- Strict partitioning clustering na may mga outlier. Sa kasong ito, ang mga bagay ay maaari ding hindi kabilang sa anumang cluster at ituring na hindi kailangan.
- Ooverlapping clustering (alternatibo din, na may maraming view). Dito, ang mga bagay ay maaaring kabilang sa higit sa isang sangay. Karaniwang kinasasangkutan ng mga solidong cluster.
- Hierarchical clustering na pamamaraan. Ang mga bagay na kabilang sa isang child group ay kabilang din sa parent subsystem.
- Pagbuo ng subspace. Bagama't katulad ng mga magkakapatong na kumpol, sa loob ng isang natatanging tinukoy na sistema, ang mga magkakasamang grupo ay hindi dapat mag-overlap.
Mga Tagubilin
Tulad ng nakasaad sa itaas, ang mga clustering algorithm ay maaaring uriin batay sa kanilang cluster model. Ang sumusunod na pagsusuri ay maglilista lamang ng mga pinakakilalang halimbawa ng mga tagubiling ito. Dahil maaaring mayroong higit sa 100 na-publish na mga algorithm, hindi lahat ay nagbibigay ng mga modelo para sa kanilang mga kumpol at samakatuwid ay hindi madaling mauri.
Walang tiyak na tamang clustering algorithm. Ngunit, tulad ng nabanggit sa itaas, ang pagtuturo ay palaging nasa larangan ng pananaw ng nagmamasid. Ang pinaka-angkop na clustering algorithm para sa isang partikular na problema ay kadalasang kailangang piliin nang eksperimental, maliban kung may matematikal na dahilan para mas gusto ang isang modelo kaysa sa isa pa. Dapat tandaan na ang isang algorithm na idinisenyo para sa isang uri ay karaniwang hindi gumaganaisang dataset na naglalaman ng kakaibang paksa. Halimbawa, hindi mahanap ng k-means ang mga non-convex na grupo.
Connection-based clustering
Kilala rin ang unyon na ito sa pangalan nito, ang hierarchical model. Ito ay batay sa karaniwang ideya na ang mga bagay ay mas konektado sa mga kalapit na bahagi kaysa sa mga bagay na mas malayo. Ang mga algorithm na ito ay nagkokonekta ng mga bagay, na bumubuo ng iba't ibang mga kumpol, depende sa kanilang distansya. Ang isang grupo ay maaaring ilarawan pangunahin sa pamamagitan ng maximum na distansya na kinakailangan upang ikonekta ang iba't ibang bahagi ng cluster. Sa lahat ng posibleng distansya, bubuo ang ibang mga grupo, na maaaring katawanin gamit ang isang dendrogram. Ipinapaliwanag nito kung saan nagmula ang karaniwang pangalan na "hierarchical clustering." Ibig sabihin, ang mga algorithm na ito ay hindi nagbibigay ng isang partition ng dataset, ngunit sa halip ay nagbibigay ng malawak na pagkakasunud-sunod ng awtoridad. Ito ay salamat sa kanya na mayroong isang alisan ng tubig sa bawat isa sa ilang mga distansya. Sa isang dendrogram, ang y-axis ay tumutukoy sa distansya kung saan ang mga kumpol ay magkakasama. At ang mga bagay ay nakaayos sa linyang X para hindi maghalo ang mga grupo.
Ang Connection-based clustering ay isang buong pamilya ng mga pamamaraan na naiiba sa paraan ng kanilang pagkalkula ng mga distansya. Bilang karagdagan sa karaniwang pagpili ng mga function ng distansya, kailangan din ng user na magpasya sa criterion ng koneksyon. Dahil ang isang kumpol ay binubuo ng ilang mga bagay, mayroong maraming mga pagpipilian para sa pag-compute nito. Ang isang popular na pagpipilian ay kilala bilang single-lever grouping, ito ang paraanbuong link, na naglalaman ng UPGMA o WPGMA (unweighted o weighted ensemble ng mga pares na may arithmetic mean, na kilala rin bilang mean link clustering). Bilang karagdagan, ang hierarchical system ay maaaring pinagsama-sama (nagsisimula sa mga indibidwal na elemento at pagsasama-sama ng mga ito sa mga pangkat) o paghahati (nagsisimula sa isang kumpletong set ng data at hatiin ito sa mga seksyon).
Nakabahaging clustering
Ang mga modelong ito ay pinaka malapit na nauugnay sa mga istatistika na nakabatay sa mga hati. Ang mga cluster ay madaling matukoy bilang mga bagay na malamang na kabilang sa parehong distribusyon. Ang isang madaling gamiting tampok ng diskarteng ito ay ang pagkakapareho nito sa paraan ng paggawa ng mga artipisyal na dataset. Sa pamamagitan ng pag-sample ng mga random na bagay mula sa isang pamamahagi.
Bagama't mahusay ang teoretikal na batayan ng mga pamamaraang ito, dumaranas ang mga ito ng isang pangunahing problema, na kilala bilang overfitting, maliban kung may mga limitasyon na ipapataw sa pagiging kumplikado ng modelo. Ang isang mas malaking asosasyon ay karaniwang magpapaliwanag ng data nang mas mahusay, na nagpapahirap sa pagpili ng tamang paraan.
Gaussian mixture model
Ang paraang ito ay gumagamit ng lahat ng uri ng expectation maximization algorithm. Dito, ang dataset ay karaniwang na-modelo ng isang nakapirming (upang maiwasan ang pag-override) na bilang ng mga distribusyon ng Gaussian na random na sinisimulan at ang mga parameter ay paulit-ulit na ino-optimize upang mas magkasya sa dataset. Ang sistemang ito ay magsasama-sama sa isang lokal na pinakamabuting kalagayan. Iyon ang dahilan kung bakit maaaring magbigay ang ilang mga pagtakboiba't ibang resulta. Upang makuha ang pinakamahigpit na clustering, ang mga feature ay kadalasang itinatalaga sa Gaussian distribution na pinakamalamang na kinabibilangan nila. At para sa mas malambot na grupo, hindi ito kailangan.
Ang clustering na nakabatay sa distribusyon ay lumilikha ng mga kumplikadong modelo na maaaring makuha sa huli ang ugnayan at dependency sa pagitan ng mga katangian. Gayunpaman, ang mga algorithm na ito ay nagpapataw ng karagdagang pasanin sa gumagamit. Para sa maraming mga dataset sa totoong mundo, maaaring walang isang maigsi na tinukoy na modelo ng matematika (halimbawa, ipagpalagay na ang distribusyon ng Gaussian ay isang medyo malakas na palagay).
Density based clustering
Sa halimbawang ito, ang mga pangkat ay karaniwang tinutukoy bilang mga lugar na may mas mataas na impermeability kaysa sa iba pang dataset. Ang mga bagay sa mga pambihirang bahaging ito, na kinakailangan upang paghiwalayin ang lahat ng mga bahagi, ay karaniwang itinuturing na ingay at mga gilid ng gilid.
Ang pinakasikat na paraan ng clustering na nakabatay sa density ay ang DBSCAN (Spatial Noise Clustering Algorithm). Hindi tulad ng maraming mas bagong pamamaraan, mayroon itong mahusay na tinukoy na bahagi ng cluster na tinatawag na "density reachability". Katulad ng clustering na nakabatay sa link, nakabatay ito sa mga punto ng koneksyon sa loob ng ilang partikular na threshold ng distansya. Gayunpaman, ang pamamaraang ito ay kinokolekta lamang ang mga item na nakakatugon sa pamantayan ng density. Sa orihinal na bersyon, na tinukoy bilang ang pinakamababang bilang ng iba pang mga bagay sa radius na ito, ang cluster ay binubuo ng lahatmga item na nauugnay sa density (na maaaring bumuo ng isang libreng-form na grupo, hindi tulad ng maraming iba pang mga pamamaraan), at lahat ng mga bagay na nasa loob ng pinapayagang hanay.
Ang isa pang kawili-wiling katangian ng DBSCAN ay ang pagiging kumplikado nito ay medyo mababa - nangangailangan ito ng linear na bilang ng mga query sa hanay laban sa database. At hindi pangkaraniwan ay mahahanap nito ang parehong mga resulta (ito ay deterministiko para sa mga core at noise point, ngunit hindi para sa mga elemento ng hangganan) sa bawat pagtakbo. Samakatuwid, hindi na kailangang patakbuhin ito nang maraming beses.
Ang pangunahing kawalan ng DBSCAN at OPTICS ay ang inaasahan nilang pagbaba ng density upang matukoy ang mga hangganan ng cluster. Halimbawa, sa mga dataset na may magkakapatong na mga distribusyon ng Gaussian-isang karaniwang kaso ng paggamit para sa mga artipisyal na bagay-ang mga hangganan ng kumpol na nabuo ng mga algorithm na ito ay kadalasang lumilitaw na arbitrary. Nangyayari ito dahil patuloy na bumababa ang density ng mga grupo. At sa isang Gaussian mixture na dataset, ang mga algorithm na ito ay halos palaging nangunguna sa mga pamamaraan gaya ng EM clustering, na tumpak na nagagawang imodelo ang mga ganitong uri ng system.
Ang Mean displacement ay isang clustering approach kung saan ang bawat bagay ay gumagalaw sa pinakasiksik na lugar sa kapitbahayan batay sa isang pagtatantya ng buong kernel. Sa huli, ang mga bagay ay nagtatagpo sa lokal na impenetrability maxima. Katulad ng k-means clustering, ang mga "density attractor" na ito ay maaaring magsilbi bilang mga kinatawan para sa isang dataset. Ngunit ang ibig sabihin ng paglilipatmaaaring makakita ng mga kumpol na arbitraryong hugis katulad ng DBSCAN. Dahil sa mahal na umuulit na pamamaraan at pagtatantya ng densidad, kadalasang mas mabagal ang average na displacement kaysa DBSCAN o k-Means. Dagdag pa rito, mahirap ang applicability ng tipikal na shift algorithm sa high-dimensional na data dahil sa hindi pare-parehong gawi ng kernel density estimate, na humahantong sa labis na fragmentation ng mga cluster tails.
Rating
Ang pag-verify ng mga resulta ng clustering ay kasing hirap ng clustering mismo. Kabilang sa mga sikat na diskarte ang "internal" na pagmamarka (kung saan ang sistema ay binabawasan sa isang sukat ng kalidad) at, siyempre, "panlabas" na pagmamarka (kung saan ang clustering ay inihambing sa isang umiiral na "ground truth" na pag-uuri). At ang manu-manong marka ng dalubhasa ng tao at hindi direktang marka ay makikita sa pamamagitan ng pagsusuri sa pagiging kapaki-pakinabang ng clustering sa nilalayong aplikasyon.
Ang mga panloob na hakbang sa flag ay dumaranas ng problema na kinakatawan ng mga ito ang mga feature na maaaring ituring mismo na mga clustering target. Halimbawa, posibleng igrupo ang data na ibinigay ng Silhouette coefficient, maliban na walang alam na mahusay na algorithm para sa paggawa nito. Gamit ang gayong panloob na panukala para sa pagsusuri, mas mainam na ihambing ang pagkakatulad ng mga problema sa pag-optimize.
Ang panlabas na marka ay may mga katulad na problema. Kung may mga ganitong label ng "ground truth", hindi na kailangang mag-cluster. At sa mga praktikal na aplikasyon, kadalasan ay walang ganoong mga konsepto. Sa kabilang banda, ang mga label ay nagpapakita lamang ng isang posibleng partition ng set ng data, na hindi ibig sabihinna wala nang iba pang (marahil ay mas mahusay) clustering.
Kaya wala sa mga pamamaraang ito ang maaaring humatol sa aktwal na kalidad. Ngunit nangangailangan ito ng pagsusuri ng tao, na lubos na subjective. Gayunpaman, ang mga naturang istatistika ay maaaring maging impormasyon sa pagtukoy ng mga masasamang kumpol. Ngunit hindi dapat balewalain ang pansariling pagtatasa ng isang tao.
Inner mark
Kapag nasuri ang resulta ng clustering batay sa data na mismong na-cluster, ito ay tinutukoy bilang terminong ito. Ang mga pamamaraang ito ay karaniwang nagtatalaga ng pinakamahusay na resulta sa isang algorithm na lumilikha ng mga pangkat na may mataas na pagkakapareho sa loob at mababa sa pagitan ng mga pangkat. Ang isa sa mga kawalan ng paggamit ng panloob na pamantayan sa pagsusuri ng kumpol ay ang mataas na mga marka ay hindi kinakailangang humantong sa epektibong mga aplikasyon sa pagkuha ng impormasyon. Gayundin, ang markang ito ay may kinikilingan sa mga algorithm na gumagamit ng parehong modelo. Halimbawa, ang k-means clustering ay natural na nag-o-optimize ng mga feature distance, at ang isang panloob na criterion batay dito ay malamang na mag-overestimate sa resultang clustering.
Samakatuwid, ang mga hakbang sa pagsusuri na ito ay pinakaangkop upang makakuha ng ideya ng mga sitwasyon kung saan ang isang algorithm ay gumaganap nang mas mahusay kaysa sa isa pa. Ngunit hindi ito nangangahulugan na ang bawat impormasyon ay nagbibigay ng mas maaasahang mga resulta kaysa sa iba. Ang validity period na sinusukat ng naturang index ay depende sa assertion na ang structure ay umiiral sa dataset. Ang isang algorithm na binuo para sa ilang mga uri ay walang pagkakataon kung ang hanay ay naglalaman ng radikalibang komposisyon o kung ang pagtatasa ay sumusukat ng iba't ibang pamantayan. Halimbawa, ang k-means clustering ay makakahanap lang ng mga convex na cluster, at maraming mga score index ang may parehong format. Sa isang dataset na may mga non-convex na modelo, hindi naaangkop na gumamit ng k-means at karaniwang pamantayan sa pagsusuri.
Panlabas na pagsusuri
Sa ganitong uri ng balling, sinusuri ang mga resulta ng clustering batay sa data na hindi ginamit para sa pagpapangkat. Iyon ay, tulad ng mga kilalang label ng klase at mga panlabas na pagsubok. Ang mga naturang tanong ay binubuo ng isang set ng mga pre-classified na item at kadalasang ginagawa ng mga eksperto (mga tao). Dahil dito, ang mga reference kit ay makikita bilang pamantayang ginto para sa pagsusuri. Ang mga uri ng pamamaraan ng pagmamarka na ito ay sumusukat kung gaano kalapit ang clustering sa mga ibinigay na reference na klase. Gayunpaman, napag-usapan kamakailan kung ito ay sapat para sa totoong data o para lamang sa mga sintetikong hanay na may aktwal na katotohanan. Dahil ang mga klase ay maaaring maglaman ng panloob na istraktura, at ang mga umiiral na katangian ay maaaring hindi payagan ang paghihiwalay ng mga kumpol. Gayundin, mula sa isang pananaw sa pagtuklas ng kaalaman, ang pagpaparami ng mga kilalang katotohanan ay maaaring hindi nangangahulugang makagawa ng inaasahang resulta. Sa isang espesyal na senaryo ng pinaghihigpitang clustering kung saan ginagamit na ang meta-impormasyon (tulad ng mga label ng klase) sa proseso ng pagpapangkat, hindi mahalaga na panatilihin ang lahat ng impormasyon para sa mga layunin ng pagsusuri.
Ngayon ay malinaw na kung ano ang hindi naaangkop sa mga pamamaraan ng clustering, at kung anong mga modelo ang ginagamit para sa mga layuning ito.
