Боби 8. Кластербандии k-means

Дар ин боб меомӯзем

• Кластербандӣ чист ва k-means додаҳоро чӣ гуна ба k гурӯҳ тақсим мекунад.
• Сентроид ва масофаи Евклидӣ.
• Қадамҳои алгоритм дар мисоли 12 нуқта.
• Се роҳи интихоби k: усули оринҷ, қоидаи тахминӣ ва дониши соҳавӣ.

Усули навбатии таҳлил гурӯҳбандӣ ё кластербандии нуқтаҳои додаҳои дорои хусусиятҳои монанд мебошад, ки бо истифода аз омӯзиши беназорат анҷом дода мешавад.

Масалан, як тиҷорати интернетӣ мехоҳад гурӯҳи муштариёнеро омӯзад, ки дар як давраи муайяни сол харид мекунанд ва бифаҳмад, ки кадом омилҳо ба рафтори харидории онҳо таъсир мерасонанд.

Бо шинохтани чунин гурӯҳи муштариён, ширкат метавонад қарор диҳад, ки тавассути аксияҳо ва пешниҳодҳои шахсигардонидашуда ба ҳар гурӯҳ кадом маҳсулотро тавсия диҳад.

Ғайр аз таҳқиқоти бозор, кластербандиро дар самтҳои дигар низ истифода мебаранд, аз ҷумла шинохти қолабҳо, ошкорсозии қаллобӣ ва коркарди тасвирҳо.

Яке аз усулҳои маъмултарини кластербандӣ k-means, ё усули k миёна, мебошад.

Ҳамчун алгоритми омӯзиши беназорат, k-means кӯшиш мекунад додаҳоро ба k гурӯҳи ҷудогона тақсим кунад. Ин усул барои ошкор кардани қолабҳои нав самаранок аст.

Намунаҳои гурӯҳҳои эҳтимолӣ метавонанд навъҳои ҳайвонот, муштариёни дорои хусусиятҳои монанд ва бахшҳои бозори манзил бошанд.

Расми 8.1. Муқоисаи додаҳои аслӣ ва додаҳои бо k-means кластербандишуда.

Алгоритми k-means додаҳоро ба шумораи муайяни кластерҳо тақсим мекунад. Дар ин ҷо k шумораи кластерҳоест, ки мехоҳед созед.

Масалан, агар хоҳед маҷмӯи додаҳоро ба се кластер тақсим кунед, бояд k = 3 гузоред. Дар расми 8.1 мебинем, ки додаҳои аслӣ ба се кластер ҷудо шудаанд.

Агар k = 4 интихоб кунем, алгоритм додаҳоро ба чор кластер тақсим мекунад.

k-means нуқтаҳоро чӣ гуна ҷудо мекунад?

Қадами аввал интихоби маркази ибтидоӣ барои ҳар кластер мебошад. Ин марказро сентроид — centroid меноманд.

Сентроидҳо метавонанд ба таври тасодуфӣ интихоб шаванд. Масалан, метавонед чанд нуқтаи мавҷударо дар диаграммаи парокандагӣ ҳамчун марказҳои ибтидоӣ интихоб кунед.

Аммо интихоби марказҳое, ки дар қисмҳои гуногуни диаграмма ҷойгиранд ва ба ҳам хеле наздик нестанд, метавонад раванди корро самараноктар кунад. Ба ибораи дигар, дар оғоз тахмин мекунед, ки маркази ҳар кластер эҳтимол дар куҷо ҷойгир аст.

Сипас ҳар нуқтаи додаҳо аз рӯйи масофаи Евклидӣ ба наздиктарин сентроид мансуб карда мешавад. Масофаи Евклидӣ байни ду нуқтаи ((x_1, y_1)) ва ((x_2, y_2)) дарозии хати рости байни онҳост:

[ d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2} ]

Масалан, масофаи нуқтаи (3, 5) то сентроиди (2, 1) чунин аст:

[ d=\sqrt{(3-2)^2+(5-1)^2}=\sqrt{1+16}=\sqrt{17}\approx 4.12 ]

Расми 8.2. Ҳисоб кардани масофаи Евклидӣ.

Ҳар нуқта танҳо ба як кластер дохил мешавад. Яъне, дар ин гурӯҳбандӣ узвияти кластерҳо ҳампӯшӣ надорад ва як кластер ҳамчун зермаҷмӯи кластерҳои дигар сохта намешавад.

