πŸ€– ΠœΠ΅Ρ‚ΠΎΠ΄ k-Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй (k-nearest neighbour)

ΠœΠ΅Ρ‚ΠΎΠ΄ k-Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй (k Nearest Neighbors, ΠΈΠ»ΠΈ kNN) – популярный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ классификации, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Π² Ρ€Π°Π·Π½Ρ‹Ρ… Ρ‚ΠΈΠΏΠ°Ρ… Π·Π°Π΄Π°Ρ‡ машинного обучСния. НаравнС с Π΄Π΅Ρ€Π΅Π²ΠΎΠΌ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΉ это ΠΎΠ΄ΠΈΠ½ ΠΈΠ· самых понятных ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ² ΠΊ классификации.

Π§Ρ‚ΠΎ это Ρ‚Π°ΠΊΠΎΠ΅?
На ΠΈΠ½Ρ‚ΡƒΠΈΡ‚ΠΈΠ²Π½ΠΎΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ ΡΡƒΡ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° проста: посмотри Π½Π° сосСдСй Π²ΠΎΠΊΡ€ΡƒΠ³, ΠΊΠ°ΠΊΠΈΠ΅ ΠΈΠ· Π½ΠΈΡ… ΠΏΡ€Π΅ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‚, Ρ‚Π°ΠΊΠΎΠ²Ρ‹ΠΌ Ρ‚Ρ‹ ΠΈ являСшься. Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎ основой ΠΌΠ΅Ρ‚ΠΎΠ΄Π° являСтся Π³ΠΈΠΏΠΎΡ‚Π΅Π·Π° компактности: Ссли ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠ° расстояния ΠΌΠ΅ΠΆΠ΄Ρƒ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ Π²Π²Π΅Π΄Π΅Π½Π° ΡƒΠ΄Π°Ρ‡Π½ΠΎ, Ρ‚ΠΎ схоТиС ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ Π³ΠΎΡ€Π°Π·Π΄ΠΎ Ρ‡Π°Ρ‰Π΅ Π»Π΅ΠΆΠ°Ρ‚ Π² ΠΎΠ΄Π½ΠΎΠΌ классС, Ρ‡Π΅ΠΌ Π² Ρ€Π°Π·Π½Ρ‹Ρ….
  • Π’ случаС использования ΠΌΠ΅Ρ‚ΠΎΠ΄Π° для классификации ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ присваиваСтся Ρ‚ΠΎΠΌΡƒ классу, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ являСтся Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ распространённым срСди k сосСдСй Π΄Π°Π½Π½ΠΎΠ³ΠΎ элСмСнта, классы ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΡƒΠΆΠ΅ извСстны.
  • Π’ случаС использования ΠΌΠ΅Ρ‚ΠΎΠ΄Π° для рСгрСссии, ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρƒ присваиваСтся срСднСС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΏΠΎ k блиТайшим ΠΊ Π½Π΅ΠΌΡƒ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π°ΠΌ, значСния ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΡƒΠΆΠ΅ извСстны.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ классификации k-Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй.

  • Π£ нас Π΅ΡΡ‚ΡŒ тСстовый ΠΎΠ±Ρ€Π°Π·Π΅Ρ† Π² Π²ΠΈΠ΄Π΅ Π·Π΅Π»Π΅Π½ΠΎΠ³ΠΎ ΠΊΡ€ΡƒΠ³Π°. Π‘ΠΈΠ½ΠΈΠ΅ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Ρ‹ ΠΌΡ‹ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΠΌ ΠΊΠ°ΠΊ класс 1, красныС Ρ‚Ρ€Π΅ΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠΈ – класс 2.
  • Π—Π΅Π»Π΅Π½Ρ‹ΠΉ ΠΊΡ€ΡƒΠ³ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ классифицирован ΠΊΠ°ΠΊ класс 1 ΠΈΠ»ΠΈ класс 2. Если рассматриваСмая Π½Π°ΠΌΠΈ ΠΎΠ±Π»Π°ΡΡ‚ΡŒ являСтся ΠΌΠ°Π»Ρ‹ΠΌ ΠΊΡ€ΡƒΠ³ΠΎΠΌ, Ρ‚ΠΎ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ классифицируСтся ΠΊΠ°ΠΊ 2-ΠΉ класс, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ Π²Π½ΡƒΡ‚Ρ€ΠΈ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΊΡ€ΡƒΠ³Π° 2 Ρ‚Ρ€Π΅ΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠ° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ 1 ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚.
  • Если ΠΌΡ‹ рассматриваСм большой ΠΊΡ€ΡƒΠ³ (с ΠΏΡƒΠ½ΠΊΡ‚ΠΈΡ€ΠΎΠΌ), Ρ‚ΠΎ ΠΊΡ€ΡƒΠ³ Π±ΡƒΠ΄Π΅Ρ‚ классифицирован ΠΊΠ°ΠΊ 1-ΠΉ класс, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π²Π½ΡƒΡ‚Ρ€ΠΈ ΠΊΡ€ΡƒΠ³Π° 3 ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π° Π² противовСс 2 Ρ‚Ρ€Π΅ΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠ°ΠΌ.

