Π‘Π²ΡΠΆΠΈΡ‚Π΅ΡΡŒ с Π½Π°ΠΌΠΈ:

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ кластСризация K-срСдних?

AI 101

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ кластСризация K-срСдних?

mm

ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСдних Π½Π΅ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΠΈΡ€ΡƒΠ΅ΠΌΠΎΠ΅ ΠΎΠ±ΡƒΡ‡Π΅Π½ΠΈΠ΅ Алгоритм, ΠΈ ΠΈΠ· всСх Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² обучСния Π±Π΅Π· учитСля, кластСризация K-срСдних ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡˆΠΈΡ€ΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠΉ благодаря своСй мощности ΠΈ простотС. Как ΠΈΠΌΠ΅Π½Π½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ кластСризация K-срСдних?

ΠšΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΉ ΠΎΡ‚Π²Π΅Ρ‚ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ кластСризация ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ K-срСдних Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ: созданиС ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΈ (Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Π°) Π½Π° ΠΆΠ΅Π»Π°Π΅ΠΌΠΎΠ΅ количСство занятий, Π° Π·Π°Ρ‚Π΅ΠΌ Π½Π°Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ‚ΠΎΡ‡Π΅ΠΊ Π΄Π°Π½Π½Ρ‹Ρ… кластСрам классов Π² зависимости ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, какая Ρ‚ΠΎΡ‡ΠΊΠ° отсчСта находится Π±Π»ΠΈΠΆΠ΅ всСго. Π₯отя это ΠΊΡ€Π°Ρ‚ΠΊΠΎΠ΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ кластСризации K-срСдних, Π΄Π°Π²Π°ΠΉΡ‚Π΅ ΡƒΠ΄Π΅Π»ΠΈΠΌ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ врСмя Ρ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡƒΠ³Π»ΡƒΠ±ΠΈΡ‚ΡŒΡΡ Π² ΠΊΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡŽ K-срСдних ΠΈ Π»ΡƒΡ‡ΡˆΠ΅ ΠΏΠΎΠ½ΡΡ‚ΡŒ, ΠΊΠ°ΠΊ ΠΎΠ½Π° Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚.

ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ кластСризации

ΠŸΡ€Π΅ΠΆΠ΄Π΅ Ρ‡Π΅ΠΌ ΠΌΡ‹ рассмотрим Ρ‚ΠΎΡ‡Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Π΅ для кластСризации K-срСдних, Π΄Π°Π²Π°ΠΉΡ‚Π΅ ΡƒΠ΄Π΅Π»ΠΈΠΌ Π½Π΅ΠΌΠ½ΠΎΠ³ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ кластСризации Π² Ρ†Π΅Π»ΠΎΠΌ.

ΠšΠ»Π°ΡΡ‚Π΅Ρ€Ρ‹ β€” это просто Π³Ρ€ΡƒΠΏΠΏΡ‹ элСмСнтов, Π° кластСризация β€” это просто объСдинСниС элСмСнтов Π² эти Π³Ρ€ΡƒΠΏΠΏΡ‹. Π’ смыслС Π½Π°ΡƒΠΊΠΈ ΠΎ Π΄Π°Π½Π½Ρ‹Ρ…, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ кластСризации ΡΡ‚Ρ€Π΅ΠΌΠΈΡ‚Π΅ΡΡŒ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Π΄Π²Π΅ Π²Π΅Ρ‰ΠΈ:

  • Π£Π±Π΅Π΄ΠΈΡ‚Π΅ΡΡŒ, Ρ‡Ρ‚ΠΎ всС Ρ‚ΠΎΡ‡ΠΊΠΈ Π΄Π°Π½Π½Ρ‹Ρ… Π² кластСрС максимально ΠΏΠΎΡ…ΠΎΠΆΠΈ Π΄Ρ€ΡƒΠ³ Π½Π° Π΄Ρ€ΡƒΠ³Π°.
  • Π£Π±Π΅Π΄ΠΈΡ‚Π΅ΡΡŒ, Ρ‡Ρ‚ΠΎ всС Ρ‚ΠΎΡ‡ΠΊΠΈ Π΄Π°Π½Π½Ρ‹Ρ… Π² Ρ€Π°Π·Π½Ρ‹Ρ… кластСрах максимально ΠΎΡ‚Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π°.