Ҳамаи нуқтаҳо, аз ҷумла нуқтаҳои ғайримуқаррарӣ, ба яке аз марказҳо мансуб карда мешаванд, ҳатто агар онҳо ба шакли ниҳоии кластер таъсири номатлуб расонанд.

Азбаски гурӯҳбандӣ ба масофа аз марказ такя мекунад, k-means одатан барои кластерҳои фишурда ва тақрибан курашакл мувофиқтар аст.

Пас аз он ки ҳамаи нуқтаҳо ба сентроидҳо мансуб шуданд, қадами навбатӣ ҳисоб кардани миёнаи қиматҳои нуқтаҳои ҳар кластер мебошад.

Дар мисоли дученака, барои ин миёнаи координатаҳои x ва y-и ҳамаи нуқтаҳои дохили кластерро ҳисоб мекунем.

Сипас координатаҳои сентроидро бо ҳамин қиматҳои миёна иваз мекунем. Дар натиҷа, эҳтимол ҷойгиршавии як ё чанд сентроид тағйир ёбад.

Аммо шумораи умумии кластерҳо ҳамон қадар мемонад. Мо кластерҳои нав намесозем, балки танҳо марказҳои онҳоро нав мекунем.

Пас аз тағйир ёфтани марказҳо, нуқтаҳо боз ба наздиктарин сентроид мансуб мешаванд. Ин раванд ба бозии «курсиҳои мусиқӣ» монанд аст: бо иваз шудани ҷойи марказҳо, нуқтаҳо метавонанд гурӯҳи худро иваз кунанд.

Агар ягон нуқта ба кластери дигар гузарад, қадами пешина такрор мешавад:

1. Миёнаи координатаҳои нуқтаҳои ҳар кластер ҳисоб карда мешавад.
2. Координатаҳои сентроидҳо нав карда мешаванд.
3. Нуқтаҳо аз нав ба наздиктарин сентроид мансуб мешаванд.

Вақте пас аз навсозии марказҳо дигар ягон нуқта кластери худро иваз намекунад, алгоритм ба натиҷаи устувор мерасад ва кластерҳои ниҳоӣ ҳосил мешаванд.

Расмҳои зерин марҳилаҳои ин равандро дар мисоли 12 нуқта ва k = 2 нишон медиҳанд.

Расми 8.3. Нуқтаҳои намунавии додаҳо дар диаграммаи парокандагӣ ҷойгир шудаанд. Додаҳо барои нишон додани қадамҳои алгоритм сохта шудаанд.

Расми 8.4. Ду нуқтаи мавҷуда — (2, 1) ва (6, 3) — ҳамчун сентроидҳои ибтидоӣ интихоб шудаанд.

Расми 8.5. Пас аз ҳисоб кардани масофаи Евклидии нуқтаҳои боқимонда то сентроидҳо, ду кластер ташкил мешавад.

Нуқтаи (3, 5)-ро бинед. Масофаи он то сентроиди чап (\sqrt{17}\approx 4.12) ва то сентроиди рост (\sqrt{(3-6)^2+(5-3)^2}=\sqrt{13}\approx 3.61) аст. Бинобар ин, дар қадами аввал он ба кластери рост дохил мешавад.

Расми 8.6. Координатаҳои сентроиди ҳар кластер мувофиқи миёнаи координатаҳои нуқтаҳои он нав карда мешаванд. Нуқтаҳое, ки қаблан марказ буданд, дар ҷойи худ мемонанд, аммо дигар сентроид нестанд (аломатҳои холӣ). Нуқтаи (3, 5), ки бо доира нишон дода шудааст, акнун ба сентроиди чап наздиктар аст ва аз кластери рост ба кластери чап мегузарад. Аз ин рӯ, марказҳои ҳар ду кластер бояд боз нав карда шаванд.

Сентроиди нави чап (1.75, 2.5) ва сентроиди нави рост (5.56, 3.44) мебошад. Масофаи нуқтаи (3, 5) то онҳо мутаносибан тақрибан 2.80 ва 3.00 аст, яъне нуқта ба кластери чап мегузарад.

Расми 8.7. Ду кластери ниҳоӣ дар асоси сентроидҳои навшуда — (2, 3) ва (5.93, 3.21) — ҳосил мешаванд. Ин дафъа ягон нуқта кластерашро иваз намекунад.

