K-միջիններով կլաստերինգ

***k'' –միջիններով կլաստերինգը''' վեկտորի քանակականացման մեթոդ է, որը սկզբնապես ծագել է ազդանշանային մշակումից։ Այն օգտագործվում է [[Տվյալների մայնինգ|տվյալների մայնինգի մեջ]] [[Կլաստեր-անալիզ|կլաստերային վերլուծության]] համար։ ''K'' -միջինների խմբավորման նպատակն է բաժանել ''n'' դիտարկումները ''k'' կլաստերների, որի յուրաքանչյուր դիտարկումը պատկանում է ամենամոտ միջինով [[Կլաստեր-անալիզ|կլաստերի]]՝ ծառայելով որպես կլաստերի նախատիպ։ ''k'' -միջինները նվազագույնի է հասցնում ներկլաստերային վարիացիան/տարբերությունները (քառակուսային էվկլիդյան հեռավորությունները), բայց ոչ կանոնավոր էվկլիդյան հեռավորությունները։ էվկլիդյան ավելի լավ լուծումները կարելի է գտնել k-մեդիանների և k-մեդոիդների օգտագործմամբ։

Խնդիրը հաշվարկային առումով դժվար է ( NP-hard ); սակայն արդյունավետ հուրիստական ալգորիթմները արագորեն գտնում են լոկալ օպտիմումը։ Սրանք սովորաբար նման են ակնկալիքի մաքսիմալացման ալգորիթմին` Գաուսի բաշխումների խառնուրդների համար` իտերատիվ հղկումների միջոցով, որն օգտագործվում է ինչպես ''k- միջիններով,'' այնպես էլ ''Գաուսյան խառնուրդների մոդելավորմամբ։'' Երկուսն էլ տվյալների մոդելավորման համար օգտագործում են կլաստերային կենտրոնները։ Այնուամենայնիվ, ''k- միջիններով'' կլաստավորումը հակված է գտնել համադրելի տարածական չափի կլաստերներ, մինչդեռ ակնկալիքների մաքսիմալացման մեխանիզմը կլաստերներին հնարավորություն է տալիս ունենալ տարբեր չափեր։

Ալգորիթմը կապ ունի k-ամենամոտ հարևանի դասակարգչի հետ, որը [[Մեքենայական ուսուցում|մեքենայական ուսուցման]] մեջ դասակարգման տեխնիկան է, որը հաճախ շփոթում են ''k'' -միջինների հետ անվան պատճառով։ Կիրառելով 1-ամենամոտ հարևանի դասակարգիչը կլաստերների կենտրոններին, որոնք ստացվել են k-միջինների կողմից, նոր տվյալները դասակարգում է գոյություն ունեցող կլաստերների մեջ։ Սա կոչվում է ամենամոտ ցենտրոիդ դասակարգիչ կամ Rocchio [[ալգորիթմ]]։

== Նկարագրություն ==
Տրված կետերի համար՝ ( '''x''' <sub>1</sub>, '''x''' <sub>2</sub>, ..., '''x''' <sub>''n''</sub> ), որտեղ յուրաքանչյուր կետ d''-'' չափանի իրական վեկտոր է, ''k- միջիններով'' կլաստերինգը նպատակ ունի ''n'' կետերը բաժանել ''k- ի'' (≤ &nbsp; ''n'' ),  '''S''' &nbsp; = {''S''<sub>1</sub>,&nbsp;''S''<sub>2</sub>,&nbsp;...,&nbsp;''S<sub>k</sub>''} այնպես, որ նվազագույնի հասցվի ներկլաստերային քառակուսիների գումարը (WCSS) (այսինքն՝ [[Դիսպերսիա (վիճակագրություն)|վարիացիան]] )։ Ֆորմալ առումով, նպատակն է գտնել. <center><math>\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2 = \underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^k |S_i| \operatorname{Var} S_i </math></center> որտեղ ***μ** <sub>i-</sub>'' ն ''S <sub>i- ում</sub>''  կետերի միջինն է։ Սա համարժեք է նույն կլաստերի ներսում կետերի զույգային քառակուսիների շեղումները նվազագույնի հասցնելուն. <center><math>\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \, \frac{1}{2 |S_i|} \, \sum_{\mathbf{x}, \mathbf{y} \in S_i} \left\| \mathbf{x} - \mathbf{y} \right\|^2</math></center> Համարժեքությունը կարող է բխել ինքնությունից՝ <math>\sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2 =\sum_{\mathbf{x}\neq\mathbf{y} \in S_i}(\mathbf x - \boldsymbol\mu_i)(\boldsymbol\mu_i - \mathbf y)</math> : Քանի որ ընդհանուր վարիացիան հաստատուն է, դա համարժեք է տարբեր կլաստերների միջև շեղումների քառակուսիների գումարի մաքսիմալացմանը (BCSS: between-cluster sum of squares):

== Պատմություն ==
« ''K-'' means» տերմինը առաջին անգամ օգտագործել է Ջեյմս ՄքՔուինի կողմից 1967 թվականին, չնայած գաղափարը ավելի վաղ օգտագործել էր Հյուգո Շտայնհաուսը 1956-ին : Ստանդարտ ալգորիթմն առաջին անգամ առաջարկել է Ստյուարտ Լլոյդը [[Բելլի լաբորատորիա|Bell Labs-]] ի կողմից 1957-ին զարկերակային կոդերի մոդուլյացիայի տեխնիկայի համար, չնայած որ այն որպես [[հոդված]] չի հրապարակվել մինչև 1982 թվականը։ 1965 թ.-ին Էդվարդ Վ. Ֆորգը հրատարակեց ըստ էության նույն մեթոդը, այդ պատճառով էլ այն երբեմն կոչվում է Լլոյդ-Ֆորգի։

== Ալգորիթմներ ==
=== Ստանդարտ ալգորիթմ (նայիվ K- միջիններ) ===
[[Պատկեր:K-means_convergence.gif|աջից|մինի| ''K- միջինների'' համընկնում]]
Ամենատարածված ալգորիթմը օգտագործում է իտերատիվ կամ անընդհատ բարելավման տեխնիկան։ Իր տարածվածության պատճառով այն հաճախ կոչվում է « ''k- ի միջինների'' ալգորիթմ»; այն նաև կոչվում է որպես Լլոյդի ալգորիթմ, մասնավորապես ՝ համակարգչային գիտությունների ոլորտում։ Այն երբեմն կոչվում է նաև «նայիվ ''k- միջիններ'' », քանի որ կան շատ ավելի արագ աշխատող այլընտրանքներ։

Տրված ''k-'' միջինների համար` ''m'' <sub>1</sub> <sup>(1)</sup>, ..., ''m <sub>k</sub>'' <sup>(1)</sup>, ստորև ներկայացված ալգորիթմն ընթանում է երկու հաջորդական և կրկնվող քայլերով.

: **Հանձնարարության քայլ**. Յուրաքանչյուր կետ նշանակել այն կլաստերին, որի միջինը ունի ամենափոքր քառակուսային էվկլիդյան հեռավորությունը, որը համարվում է ՙՙամենամոտ՚՚ միջինը : Մաթեմատիկորեն, սա նշանակում է, որ կետերը բաժանում են ըստ [[Վորոնեի դիագրամ|Վորոնոյի դիագրամի]] ստեղծած միջինների։ 
:: <math>S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \|^2 \le \big \| x_p - m^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math> 
:: որտեղ յուրաքանչյուրը <math>x_p</math>-ին նշանակվում է միայն մեկ <math>S^{(t)}</math>-ի, նույնիսկ եթե այն կարող էր նշանակվել երկուսի կամ ավելիի։ 
: **Թարմացման քայլ*'. Հաշվարկեք դիտարկումների նոր միջինները ( ցենտրոիդները ) նոր կլաստերում։ 
:: <math>m^{(t+1)}_i = \frac{1}{\left|S^{(t)}_i\right|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Ալգորիթմը վերջանում է, երբ հանձնարարության արդյունքներն այլևս չեն փոխվում։ Ալգորիթմը չի երաշխավորում գտնել օպտիմալը։ <gallery class="center" widths="150" caption="Ստանդարտ ալգորիթմի ցուցադրում">
Պատկեր:K Means Example Step 1.svg|1. *k* սկզբնական «միջինները» (այս դեպքում *k* = 3) պատահականորեն ստեղծվում են տվյալների տիրույթում (ցույց է տրված գույնով)։
Պատկեր:K Means Example Step 2.svg|2. *k* կլաստերը ստեղծվում է ամեն դիտարկումը մոտակա միջինի հետ կապելով։ Բաժանումներն այստեղ ներկայացնում են միջինների կողմից առաջ բերված [[Voronoi diagram|Վորոնոյի դիագրամը]] ։
Պատկեր:K Means Example Step 3.svg|3. Յուրաքանչյուր *k* կլաստերների ցենտրոիդը դառնում է նրա նոր միջինը։
Պատկեր:K Means Example Step 4.svg|4. 2-րդ և 3-րդ քայլերը կրկնվում են, քանի դեռ չեն  զուգամիտել։
</gallery> «Հանձնարարություն» քայլը կոչվում է «սպասման քայլ», մինչդեռ «թարմացման քայլը» առավելագույնի հասցնելու/մաքսիմալացման քայլ է՝ ալգորիթմը դարձնելով *ընդհանրացված* սպասումների մաքսիմալացման ալգորիթմի տարբերակ ։

== Քննարկում ==
[[Պատկեր:K-means_convergence_to_a_local_minimum.png|մինի|650x650փքս| K-միջինների՝ լոկալ մինիմումը գտնելու տիպիկ օրինակ: Այս օրինակում K-միջիններով կլաստերինգի արդյունքը (աջ կողմում) համընկնում է ակնհայտ կլաստերների հետ: Փոքր կետերը տվյալներն են, 4 աստղերը՝ ցենտրոիդները(միջիններ): Նախնական տարբերակը ցույց է տրված ձախ կողմում: Ալգորիթմը համընկնում է հինգ կրկնությունից հետո, ինչպես ցույց է տրված նկարներում՝ ձախից աջ: Պատրաստված է Mirkes Java ծրագրի միջոցով:]]
[[Պատկեր:Iris_Flowers_Clustering_kMeans.svg|մինի|450x450փքս| *k-* ն*k*-միջիններով կլաստերինգի արդյունքը իրիս ծաղիկների տվյալների համար և իրական տեսակները՝ պատկերված ELKI ծրագրի միջոցով: Կլաստերների միջինները ընդգծված են ավելի մեծ սիմվոլներով:]]
[[Պատկեր:ClusterAnalysis_Mouse.svg|մինի|450x450փքս| *k*-միջիններով կլաստերինգ և EM կլաստերինգ արհեստական "mouse" տվյալների վրա: k-միջինները հակված են ստեղծել հավասար չափերով կլաստերներ, ինչն այս դեպքում հանգեցնում է վատ արդյունքների, մինչդեռ EM-ը առավելություն է ստանում գաուսյան բաշխումներից տարբեր շառավղով տվյալների շարքում:]]
*K- միջինների* երեք հիմնական առանձնահատկությունները, որոնք այն դարձնում են արդյունավետ, հաճախ դիտվում են որպես դրա ամենամեծ թերությունները.

* Էվկլիդյան հեռավորությունը օգտագործվում է որպես չափման մեթոդ, իսկ վարիացիան՝ որպես կլաստերի ցրվածության չափման միջոց։ 
* Կլաստերների քանակը *k* մուտքագրվող պարամետր է. *K-* ի ոչ պատշաճ ընտրությունը կարող է բերել վատ արդյունքների։ Այդ իսկ պատճառով, *k- միջինները* օգտագործելիս անհրաժեշտ է ախտորոշիչ ստուգումներ անցկացնել տվյալների հավաքածուի քանակի որոշման համար։ 
* Լոկալ մինիմումը գտնելը կարող է բերել սխալ արդյունքների։

*K* –միջինների կարևոր սահմանափակումը նրա կլաստերի մոդելն է։ Հայեցակարգը հիմնված է գնդաձև կլաստերի վրա, որոնք հնարավոր է առանձնացնել այնպես, որ միջինը համընկնում է կլաստերի կենտրոնի նկատմամբ։ Ակնկալվում է, որ կլաստերների չափերը նման են, այնպես որ մոտակա կլաստերային կենտրոնին նշանակումը ճիշտ հանձնարարություն է։ Օրինակ` օգտագործելով *k- միջիններ* իրիսի հայտնի ծաղիկների տվյալների վրա, *երբ* <math>k=3</math>,  հաճախ չի հաջողվում առանձնացնել [[Հիրիկ|Iris-]] ի երեք տեսակները, որոնք պարունակում են տվյալների շարքում։ <math>k=2</math> դեպքում հայտնաբերվելու են երկու տեսանելի կլաստեր (մեկը, որը պարունակում է երկու տեսակ), մինչդեռ <math>k=3</math> երկու կլաստերից մեկը բաժանվելու է երկու հավասար մասերի։ Իրականում, <math>k=2</math> այս տվյալների համար առավել նպատակահարմար է, չնայած տվյալների պարունակում են 3 *դաս*։ Ցանկացած այլ կլաստերավորման ալգորիթմի հետ *k-միջինների* արդյունքը ենթադրություններ է կատարում, որ տվյալները բավարարում են որոշակի չափանիշների։ Այն լավ է աշխատում որոշ տվյալների վրա, իսկ մյուսների վրա՝ ոչ։

== Կիրառությունը ==
*k* –միջիններով կլաստերավորումը բավականին հեշտ է կիրառել նույնիսկ մեծ տվյալների համար, մասնավորապես, երբ օգտագործվում է հյուրիստիկա (heuristics), ինչպիսին է Լլոյդի ալգորիթմը։ Այն հաջողությամբ օգտագործվել է [[Շուկայի սեգմենտավորում|շուկայի սեգմենտավորման]], [[Համակարգչային տեսլական|համակարգչային տեսողության]] և [[Աստղագիտություն|աստղագիտության]] մեջ, ինչպես նաև շատ այլ ոլորտներում։ Այն հաճախ օգտագործվում է որպես այլ ալգորիթմների նախնական մշակման քայլ, օրինակ`սկզբնական բաժանում գտնելու համար։

=== Հանրամատչելի ծրագրեր ===
Ստորև նշված ծրագրերն ունեն բաց հասանելիություն.

* Accord.NET. պարունակում է C# կիրառություններ *k* -միջինների, *k* -միջիններ++ և *k* -մոդերի համար։ 
* ALGLIB- ը պարունակում է զուգահեռաբար C++ և C# ներդրումներ *k- միջինների* և *k- միջիններ*++ համար։ 
* [[Անդրոիդ|AOSP- ն]] պարունակում է Java-ի ներդրումներ *k-*միջինների համար։ 
* CrimeStat- ը իրականացնում է երկու տարածական *k- միջինների* ալգորիթմ, որոնցից մեկը թույլ է տալիս օգտագործողին սահմանել սկզբնական/մեկնարկային տեղերը։ 
* ELKI- ն պարունակում է *k- միջիններ* (Lloyd- ի և MacQueen- ի կրկնողությամբ, ինչպես նաև *k-* միջիններ++ և այլն) և տարբեր ավելի առաջադեմ կլաստերի ալգորիթմներ։ 
* Julia- ն պարունակում է *k- միջինների* իրականացում JuliaStats Clustering փաթեթում։ 
* KNIME պարունակում է նոդեր *k* -միջինների և *k* -մեդոիդների համար։ 
* Mahout- ը պարունակում է MapReduce- ի վրա հիմնված *k- միջիններ* ։ 
* mlpack- ը պարունակում է *k-*միջինների C++ ներդրումներ։ 
* Octave- ը պարունակում է *k- միջիններ* ։ 
* OpenCV- ն պարունակում է *k- միջինների* կիրառություններ։ 
* Orange-ը պարունակում է *k-* միջիններով կլաստերինգի բաղադրիչներ՝ *k-ի* և կլաստերների ավտոմատ ընտրությամբ։ 
* PSPP պարունակում *k* -միջիններ, THE QUICK CLUSTER հրամանը կատարում է տվյալների *k* -միջիններով կլաստերինգ։ 
* [[R (ծրագրավորման լեզու)|R- ը]] պարունակում է երեք *k-*միջիններով տատանումներ։ 
* SciPy և scikit learn պարունակում են մի քանի *K* -միջինների ներդումները։ 
* Spark MLlib- ն աշխատացնում է բաշխված *k- միջոիների* ալգորիթմը։ 
* Torch-ը պարունակում է *unsup* փաթեթ, որը ապահովում է *K* -միջիններով կլաստերինգի իրականացումը։ 
* Weka- ն պարունակում է *k-* միջիններ և *x-'' միջիններ։

## Ծանոթագրություններ

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