ВСорСтичСская ΡΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π°Ρ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° k-NN

Помимо простого объяснСния, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅ основных матСматичСских ΡΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‰ΠΈΡ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° k-Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй.

  • Π•Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²Π° ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠ° (Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²ΠΎ расстояниС, ΠΈΠ»ΠΈ ΠΆΠ΅ Euclidean distance) – ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠ° Π² Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²ΠΎΠΌ пространствС, расстояниС ΠΌΠ΅ΠΆΠ΄Ρƒ двумя Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²Π° пространства, вычисляСмоС ΠΏΠΎ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ΅ ΠŸΠΈΡ„Π°Π³ΠΎΡ€Π°. ΠŸΡ€ΠΎΡ‰Π΅ говоря, это наимСньшСС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ΅ расстояниС ΠΌΠ΅ΠΆΠ΄Ρƒ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ A ΠΈ B. Π₯отя Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²ΠΎ расстояниС ΠΏΠΎΠ»Π΅Π·Π½ΠΎ для ΠΌΠ°Π»Ρ‹Ρ… ΠΈΠ·ΠΌΠ΅Ρ€Π΅Π½ΠΈΠΉ, ΠΎΠ½ΠΎ Π½Π΅ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ для Π±ΠΎΠ»ΡŒΡˆΠΈΡ… ΠΈΠ·ΠΌΠ΅Ρ€Π΅Π½ΠΈΠΉ ΠΈ для ΠΊΠ°Ρ‚Π΅Π³ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. НСдостатком Π΅Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²Π° расстояния являСтся Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΎ ΠΈΠ³Π½ΠΎΡ€ΠΈΡ€ΡƒΠ΅Ρ‚ сходство ΠΌΠ΅ΠΆΠ΄Ρƒ Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Π°ΠΌΠΈ. ΠšΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΈΠ· Π½ΠΈΡ… рассматриваСтся ΠΊΠ°ΠΊ ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ ΠΎΡ‚Π»ΠΈΡ‡Π½Ρ‹ΠΉ ΠΎΡ‚ всСх ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Ρ….

Π€ΠΎΡ€ΠΌΡƒΠ»Π° вычислСния Π•Π²ΠΊΠ»ΠΈΠ΄ΠΎΠ²Π° расстояния:

d(p,q)=βˆ‘i=1n(qiβˆ’pi)2
  • Π”Ρ€ΡƒΠ³ΠΎΠΉ Π²Π°ΠΆΠ½ΠΎΠΉ ΡΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π΅ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° являСтся нормализация. Π Π°Π·Π½Ρ‹Π΅ Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Ρ‹ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‚ Ρ€Π°Π·Π½Ρ‹ΠΌ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½ΠΎΠΌ прСдставлСнных Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Π² Π²Ρ‹Π±ΠΎΡ€ΠΊΠ΅. К ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρƒ, Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ А прСдставлСн Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ ΠΎΡ‚ 0.01 Π΄ΠΎ 0.05, Π° Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ Π‘ прСдставлСн Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ ΠΎΡ‚ 500 Π΄ΠΎ 1000). Π’ Ρ‚Π°ΠΊΠΎΠΌ случаС значСния дистанции ΠΌΠΎΠ³ΡƒΡ‚ сильно Π·Π°Π²ΠΈΡΠ΅Ρ‚ΡŒ ΠΎΡ‚ Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΎΠ² с бо́льшими Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π°ΠΌΠΈ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π΄Π°Π½Π½Ρ‹Π΅ Π² Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π΅ случаСв проходят Ρ‡Π΅Ρ€Π΅Π· Π½ΠΎΡ€ΠΌΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΡŽ. ΠŸΡ€ΠΈ кластСрном Π°Π½Π°Π»ΠΈΠ·Π΅ Π΅ΡΡ‚ΡŒ Π΄Π²Π° основных способа Π½ΠΎΡ€ΠΌΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Π΄Π°Π½Π½Ρ‹Ρ…: MinMax-нормализация ΠΈ Z-нормализация.