Алгоритмы кластСризации Π³Ρ€ΡƒΠΏΠΏΠΈΡ€ΡƒΡŽΡ‚ элСмСнты вмСстС Π½Π° основС Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠΈ сходства. Π­Ρ‚ΠΎ часто дСлаСтся ΠΏΡƒΡ‚Π΅ΠΌ нахоТдСния Β«Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Π°Β» Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… Π³Ρ€ΡƒΠΏΠΏ Π² Π½Π°Π±ΠΎΡ€Π΅ Π΄Π°Π½Π½Ρ‹Ρ…, хотя ΠΈ Π½Π΅ ΠΈΡΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ. БущСствуСт мноТСство Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² кластСризации, Π½ΠΎ Ρ†Π΅Π»ΡŒ всСх Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² кластСризации ΠΎΠ΄Π½Π° ΠΈ Ρ‚Π° ΠΆΠ΅ β€” ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π³Ρ€ΡƒΠΏΠΏΡ‹, присущиС Π½Π°Π±ΠΎΡ€Ρƒ Π΄Π°Π½Π½Ρ‹Ρ….

ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСд

ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСдних β€” ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΡΡ‚Π°Ρ€Π΅ΠΉΡˆΠΈΡ… ΠΈ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ часто ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Ρ… Ρ‚ΠΈΠΏΠΎΠ² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² кластСризации, Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰ΠΈΠΉ Π½Π° основС Π²Π΅ΠΊΡ‚ΠΎΡ€Π½ΠΎΠ΅ ΠΊΠ²Π°Π½Ρ‚ΠΎΠ²Π°Π½ΠΈΠ΅. Π’ качСствС исходной Ρ‚ΠΎΡ‡ΠΊΠΈ Π²Ρ‹Π±Ρ€Π°Π½Π° Ρ‚ΠΎΡ‡ΠΊΠ° Π² пространствС, Π° Π·Π°Ρ‚Π΅ΠΌ ΠΎΡ‚ исходной Ρ‚ΠΎΡ‡ΠΊΠΈ Ρ€ΠΈΡΡƒΡŽΡ‚ΡΡ Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ‹ ΠΊΠΎ всСм Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌ Π΄Π°Π½Π½Ρ‹Ρ… Π² Π½Π°Π±ΠΎΡ€Π΅ Π΄Π°Π½Π½Ρ‹Ρ….

Π’ Ρ†Π΅Π»ΠΎΠΌ, ΠΊΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡŽ K-срСдних ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°Π·Π±ΠΈΡ‚ΡŒ Π½Π° ΠΏΡΡ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… этапов:

  • ΠŸΠΎΠΌΠ΅ΡΡ‚ΠΈΡ‚Π΅ всС экзСмпляры Π² подмноТСства, Π³Π΄Π΅ количСство подмноТСств Ρ€Π°Π²Π½ΠΎ K.
  • НайдитС ΡΡ€Π΅Π΄Π½ΡŽΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ/Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‡Ρ‚ΠΎ созданных Ρ€Π°Π·Π΄Π΅Π»ΠΎΠ² кластСра.
  • На основС этих Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ΠΎΠ² Π½Π°Π·Π½Π°Ρ‡ΡŒΡ‚Π΅ ΠΊΠ°ΠΆΠ΄ΡƒΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΌΡƒ кластСру.
  • ВычислитС расстояния ΠΎΡ‚ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΈ Π΄ΠΎ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ΠΎΠ² ΠΈ Π½Π°Π·Π½Π°Ρ‡ΡŒΡ‚Π΅ Ρ‚ΠΎΡ‡ΠΊΠΈ кластСрам, Π³Π΄Π΅ расстояниС ΠΎΡ‚ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Π° минимально.
  • ПослС Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Ρ‚ΠΎΡ‡ΠΊΠΈ Π±Ρ‹Π»ΠΈ Π½Π°Π·Π½Π°Ρ‡Π΅Π½Ρ‹ кластСрам, Π½Π°ΠΉΠ΄ΠΈΡ‚Π΅ Π½ΠΎΠ²Ρ‹ΠΉ Ρ†Π΅Π½Ρ‚Ρ€ тяТСсти кластСров.