Дар ин мисол сентроидҳо ду маротиба нав карда шуданд: пас аз даври аввал як нуқта кластерашро иваз кард, пас аз даври дуюм тақсимот дигар тағйир наёфт ва алгоритм қатъ гардид.

Бо вуҷуди ин, k-means на ҳамеша гурӯҳбандии мувофиқу боэътимодро ошкор мекунад. Дар чунин ҳолатҳо шояд лозим шавад, ки равишро иваз карда, аз алгоритми дигари кластербандӣ истифода баред.

Ҳамчунин, пеш аз иҷрои k-means мумкин аст хусусиятҳои воридотиро бо истифода аз стандартизатсия миқёсбандӣ кардан лозим шавад.

Ин кор ёрӣ медиҳад, ки фарқияти миқёси хусусиятҳо натиҷаро таҳриф накунад ва боиси аз ҳад кашида шудани кластерҳо дар самти як хусусият нагардад.

Интихоби қимати k

Ҳангоми истифодаи k-means интихоби шумораи мувофиқи кластерҳо муҳим аст.

Умуман, бо зиёд шудани k кластерҳо хурдтар мешаванд ва парокандагии дохилии онҳо кам мешавад. Аммо дар айни замон фарқ кардани кластерҳои ҳамсоя аз якдигар метавонад душвортар гардад.

Агар k-ро ба шумораи умумии нуқтаҳои додаҳо баробар гузоред, ҳар нуқта кластери алоҳида мешавад.

Баръакс, агар k = 1 бошад, ҳамаи нуқтаҳо ба як кластери калон дохил мешаванд.

Маълум аст, ки чунин интихоби ҳаддӣ одатан барои фаҳмидани сохтори додаҳо иттилооти муфиди зиёд намедиҳад.

Усули оринҷ

Барои интихоби k метавон аз графике истифода бурд, ки тағйирёбии парокандагии дохили кластерҳоро вобаста ба шумораи кластерҳо нишон медиҳад. Ин равиш бо номи усули оринҷ — elbow method маъруф аст.

Дар чунин график барои ҳар қимати k нишондиҳандаи ҷамъи квадратҳои хато — SSE ҳисоб карда мешавад.

SSE ҷамъи квадратҳои масофаи ҳар нуқта то сентроиди кластери худ мебошад.

Бо зиёд шудани шумораи кластерҳо SSE одатан кам мешавад.

Расми 8.8. График барои интихоби шумораи кластерҳо бо усули оринҷ (барои додаҳои расми 8.1).

Пас шумораи беҳтарини кластерҳо чанд аст?

Одатан қиматеро интихоб мекунанд, ки то он SSE босуръат кам мешавад, аммо баъд аз он илова кардани кластерҳои нав беҳбудии чандоне намедиҳад. Ин нуқта дар график ба «оринҷ» монанд аст.

Масалан, дар расми 8.8 ҳангоми интихоби чор ё бештар кластер SSE хеле кам тағйир меёбад. Чунин тақсимот метавонад кластерҳои хурдеро ба вуҷуд орад, ки фарқ карданашон душвор аст.

Дар ин график се кластер интихоби мувофиқ аст. То k = 3 SSE ба таври назаррас паст мешавад, аммо баъд аз он суръати коҳиш хеле суст мегардад. Ин ба расми 8.1 мувофиқ аст, ки дар он додаҳо ба се гурӯҳ ҷудо мешаванд. Дар додаҳои воқеӣ «оринҷ» на ҳамеша ин қадар равшан аст ва гоҳо ду қимати ҳамсоя ба як андоза мувофиқ менамоянд.

Қоидаи тахминӣ

Роҳи дигари тахмини шумораи кластерҳо ин аст, ки шумораи умумии нуқтаҳои додаҳо — n — ро ба ду тақсим карда, решаи квадратии натиҷаро гирем:

[ k \approx \sqrt{\frac{n}{2}} ]

Масалан, агар 200 нуқта дошта бошем:

[ k \approx \sqrt{\frac{200}{2}}=\sqrt{100}=10 ]

Агар 18 нуқта дошта бошем:

[ k \approx \sqrt{\frac{18}{2}}=\sqrt{9}=3 ]

Ин танҳо қоидаи тахминӣ аст, на кафолати интихоби беҳтарин.

Истифодаи дониши соҳавӣ

Роҳи содатар ва ғайриматематикии интихоби k истифодаи дониши соҳавӣ мебошад.