MinMax-нормализация осущСствляСтся ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

xβ€²=(xβˆ’min[X])/(max[X]βˆ’min[X])

Π² Π΄Π°Π½Π½ΠΎΠΌ случаС всС значСния Π±ΡƒΠ΄ΡƒΡ‚ Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ ΠΎΡ‚ 0 Π΄ΠΎ 1; дискрСтныС Π±ΠΈΠ½Π°Ρ€Π½Ρ‹Π΅ значСния ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ΡΡ ΠΊΠ°ΠΊ 0 ΠΈ 1.

Z-нормализация:

xβ€²=(xβˆ’M[X])/Οƒ[X]

Π³Π΄Π΅ Οƒ – срСднСквадратичноС ΠΎΡ‚ΠΊΠ»ΠΎΠ½Π΅Π½ΠΈΠ΅. Π’ Π΄Π°Π½Π½ΠΎΠΌ случаС Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠΎΠΏΠ°Π΄Π°Π΅Ρ‚ Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½.

Каков порядок дСйствий?

  • Π—Π°Π³Ρ€ΡƒΠ·ΠΈΡ‚Π΅ ваши Π΄Π°Π½Π½Ρ‹Π΅.
  • Π˜Π½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·ΠΈΡ€ΡƒΠΉΡ‚Π΅ k ΠΏΡƒΡ‚Π΅ΠΌ Π²Ρ‹Π±ΠΎΡ€Π° ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ числа сосСдСй.
  • Для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΎΠ±Ρ€Π°Π·Ρ†Π° Π² Π΄Π°Π½Π½Ρ‹Ρ…:
  1. ВычислитС расстояниС ΠΌΠ΅ΠΆΠ΄Ρƒ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ запроса ΠΈ Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ ΠΈΠ· Π΄Π°Π½Π½Ρ‹Ρ….
  2. Π”ΠΎΠ±Π°Π²ΡŒΡ‚Π΅ индСкс ΠΎΠ±Ρ€Π°Π·Ρ†Π° Π² ΡƒΠΏΠΎΡ€ΡΠ΄ΠΎΡ‡Π΅Π½Π½ΡƒΡŽ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΡŽ, ΠΊΠ°ΠΊ ΠΈ Π΅Π³ΠΎ расстояниС.
  • ΠžΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΡƒΠΉΡ‚Π΅ ΡƒΠΏΠΎΡ€ΡΠ΄ΠΎΡ‡Π΅Π½Π½ΡƒΡŽ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΡŽ расстояний ΠΈ индСксов ΠΎΡ‚ наимСньшСго Π΄ΠΎ наибольшСго, Π² порядкС возрастания.
  • Π’Ρ‹Π±Π΅Ρ€ΠΈΡ‚Π΅ ΠΏΠ΅Ρ€Π²Ρ‹Π΅ k записСй ΠΈΠ· отсортированной ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ.
  • Π’ΠΎΠ·ΡŒΠΌΠΈΡ‚Π΅ ΠΌΠ΅Ρ‚ΠΊΠΈ Π²Ρ‹Π±Ρ€Π°Π½Π½Ρ‹Ρ… k записСй.
  • Если Ρƒ вас Π·Π°Π΄Π°Ρ‡Π° рСгрСссии, Π²Π΅Ρ€Π½ΠΈΡ‚Π΅ срСднСС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²Ρ‹Π±Ρ€Π°Π½Π½Ρ‹Ρ… Ρ€Π°Π½Π΅Π΅ k ΠΌΠ΅Ρ‚ΠΎΠΊ.
  • Если Ρƒ вас Π·Π°Π΄Π°Ρ‡Π° классификации, Π²Π΅Ρ€Π½ΠΈΡ‚Π΅ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ часто Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰Π΅Π΅ΡΡ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²Ρ‹Π±Ρ€Π°Π½Π½Ρ‹Ρ… Ρ€Π°Π½Π΅Π΅ ΠΌΠ΅Ρ‚ΠΎΠΊ k.