Π’Ρ‹ΡˆΠ΅ΡƒΠΊΠ°Π·Π°Π½Π½Ρ‹Π΅ шаги ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡŽΡ‚ΡΡ Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° процСсс обучСния Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½.

На Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΌ этапС Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Ρ‹ Ρ€Π°Π·ΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ Π³Π΄Π΅-Ρ‚ΠΎ срСди Ρ‚ΠΎΡ‡Π΅ΠΊ Π΄Π°Π½Π½Ρ‹Ρ….
Π€ΠΎΡ‚ΠΎ: Weston.pace Ρ‡Π΅Ρ€Π΅Π· wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Π’ качСствС Π°Π»ΡŒΡ‚Π΅Ρ€Π½Π°Ρ‚ΠΈΠ²Ρ‹, послС Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Ρ‹ Π±Ρ‹Π»ΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ‰Π΅Π½Ρ‹, ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ сСбС ΠΊΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡŽ K-срСдних ΠΊΠ°ΠΊ ΠΏΠ΅Ρ€Π΅ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρƒ двумя Ρ€Π°Π·Π½Ρ‹ΠΌΠΈ Ρ„Π°Π·Π°ΠΌΠΈ: ΠΌΠ°Ρ€ΠΊΠΈΡ€ΠΎΠ²ΠΊΠ° Ρ‚ΠΎΡ‡Π΅ΠΊ Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ ΠΎΠ±Π½ΠΎΠ²Π»Π΅Π½ΠΈΠ΅ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ΠΎΠ².

