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) (այսինքն՝ վարիացիան )։ Ֆորմալ առումով, նպատակն է գտնել.
որտեղ μ i- ն S i- ում կետերի միջինն է։ Սա համարժեք է նույն կլաստերի ներսում կետերի զույգային քառակուսիների շեղումները նվազագույնի հասցնելուն.
Համարժեքությունը կարող է բխել ինքնությունից՝ : Քանի որ ընդհանուր վարիացիան հաստատուն է, դա համարժեք է տարբեր կլաստերների միջև շեղումների քառակուսիների գումարի մաքսիմալացմանը (BCSS: between-cluster sum of squares)[1]:
Պատմություն
[խմբագրել | խմբագրել կոդը]« K- means» տերմինը առաջին անգամ օգտագործել է Ջեյմս ՄքՔուինի կողմից 1967 թվականին, չնայած գաղափարը ավելի վաղ օգտագործել էր Հյուգո Շտայնհաուսը 1956-ին[2] : Ստանդարտ ալգորիթմն առաջին անգամ առաջարկել է Ստյուարտ Լլոյդը Bell Labs- ի կողմից 1957-ին զարկերակային կոդերի մոդուլյացիայի տեխնիկայի համար, չնայած որ այն որպես հոդված չի հրապարակվել մինչև 1982 թվականը[3]։ 1965 թ.-ին Էդվարդ Վ. Ֆորգը հրատարակեց ըստ էության նույն մեթոդը, այդ պատճառով էլ այն երբեմն կոչվում է Լլոյդ-Ֆորգի[4]։
Ալգորիթմներ
[խմբագրել | խմբագրել կոդը]Ստանդարտ ալգորիթմ (նայիվ K- միջիններ)
[խմբագրել | խմբագրել կոդը]
Ամենատարածված ալգորիթմը օգտագործում է իտերատիվ կամ անընդհատ բարելավման տեխնիկան։ Իր տարածվածության պատճառով այն հաճախ կոչվում է « k- ի միջինների ալգորիթմ»; այն նաև կոչվում է որպես Լլոյդի ալգորիթմ, մասնավորապես ՝ համակարգչային գիտությունների ոլորտում։ Այն երբեմն կոչվում է նաև «նայիվ k- միջիններ », քանի որ կան շատ ավելի արագ աշխատող այլընտրանքներ[5]։
Տրված k- միջինների համար` m 1 (1), ..., m k (1), ստորև ներկայացված ալգորիթմն ընթանում է երկու հաջորդական և կրկնվող քայլերով[6].
- Հանձնարարության քայլ. Յուրաքանչյուր կետ նշանակել այն կլաստերին, որի միջինը ունի ամենափոքր քառակուսային էվկլիդյան հեռավորությունը, որը համարվում է ՙՙամենամոտ՚՚ միջինը[7] : Մաթեմատիկորեն, սա նշանակում է, որ կետերը բաժանում են ըստ Վորոնոյի դիագրամի ստեղծած միջինների։
- որտեղ յուրաքանչյուրը -ին նշանակվում է միայն մեկ -ի, նույնիսկ եթե այն կարող էր նշանակվել երկուսի կամ ավելիի։
- Թարմացման քայլ. Հաշվարկեք դիտարկումների նոր միջինները ( ցենտրոիդները ) նոր կլաստերում։
Ալգորիթմը վերջանում է, երբ հանձնարարության արդյունքներն այլևս չեն փոխվում։ Ալգորիթմը չի երաշխավորում գտնել օպտիմալը[8]։
- Ստանդարտ ալգորիթմի ցուցադրում
-
1. k սկզբնական «միջինները» (այս դեպքում k = 3) պատահականորեն ստեղծվում են տվյալների տիրույթում (ցույց է տրված գույնով)։
-
2. k կլաստերը ստեղծվում է ամեն դիտարկումը մոտակա միջինի հետ կապելով։ Բաժանումներն այստեղ ներկայացնում են միջինների կողմից առաջ բերված Վորոնոյի դիագրամը ։
-
3. Յուրաքանչյուր k կլաստերների ցենտրոիդը դառնում է նրա նոր միջինը։
-
4. 2-րդ և 3-րդ քայլերը կրկնվում են, քանի դեռ չեն զուգամիտել։
«Հանձնարարություն» քայլը կոչվում է «սպասման քայլ», մինչդեռ «թարմացման քայլը» առավելագույնի հասցնելու/մաքսիմալացման քայլ է՝ ալգորիթմը դարձնելով ընդհանրացված սպասումների մաքսիմալացման ալգորիթմի տարբերակ ։
Քննարկում
[խմբագրել | խմբագրել կոդը]


K- միջինների երեք հիմնական առանձնահատկությունները, որոնք այն դարձնում են արդյունավետ, հաճախ դիտվում են որպես դրա ամենամեծ թերությունները.
- Էվկլիդյան հեռավորությունը օգտագործվում է որպես չափման մեթոդ, իսկ վարիացիան՝ որպես կլաստերի ցրվածության չափման միջոց։
- Կլաստերների քանակը k մուտքագրվող պարամետր է. K- ի ոչ պատշաճ ընտրությունը կարող է բերել վատ արդյունքների։ Այդ իսկ պատճառով, k- միջինները օգտագործելիս անհրաժեշտ է ախտորոշիչ ստուգումներ անցկացնել տվյալների հավաքածուի քանակի որոշման համար։
- Լոկալ մինիմումը գտնելը կարող է բերել սխալ արդյունքների։
K –միջինների կարևոր սահմանափակումը նրա կլաստերի մոդելն է։ Հայեցակարգը հիմնված է գնդաձև կլաստերի վրա, որոնք հնարավոր է առանձնացնել այնպես, որ միջինը համընկնում է կլաստերի կենտրոնի նկատմամբ։ Ակնկալվում է, որ կլաստերների չափերը նման են, այնպես որ մոտակա կլաստերային կենտրոնին նշանակումը ճիշտ հանձնարարություն է։ Օրինակ` օգտագործելով k- միջիններ իրիսի հայտնի ծաղիկների տվյալների վրա, երբ , հաճախ չի հաջողվում առանձնացնել Iris- ի երեք տեսակները, որոնք պարունակում են տվյալների շարքում։ դեպքում հայտնաբերվելու են երկու տեսանելի կլաստեր (մեկը, որը պարունակում է երկու տեսակ), մինչդեռ երկու կլաստերից մեկը բաժանվելու է երկու հավասար մասերի։ Իրականում, այս տվյալների համար առավել նպատակահարմար է, չնայած տվյալների պարունակում են 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- միջիններ։
Ծանոթագրություններ
[խմբագրել | խմբագրել կոդը]- ↑ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). «The (black) art of runtime evaluation: Are we comparing algorithms or implementations?». Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377.
- ↑ Steinhaus, Hugo (1957). «Sur la division des corps matériels en parties». Bull. Acad. Polon. Sci. (French). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
{{cite journal}}
: CS1 սպաս․ չճանաչված լեզու (link) - ↑ Lloyd, Stuart P. (1957). «Least square quantization in PCM». Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, Stuart P. (1982). «Least squares quantization in PCM» (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. Վերցված է 2009 թ․ ապրիլի 15-ին.
- ↑ Forgy, Edward W. (1965). «Cluster analysis of multivariate data: efficiency versus interpretability of classifications». Biometrics. 21 (3): 768–769. JSTOR 2528559.
- ↑ Pelleg, Dan; Moore, Andrew (1999). «Accelerating exact k -means algorithms with geometric reasoning». Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '99 (անգլերեն). San Diego, California, United States: ACM Press: 277–281. doi:10.1145/312129.312248. ISBN 9781581131437.
- ↑ MacKay, David (2003). «Chapter 20. An Example Inference Task: Clustering» (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. էջեր 284–292. ISBN 978-0-521-64298-9. MR 2012999.
- ↑ Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
- ↑ Hartigan, J. A.; Wong, M. A. (1979). «Algorithm AS 136: A k-Means Clustering Algorithm». Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830.
- ↑ Mirkes, E. M. «K-means and k-medoids applet». Վերցված է 2016 թ․ հունվարի 2-ին.