РСализация Π½Π° языкС Python

Для дСмонстрации ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ самоС распространСнноС ΡΠΎΡ€Π΅Π²Π½ΠΎΠ²Π°Π½ΠΈΡŽ-пСсочницу Π½Π° Kaggle: Titanic. Π”Π°Π½Π½Ρ‹Π΅ Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ Π½Π°ΠΉΡ‚ΠΈ здСсь. ΠœΡ‹ стрСмимся ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ python-Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΡƒ для машинного обучСния scikit-learn. ΠœΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ Π½Π°Π±ΠΎΡ€ Π΄Π°Π½Π½Ρ‹Ρ… Β«Π’ΠΈΡ‚Π°Π½ΠΈΠΊΒ» для логистичСской рСгрСссии.

Набор Π΄Π°Π½Π½Ρ‹Ρ… состоит ΠΈΠ· 15 столбцов, Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ sex (ΠΏΠΎΠ»), fare (ΠΏΠ»Π°Ρ‚Π° Π·Π° ΠΏΡ€ΠΎΠ΅Π·Π΄), p_class (класс ΠΊΠ°ΡŽΡ‚Ρ‹), family_size (Ρ€Π°Π·ΠΌΠ΅Ρ€ сСмьи), ΠΈ Ρ‚. Π΄. Π“Π»Π°Π²Π½Ρ‹ΠΌ ΠΏΡ€ΠΈΠ·Π½Π°ΠΊΠΎΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΡ‹ ΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ‹ ΠΏΡ€Π΅Π΄ΡΠΊΠ°Π·Π°Ρ‚ΡŒ Π² сорСвновании, являСтся survived (Π²Ρ‹ΠΆΠΈΠ» пассаТир ΠΈΠ»ΠΈ Π½Π΅Ρ‚).

Π”ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π°Π½Π°Π»ΠΈΠ· ΠΏΠΎΠΊΠ°Π·Π°Π», Ρ‡Ρ‚ΠΎ находящиСся Π² Π±Ρ€Π°ΠΊΠ΅ люди ΠΈΠΌΠ΅ΡŽΡ‚ больший шанс Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π±Ρ‹Ρ‚ΡŒ спасСнными с корабля. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π±Ρ‹Π»ΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½Ρ‹ Π΅Ρ‰Π΅ 4 столбца, ΠΏΠ΅Ρ€Π΅ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½Π½Ρ‹Π΅ ΠΈΠ· Name (Имя), ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ ΠΌΡƒΠΆΡ‡ΠΈΠ½ ΠΈ ΠΆΠ΅Π½Ρ‰ΠΈΠ½ Π² зависимости ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, Π±Ρ‹Π»ΠΈ ΠΎΠ½ΠΈ ΠΆΠ΅Π½Π°Ρ‚Ρ‹ ΠΈΠ»ΠΈ Π½Π΅Ρ‚ (Mr, Mrs, Mister, Miss).

ΠŸΠΎΠ»Π½Ρ‹ΠΉ Π½Π°Π±ΠΎΡ€ Π΄Π°Π½Π½Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ Π·Π°Π³Ρ€ΡƒΠ·ΠΈΡ‚ΡŒ ΠΎΡ‚ΡΡŽΠ΄Π°, Π° ΠΏΠΎΠ»Π½Ρ‹ΠΉ ΠΊΠΎΠ΄ для этой ΡΡ‚Π°Ρ‚ΡŒΠΈ Π²Ρ‹ Π½Π°ΠΉΠ΄Π΅Ρ‚Π΅ здСсь.

Π§Ρ‚ΠΎΠ±Ρ‹ наглядно ΠΏΡ€ΠΎΠ΄Π΅ΠΌΠΎΠ½ΡΡ‚Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ k-NN для прСдсказания выТивания пассаТира, ΠΌΡ‹ рассматриваСм Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π΄Π²Π° ΠΏΡ€ΠΈΠ·Π½Π°ΠΊΠ°: age (возраст), fare (ΠΏΠ»Π°Ρ‚Π° Π·Π° ΠΏΡ€ΠΎΠ΅Π·Π΄).

