Suure hulga vaatluste korral ei sobi klasteranalüüsi hierarhilised meetodid. Sellistel juhtudel kasutatakse jagamisel põhinevaid mittehierarhilisi meetodeid, mis on iteratiivsed meetodid algse populatsiooni tükeldamiseks. Jagamise käigus moodustuvad uued klastrid kuni peatamisreegli täitmiseni.
Selline mittehierarhiline rühmitamine seisneb andmekogumi jagamises teatud arvuks eraldiseisvateks klastriteks. On kaks lähenemist. Esimene on defineerida klastrite piirid kui kõige tihedamad alad algandmete mitmemõõtmelises ruumis, s.o. klastri määratlus, kus on suur "punktide kontsentratsioon". Teine lähenemisviis on objektide erinevuse mõõtmise minimeerimine
Algoritm k-means (k-means)
Mittehierarhiliste meetodite seas on kõige levinum k-keskmiste algoritm, mida nimetatakse ka kiireks klasteranalüüsiks. Algoritmi täieliku kirjelduse leiate artiklist Hartigan ja Wong (1978). Erinevalt hierarhilistest meetoditest, mis ei nõua esialgseid eeldusi klastrite arvu kohta, on selle meetodi kasutamiseks vajalik hüpotees kõige tõenäolisema klastrite arvu kohta.
K-keskmise algoritm loob k klastrit, mis on üksteisest võimalikult kaugel. Peamine probleemide tüüp, mida k-keskmise algoritm lahendab, on eelduste (hüpoteeside) olemasolu klastrite arvu kohta, samas kui need peaksid olema võimalikult erinevad. Arvu k valik võib põhineda varasematel uuringutel, teoreetilistel kaalutlustel või intuitsioonil.
Algoritmi üldidee: antud kindlat arvu k vaatlusklastreid võrreldakse klastritega nii, et klastri keskmised (kõikide muutujate puhul) erinevad üksteisest võimalikult palju.
Algoritmi kirjeldus
- Objektide esialgne jaotus klastrite kaupa. Valitakse arv k ja esimeses etapis loetakse need punktid klastrite "keskpunktideks". Iga klaster vastab ühele keskusele.
Esialgsete tsentroidide valiku saab teha järgmiselt:
- k-vaatluste valik algkauguse maksimeerimiseks;
- juhuslik valik k-vaatlusi;
- esimeste k-vaatluste valik.
Selle tulemusena määratakse iga objekt konkreetsesse klastrisse. - Iteratiivne protsess. Arvutatakse välja klastrite keskpunktid, mida siis ja edasi loetakse klastrite koordinaatkeskväärtusteks. Objektid jaotatakse uuesti ümber.
Keskuste arvutamise ja objektide ümberjaotamise protsess jätkub, kuni on täidetud üks järgmistest tingimustest:
- klastrite keskused on stabiliseerunud; kõik vaatlused kuuluvad klastrisse, kuhu nad kuulusid enne praegust iteratsiooni;
- iteratsioonide arv on võrdne maksimaalse iteratsioonide arvuga.
Joonis 1 – K-keskmise algoritmi (k=2) toimimise näide
Klastrite arvu valik on keeruline küsimus. Kui selle arvu kohta eeldusi pole, on soovitav tulemusi võrrelda 2 klastrit, seejärel 3, 4, 5 jne.
Klastrite kvaliteedi kontrollimine
Pärast k-keskmiste meetodil klasteranalüüsi tulemuste saamist tuleks kontrollida klastri moodustamise õigsust (st hinnata, kuidas klastrid erinevad üksteisest). Selleks arvutatakse iga klastri keskmised väärtused. Hea klasterdamine peaks andma kõigi mõõtmiste või vähemalt enamiku mõõtmiste jaoks väga erinevaid vahendeid.
K-keskmise algoritmi eelised:
- kasutusmugavus;
- kasutuskiirus;
- algoritmi selgus ja läbipaistvus.
- Algoritm on liiga tundlik kõrvalekallete suhtes, mis võivad keskmist moonutada. Selle probleemi võimalikuks lahenduseks on kasutada algoritmi modifikatsiooni – k-mediaanalgoritmi;
- Algoritm võib suurtes andmebaasides olla aeglane. Selle probleemi võimalik lahendus on andmete valimi kasutamine.
PAM on k-keskmise algoritmi modifikatsioon, k-mediaanalgoritm (k-medoidid).
Algoritm on andmemüra ja kõrvalekallete suhtes vähem tundlik kui k-keskmiste algoritm, kuna mediaani mõjutavad kõrvalekalded vähem.
PAM on efektiivne väikeste andmebaaside jaoks, kuid seda ei tohiks kasutada suurte andmekogude jaoks. Mõõtmete eelvähendamine
Kaaluge näidet. On olemas ettevõtte klientide andmebaas, mis tuleks jagada homogeenseteks rühmadeks. Iga klienti kirjeldatakse 25 muutuja abil. Nii suure hulga muutujate kasutamine toob kaasa hägusa struktuuriga klastrite valiku. Seetõttu on analüütikul üsna raske tõlgendada tekkinud klastreid.
Arusaadavamaid ja läbipaistvamaid klasterdamistulemusi saab siis, kui algmuutujate komplekti asemel kasutatakse mõnda üldistatud muutujat või kriteeriumi, mis sisaldavad tihendatud kujul infot muutujatevaheliste seoste kohta. Need. tekib andmete mõõtmete vähendamise probleem. Seda saab lahendada erinevate meetoditega; üks levinumaid on faktoranalüüs. Peatume sellel üksikasjalikumalt.
Faktoranalüüs
Faktoranalüüs on meetod, mida kasutatakse muutujate väärtuste vaheliste seoste uurimiseks.
Üldiselt on faktorianalüüsil kaks eesmärki:
- muutujate arvu vähendamine;
- muutujate klassifikatsioon - muutujatevaheliste seoste struktuuri määramine.
Faktoranalüüsi tulemusena tuvastatud kriteeriumid või peamised tegurid sisaldavad tihendatud kujul teavet muutujatevaheliste olemasolevate seoste kohta. See teave võimaldab teil saada paremaid klastrite moodustamise tulemusi ja selgitada paremini klastrite semantikat. Faktoritele endile saab anda teatud tähenduse.
Faktoranalüüsi abil taandatakse suur hulk muutujaid väiksemaks arvuks sõltumatuteks mõjutavateks suurusteks, mida nimetatakse teguriteks.
Tihendatud kujul olev tegur sisaldab teavet mitme muutuja kohta. Muutujad, mis on üksteisega tugevas korrelatsioonis, ühendatakse üheks teguriks. Faktoranalüüsi tulemusena leitakse sellised keerulised tegurid, mis selgitavad võimalikult täpselt vaadeldavate muutujate vahelisi seoseid.
Faktoranalüüsi esimeses etapis standardiseeritakse muutujate väärtused, mille vajadust käsitleti eelmises loengus.
Faktoranalüüs põhineb hüpoteesil, et analüüsitavad muutujad on suhteliselt väikese hulga mõne varjatud teguri kaudsed ilmingud.
Faktoranalüüs on meetodite kogum, mis keskendub vaadeldavate muutujate vaheliste varjatud sõltuvuste tuvastamisele ja analüüsimisele. Varjatud sõltuvusi nimetatakse ka varjatud sõltuvusteks.
Üks faktorianalüüsi meetoditest – põhikomponentide meetod – põhineb eeldusel, et tegurid on üksteisest sõltumatud.
Iteratiivne klasterdamine SPSS-is Tavaliselt rakendatakse statistikapakettides laia meetodite arsenali, mis võimaldab esmalt vähendada andmestiku dimensiooni (näiteks faktoranalüüsi abil) ja seejärel ise klastrida (näiteks kiirklasteranalüüsi meetodi abil) . Kaaluge seda võimalust SPSS-i paketis klasterdamiseks.
Algandmete mõõtme vähendamiseks kasutame faktoranalüüs. Selleks valige menüüst: Analüüsi (Analüüs) / Andmete redutseerimine (Andmete teisendamine) / Tegur (Faktoranalüüs):
Ekstraheerimismeetodi valimiseks kasutage nuppu Ekstraheerimine:. Jätame ülalmainitud põhikomponentide vaikeanalüüsi. Samuti peaksite valima pöörlemismeetodi - valime ühe populaarseima - varimaxi meetodi. Faktoriväärtuste muutujatena salvestamiseks tuleb vahekaardil "Väärtused" märkida "Salvesta muutujatena".
Selle protseduuri tulemusena saab kasutaja aruande "Selgitatud kogudispersioon", mis näitab valitud tegurite arvu - need on komponendid, mille omaväärtused ületavad ühe.
Saadud tegurite väärtusi, millele tavaliselt antakse nimed fakt1_1, fakt1_2 jne, kasutatakse klasteranalüüsiks k-means meetodil. Kiire klastrianalüüsi tegemiseks valige menüüst:
Analüüsi/Classify/K-Means Cluster: (K-means cluster analysis).
Dialoogiboksis K Means Cluster Analysis (Cluster analysis by k-means) tuleb panna tegurimuutujad fact1_1, fact1_2 jne. testitud muutujate valdkonnas. Siin tuleb määrata ka klastrite arv ja iteratsioonide arv.
Selle protseduuri tulemusena saame aruande, mis sisaldab moodustunud klastrite tsentrite väärtuste väljundit, igas klastris tehtud vaatluste arvu ja kasutaja määratud lisateavet.
Seega jagab k-keskmise algoritm algandmete hulga etteantud arvuks klastriteks. Saadud tulemuste visualiseerimiseks tuleks kasutada üht graafikutest, näiteks hajuvusgraafikut. Traditsiooniline visualiseerimine on aga võimalik piiratud arvu dimensioonide puhul, sest teadupärast suudab inimene tajuda vaid kolmemõõtmelist ruumi. Seega, kui analüüsida rohkem kui kolme muutujat, tuleks info esitamiseks kasutada spetsiaalseid mitmemõõtmelisi meetodeid, neist tuleb juttu mõnes järgnevas kursuse loengus.
Iteratiivsed klastrimeetodid erinevad järgmiste parameetrite valiku poolest:
- alguspunkt;
- uute klastrite moodustamise reegel;
- peatamise reegel.
Näiteks kui SPSS-is on vaja töötada nii kvantitatiivsete (näiteks sissetulek) kui ka kategooriliste (näiteks perekonnaseis) muutujatega ja ka piisavalt suure andmemahu korral, on kaheastmelise klastrianalüüsi meetod. kasutatud, mis on skaleeritav klasterdamisprotseduur.analüüs, mis võimaldab töötada erinevat tüüpi andmetega. Selleks rühmitatakse kirjed töö esimeses etapis suureks arvuks alamklastriteks. Teises etapis rühmitatakse saadud alamklastrid vajalikuks arvuks. Kui see arv on teadmata, määrab protseduur ise selle automaatselt. Selle protseduuriga saab pangatöötaja valida näiteks inimeste gruppe, kasutades samaaegselt selliseid näitajaid nagu vanus, sugu ja sissetulekute tase. Saadud tulemused võimaldavad tuvastada kliente, keda ähvardab laenumaksehäire.
Üldjuhul on kõik klasteranalüüsi etapid omavahel seotud ja ühes neist tehtud otsused määravad toimingud järgmistes etappides.
Analüütik peab otsustama, kas kasutada kõiki vaatlusi või jätta andmestikust välja mõned andmed või proovid.
Mõõdiku valik ja lähteandmete standardimise meetod.
Klastrite arvu määramine (iteratiivseks klastrite analüüsiks).
Klasterdamismeetodi määratlemine (liitmis- või sidumisreeglid).
Paljude ekspertide hinnangul on klastrite vormi ja spetsiifilisuse määramisel määravaks klastrimeetodi valik.
Klastrite tulemuste analüüs. See etapp hõlmab järgmiste küsimuste lahendamist: kas tulemuseks olev klasterdamine on juhuslik; kas partitsioon on andmete alamvalimitel usaldusväärne ja stabiilne; kas klasterdamise tulemuste ja klastri moodustamise protsessis mitteosalenud muutujate vahel on seos; kas klasterdamise tulemusi on võimalik tõlgendada.
Klastrite tulemuste kontrollimine. Klasterdamise tulemusi tuleks kontrollida ka formaalsete ja mitteametlikud meetodid. Formaalsed meetodid sõltuvad klastrite moodustamiseks kasutatavast meetodist. Mitteametlikud toimingud hõlmavad järgmisi klastrite kvaliteedi kontrollimise protseduure:
- andmestiku teatud näidistel saadud klasterdamistulemuste analüüs;
- ristvalideerimine;
- rühmitamise teostamine vaatluste järjekorra muutmisel andmekogumis;
- klasterdamise läbiviimine mõne vaatluse kustutamisel;
- rühmitus väikestele proovidele.
Klasteranalüüsi rakendamisel tekkida võivad raskused ja probleemid
Nagu kõigil teistel meetoditel, on ka klasteranalüüsi meetoditel kindel nõrgad küljed, st. mõningaid raskusi, probleeme ja piiranguid.
Klasteranalüüsi läbiviimisel tuleb arvestada, et klasterdamise tulemused sõltuvad lähteandmete kogumi poolitamise kriteeriumidest. Andmemõõtme vähendamisel võivad tekkida teatud moonutused, üldistuste tõttu võivad mõned objektide individuaalsed omadused kaduda.
Enne rühmitamist tuleks arvesse võtta mitmeid keerukusi.
- Klasterdamise aluseks olevate tunnuste valiku keerukus. Läbimõtlemata valik toob kaasa ebapiisava jaotuse klastriteks ja selle tulemusena probleemi vale lahenduseni.
- Raskused rühmitusmeetodi valimisel. See valik eeldab meetodite ja nende kasutamise eelduste head tundmist. Konkreetse meetodi tõhususe kontrollimiseks konkreetses ainevaldkonnas on soovitatav rakendada järgmist protseduuri: kaaluda mitut rühma, mis on a priori üksteisest erinevad, ja segada nende esindajad juhuslikult üksteisega. Järgmisena viiakse läbi rühmitamine, et taastada algne partitsioon klastriteks. Objektide kokkulangemiste osakaal tuvastatud ja algrühmades on meetodi efektiivsuse näitaja.
- Klastrite arvu valiku probleem. Kui klastrite võimaliku arvu kohta pole teavet, on vaja läbi viia rida katseid ja erineva arvu klastrite loendamise tulemusena valida nende optimaalne arv.
- Klastrite tulemuste tõlgendamise probleem. Klastrite vormi määrab enamikul juhtudel seostamismeetodi valik. Siiski tuleb arvestada, et spetsiifilised meetodid kipuvad looma teatud kujuga klastreid, isegi kui tegelikult pole uuritavas andmekogumis klastreid.
Enne klasterdamist võib analüütikul tekkida küsimus, millist klasteranalüüsi meetodite rühma eelistada. Valides hierarhiliste ja mittehierarhiliste meetodite vahel, on vaja arvestada järgmiste tunnustega.
Mittehierarhilised meetodid näitavad suuremat vastupidavust mürale ja kõrvalekalletele, valet mõõdiku valikut, ebaoluliste muutujate kaasamist klastrisse kaasatud komplekti. Meetodi eeliste eest tuleb maksta sõna "a priori". Analüütik peab eelnevalt kindlaks määrama klastrite arvu, iteratsioonide arvu või peatamisreegli, aga ka mõned muud klastri parameetrid. See on eriti raske algajatele.
Kui klastrite arvu kohta pole eeldusi, on soovitatav kasutada hierarhilisi algoritme. Kui aga valimi suurus seda ei võimalda, on võimalik viis läbi viia katseseeria erineva arvu klastritega, näiteks hakata andmestikku kahest rühmast jagama ja nende arvu järk-järgult suurendades võrrelda tulemusi. Tänu sellele tulemuste "variatsioonile" saavutatakse piisavalt suur klastrite paindlikkus.
Hierarhilised meetodid, erinevalt mittehierarhilistest, keelduvad klastrite arvu määramisest, vaid loovad tervikliku pesastatud klastrite puu.
Hierarhiliste klasterdamismeetodite keerukus: andmestiku mahu piiramine; läheduse mõõtmise valik; saadud klassifikatsioonide paindumatus.
Selle meetodite rühma eeliseks võrreldes mittehierarhiliste meetoditega on nende selgus ja võimalus saada üksikasjalik ülevaade andmestruktuurist.
Hierarhiliste meetodite kasutamisel on võimalik üsna lihtsalt tuvastada andmekogus kõrvalekaldeid ja seeläbi parandada andmete kvaliteeti. See protseduur on kaheastmelise rühmitamisalgoritmi aluseks. Sellist andmekogumit saab hiljem kasutada mittehierarhiliseks rühmitamiseks.
On veel üks aspekt, mida selles loengus juba mainitud. See on kogu andmekogumi või selle valimi rühmitamine. See aspekt on oluline mõlema vaadeldava meetodirühma jaoks, kuid see on kriitilisem hierarhiliste meetodite puhul. Hierarhilised meetodid ei saa töötada suurte andmehulkidega ning mingi valiku kasutamine, s.t. osa andmetest võimaldaks neid meetodeid rakendada.
Klasterdamistulemustel ei pruugi olla piisavat statistilist põhjendust. Teisest küljest on klastriprobleemide lahendamisel vastuvõetav saadud tulemuste mittestatistiline tõlgendus, aga ka üsna suur valik klastri kontseptsiooni võimalusi. Selline mittestatistiline tõlgendus võimaldab analüütikul saada rahuldavaid klasterdamistulemusi, mis on teiste meetodite kasutamisel sageli keeruline.
Uued algoritmid ja mõned klastrianalüüsi algoritmide modifikatsioonid
Meetodid, mida oleme selles ja varasemates loengutes käsitlenud, on klasteranalüüsi "klassika". Kuni viimase ajani oli peamiseks kriteeriumiks, mille järgi klastrite algoritmi hinnati, klasterdamise kvaliteet: eeldati, et kogu andmehulk sobib muutmälu.
Kuid nüüd, seoses ülisuurte andmebaaside tulekuga, on uued nõuded, millele klasterdamisalgoritm peab vastama. Peamine, nagu eelmistes loengutes mainitud, on algoritmi skaleeritavus.
Märgime ka muid omadusi, millele klasterdamisalgoritm peab vastama: tulemuste sõltumatus sisendandmete järjekorrast; algoritmi parameetrite sõltumatus sisendandmetest.
Viimasel ajal on aktiivselt arendatud uusi rühmitusalgoritme, mis on võimelised töötlema üli suuri andmebaase. Nad keskenduvad skaleeritavusele. Sellised algoritmid hõlmavad üldistatud klastri esitust, samuti valimi võtmist ja andmestruktuuride kasutamist, mida toetab aluseks olev DBMS.
On välja töötatud algoritmid, milles hierarhilised klasterdamismeetodid on integreeritud teiste meetoditega. Nende algoritmide hulka kuuluvad: KASK, CURE, KAMEELEON, KIVI.
Algoritm BIRCH (tasakaalustatud iteratiivne redutseerimine ja rühmitamine hierarhiate abil)
Algoritmi pakkusid välja Tian Zang ja tema kolleegid.
Tänu klastrite üldistatud esitustele suureneb klastrite moodustamise kiirus, samas kui algoritmil on suur skaleerimine.
See algoritm rakendab kaheetapilise klastrite moodustamise protsessi.
Esimese etapi käigus moodustatakse esialgne klastrite komplekt. Teises etapis rakendatakse tuvastatud klastritele muid klastrite moodustamise algoritme, mis sobivad RAM-is töötamiseks.
Järgmises analoogias kirjeldatakse seda algoritmi. Kui mõelda igast andmeelemendist kui laua pinnal lebavast helmest, siis saab helmeste kobarad "asendada" tennisepallide vastu ja teha tennisepalliklastrite täpsema uuringu. Helmeste arv võib olla üsna suur, kuid tennisepallide läbimõõtu saab valida selliselt, et teises etapis oleks võimalik traditsiooniliste klasterdamisalgoritmide abil määrata klastrite tegelik komplekskuju.
WaveCluster algoritm
WaveCluster on laineteisendustel põhinev klasterdamisalgoritm. Algoritmi alguses üldistatakse andmed, kehtestades andmeruumile mitmemõõtmelise võre. Algoritmi edasistes etappides ei analüüsita mitte üksikuid punkte, vaid võre ühte lahtrisse langevate punktide üldistatud omadusi. Sellise üldistuse tulemusena mahub vajalik info RAM-i. Järgnevates etappides rakendab algoritm klastrite määramiseks üldistatud andmetele laineteisendust.
WaveClusteri peamised omadused:
- rakendamise keerukus;
- algoritm suudab tuvastada suvalise kujuga klastreid;
- algoritm ei ole müra suhtes tundlik;
- algoritm on rakendatav ainult väikesemõõtmeliste andmete puhul.
CLARA algoritmi töötasid välja Kaufmann ja Rousseeuw 1990. aastal, et koondada andmeid suurtesse andmebaasidesse. See algoritm on ehitatud statistilistesse analüüsipakettidesse, näiteks S+.
Kirjeldame lühidalt algoritmi olemust. CLARA algoritm hangib andmebaasist palju näidiseid. Klasterdamist rakendatakse igale valimile, algoritmi väljundina pakutakse välja parim klasterdamine.
Suurte andmebaaside puhul on see algoritm tõhusam kui PAM-algoritm. Algoritmi efektiivsus sõltub valimiks valitud andmekogumist. Valitud komplekti hea rühmitamine ei pruugi anda head rühmitust kogu andmekogumile.
Algoritmid Clarans, CURE, DBScan
Claransi algoritm (suurte rakenduste rühmitamine, mis põhineb RANdomiseeritud otsingul) sõnastab klastriprobleemi juhusliku otsinguna graafikus. Selle algoritmi tulemusena on graafiku sõlmede kogum andmestiku jaotus kasutaja määratud arvuks klastriteks. Saadud klastrite "kvaliteet" määratakse kriteeriumi funktsiooni abil. Claransi algoritm sorteerib vastuvõetava lahenduse otsimiseks kõik võimalikud andmekogumi partitsioonid. Lahenduse otsimine peatub sõlmes, kus saavutatakse etteantud arvu kohalike miinimumide hulgast miinimum.
Uutest skaleeritavatest algoritmidest võib välja tuua ka CURE algoritmi - hierarhilise klastri moodustamise algoritmi ja DBScani algoritmi, kus klastri mõiste formuleeritakse tiheduse kontseptsiooni kasutades.
BIRCH, Clarans, CURE, DBScan algoritmide peamiseks puuduseks on asjaolu, et nad nõuavad teatud punktitiheduse lävede määramist, mis ei ole alati vastuvõetav. Need piirangud tulenevad sellest, et kirjeldatud algoritmid on keskendunud väga suurtele andmebaasidele ega saa kasutada suuri arvutusressursse.
Paljud teadlased tegelevad aktiivselt skaleeritavate meetodite kallal, mille peamiseks ülesandeks on ületada tänapäeval eksisteerivate algoritmide puudused.
Suure hulga vaatluste korral ei sobi klasteranalüüsi hierarhilised meetodid. Sellistel juhtudel kasutatakse mittehierarhilisi jaotuspõhiseid meetodeid, mis on iteratiivsed meetodid algse populatsiooni poolitamine. Jagamise käigus moodustuvad uued klastrid kuni peatamise reegel.
Selline mittehierarhiline rühmitamine seisneb andmekogumi jagamises teatud arvuks eraldiseisvateks klastriteks. On kaks lähenemist. Esimene on defineerida klastrite piirid kui kõige tihedamad alad algandmete mitmemõõtmelises ruumis, s.o. klastri määratlus, kus on suur "punktide kontsentratsioon". Teine lähenemisviis on objektide erinevuse mõõtmise minimeerimine
Algoritm k-means (k-means)
Levinuim mittehierarhiliste meetodite seas k-tähendab algoritm, nimetatud ka kiire klastrianalüüs. Algoritmi täieliku kirjelduse leiate artiklist Hartigan ja Wong (1978). Erinevalt hierarhilistest meetoditest, mis ei nõua esialgseid eeldusi klastrite arvu kohta, on selle meetodi kasutamiseks vajalik hüpotees kõige tõenäolisema klastrite arvu kohta.
k-tähendab algoritm ehitab k klastrit, mis asuvad üksteisest võimalikult suurel kaugusel. Peamised probleemide tüübid, mis lahendatakse k-tähendab algoritm, - eelduste (hüpoteeside) olemasolu klastrite arvu kohta, samas kui need peaksid olema võimalikult erinevad. Arvu k valik võib põhineda varasematel uuringutel, teoreetilistel kaalutlustel või intuitsioonil.
Algoritmi üldidee: antud kindlat arvu k vaatlusklastreid võrreldakse klastritega nii, et klastri keskmised (kõikide muutujate puhul) erinevad üksteisest võimalikult palju.
Algoritmi kirjeldus
- Objektide esialgne jaotus klastrite kaupa.
Valitakse arv k ja esimeses etapis loetakse need punktid klastrite "keskpunktideks". Iga klaster vastab ühele keskusele.
Esialgsete tsentroidide valiku saab teha järgmiselt:
- k-vaatluste valimine algkauguse maksimeerimiseks;
- juhuslik valik k-vaatlusi;
- esimeste k-vaatluste valik.
Selle tulemusena määratakse iga objekt konkreetsesse klastrisse.
- Iteratiivne protsess.
Arvutatakse klastri keskused, mis siis ja allpool on klastrite koordinaatide keskmised. Objektid jaotatakse uuesti ümber.
Keskuste arvutamise ja objektide ümberjaotamise protsess jätkub, kuni on täidetud üks järgmistest tingimustest:
- klastrikeskused on stabiliseerunud, s.t. kõik vaatlused kuuluvad klastrisse, kuhu nad kuulusid enne praegust iteratsiooni;
- iteratsioonide arv on võrdne maksimaalse iteratsioonide arvuga.
Joonisel fig. 14.1 on töö näide k-tähendab algoritm kui k on võrdne kahega.
Riis. 14.1.
Klastrite arvu valik on keeruline küsimus. Kui selle arvu kohta eeldusi pole, on soovitav tulemusi võrrelda 2 klastrit, seejärel 3, 4, 5 jne.
Klasteranalüüs on statistiline analüüs, mis võimaldab jagada suure hulga andmeid klassidesse või rühmadesse (inglise keelest, klaster- klass) mõne kriteeriumi või nende kombinatsiooni järgi.
Andmete klassifitseerimiseks X x,...,X lk kasutada meetrika või kauguse mõistet.
meetriline on funktsioon p, mis kaardistab mingi meetrilise ruumi reaalarvude ruumi ja millel on järgmised omadused (meetrilised aksioomid):
- 1) p(ZD>0,
- 2) p(X,Y)=p(Y, X),
- 3) p(X, Y) = 0 X=Y
- 4) P(X,Y) P(Z, Y).
Klasteranalüüsi teooria kasutab üksikute punktide (vektorite) vahelise kauguse mõõtmiseks järgmisi mõõdikuid:
1) Eukleidiline kaugus
2) kaalutud eukleidiline kaugus
Kus nädal - kaalud, mis on proportsionaalsed tunnuse tähtsusega klassifitseerimisülesandes. Kaalud määratakse pärast täiendavaid uuringuid
ja oletame, et ^ w* = 1;
- 3) hammimise kaugus (või linnaplokk) - vahemaa kaardil kvartalite vahel linnas
4) Mahalanobise kaugus (või Mahalanobise nurk)
kus A on sümmeetriline positiivselt määratud kaalumaatriks (sageli valitakse diagonaalseks); A - vektori kovariatsioonimaatriks X 19 ..., X p;
5) Minkowski kaugus
Kaugusi 1), 2), 3) või 5) kasutatakse sõltumatute juhuslike suuruste normaaljaotuse korral X l9 ...,X n ~N(M,A) või nende homogeensuse korral geokeemilises mõttes, kui iga vektor on klassifitseerimisel võrdselt oluline. Distance 4) kasutatakse vektorite kovariatsioonisuhe olemasolu korral X x,...,X P.
Mõõdiku valiku teeb uurija, olenevalt sellest, millist tulemust ta saada soovib. Seda valikut ei vormistata, kuna see sõltub paljudest teguritest, eriti oodatavast tulemusest, teadlase kogemusest, tema matemaatilise ettevalmistuse tasemest jne.
Paljudes algoritmides kasutatakse koos vektorite vahemaadega ka klastrite ja klastrite ühenduste vahelisi kaugusi.
Lase S(- /-nda klaster, mis koosneb n t vektorid või punktid. Lase
X (l) - valimi keskmine klastrisse langevate punktide kohal S f , ehk klastri raskuskese 5.. Siis eristatakse järgmisi kaugusi klastrite vahel, mille sees ei ole teisi klastreid:
1) klastrite vaheline kaugus “lähinaabri” põhimõttel
2) klastrite vaheline kaugus vastavalt "kaugnaabri" põhimõttele
3) rühmade raskuskeskmete vaheline kaugus
4) klastrite vaheline kaugus vastavalt "keskmise ühenduse" põhimõttele
5) üldistatud Kolmogorovi kaugus
Klastrite vahelise kauguse, mis on teiste klasside liit, saab arvutada üldvalemi abil:
Kus S^k^- klasside kombineerimisel saadud klaster S k Ja S t .
Kõik kauguste erijuhud saadakse sellest üldistatud valemist. Kui a = p = 1/2, 8 = -1/2, y = 0, on meil kaugus "lähinaabri" põhimõttel, kus a = p = 5 = 1/2, y = O - "kauge naaber",
\u003d ---, p \u003d---, 5 \u003d 0, y \u003d 0 - kaugusel piki raskuskeskmeid
p k + n i p k + n i
rühmad.
Klasteranalüüsi meetodid jagunevad I) aglomeratiivseks (ühendavaks), II) jagunevaks (eraldavaks) ja III) iteratiivseks.
Esimesed ühendavad üksikuid objekte järjekindlalt klastriteks, teised, vastupidi, tükeldavad klastreid objektideks. Kolmas ühendab kaks esimest. Nende eripäraks on partitsioonitingimustel (nn parameetritel) põhinevate klastrite moodustamine, mida saab algoritmi töö käigus partitsiooni kvaliteedi parandamiseks muuta. Suure teabehulga klassifitseerimiseks kasutatakse tavaliselt iteratiivseid meetodeid.
Vaatleme üksikasjalikumalt aglomeratiivseid meetodeid. Aglomeratiivsed meetodid on klasteranalüüsi algoritmide seas kõige lihtsamad ja levinumad. Esimeses etapis iga vektor või objekt X 19 ..., X lk lähteandmeid käsitletakse eraldi klastri või klassina. Vastavalt arvutatud kauguste maatriksile valitakse ja kombineeritakse üksteisele lähimad. Ilmselgelt lõpeb protsess sellega (P - 1) samm, mille tulemusena liidetakse kõik objektid üheks klastriks.
Assotsiatsioonide jada võib esitada dendrogrammina või puuna. Joonisel fig. 1.18 näitab, et vektorid ühendati esimeses etapis X t , X 2 , kuna nende vaheline kaugus on 0,3.
Teises etapis kinnitati neile vektor X 3 kobarast eemal (X 1, X 2) kauguseni 0,5 jne. Viimases etapis ühendatakse kõik vektorid üheks klastriks.
Riis. 1.18.
Aglomeratiivsed meetodid hõlmavad ühe, keskmise, täieliku ühendamise meetodeid ja Wardi meetodit.
1.ühe ühenduse meetod. Lase X v ..., X n - vektorandmed, kusjuures iga vektor moodustab ühe klastri. Esiteks arvutatakse nende klastrite vaheline kauguste maatriks ja mõõdikuna kasutatakse lähimat naabri kaugust. Seda maatriksit kasutades valitakse kaks lähimat vektorit, mis moodustavad esimese klastri 5,. Järgmine samm vahel S] ja ülejäänud vektorid (mida me peame klastriteks), arvutatakse uus kaugusmaatriks ja klastrite vaheline kaugus kombineeritakse klassidesse (a = p = 1/2, 5 = -1/2, y = 0) kasutatakse mõõdikuna. Lähim varem omandatud klassile S( kobar ühineb sellega, moodustades S2. Jne läbi P- 1 sammu, saame, et kõik vektorid on ühendatud üheks klastriks.
Eelised: 1) algoritmi igas etapis lisatakse ainult üks element, 2) meetod on äärmiselt lihtne, 3) algoritm on tundetu algandmete teisendustele (pööramine, nihe, translatsioon, venitamine).
Puudused: 1) kaugusmaatriksit on vaja pidevalt ümber arvutada, 2) klastrite arv on ette teada ja seda ei saa vähendada
- 2. Täielik ühendamise meetod. Meetod kordab praktiliselt ühe lingi meetodit, välja arvatud see, et uue objekti kaasamine klastrisse toimub siis ja ainult siis, kui objektide (vektorite või klastrite) vaheline kaugus on väiksem kui mingi etteantud arv. Numbri määrab kasutaja. Kaugus arvutatakse ainult "kaugnaabri" põhimõtte järgi (sama võib öelda ka klassidesse kombineeritud klasside vahelise kauguse kohta - ainult kauge naabri põhimõte os = p = 8 = 1/2, y = 0).
- 3.Keskmine ühendusviis. Klastrite moodustamise algoritm langeb kokku ühe lingi algoritmiga, kuid uue objekti klastris kaasamise otsustamisel tehakse arvutused keskmise lingi põhimõttel. Nagu täieliku lingi meetodi puhul, võrreldakse kõiki klastrite vahelisi arvutatud vahemaid kasutaja määratud arvuga. Ja kui see (kaugus) on etteantud arvust väiksem, kaasatakse uus objekt vanasse klassi. Seega erineb keskmine ühendusmeetod täisühendusmeetodist ainult klastritevahelise kauguse arvutamise viisi poolest.
- 4. WARD meetod. Lase X 19 ..., X lk- andmed, kus iga vektor moodustab ühe klastri. Leiame kaugusmaatriksi kasutades mingit mõõdikut (näiteks Mahalanobise kaugust), määrame selle järgi üksteisele lähimad klastrid. Arvutage klastri sees olevate vektorite hälvete ruudu summa S k valemi järgi:
Kus Kellele - klastri number, mina- vektori number klastris, j- koordinaadi number X t e U1 R, p kuni- vektorite arv klastris, Xjk- näidise keskmine X i V S k . Väärtus Vk iseloomustab vektorite kõrvalekaldeid üksteisest klastri sees (uus Sk+Sf või vana^). Arvutus Vk tuleks läbi viia enne ja pärast liitu ning peate kõike kordama võimalikud variandid sellised ühendused. Hiljem klastris S k lisatakse ainult need vektorid või klastrid, mille tulemuseks on kõige väiksem muutus Vk pärast ühendamist ja selle tulemusena asub see algsest klastrist minimaalsel kaugusel S k .
Kaaluge täiendavaid iteratiivseid meetodeid. Iteratiivsete meetodite olemus seisneb selles, et klasterdamine algab teatud algtingimuste seadmisega. Näiteks on vaja määrata saadavate klastrite arv või määrata kaugus, mis määrab klastri moodustumise protsessi lõpu jne. Algtingimused valitakse vastavalt sellele, millist tulemust uurija vajab. Tavaliselt seatakse need aga ühe aglomeratiivse meetodi abil leitud lahenduse järgi. Iteratiivsed meetodid hõlmavad ^-keskmiste meetodit ja kontsentratsioonide otsimise meetodit.
1. Meetod /r-tähendab. Olgu vektorid Xl9 ...,Xn e9F ja need tuleb jagada To klastrid. Nullastmel P vektorid valivad juhuslikult To eeldades, et igaüks moodustab ühe klastri. Saame võrdlusklastrite komplekti,...,e[ 0) koos kaaludega
coj 0) ,...,X. ja arvutage vaheline kaugusmaatriks x. ja standardid e 1 (0),...,^ 0) mõne mõõdiku järgi, näiteks eukleidilise järgi:
Arvutatud kaugusmaatriksi teadmiste põhjal vektori X ( asetatakse standardisse, mille kaugus on minimaalne. Oletame kindluse mõttes, mis see on. See asendatakse uuega, mis arvutatakse ümber, võttes arvesse lisatud punkti, vastavalt valemile
Lisaks arvutatakse ka kaal ümber:
Kui maatriksis esineb kaks või enam minimaalset kaugust, siis X t sisaldub madalaima järjenumbriga klastris.
Järgmises etapis valitakse ülejäänud vektorite hulgast järgmine ja protseduuri korratakse. Seega läbi ( PC) sammud igaühe juurde
standard e^~ k) vastab kaalule ja klastrite moodustamise protseduur lõpeb. Suurega P ja väike To algoritm koondub kiiresti stabiilsele lahendusele, s.t lahendusele, kus pärast algoritmi esmakordset rakendamist saadud standardid langevad arvult ja koostiselt kokku meetodi kordamisel leitud standarditega. Sellegipoolest korratakse algoritmiprotseduuri alati mitu korda, kasutades võrdlusvektoritena eelmistes arvutustes saadud partitsiooni (esialgse lähendusena): varem leitud viiteid e[ p k e (2 p k) k) jaoks võetud e (x 0) 9 ... 9 e (k 0) 9 ja algoritmiprotseduuri korratakse.
- 2. Kondensatsiooni otsimise meetod. See on järgmine iteratiivne algoritm. See ei nõua klastrite arvu a priori täpsustamist. Esimeses etapis vahemaatriks vahel X X9 ... 9 X p e Y1 p mingi mõõdiku järgi. Seejärel valitakse juhuslikult üks vektor, mis täidab esimese klastri keskpunkti rolli. See on esialgne lähendus. Oletame, et see vektor asub p-mõõtmelise raadiusega sfääri keskpunktis R, ja selle raadiuse määrab uurija. Pärast seda määratakse vektorid X Si ,... 9 X Sk , selle sfääri sees lõksus ja valik arvutatakse nende põhjal
- - 1 To
fikseeritud ootus X \u003d ~ Y] X 5. Siis sfääri keskpunkt
sisse kantud X ja arvutusprotseduuri korratakse. Iteratiivse protsessi lõpu tingimuseks on keskmiste vektorite võrdsus X leitud T Ja (t+ 1) sammud. Sfääri sees lõksus olevad elemendid X 9 ... 9 X
koondame nad ühte klastrisse ja jätame edasisest uurimistööst välja. Ülejäänud punktide puhul korratakse algoritmi. Algoritm läheneb mis tahes esialgse lähenduse valiku ja mis tahes algandmete hulga jaoks. Stabiilse partitsiooni saamiseks (st partitsiooni, milles pärast algoritmi esmakordset rakendamist leitud klastrid kattuvad arvult ja koostiselt meetodi kordamisel leitud klastritega) on soovitatav algoritmiprotseduuri mitu korda korrata. sfääri raadiuse erinevate väärtuste jaoks R. Stabiilse partitsiooni märk on sama arvu sama koostisega klastrite moodustamine.
Pange tähele, et rühmitamise probleemi ei ole ainus lahendus. Seetõttu on üsna keeruline ja mitte alati võimalik loetleda kõiki lubatud andmejaotusi klassidesse. Et hinnata kvaliteeti erinevaid viise klasterdamine tutvustab partitsioonikvaliteedi funktsionaali mõistet, mis võtab parimal (uurija seisukohalt) partitsioonil minimaalse väärtuse.
Lase X X9 ... 9 X lk e U1 R - mingi vaatluste kogum, mis on jagatud klassideks S = (S l9 ... 9 S k ) 9 ja To ette teada. Siis on teadaoleva arvu klastrite jaoks peamised partitsioonikvaliteedi funktsionaalid järgmine:
1) Klassisisese dispersiooni kaalutud summa
Kus a(1)- klastri valikuline matemaatiline ootus S l
Funktsionaalne Q((S) võimaldab hinnata kõigi klastrite kui terviku homogeensuse astet.
2) Elementide paarisiseste kauguste summa 
või
Kus lk 1- elementide arv klastris S { .
3) Üldistatud klassisisene dispersioon
Kus nj- elementide arv S., A; . - proovi kovariatsioonimaatriks jaoks sj.
Funktsionaal on iga klastri jaoks arvutatud üldistatud klassisiseste dispersioonide aritmeetiline keskmine. Nagu teada, võimaldab üldistatud dispersioon hinnata mitme muutujaga vaatluste hajutatuse astet. Sellepärast Q3 (S) võimaldab hinnata vaatlusvektorite keskmist hajumist klassides S l9 ... 9 S k . Sellest ka selle nimi – üldistatud klassisisene dispersioon. Q3 (S) kasutatakse siis, kui on vaja lahendada andmete tihendamise või vaatluste koondamise probleem ruumi, mille mõõtmed on väiksemad kui algne.
4) Vaatluste klassifikatsiooni kvaliteeti saab hinnata ka Hotellingu kriteeriumi abil. Selleks rakendame hüpoteesi kontrollimise kriteeriumi H 0 kahe mitmemõõtmelise populatsiooni keskmiste vektorite võrdsuse kohta ja arvutada statistika
Kus n t Ja p t - vektorite arv klassides S l ,S m ; X, X t- tsentreeritud lähteandmed; S*- klastrite ühendatud kovariatsioonimaatriks S n S m: S* =--- (XjX l + X^X m). Nagu varemgi, väärtus Q 4 (S)
p,+p t -2
võrreldes valemi järgi arvutatud tabeli väärtusega
Kus m- vaatlusvektorite algmõõde ja olulisuse tase.
Hüpotees H 0 aktsepteeritakse tõenäosusega (1-oc), kui Q 4 (S) n _ m ja muul juhul lükatakse tagasi.
Samuti on võimalik empiiriliselt hinnata klassideks jaotamise kvaliteeti. Näiteks võib võrrelda iga klassi kohta leitud valimi keskmisi kogu vaatluste populatsiooni valimi keskmisega. Kui need erinevad kahe või enama teguri võrra, on partitsioon hea. Klastri valimi keskmiste korrektsem võrdlemine kogu vaatluskogumi valimi keskmisega toob kaasa dispersioonanalüüsi kasutamise klassidesse jaotuse kvaliteedi hindamiseks.
Kui klastrite arv on S = (S l9 ...,S k ) ei ole ette teada, siis kasutatakse suvaliselt valitud täisarvu jaoks järgmisi partitsioonikvaliteedi funktsioone m:
IITo 1 1 m
- - klassisisese klassi keskmine mõõt
P i=1 n i XjeSj X"tSj J
öökull laiali,
- (1 P/ 1W
- - X ~-~ r “ hulga punktide kontsentratsiooni mõõt
P nV l J J
S, - punkti sisaldava klastri elementide arv X g
Pange tähele, et parameetri suvalise väärtuse korral T funktsionaalne Z m (S) jõuab miinimumini, mis on võrdne I/p, kui algne rühmitus S = (S l9 ...,S k ) on partitsioon monoklastriteks S. = (Xj), sest V(Xt) = 1. Samal ajal Z m (S) jõuab maksimaalselt 1-ni, kui S- üks klaster, mis sisaldab kõiki algandmeid,
sest V(X() = n. Erijuhtudel saab seda näidata Z_l (S) =-, Kus Kellele - erinevate klastrite arv S = (S 19 ... 9 S k ) 9 Z X (S) = max - ,
*" V P)
Kus n t - elementide arv klastris S i9 Z^(S) = min - ,
G" P)
Pange tähele, et teadmata arvu klastrite korral toimib partitsioonikvaliteet Q(S) saab valida kahe funktsionaali algebralise kombinatsioonina (summa, vahe, korrutis, suhe). I m (S), Z m (S), kuna esimene on klasside arvu kahanev ja teine kasvav funktsioon To. Selline käitumine Z m (S)
garanteerib ekstreemumi olemasolu Q(S).
Sissejuhatus
Mõiste klastrianalüüs, mille Tryon esmakordselt kasutusele võttis 1939. aastal, sisaldab enam kui 100 erinevat algoritmi.
Erinevalt klassifitseerimisprobleemidest ei nõua klastrianalüüs andmekogumi kohta a priori eeldusi, ei sea piiranguid uuritavate objektide esitamisele ning võimaldab analüüsida erinevat tüüpi andmete (intervallandmete, sageduste, binaarandmete) näitajaid. . Tuleb meeles pidada, et muutujaid tuleb mõõta võrreldavatel skaaladel.
Klasteranalüüs võimaldab vähendada andmete dimensiooni ja muuta need visuaalseks.
Klasteranalüüsi saab rakendada aegridade kogumitele, siin saab eristada mõne näitaja sarnasuse perioode ja määrata sarnase dünaamikaga aegridade rühmi.
Klasteranalüüs on arenenud paralleelselt mitmes suunas, näiteks bioloogias, psühholoogias jt, seega on enamikul meetoditel kaks või enam nimetust.
Klasteranalüüsi ülesandeid saab rühmitada järgmistesse rühmadesse:
Tüpoloogia või klassifikatsiooni väljatöötamine.
Objektide rühmitamiseks kasulike kontseptuaalsete skeemide uurimine.
Hüpoteeside esitamine andmete uurimisel.
Hüpoteeside testimine või uurimine, et teha kindlaks, kas ühel või teisel viisil tuvastatud tüübid (rühmad) on olemasolevates andmetes tegelikult olemas.
Klasteranalüüsi praktilisel kasutamisel lahendatakse reeglina mitu neist ülesannetest korraga.
Tunni eesmärk
Klasteranalüüsi hierarhiliste ja iteratiivsete meetodite praktilise rakendamise oskuste omandamine.
Praktiline ülesanne
Töötada välja lähinaabermeetodite algoritmid ja k-medium ja rakendada neid arvutiprogrammide kujul. Looge DNC abil 50 rakendust x= (x 1 ,x 2) - juhuslik 2-mõõtmeline muutuja, mille koordinaadid on jaotunud ühtlaselt intervallis (3.8). Jaotage need väljatöötatud programmide abil minimaalse arvu klastritesse, millest igaüks on paigutatud 0,15 raadiusega sfääri.
Juhised
Klastrianalüüsi nimetus tuleb ingliskeelsest sõnast cluster - hunnik, akumulatsioon Klastrianalüüs on mitme muutujaga statistilise analüüsi protseduuride lai klass, mis võimaldab vaatlusi automatiseeritud rühmitada homogeenseteks klassideks - klastriteks.
Klastril on järgmised matemaatilised omadused:
klastri dispersioon;
standardhälve.
Klastri keskus on muutujate ruumi punktide asukoht.
Klastri raadius – punktide maksimaalne kaugus klastri keskpunktist.
Klastri dispersioon on punktide hajumise mõõt ruumis klastri keskpunkti suhtes.
Objektide standardhälve (RMS) klastri keskpunkti suhtes on klastri dispersiooni ruutjuur.
Klasteranalüüsi meetodid
Klasteranalüüsi meetodid võib jagada kahte rühma:
hierarhiline;
mittehierarhiline.
Iga rühm sisaldab palju lähenemisviise ja algoritme.
Erinevaid klasteranalüüsi meetodeid kasutades saab analüütik samadele andmetele erinevaid lahendusi. Seda peetakse normaalseks.
Klasteranalüüsi hierarhilised meetodid
Hierarhilise klastri sisuks on väiksemate klastrite järjestikune liitmine suuremateks klastriteks või suurte klastrite jagamine väiksemateks.
Hierarhilised aglomeratiivsed meetodid(Agglomeratiivne pesastumine, AGNES)
Seda meetodite rühma iseloomustab algelementide järjekindel kombinatsioon ja vastav klastrite arvu vähenemine.
Algoritmi alguses on kõik objektid eraldi klastrid. Esimeses etapis ühendatakse kõige sarnasemad objektid klastriks. Järgmistes etappides jätkub liitmine, kuni kõik objektid moodustavad ühe klastri.
Hierarhilised jagatavad (jagatavad) meetodid(Divisive ANAlysis, DIANA)
Need meetodid on aglomeratiivsete meetodite loogiline vastand. Algoritmi alguses kuuluvad kõik objektid ühte klastrisse, mis jagatakse järgnevate sammude käigus väiksemateks klastriteks, mille tulemusena moodustub gruppide jada.
Hierarhilised klastrite meetodid erinevad klastrite ehitamise reeglite poolest. Reeglid on kriteeriumid, mida kasutatakse objektide "sarnasuse" üle otsustamisel, kui need on rühmaks ühendatud.
Sarnasusmeetmed
Objektide vahelise kauguse arvutamiseks kasutatakse erinevaid sarnasusmõõte (sarnasusmõõte), mida nimetatakse ka mõõdikuteks või kaugusfunktsioonideks.
Eukleidiline kaugus on geomeetriline kaugus mitmemõõtmelises ruumis ja arvutatakse valemiga (4.1).
Eukleidiline kaugus (ja selle ruut) arvutatakse algandmete, mitte standardsete andmete põhjal.
Eukleidiline kaugus ruudus arvutatakse valemiga (4.2).
(4.2)
Manhattani kaugus (linnaploki kaugus), mida nimetatakse ka "hamming" või "linnaploki" kauguseks, arvutatakse koordinaatide erinevuste keskmisena. Enamikul juhtudel annab see kauguse mõõt eukleidilise kauguse arvutustele sarnaseid tulemusi. Selle mõõdu puhul on üksikute kõrvalekallete mõju siiski väiksem kui Eukleidilise kauguse kasutamisel, kuna siin ei ole koordinaadid ruudus. Manhattani vahemaa arvutatakse valemi (4.3) abil.
(4.3)
Tšebõševi kaugus tuleks kasutada, kui on vaja määratleda kaks objekti kui "erinevad", kui need erinevad ühes mõõtmes. Tšebõševi kaugus arvutatakse valemiga (4.4).
(4.4)
Võimsuskaugus kasutatakse, kui soovitakse järk-järgult suurendada või vähendada kaalu, mis on seotud mõõtmega, mille vastavad objektid on väga erinevad. Võimsuskaugus arvutatakse valemiga (4.5).
(4.5)
Kus r Ja p- kasutaja määratud parameetrid. Parameeter lk vastutab üksikute koordinaatide, parameetri erinevuste järkjärgulise kaalumise eest r objektide vaheliste suurte vahemaade järkjärguliseks kaalumiseks. Kui mõlemad variandid r Ja lk on võrdsed kahega, siis kattub see kaugus Eukleidese kaugusega.
Lahkarvamuste protsent kasutatakse siis, kui andmed on kategoorilised. See vahemaa arvutatakse valemiga (4.6).
(4.6)
Liitu- või linkimismeetodid
Esimesel etapil, kui iga objekt on eraldi klaster, määratakse nende objektide vahelised kaugused valitud mõõdiku järgi. Kui aga mitu objekti on omavahel seotud, tuleb klastrite vahelise kauguse määramiseks kasutada muid meetodeid. Klastritega liitumiseks on palju meetodeid:
Single link (lähima naabri meetod) – kahe klastri vaheline kaugus määratakse kahe lähima objekti (lähima naabri) vahemaa järgi erinevates klastrites.
Täielik ühendus (kõige kaugema naabri meetod) – klastrite vahelised kaugused määratakse suurima vahemaa järgi mis tahes kahe objekti vahel erinevates klastrites (st "kõige kaugemate naabrite" vahel).
Kaalumata paariskeskmine – kahe erineva klastri vaheline kaugus arvutatakse kõigi neis olevate objektide paaride keskmise kaugusena.
Kaalutud paaripõhine keskmine – meetod on meetodiga identne kaalumata paaride keskmine, välja arvatud see, et arvutustes kasutatakse kaalutegurina vastavate klastrite suurust (st neis sisalduvate objektide arvu).
Kaalumata tsentroidi meetod – kahe klastri vaheline kaugus on määratletud kui nende raskuskeskmete vaheline kaugus.
Kaalutud tsentroidi meetod (mediaan) - meetod on identne kaalumata tsentroidi meetodiga, välja arvatud see, et arvutustes kasutatakse kaalusid, et võtta arvesse klastrite suuruste erinevust (st nendes olevate objektide arvu).
Wardi meetod – klastrite vaheline kaugus on määratletud kui objektide ja klastrite keskpunktide kauguste ruudu summa suurenemine, mis saadakse nende ühinemise tulemusena. Meetod erineb kõigist teistest meetoditest, kuna see kasutab klastrite vaheliste kauguste hindamiseks ANOVA meetodeid. Meetod minimeerib igas etapis moodustatava kahe (hüpoteetilise) klastri ruutude summa.
Lähima naabri meetod
Kahe klassi vaheline kaugus on määratletud kui kaugus nende lähimate liikmete vahel.
Enne algoritmi käivitamist arvutatakse see välja kaugusmaatriks objektide vahel. Klassifikatsioonikriteeriumi järgi toimub liit klastrite vahel, mille lähimate esindajate vaheline kaugus on kõige väiksem: valitakse kaks kõige väiksema kaugusega objekti ühes klastris. Pärast seda on vaja kaugusmaatriks ümber arvutada, võttes arvesse uut klastrit. Igas etapis otsitakse kaugusmaatriksist minimaalset väärtust, mis vastab kahe lähima klastri vahelisele kaugusele. Leitud klastrid ühendatakse uueks klastriks. Seda protseduuri korratakse, kuni kõik klastrid on ühendatud.
Lähima naabri meetodi kasutamisel tuleks erilist tähelepanu pöörata objektide vahelise kauguse mõõdu valikule. Selle põhjal moodustatakse esialgne kaugusmaatriks, mis määrab kogu edasise klassifitseerimisprotsessi.
iteratiivsed meetodid.
Suure hulga vaatluste korral ei sobi klasteranalüüsi hierarhilised meetodid. Sellistel juhtudel kasutatakse mittehierarhilisi meetodeid, mis põhinevad algsete klastrite jagamisel teisteks klastriteks ja mis on iteratiivsed meetodid algse populatsiooni tükeldamiseks. Jagamise käigus moodustuvad uued klastrid kuni peatamisreegli täitmiseni.
Selline mittehierarhiline rühmitamine seisneb andmekogumi jagamises teatud arvuks eraldiseisvateks klastriteks. On kaks lähenemist. Esimene on defineerida klastrite piirid kui kõige tihedamad alad algandmete mitmemõõtmelises ruumis, st klastri määratlus, kus on suur "punktiklaster". Teine lähenemisviis on objektide erinevuse mõõtmise minimeerimine.
Erinevalt hierarhilistest klassifitseerimismeetoditest võivad iteratiivsed meetodid viia kattuvate klastrite moodustumiseni, kui üks objekt võib korraga kuuluda mitmesse klastrisse.
Iteratiivsed meetodid hõlmavad näiteks meetodit k-keskmised, kontsentratsioonide otsimise meetod ja teised. Iteratiivsed meetodid on kiired, mis võimaldab neid kasutada suurte algteabe massiivide töötlemiseks.
Algoritm k-means (k-means)
Iteratiivsete meetodite hulgas on kõige populaarsem meetod meetod k- keskmine McKean. Erinevalt hierarhilistest meetoditest peab enamiku selle meetodi rakenduste puhul kasutaja ise määrama soovitud arvu lõplikke klastreid, mida tavaliselt tähistatakse " k". Algoritm k- keskmise ehitusega küksteisest võimalikult kaugel paiknevad klastrid. Algoritmi lahendatavate probleemide tüübi põhinõue k-keskmised - eelduste (hüpoteeside) olemasolu klastrite arvu kohta, samas kui need peaksid olema võimalikult erinevad. Numbri valik k võib põhineda eelnevatel uuringutel, teoreetilistele kaalutlustele või intuitsioonile.
Sarnaselt hierarhiliste klastrimeetoditega saab kasutaja valida üht või teist tüüpi sarnasuse mõõtmise. Erinevad meetodite algoritmid k-keskmised erinevad ka antud klastrite algtsentrite valimise viisi poolest. Mõnes meetodi versioonis saab (või peab) kasutaja ise selliseid algpunkte täpsustama, valides need reaalsete vaatluste hulgast või määrates iga muutuja jaoks nende punktide koordinaadid. Selle meetodi teistes rakendustes antud numbri valimine k algpunktid luuakse juhuslikult ja neid lähtepunkte (klastri keskusi) saab seejärel mitmes etapis täpsustada. Sellistel meetoditel on 4 peamist etappi:
valitud või määratud k vaatlused, mis on klastrite esmased keskused;
vajadusel moodustatakse vaheklastrid, määrates iga vaatluse lähimatele etteantud klastri keskustele;
pärast kõigi vaatluste määramist üksikutele klastritele asendatakse esmased klastri keskused klastri keskmiste väärtustega;
eelmist iteratsiooni korratakse seni, kuni muutused klastri tsentrite koordinaatides muutuvad minimaalseks.
Algoritmi üldidee: antud kindlat arvu k vaatlusklastreid võrreldakse klastritega nii, et klastri keskmised (kõikide muutujate puhul) erinevad üksteisest võimalikult palju.
Algoritmi kirjeldus
Objektide esialgne jaotus klastrite kaupa.
Valitud number k Ja k punktid. Esimeses etapis peetakse neid punkte klastrite "keskpunktideks". Iga klaster vastab ühele keskusele. Esialgsete tsentroidide valiku saab teha järgmiselt:
valik k- vaatlused esialgse vahemaa maksimeerimiseks;
juhuslik valik k- tähelepanekud;
esimene valik k- tähelepanekud.
Seejärel määratakse iga objekt teatud lähimasse klastrisse.
Iteratiivne protsess.
Arvutatakse välja klastrite keskpunktid, mida siis ja edasi loetakse klastrite koordinaatkeskväärtusteks. Objektid jaotatakse uuesti ümber. Keskuste arvutamise ja objektide ümberjaotamise protsess jätkub, kuni on täidetud üks järgmistest tingimustest:
klastri keskused on stabiliseerunud, st kõik vaatlused kuuluvad klastrisse, kuhu nad kuulusid enne praegust iteratsiooni. Selle meetodi mõnes versioonis saab kasutaja määrata kriteeriumi arvväärtuse, mida tõlgendatakse uute klastri keskuste valimise minimaalse kaugusena. Vaatlust ei peeta kandidaadiks uus keskus klastri, kui selle kaugus klastri asendatud keskpunktist ületab määratud arvu. Sellist parameetrit paljudes programmides nimetatakse "raadiuseks". Lisaks sellele parameetrile on võimalik määrata tavaliselt piisavalt väike arv, millega võrreldakse kauguse muutust kõigi klastri keskuste lõikes. Seda parameetrit nimetatakse tavaliselt "konvergentsiks", kuna see peegeldab iteratiivse klastri moodustamise protsessi konvergentsi;
iteratsioonide arv on võrdne maksimaalse iteratsioonide arvuga.
Klastrite kvaliteedi kontrollimine
Pärast meetodiga klasteranalüüsi tulemuste saamist k- keskmised, peaksite kontrollima rühmitamise õigsust (st hindama, kuidas klastrid erinevad üksteisest). Selleks arvutatakse iga klastri keskmised väärtused. Hea klasterdamine peaks andma kõigi mõõtmiste või vähemalt enamiku mõõtmiste jaoks väga erinevaid vahendeid.
Eelisedk-tähendab algoritm:
kasutusmugavus;
kasutuskiirus;
algoritmi selgus ja läbipaistvus.
Puudusedk-tähendab algoritm:
Algoritm on liiga tundlik kõrvalekallete suhtes, mis võivad keskmist moonutada. Selle probleemi võimalik lahendus on kasutada algoritmi modifikatsiooni - algoritmi k- mediaanid;
Algoritm võib suurtes andmebaasides olla aeglane. Selle probleemi võimalik lahendus on andmete valimi kasutamine.
Aruanne peab sisaldama:
algoritmide kirjeldus ja plokkskeemid;
programmimoodulite lähtetekstid;
algoritmide tulemused graafikute kujul.
Nende meetodite olemus seisneb selles, et klassifitseerimisprotsess algab teatud algtingimuste seadmisega (moodustunud klastrite arv, klassifitseerimisprotsessi lõpuleviimise lävi jne). Klasteranalüüsi iteratiivsed meetodid hõlmavad meetodit k-keskmised (McQueen), kontsentratsioonide otsimise meetod, vastastikuse absorptsiooni meetod jne.
k-tähendab meetod
Selle meetodi rakendamiseks määratakse algselt klasside arv, milleks on vaja jagada olemasolev objektide kogu. Algtingimuste seadmiseks on vaja kumbagi Lisainformatsioon klastrite arvu kohta või esialgselt hinnata klastrite arvu hierarhiliste klastriprotseduuride abil.
Klassifitseerimisprotseduuri alustamiseks seadke R juhuslikult valitud objektid - klassi standardid ( ε ). Igale standardile on määratud seerianumber, mis on samal ajal ka klassi number. Ülejäänutest n-lk objektid, objekt ekstraheeritakse ja kontrollitakse, millisele standardile see lähemal on. See objekt on kinnitatud standardi külge, mille kaugus on väikseim. Kaalud ja klassinormid arvutatakse ümber vastavalt reeglile:
kus on klassi "kaal", on iteratsiooniarv.
Sel juhul konstrueeritakse nulliproksimatsioon, kasutades uuritava üldkogumi juhuslikult valitud punkte: , , .
Läbi n-lk iteratsioonide korral määratakse kõik objektid ühele lk klastrid. Stabiilse partitsiooni saavutamiseks kõik n objektid on jälle jagatud lk klassid. Uut partitsiooni võrreldakse eelmisega. Kui need ühtivad, siis algoritm lõpeb, vastasel juhul algoritm kordub.
Kondensatsiooni otsimise meetod
Selle iteratiivse algoritmi põhiolemus seisneb punktide lokaalsete kontsentratsioonide otsimiseks etteantud raadiusega hüpersfääri kasutamine, mis liigub klassifikatsioonitunnuste ruumis.
Kontsentratsioonide otsimise meetod nõuab objektide vahelise kaugusmaatriksi (sarnasuse mõõtmiste maatriksi) arvutamist. Seejärel valitakse objekt, mis on esimese klastri esialgne keskpunkt. Valitud punkt on antud raadiusega hüpersfääri keskpunkt. Määratakse sellesse sfääri jäävate punktide kogum ja nende jaoks arvutatakse keskpunkti koordinaadid (tunnuste keskmiste väärtuste vektor). Järgmisena vaatleme uuesti sama raadiusega, kuid uue keskpunktiga hüpersfääri ja sellesse langevate punktide hulga jaoks arvutame uuesti keskmiste väärtuste vektori, võtame selle kera uueks keskpunktiks ja nii peal. Kui järgmine kera keskpunkti koordinaatide ümberarvutamine annab sama tulemuse, mis eelmises etapis, siis kera liikumine peatub ning sinna langevad punktid moodustavad klastri ning jäetakse edasisest klasterdamise protsessist välja. Kõigi ülejäänud punktide puhul korratakse protseduure, st valitakse uuesti suvaline objekt, mis on raadiusega sfääri esialgne keskpunkt ja nii edasi.
Seega saab algoritmi töö lõpule viia piiratud arvu sammudega ning kõik punktid on jaotatud klastrite vahel. Moodustunud klastrite arv ei ole ette teada ja sõltub tugevalt sfääri raadiuse valikust. Mõned algoritmi modifikatsioonid võimaldavad jagada hulga etteantud arvuks klastriteks, muutes järjestikku kera raadiust.
Saadud partitsiooni stabiilsuse hindamiseks on soovitatav sfääri raadiuse erinevate väärtuste jaoks korrata klastrite moodustamise protsessi mitu korda, muutes iga kord raadiust vähesel määral.
Sfääri raadiuse valimiseks on mitu võimalust. Kui -nda ja -nda objekti vaheline kaugus on , valitakse raadiuse alumiseks piiriks ja raadiuse ülempiir saab määratleda kui .
Kui algoritm algab väärtusega ja muutub iga kordumisel väikese väärtuse võrra, siis on võimalik tuvastada raadiuste väärtused, mis viivad sama arvu klastrite moodustumiseni, st stabiilseni. vahesein .
Vastastikuse absorptsiooni meetod
Iteratiivne vastastikuse absorptsiooni algoritm kasutab ka hüpersfääri ideed. Selle olemus on see, et igaühe jaoks i th objekti, selle raadius määratakse näiteks järgmiselt: , kus on mingi valitud väärtus, kõigi punktide konstant, .
Raadiusega sfäärid on ehitatud keskpunktidega (). Nende sfääride keskpunkte sisaldavate punktide raadiustega sfääride ristumisala nimetatakse vastastikuse neeldumise piirkonnaks. Ja sellesse piirkonda langevate sfääride tsentrite kogumit nimetatakse kobaraks.
Väärtuse muutmisel on võimalik partitsiooni mitu korda korrata. Probleemi lõplikuks lahenduseks tuleks valida kõige stabiilsemaks partitsioonivalik, mis on mitme väärtuse jaoks säilinud.
Kõik klasteranalüüsi ülesanded, olenevalt eesmärgist, saab jagada järgmiste kriteeriumide alusel:
Selline klassifitseerimisülesannete eraldamine, kuigi tinglik, on väga vajalik klastriprotseduuride konstrueerimise aluseks olevate ideede ja meetodite põhimõttelise erinevuse seisukohalt. Seega on hierarhilised klastriprotseduurid mõeldud peamiselt seda tüüpi probleemide lahendamiseks A1B1, A1B2, A1B3, iteratiivsed klastri protseduurid – A2B1, A2B2.