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

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


== Նկարագրություն ==
Տրված կետերի համար՝ ( x 1, x 2, ..., x n ), որտեղ յուրաքանչյուր կետ d- չափանի իրական վեկտոր է, k- միջիններով կլաստերինգը նպատակ ունի n կետերը բաժանել k- ի (≤   n ),  S   = {S1, S2, ..., Sk} այնպես, որ նվազագույնի հասցվի ներկլաստերային քառակուսիների գումարը (WCSS) (այսինքն՝ վարիացիան )։ Ֆորմալ առումով, նպատակն է գտնել. 
  
    
      
        
          
            
              a
              r
              g
              
              m
              i
              n
            
            
              S
            
          
        
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
          ∑
          
            
              x
            
            ∈
            
              S
              
                i
              
            
          
        
        
          
            ‖
            
              
                x
              
              −
              
                
                  μ
                
                
                  i
                
              
            
            ‖
          
          
            2
          
        
        =
        
          
            
              a
              r
              g
              
              m
              i
              n
            
            
              S
            
          
        
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
          |
        
        
          S
          
            i
          
        
        
          |
        
        Var
        ⁡
        
          S
          
            i
          
        
      
    
    {\displaystyle {\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}}
   որտեղ μ i- ն S i- ում  կետերի միջինն է։ Սա համարժեք է նույն կլաստերի ներսում կետերի զույգային քառակուսիների շեղումները նվազագույնի հասցնելուն. 
  
    
      
        
          
            
              a
              r
              g
              
              m
              i
              n
            
            
              S
            
          
        
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
        
          
            1
            
              2
              
                |
              
              
                S
                
                  i
                
              
              
                |
              
            
          
        
        
        
          ∑
          
            
              x
            
            ,
            
              y
            
            ∈
            
              S
              
                i
              
            
          
        
        
          
            ‖
            
              
                x
              
              −
              
                y
              
            
            ‖
          
          
            2
          
        
      
    
    {\displaystyle {\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}}
   Համարժեքությունը կարող է բխել ինքնությունից՝ 
  
    
      
        
          ∑
          
            
              x
            
            ∈
            
              S
              
                i
              
            
          
        
        
          
            ‖
            
              
                x
              
              −
              
                
                  μ
                
                
                  i
                
              
            
            ‖
          
          
            2
          
        
        =
        
          ∑
          
            
              x
            
            ≠
            
              y
            
            ∈
            
              S
              
                i
              
            
          
        
        (
        
          x
        
        −
        
          
            μ
          
          
            i
          
        
        )
        (
        
          
            μ
          
          
            i
          
        
        −
        
          y
        
        )
      
    
    {\displaystyle \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} )}
   : Քանի որ ընդհանուր վարիացիան հաստատուն է, դա համարժեք է տարբեր կլաստերների միջև շեղումների քառակուսիների գումարի մաքսիմալացմանը (BCSS: between-cluster sum of squares) :


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


== Ալգորիթմներ ==


=== Ստանդարտ ալգորիթմ (նայիվ K- միջիններ) ===