# Π—Π°Π³Ρ€ΡƒΠΆΠ°Π΅ΠΌ Π΄Π°Π½Π½Ρ‹Π΅
train_df = pd.read_csv('/kaggle/input/titanic/train_data.csv') 
# ИзбавляСмся ΠΎΡ‚ Π΄Π²ΡƒΡ… столбцов Π±Π΅Π· Π½ΡƒΠΆΠ½ΠΎΠΉ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ
train_df = train_df.drop(columns=['Unnamed: 0', 'PassengerId']) 
from sklearn.neighbors import KNeighborsClassifier 
predictors = ['Age', 'Fare'] 
outcome = 'Survived' 

new_record = train_df.loc[0:0, predictors] 
X = train_df.loc[1:, predictors] 
y = train_df.loc[1:, outcome] 

kNN = KNeighborsClassifier(n_neighbors=20) 
kNN.fit(X, y) 
kNN.predict(new_record)
print(kNN.predict_proba(new_record)) 

#[Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚/Π²Ρ‹Π²ΠΎΠ΄]: [[0.7 0.3]]

Π—Π΄Π΅ΡΡŒ Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ выТивания составляСт 0.3 – 30%.

Π”Π°Π»Π΅Π΅ ΠΌΡ‹ настраиваСм Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ k-NN Π½Π° поиск ΠΈ использованиС 20 Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ состояниС пассаТира. Для наглядности Π²Ρ‹Π²ΠΎΠ΄ΠΈΠΌ 20 ΠΏΠ΅Ρ€Π²Ρ‹Ρ… сосСдСй Π½ΠΎΠ²ΠΎΠΉ записи с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΈΠΌΠΏΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° kneighbors. РСализация выглядит ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

nbrs = knn.kneighbors(new_record)
maxDistance = np.max(nbrs[0][0])

fig, ax = plt.subplots(figsize=(10, 8))
sns.scatterplot(x = 'Age', y = 'Fare', style = 'Survived', 
                hue='Survived', data=train_df, alpha=0.3, ax=ax)
sns.scatterplot(x = 'Age', y = 'Fare', style = 'Survived', 
                hue = 'Survived', 
                data = pd.concat([train_df.loc[0:0, :], train_df.loc[nbrs[1][0] + 1,:]]), 
                ax = ax, legend=False)
ellipse = Ellipse(xy = new_record.values[0], 
                  width = 2 * maxDistance, height = 2 * maxDistance,
                  edgecolor = 'black', fc = 'None', lw = 1)
ax.add_patch(ellipse)
ax.set_xlim(.25, .29)
ax.set_ylim(0, .03)

plt.tight_layout()
plt.show()

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΊΠΎΠ΄Π°:

Как Π²ΠΈΠ΄ΠΈΡ‚Π΅, Π½Π° Π³Ρ€Π°Ρ„ΠΈΠΊΠ΅ ΠΏΠΎΠΊΠ°Π·Π°Π½Ρ‹ 20 Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй, 14 ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… связаны с Ρ‚Π΅ΠΌΠΈ, ΠΊΡ‚ΠΎ Π½Π΅ Π²Ρ‹ΠΆΠΈΠ» (Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ 0,7 – 70%), Π° 6 связаны с Π²Ρ‹ΠΆΠΈΠ²ΡˆΠΈΠΌΠΈ (Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ 0,3 – 30%).

ΠœΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΏΡ€ΠΎΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΏΠ΅Ρ€Π²Ρ‹Π΅ 20 Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй для Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ ΠΊΠΎΠ΄Π°:

nbrs = knn.kneighbors(new_record)
nbr_df = pd.DataFrame({'Age': X.iloc[nbrs[1][0], 0], 
                         'Fare': X.iloc[nbrs[1][0], 1],
                         'Survived': y.iloc[nbrs[1][0]]})
nbr_df

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠΌ Π±ΡƒΠ΄Π΅Ρ‚ Ρ‚Π°ΠΊΠΈΠΌ:

Π’Ρ‹Π±ΠΎΡ€ ΠžΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ значСния для k-NN

