Կլաստերիկ վերլուծություն

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Cluster – նշանակում է միատիպ տարրերի միավորում, որը կարելի է համարել որոշակի հատկություններով օժտված մի ամբողջություն։ Clustering – ը իրենից ներկայացնում է բազմության բաժանումը խմբերի։ Այս ալգորիթմը օգտագործվում է բազմաբնույթ խնդիրներում, տվյալներ մշակելիս, մեքենաների ուսուցման, ավտոմատացված կլասիֆիկացիայի, ստրատեգիայով ղեկավարվող արդյունքների ժամանակ։ Մինչև հիմա չկա այնպիսի ունիվերսալ ալգորիթմ, որը լիներ էֆեկտիվ ցանկացած բնագավառում։ Հիմնականում օգտագործում են իտեռատիվ բազմաբնույթ մեթոդներ, երբ արդյունքը իրապես կախված է լինում խմբերի (cluster) քանակի ճշտությունից։ Ճշտությունը ալգորիթմի ցուց է տալիս, թե ինչքան տարբեր են ստացվում ալգուրիթմի արդյունքները, բազնաթիվ կիրառումներից հետո՝ միևնույն տվյալների դեպքում։ Կան այնպիսի ալգորիթմներ, որոնց միջոցով պարզում են խմբավորում կատարող ալգորիթմի ճշտությունը՝ կախված խմբերի քանակից։ Խմբավորման խնդիրը Cluster ալգորիթմը կարելի համարել ինչպես մի պրոցես , որը միավորում է տվյալները, ըստ նրանց հատկությունների։ Այն հանդիսանում է ֆունդամենտալ խնդիր տվյալների անալիզի - վերլուծության և Data Mining – ի շրջանակներում։ Ալգորիթմի կիրառման շատ բնագավառներ կան նկարի սեգմենտացում, տեքստերի անալիզ, տվյալների սեղմում և այլն։ Սկզբնական էտապում կատավում է տվյալների վերլուծություն։ Խմբերի կառուցումից հետո նոր աշխատում են այլ ալգորիթմներ։ Ամեն մի խմբի համար ստեղծվում է առանձին մոդել։ Խմբավորման խնդրի լուծումները օգտագործվում են գիտական ուղղություններում ` վիճակագրությունում, օպտիմիզացիայում, մեքենաների ուսուցման, ԴՆԹ-ի ուսումնասիրման, մոդելավորման մեջ և այլ բնագավառներում: Այստեղից և հոմանիշները կլաստեր հասկացությանը` դաս (class), խտացում, (տակսոն)։ Եվ հետևաբար կարիք կա բաժանելու կլասիֆիկացիա և կլաստերիզացիա հասկացությունները։ Կլասիֆիկացիան նշանակում է յուրաքանչյուր տարրի կախվածությունը որոշակի դասից՝ արդեն հայտնի պարամետրերի դեպքում, որը ստացել է ուսուցման էտապում։ Կլաստերիզացիան դա բազմության տրոհումն է կլաստերների։ Կլաստեր կանվանենք ենթաբազմությունը, որի պարամետրերը սկզբից հայտնի չեն լինում։ Կլաստերների քանակը կարող է լինել ֆիքսված կամ ոչ ֆիքսված։ Կլաստերիզացիաի նպատակը կարող է լինել տարբեր կախված կոնկրետ կիրառական խնդրից . Որոշել տվյալների բազմության կառուցվածքը՝ բաժանելով խմբերի, պարզեցնելով հետագա մշակումը տվյալների, յուրաքանչյու կլաստերում առանձին առանձին։

Քչացնել հիշողության չափը՝ պահվող տվյալների։

Եվ նշել ոչ տիպիկ օբյեկտները, որոնք չեն մտնում ոչ մի կլաստերում։

Հիմնական գաղափարը կլաստերիզացիայի հիմքում ընկած է հետևյալում։ Տրված է ուսումնասիրվող հաջորդականություն (տվյալների հավաքածու){x_1,…, x_n }∈X և ֆունկցիա՝ օբյեկտների հեռավորությունը որոշող ` ρ(x, x ́): Պահանջվում է բաժանել հաջորդականությունը չհատվող ենթաբազմությունների կլաստեր անվանվող այնպես, որ յուրաքանչյուր կլաստեր կազմված լինի այնպիսի օբյեկտներից, որոնք մոտիկ են ըստ ρ մետրիկայի, իսկ տարբեր կլաստերների օբյեկտներ իրապես տարբերվեն: Կլաստերիզացիայի ալգորիթմը դա ֆունկցիա է ` a։X→Y, որը ցանկացած օբյեկտի x∈X համապատասխանության մեջ է դնում y_(i )∈Y կլաստեր։ Y կլաստերների բազմությունը սկզբից հայտնի չի լինում։

Կլաստերիզացիայում տարանջատում են երկու հիմնական մոտեցումներ. դեկոմպոզիցիա (ոչ հերարխիկ), երբ յուրաքանչյուր օբյեկտ կապված է միայն մեկ խմբի հետ , և կլաստերիզացիա հերարխիայի(հերարխիկ) հիմքում, երբ յուրաքանչյուր մեծ չափի խումբ կազմված է փոքր չափի խմբերից։ Մենք կուսումնասիրենք ոչ հերարխիկ կլաստերիզացիա։ Ոչ հերարխիկ կլաստերիզացիայի հիմքում ընկած է որոշակի ֆունկցիայի օպտիմիզացիա, որը որոշում է օպտիմալը օբյեկտների բազմության բաժանումը կլաստերների իմաստով։ Այդ խմբում հայտնի ալգորիթմ է (k-means) – ը։ Կլաստերիզացիայի խնդիրների լուծումները միարժեք չեն, քանի որ չկա միարժեքորեն լավագույն կրիտերիա։ Կլաստերների քանակը ինչպես կանոն սկզբից հայտնի չի լինում, և այն տրվում է համապատասխանացնելով որոշակի կրիտերիայի հետ։ Նաև կլաստերիզացիայի արդյունքը շատ ալգորիթմերում կախված է լինում մետրիկայից։