Масалан, агар додаҳои боздидкунандагони сомонаи як таъминкунандаи бузурги технологияҳои иттилоотиро таҳлил кунам, шояд k = 2 интихоб намоям.

Чаро ду кластер?

Зеро аз таҷриба медонам, ки рафтори хароҷотии боздидкунандагони нав ва такрорӣ ба таври назаррас фарқ мекунад.

Одамоне, ки бори аввал ба сомона меоянд, хеле кам маҳсулот ё хидматҳои IT-и сатҳи корхонаҳои бузургро мехаранд. Одатан онҳо пеш аз тасдиқи харид раванди тӯлонии таҳқиқ, санҷиш ва арзёбиро мегузаранд.

Бо такя ба ин дониш, метавонам тавассути k-means ду кластер созам ва фарзияи худро бисанҷам.

Пас аз ҳосил кардани ду кластер, шояд яке аз онҳоро муфассалтар омӯзам. Барои ин метавонам усули дигар ё боз ҳам k-means-ро истифода барам.

Масалан, шояд хоҳам корбарони такрориро ба ду кластер тақсим кунам, то фарзияеро бисанҷам: оё корбарони дастгоҳҳои мобилӣ ва компютерҳои рӯимизӣ ду гурӯҳи ҷудогона ташкил медиҳанд?

Бо такя ба дониши соҳавӣ медонам, ки корхонаҳои бузург хеле кам харидҳои гаронбаҳоро тавассути дастгоҳи мобилӣ анҷом медиҳанд. Ин фарзияро метавон бо k-means санҷид.

Аммо агар саҳифаи маҳсулоти арзон, масалан, номи домени 4.99-долларӣ-ро таҳлил кунам, эҳтимоли он ки боздидкунандагони нав ва такрорӣ ду кластери равшан ташкил кунанд, камтар аст.

Азбаски нархи маҳсулот паст аст, корбарони нав эҳтимол пеш аз харид муддати зиёд фикр намекунанд.

Дар ин ҳолат, шояд бо назардошти се манбаи асосии ҷалби муштариёни эҳтимолӣ k = 3 интихоб кунам:

а) Трафики органикӣ. Он одатан ҳам муштариёни нав ва ҳам муштариёни такрориро дар бар мегирад, ки нияти харид доранд. Онҳо метавонанд пешакӣ тавассути тавсияи дигарон ё таҷрибаи хариди қаблӣ сомонаро интихоб карда бошанд.

б) Трафики пулакӣ. Он муштариёни наверо ҷалб мекунад, ки одатан нисбат ба боздидкунандагони органикӣ эътимоди камтар доранд. Ба ин гурӯҳ одамоне низ дохил мешаванд, ки тасодуфан рӯйи реклама пахш кардаанд.

в) Маркетинги почтаи электронӣ. Он ба муштариёни мавҷуда мерасад, ки аллакай таҷрибаи харид аз сомона ва ҳисобҳои сабтшудаву тасдиқшуда доранд.

Бо такя ба ин фарқиятҳо метавон фарз кард, ки ин се манбаъ гурӯҳҳои гуногун ташкил медиҳанд ва сипас фарзияро бо таҳлил санҷид.

Ин мисоли истифодаи дониши соҳавӣ аз таҷрибаи касбии муаллифи аслии китоб аст. Аммо фоидаи чунин дониш ҳангоми зиёд шудани шумораи кластерҳо хеле кам мешавад.

Ба ибораи дигар, дониши соҳавӣ метавонад барои интихоби ду то чор кластер кофӣ бошад, аммо барои интихоб байни 20 ё 21 кластер роҳнамоии чандоне намедиҳад.

Чиро бояд дар ёд дошт

• k-means усули омӯзиши беназорат аст: додаҳоро бе нишонаҳо ба k гурӯҳ тақсим мекунад.
• Алгоритм ду қадамро такрор мекунад: ҳар нуқтаро ба наздиктарин сентроид мансуб мекунад ва сентроидро ба миёнаи нуқтаҳои кластераш мекӯчонад. Вақте ягон нуқта кластерашро иваз намекунад, кор тамом мешавад.
• k-means барои кластерҳои фишурда ва курашакл беҳтар кор мекунад; хусусиятҳоро пеш аз он миқёсбандӣ кунед.
• k-ро бо усули оринҷ, қоидаи тахминии (k \approx \sqrt{n/2}) ё дониши соҳавӣ интихоб мекунанд — ҳеҷ кадоме кафолати қимати беҳтарин нест.