НС сущСствуСт ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠ³ΠΎ способа ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ для k, поэтому Π½Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΏΠΎΠΏΡ€ΠΎΠ±ΠΎΠ²Π°Ρ‚ΡŒ нСсколько Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ Π»ΡƒΡ‡ΡˆΠ΅Π΅ ΠΈΠ· Π½ΠΈΡ…. Но Ρ‡Π°Ρ‰Π΅ всСго Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΏΡ€Π΅Π΄ΠΏΠΎΡ‡Ρ‚ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ для k являСтся 5:

  • НизкоС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ k, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, 1 ΠΈΠ»ΠΈ 2, ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ эффСкту нСдообучСния ΠΌΠΎΠ΄Π΅Π»ΠΈ.
  • ВысокоС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ k Π½Π° ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ взгляд выглядит ΠΏΡ€ΠΈΠ΅ΠΌΠ»Π΅ΠΌΠΎ, ΠΎΠ΄Π½Π°ΠΊΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹ трудности с ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΌΠΎΠ΄Π΅Π»ΠΈ, Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΏΠΎΠ²Ρ‹ΡˆΠ°Π΅Ρ‚ΡΡ риск пСрСобучСния.

ΠŸΡ€Π΅ΠΈΠΌΡƒΡ‰Π΅ΡΡ‚Π²Π° ΠΈ НСдостатки

ΠŸΡ€Π΅ΠΈΠΌΡƒΡ‰Π΅ΡΡ‚Π²Π°:

  • Алгоритм прост ΠΈ Π»Π΅Π³ΠΊΠΎ Ρ€Π΅Π°Π»ΠΈΠ·ΡƒΠ΅ΠΌ.
  • НС чувствитСлСн ΠΊ выбросам.
  • НСт нСобходимости ΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ модСль, Π½Π°ΡΡ‚Ρ€Π°ΠΈΠ²Π°Ρ‚ΡŒ нСсколько ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² ΠΈΠ»ΠΈ Π΄Π΅Π»Π°Ρ‚ΡŒ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ допущСния.
  • Алгоритм унивСрсалСн. Π•Π³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ для ΠΎΠ±ΠΎΠΈΡ… Ρ‚ΠΈΠΏΠΎΠ² Π·Π°Π΄Π°Ρ‡: классификации ΠΈ рСгрСссии.

НСдостатки:

  • Алгоритм Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ объСма Π²Ρ‹Π±ΠΎΡ€ΠΊΠΈ, ΠΏΡ€Π΅Π΄ΠΈΠΊΡ‚ΠΎΡ€ΠΎΠ² ΠΈΠ»ΠΈ нСзависимых ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….
  • Из Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π° Π²Ρ‹ΡˆΠ΅ ΡΠ»Π΅Π΄ΡƒΡŽΡ‚ большиС Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ Π·Π°Ρ‚Ρ€Π°Ρ‚Ρ‹ Π²ΠΎ врСмя выполнСния.
  • ВсСгда Π½ΡƒΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡ‚ΡŒ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ k.

Π’ Π·Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅

ΠœΠ΅Ρ‚ΠΎΠ΄ k-Π±Π»ΠΈΠΆΠ°ΠΉΡˆΠΈΡ… сосСдСй (k-nearest neighbors) – это простой Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ машинного обучСния с ΡƒΡ‡ΠΈΡ‚Π΅Π»Π΅ΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ классификации ΠΈ рСгрСссии. Он прост Π² Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΈ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠΈ, Π½ΠΎ ΠΈΠΌΠ΅Π΅Ρ‚ сущСствСнный нСдостаток – Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ Π·Π°ΠΌΠ΅Π΄Π»Π΅Π½ΠΈΠ΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹, ΠΊΠΎΠ³Π΄Π° объСм Π΄Π°Π½Π½Ρ‹Ρ… растСт.

Алгоритм Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ расстояния ΠΌΠ΅ΠΆΠ΄Ρƒ запросом ΠΈ всСми ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ Π² Π΄Π°Π½Π½Ρ‹Ρ…, выбирая ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ количСство ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ² (k), Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π±Π»ΠΈΠ·ΠΊΠΈΡ… ΠΊ запросу, Π·Π°Ρ‚Π΅ΠΌ голосуСт Π·Π° Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ часто Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΡƒΡŽΡΡ ΠΌΠ΅Ρ‚ΠΊΡƒ (Π² случаС Π·Π°Π΄Π°Ρ‡ΠΈ классификации) ΠΈΠ»ΠΈ усрСдняСт ΠΌΠ΅Ρ‚ΠΊΠΈ (Π² случаС Π·Π°Π΄Π°Ρ‡ΠΈ рСгрСссии).
***