Ամենատարածված ալգորիթմը օգտագործում է իտերատիվ կամ անընդհատ բարելավման տեխնիկան։ Իր տարածվածության պատճառով այն հաճախ կոչվում է « k- ի միջինների ալգորիթմ»; այն նաև կոչվում է որպես Լլոյդի ալգորիթմ, մասնավորապես ՝ համակարգչային գիտությունների ոլորտում։ Այն երբեմն կոչվում է նաև «նայիվ k- միջիններ », քանի որ կան շատ ավելի արագ աշխատող այլընտրանքներ ։
Տրված k- միջինների համար` m 1 (1), ..., m k (1), ստորև ներկայացված ալգորիթմն ընթանում է երկու հաջորդական և կրկնվող քայլերով.

Հանձնարարության քայլ. Յուրաքանչյուր կետ նշանակել այն կլաստերին, որի միջինը ունի ամենափոքր քառակուսային էվկլիդյան հեռավորությունը, որը համարվում է ՙՙամենամոտ՚՚ միջինը : Մաթեմատիկորեն, սա նշանակում է, որ կետերը բաժանում են ըստ Վորոնոյի դիագրամի ստեղծած միջինների։

  
    
      
        
          S
          
            i
          
          
            (
            t
            )
          
        
        =
        
          
            {
          
        
        
          x
          
            p
          
        
        :
        
          
            ‖
          
        
        
          x
          
            p
          
        
        −
        
          m
          
            i
          
          
            (
            t
            )
          
        
        
          
            
              ‖
            
          
          
            2
          
        
        ≤
        
          
            ‖
          
        
        
          x
          
            p
          
        
        −
        
          m
          
            j
          
          
            (
            t
            )
          
        
        
          
            
              ‖
            
          
          
            2
          
        
         
        ∀
        j
        ,
        1
        ≤
        j
        ≤
        k
        
          
            }
          
        
        ,
      
    
    {\displaystyle S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},}
  
որտեղ յուրաքանչյուրը 
  
    
      
        
          x
          
            p
          
        
      
    
    {\displaystyle x_{p}}
  -ին նշանակվում է միայն մեկ 
  
    
      
        
          S
          
            (
            t
            )
          
        
      
    
    {\displaystyle S^{(t)}}
  -ի, նույնիսկ եթե այն կարող էր նշանակվել երկուսի կամ ավելիի։
Թարմացման քայլ. Հաշվարկեք դիտարկումների նոր միջինները ( ցենտրոիդները ) նոր կլաստերում։

  
    
      
        
          m
          
            i
          
          
            (
            t
            +
            1
            )
          
        
        =
        
          
            1
            
              |
              
                S
                
                  i
                
                
                  (
                  t
                  )
                
              
              |
            
          
        
        
          ∑
          
            
              x
              
                j
              
            
            ∈
            
              S
              
                i
              
              
                (
                t
                )
              
            
          
        
        
          x
          
            j
          
        
      
    
    {\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}
  
Ալգորիթմը վերջանում է, երբ հանձնարարության արդյունքներն այլևս չեն փոխվում։ Ալգորիթմը չի երաշխավորում գտնել օպտիմալը ։ Ստանդարտ ալգորիթմի ցուցադրում
		
		
		
		
 «Հանձնարարություն» քայլը կոչվում է «սպասման քայլ», մինչդեռ «թարմացման քայլը» առավելագույնի հասցնելու/մաքսիմալացման քայլ է՝ ալգորիթմը դարձնելով ընդհանրացված սպասումների մաքսիմալացման ալգորիթմի տարբերակ ։


== Քննարկում ==

K- միջինների երեք հիմնական առանձնահատկությունները, որոնք այն դարձնում են արդյունավետ, հաճախ դիտվում են որպես դրա ամենամեծ թերությունները.

Էվկլիդյան հեռավորությունը օգտագործվում է որպես չափման մեթոդ, իսկ վարիացիան՝ որպես կլաստերի ցրվածության չափման միջոց։
Կլաստերների քանակը k մուտքագրվող պարամետր է. K- ի ոչ պատշաճ ընտրությունը կարող է բերել վատ արդյունքների։ Այդ իսկ պատճառով, k- միջինները օգտագործելիս անհրաժեշտ է ախտորոշիչ ստուգումներ անցկացնել տվյալների հավաքածուի քանակի որոշման համար։
Լոկալ մինիմումը գտնելը կարող է բերել սխալ արդյունքների։K –միջինների կարևոր սահմանափակումը նրա կլաստերի մոդելն է։ Հայեցակարգը հիմնված է գնդաձև կլաստերի վրա, որոնք հնարավոր է առանձնացնել այնպես, որ միջինը համընկնում է կլաստերի կենտրոնի նկատմամբ։ Ակնկալվում է, որ կլաստերների չափերը նման են, այնպես որ մոտակա կլաստերային կենտրոնին նշանակումը ճիշտ հանձնարարություն է։ Օրինակ` օգտագործելով k- միջիններ իրիսի հայտնի ծաղիկների տվյալների վրա, երբ 
  
    
      
        k
        =
        3
      
    
    {\displaystyle k=3}
  ,  հաճախ չի հաջողվում առանձնացնել Iris- ի երեք տեսակները, որոնք պարունակում են տվյալների շարքում։ 
  
    
      
        k
        =
        2
      
    
    {\displaystyle k=2}
   դեպքում հայտնաբերվելու են երկու տեսանելի կլաստեր (մեկը, որը պարունակում է երկու տեսակ), մինչդեռ 
  
    
      
        k
        =
        3
      
    
    {\displaystyle k=3}
   երկու կլաստերից մեկը բաժանվելու է երկու հավասար մասերի։ Իրականում, 
  
    
      
        k
        =
        2
      
    
    {\displaystyle k=2}
   այս տվյալների համար առավել նպատակահարմար է, չնայած տվյալների պարունակում են 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- ը պարունակում է երեք k-միջիններով տատանումներ։
SciPy և scikit learn պարունակում են մի քանի K -միջինների ներդումները։
Spark MLlib- ն աշխատացնում է բաշխված k- միջոիների ալգորիթմը։
Torch-ը պարունակում է unsup փաթեթ, որը ապահովում է K -միջիններով կլաստերինգի իրականացումը։
Weka- ն պարունակում է k- միջիններ և x- միջիններ։


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