На Π²Ρ‚ΠΎΡ€ΠΎΠΌ этапС ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠ° расстояния, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²ΠΎ расстояниС, для вычислСния блиТайшСго ΠΊ Π·Π°Π΄Π°Π½Π½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Π°, послС Ρ‡Π΅Π³ΠΎ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌ присваиваСтся класс этого Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Π°. Π€ΠΎΡ‚ΠΎ: Weston.pace Ρ‡Π΅Ρ€Π΅Π· Wikimedia Commons, лицСнзия GNU Free Doc (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

На этапС ΠΌΠ°Ρ€ΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ Ρ‚ΠΎΡ‡Π΅ΠΊ Π΄Π°Π½Π½Ρ‹Ρ… ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ… присваиваСтся ΠΌΠ΅Ρ‚ΠΊΠ°, которая ΠΏΠΎΠΌΠ΅Ρ‰Π°Π΅Ρ‚ Π΅Π΅ Π² кластСр, ΠΏΡ€ΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ°Ρ‰ΠΈΠΉ Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠ΅ΠΌΡƒ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Ρƒ. Π‘Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΠΉ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ опрСдСляСтся с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π²ΠΎΠ·Π²Π΅Π΄Π΅Π½Π½ΠΎΠ³ΠΎ Π² ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²Π° расстояния, хотя ΠΌΠΎΠ³ΡƒΡ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠΈ расстояния, Ρ‚Π°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ манхэттСнскоС расстояниС, косинусноС расстояниС ΠΈ расстояниС Π–Π°ΠΊΠΊΠ°Ρ€Π°, Π² зависимости ΠΎΡ‚ Ρ‚ΠΈΠΏΠ° Π΄Π°Π½Π½Ρ‹Ρ…, ΠΏΠΎΠ΄Π°Π²Π°Π΅ΠΌΡ‹Ρ… Π² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ кластСризации.

На Ρ‚Ρ€Π΅Ρ‚ΡŒΠ΅ΠΌ этапС Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Ρ‹ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ Π² срСднСС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ всСх Ρ‚ΠΎΡ‡Π΅ΠΊ Π΄Π°Π½Π½Ρ‹Ρ…. Π—Π°Ρ‚Π΅ΠΌ классы ΠΏΠ΅Ρ€Π΅Ρ€Π°ΡΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ΡΡ. Π€ΠΎΡ‚ΠΎ: Weston.pace Ρ‡Π΅Ρ€Π΅Π· Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

На этапС обновлСния Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄Π° Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ вычисляСтся ΠΏΡƒΡ‚Π΅ΠΌ нахоТдСния срСднСго расстояния ΠΌΠ΅ΠΆΠ΄Ρƒ всСми Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ Π΄Π°Π½Π½Ρ‹Ρ…, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π² настоящСС врСмя содСрТатся Π² кластСрС.

Как Π²Ρ‹Π±Ρ€Π°Ρ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ для «К»

Учитывая, Ρ‡Ρ‚ΠΎ кластСризация K-срСдних β€” это Π½Π΅ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΠΈΡ€ΡƒΠ΅ΠΌΡ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, Π° количСство классов Π·Π°Ρ€Π°Π½Π΅Π΅ нСизвСстно, ΠΊΠ°ΠΊ Π²Ρ‹Π±Ρ€Π°Ρ‚ΡŒ подходящСС количСство классов/ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ для K?

Один ΠΈΠ· ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² Π²Ρ‹Π±ΠΎΡ€Π° ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ³ΠΎ значСния K называСтся Β«Ρ‚Π΅Ρ…Π½ΠΈΠΊΠ° локтя». ΠœΠ΅Ρ‚ΠΎΠ΄ локтя состоит ΠΈΠ· запуска Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° кластСризации K-срСдних для Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π° Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ K ΠΈ использования ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠΈ точности, ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ суммы ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΎΠ² ошибок, для опрСдСлСния Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊΠΈΠ΅ значСния K Π΄Π°ΡŽΡ‚ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠΈΠ΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹. Π‘ΡƒΠΌΠΌΠ° ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΎΠ² ошибок опрСдСляСтся ΠΏΡƒΡ‚Π΅ΠΌ вычислСния срСднСго расстояния ΠΌΠ΅ΠΆΠ΄Ρƒ Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΌ тяТСсти кластСра ΠΈ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ Π΄Π°Π½Π½Ρ‹Ρ… Π² этом кластСрС.

Π’Π΅Ρ€ΠΌΠΈΠ½ Β«ΠΌΠ΅Ρ‚ΠΎΠ΄ локтя» происходит ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ Ρ„Π°ΠΊΡ‚Π°, Ρ‡Ρ‚ΠΎ ΠΊΠΎΠ³Π΄Π° Π²Ρ‹ строитС SSE ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ K, Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚ΠΈΡ€ΡƒΡŽΡ‰ΠΈΠΉ Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ Π³Ρ€Π°Ρ„ΠΈΠΊ часто Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ «локтя», Π³Π΄Π΅ SSE быстро ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅Ρ‚ΡΡ для ΠΏΠ΅Ρ€Π²Ρ‹Ρ… Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ K, Π½ΠΎ ΠΏΠΎΡ‚ΠΎΠΌ выравниваСтся. Π’ Ρ‚Π°ΠΊΠΈΡ… условиях Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ К, располоТСнноС Π½Π° ΠΈΠ·Π³ΠΈΠ±Π΅, являСтся Π»ΡƒΡ‡ΡˆΠΈΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ К, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ послС этого значСния происходит быстроС ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½ΠΈΠ΅ ΠΎΡ‚Π΄Π°Ρ‡ΠΈ.

Мини-пакСтная кластСризация K-срСдних

По ΠΌΠ΅Ρ€Π΅ Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Π½Π°Π±ΠΎΡ€Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ… становятся большС, врСмя вычислСний Ρ‚Π°ΠΊΠΆΠ΅ увСличиваСтся. Базовая кластСризация K-срСдних ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π°Π½ΡΡ‚ΡŒ ΠΌΠ½ΠΎΠ³ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с массивными Π½Π°Π±ΠΎΡ€Π°ΠΌΠΈ Π΄Π°Π½Π½Ρ‹Ρ…, ΠΈ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ Π±Ρ‹Π»ΠΈ внСсСны измСнСния Π² ΠΊΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡŽ K-срСдних, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡƒΠΌΠ΅Π½ΡŒΡˆΠΈΡ‚ΡŒ пространствСнныС ΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Π·Π°Ρ‚Ρ€Π°Ρ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°.

Мини-пакСтная кластСризация K-срСдних являСтся Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ кластСризации K-срСдних Π³Π΄Π΅ Ρ€Π°Π·ΠΌΠ΅Ρ€ рассматриваСмого Π½Π°Π±ΠΎΡ€Π° Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½. ΠžΠ±Ρ‹Ρ‡Π½Π°Ρ кластСризация K-срСдних Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ сразу со всСм Π½Π°Π±ΠΎΡ€ΠΎΠΌ Π΄Π°Π½Π½Ρ‹Ρ…/ΠΏΠ°ΠΊΠ΅Ρ‚ΠΎΠΌ, Π² Ρ‚ΠΎ врСмя ΠΊΠ°ΠΊ ΠΌΠΈΠ½ΠΈ-пакСтная кластСризация K-срСдних Ρ€Π°Π·Π±ΠΈΠ²Π°Π΅Ρ‚ Π½Π°Π±ΠΎΡ€ Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° подмноТСства. Мини-ΠΏΠ°Ρ€Ρ‚ΠΈΠΈ случайным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ΡΡ ΠΈΠ· всСго Π½Π°Π±ΠΎΡ€Π° Π΄Π°Π½Π½Ρ‹Ρ…, ΠΈ для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π½ΠΎΠ²ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ выбираСтся новая случайная Π²Ρ‹Π±ΠΎΡ€ΠΊΠ°, которая ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для обновлСния полоТСния Ρ†Π΅Π½Ρ‚Ρ€ΠΎΠΈΠ΄ΠΎΠ².

Π’ ΠΌΠΈΠ½ΠΈ-ΠΏΠ°ΠΊΠ΅Ρ‚Π½ΠΎΠΉ кластСризации K-срСдних кластСры ΠΎΠ±Π½ΠΎΠ²Π»ΡΡŽΡ‚ΡΡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΌΠΈΠ½ΠΈ-ΠΏΠ°ΠΊΠ΅Ρ‚Π° ΠΈ скорости обучСния. Π‘ΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ обучСния ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅Ρ‚ΡΡ ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΉ, ΠΈ ΠΎΠ½Π° ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Π° количСству Ρ‚ΠΎΡ‡Π΅ΠΊ Π΄Π°Π½Π½Ρ‹Ρ…, ΠΏΠΎΠΌΠ΅Ρ‰Π΅Π½Π½Ρ‹Ρ… Π² ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹ΠΉ кластСр. Π­Ρ„Ρ„Π΅ΠΊΡ‚ сниТСния скорости обучСния Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ сниТаСтся влияниС Π½ΠΎΠ²Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ достигаСтся ΡΡ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒ, ΠΊΠΎΠ³Π΄Π° послС Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΉ Π² кластСрах Π½Π΅Ρ‚ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ.

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ исслСдований эффСктивности ΠΌΠΈΠ½ΠΈ-ΠΏΠ°ΠΊΠ΅Ρ‚Π½ΠΎΠΉ кластСризации K-срСдних ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‚, Ρ‡Ρ‚ΠΎ ΠΎΠ½Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΡƒΡΠΏΠ΅ΡˆΠ½ΠΎ ΡΠΎΠΊΡ€Π°Ρ‚ΠΈΡ‚ΡŒ врСмя вычислСний с нСбольшим компромиссом Π² качСствС кластСра.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ кластСризации K-срСдних

ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡŽ K-срСдних ΠΌΠΎΠΆΠ½ΠΎ бСзопасно ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π² любой ситуации, ΠΊΠΎΠ³Π΄Π° Ρ‚ΠΎΡ‡ΠΊΠΈ Π΄Π°Π½Π½Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΅Π³ΠΌΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π½Π° ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹Π΅ Π³Ρ€ΡƒΠΏΠΏΡ‹/классы. Π’ΠΎΡ‚ нСсколько ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ² распространСнных Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² использования кластСризации K-mean.

ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСдних ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒΡΡ для классификации Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ², Π³Ρ€ΡƒΠΏΠΏΠΈΡ€ΠΎΠ²ΠΊΠΈ Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² Π½Π° основС Ρ‚Π°ΠΊΠΈΡ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, ΠΊΠ°ΠΊ Ρ‚Π΅ΠΌΡ‹, Ρ‚Π΅Π³ΠΈ, использованиС слов, ΠΌΠ΅Ρ‚Π°Π΄Π°Π½Π½Ρ‹Π΅ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π°. Π•Π³ΠΎ Ρ‚Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ для классификации ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»Π΅ΠΉ ΠΊΠ°ΠΊ Π±ΠΎΡ‚ΠΎΠ² ΠΈΠ»ΠΈ Π½Π΅ Π±ΠΎΡ‚ΠΎΠ² Π½Π° основС ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ активности, Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ сообщСния ΠΈ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΈ. ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСдних Ρ‚Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ для раздСлСния людСй Π½Π° Π³Ρ€ΡƒΠΏΠΏΡ‹ Π² зависимости ΠΎΡ‚ уровня бСспокойства ΠΏΡ€ΠΈ наблюдСнии Π·Π° ΠΈΡ… Π·Π΄ΠΎΡ€ΠΎΠ²ΡŒΠ΅ΠΌ, Π½Π° основС Ρ‚Π°ΠΊΠΈΡ… характСристик, ΠΊΠ°ΠΊ ΡΠΎΠΏΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ заболСвания, возраст, история Π±ΠΎΠ»Π΅Π·Π½ΠΈ ΠΈ Ρ‚. Π΄.

ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСдних Ρ‚Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ для Π±ΠΎΠ»Π΅Π΅ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡, Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ созданиС систСм Ρ€Π΅ΠΊΠΎΠΌΠ΅Π½Π΄Π°Ρ†ΠΈΠΉ. ΠŸΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»ΠΈ Ρ‚Π°ΠΊΠΎΠΉ систСмы, ΠΊΠ°ΠΊ Netflix, ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ сгруппированы Π½Π° основС шаблонов просмотра ΠΈ Ρ€Π΅ΠΊΠΎΠΌΠ΅Π½Π΄ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ΠΏΠΎΡ…ΠΎΠΆΠ΅Π³ΠΎ ΠΊΠΎΠ½Ρ‚Π΅Π½Ρ‚Π°. ΠšΠ»Π°ΡΡ‚Π΅Ρ€ΠΈΠ·Π°Ρ†ΠΈΡ K-срСдних ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ для Π·Π°Π΄Π°Ρ‡ обнаруТСния Π°Π½ΠΎΠΌΠ°Π»ΠΈΠΉ, выдСляя ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Π΅ случаи ΠΌΠΎΡˆΠ΅Π½Π½ΠΈΡ‡Π΅ΡΡ‚Π²Π° ΠΈΠ»ΠΈ Π΄Π΅Ρ„Π΅ΠΊΡ‚Π½Ρ‹Π΅ элСмСнты.

Π‘Π»ΠΎΠ³Π΅Ρ€ ΠΈ программист со спСциализациСй Π² МашинноС ΠΎΠ±ΡƒΡ‡Π΅Π½ΠΈΠ΅ ΠΈ Π“Π»ΡƒΠ±ΠΎΠΊΠΎΠ΅ ΠΎΠ±ΡƒΡ‡Π΅Π½ΠΈΠ΅ Ρ‚Π΅ΠΌΡ‹. ДэниСл надССтся ΠΏΠΎΠΌΠΎΡ‡ΡŒ Π΄Ρ€ΡƒΠ³ΠΈΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ возмоТности ИИ Π½Π° Π±Π»Π°Π³ΠΎ общСства.