Π₯ΠΎΡ‡Ρƒ ΠΎΡΠ²ΠΎΠΈΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…, Π½ΠΎ слоТно Ρ€Π°Π·ΠΎΠ±Ρ€Π°Ρ‚ΡŒΡΡ ΡΠ°ΠΌΠΎΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΠ½ΠΎ. Π§Ρ‚ΠΎ Π΄Π΅Π»Π°Ρ‚ΡŒ?

Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ нСпростая Ρ‚Π΅ΠΌΠ° для ΡΠ°ΠΌΠΎΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ изучСния: Π½Π΅ Ρƒ ΠΊΠΎΠ³ΠΎ ΡΠΏΡ€ΠΎΡΠΈΡ‚ΡŒ ΠΈ Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ ΡƒΡ‚ΠΎΡ‡Π½ΠΈΡ‚ΡŒ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΌΡ‹ запустили курс «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β», Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Π² Ρ„ΠΎΡ€ΠΌΠ°Ρ‚Π΅ Π΅ΠΆΠ΅Π½Π΅Π΄Π΅Π»ΡŒΠ½Ρ‹Ρ… Π²Π΅Π±ΠΈΠ½Π°Ρ€ΠΎΠ² Π²Ρ‹:

  • ΠΈΠ·ΡƒΡ‡ΠΈΡ‚Π΅ слСнг, Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ говорят всС Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ нСзависимо ΠΎΡ‚ языка программирования: язык Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΈ структур Π΄Π°Π½Π½Ρ‹Ρ…;
  • Π½Π°ΡƒΡ‡ΠΈΡ‚Π΅ΡΡŒ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΡ€ΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ;
  • ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΈΡ‚Π΅ΡΡŒ ΠΊ тСхничСскому собСсСдованию ΠΈ ΠΏΡ€ΠΎΠ΄Π²ΠΈΠ½ΡƒΡ‚ΠΎΠΉ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅.

ΠšΡƒΡ€Ρ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ ΠΊΠ°ΠΊ junior, Ρ‚Π°ΠΊ ΠΈ middle-Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ°ΠΌ.

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•

matyushkin
07 апрСля 2020

ВОП-15 ΠΊΠ½ΠΈΠ³ ΠΏΠΎ Python: ΠΎΡ‚ Π½ΠΎΠ²ΠΈΡ‡ΠΊΠ° Π΄ΠΎ профСссионала

Книги ΠΏΠΎ Python (ΠΈ связанным с Π½ΠΈΠΌ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹ΠΌ Ρ‚Π΅ΠΌΠ°ΠΌ) Π½Π° русском языкС. Рас...
Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° программиста
16 ноября 2019

DeepFake-Ρ‚ΡƒΡ‚ΠΎΡ€ΠΈΠ°Π»: создаСм собствСнный Π΄ΠΈΠΏΡ„Π΅ΠΉΠΊ Π² DeepFaceLab

РассказываСм ΠΎ Ρ‚Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΈ DeepFake ΠΈ шаг Π·Π° шагом учимся Π΄Π΅Π»Π°Ρ‚ΡŒ Π΄ΠΈΠΏΡ„Π΅ΠΉΠΊΠΈ Π² ...
admin
14 июля 2017

ПишСм свою Π½Π΅ΠΉΡ€ΠΎΡΠ΅Ρ‚ΡŒ: пошаговоС руководство

ΠžΡ‚Π»ΠΈΡ‡Π½Ρ‹ΠΉ Π³Π°ΠΉΠ΄ ΠΏΡ€ΠΎ Π½Π΅ΠΉΡ€ΠΎΡΠ΅Ρ‚ΡŒ ΠΎΡ‚ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΊ ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅. Π’Ρ‹ ΡƒΠ·Π½Π°Π΅Ρ‚Π΅ ΠΈΠ· ΠΊΠ°ΠΊΠΈΡ… элСмС...