ADsP

ADsP 3๊ณผ๋ชฉ 5-5 ๊ตฐ์ง‘๋ถ„์„ | ์ •๋ฆฌ๐Ÿ“

studyrooom 2024. 10. 1. 17:08
SMALL

๋ฐ์ดํ„ฐ ๊ฐ„ ์œ ์‚ฌ๋„/๋น„์œ ์‚ฌ๋„๋ฅผ ํ‰๊ฐ€ํ•˜์—ฌ ๋ฐ์ดํ„ฐ๋ฅผ ํŠน์ • ๊ฐœ์ˆ˜์˜ ๊ตฐ์ง‘์œผ๋กœ ๋ถ„ํ• ํ•˜๋Š” ๊ธฐ๋ฒ•
๊ตฐ์ง‘์˜ ๊ฐœ์ˆ˜๋‚˜ ๊ตฌ์กฐ์— ๋Œ€ํ•œ ๊ฐ€์ • ์—†์ด ๋‹ค๋ณ€๋Ÿ‰ ๋ฐ์ดํ„ฐ๋กœ๋ถ€ํ„ฐ ๊ฑฐ๋ฆฌ ๊ธฐ์ค€์— ์˜ํ•œ ์ž๋ฐœ์  ๊ตฐ์ง‘ํ™”๋ฅผ ์œ ๋„ํ•จ

  • ๋น„์ง€๋„ ํ•™์Šต์œผ๋กœ ์‚ฌ์ „ ์ •๋ณด ์—†์ด ์ž๋ฃŒ๋ฅผ ์œ ์‚ฌํ•œ ๋Œ€์ƒ๋ผ๋ฆฌ ๋ฌถ์Œ
  • ๋‹ค๋ณ€๋Ÿ‰ ๋ถ„์„(์ƒ๊ด€๋ถ„์„, ํšŒ๊ท€๋ถ„์„, ์ฃผ์„ฑ๋ถ„ ๋ถ„์„ ๋“ฑ)์„ ํ™œ์šฉํ•˜์—ฌ ๊ฐ ๊ตฐ์ง‘์— ๋Œ€ํ•œ ํŠน์ง•์„ ํŒŒ์•…ํ•จ
    ๊ตฐ์ง‘๋ถ„์„์— ์ด์šฉ๋˜๋Š” ๋‹ค๋ณ€๋Ÿ‰ ์ž๋ฃŒ๋Š” ๋ณ„๋„์˜ ๋ฐ˜์‘๋ณ€์ˆ˜๊ฐ€ ํ•„์š” ์—†์Œ
    • ์ƒ๊ด€๋ถ„์„: ๊ฒฝํ–ฅ๊ณผ ๊ด€๊ณ„์˜ ์ •๋„๋ฅผ ์•Œ์•„๋ณด๋Š” ๋ถ„์„ (์ธ๊ณผ๊ด€๊ณ„, ๋ถ„์‚ฐ์„ ์•Œ ์ˆ˜ ์—†์Œ)
  • ๊ฐœ์ฒด๋ฅผ ๋ถ„๋ฅ˜ํ•˜๊ธฐ ์œ„ํ•œ ๋ช…ํ™•ํ•œ ๊ธฐ์ค€์ด ์กด์žฌํ•˜์ง€ ์•Š๊ฑฐ๋‚˜ ๊ธฐ์ค€์ด ๋ฐํ˜€์ง€์ง€ ์•Š์€ ์ƒํƒœ์—์„œ ์œ ์šฉํ•จ
  • ๊ตฐ์ง‘๋ถ„์„์€ ํ•˜์œ„๊ตฐ์ง‘ ๋‚ด ๋™์งˆ์„ฑ / ํ•˜์œ„๊ตฐ์ง‘ ๊ฐ„ ์ด์งˆ์„ฑ์„ ๋งŒ์กฑ
  • ๊ตฐ์ง‘ํ™”์˜ ๋ฐฉ๋ฒ•์—๋Š” ๋ถ„๋ฆฌ ๊ตฐ์ง‘, ๋ฐ€๋„ ๊ธฐ๋ฐ˜ ๊ตฐ์ง‘ ๋“ฑ์ด ์žˆ์Œ
  • ์‹ค๋ฃจ์—ฃ ๊ณ„์ˆ˜(silhouette coefficient): ๊ตฐ์ง‘๋ถ„์„ ํ’ˆ์งˆ ํ‰๊ฐ€์˜ ๊ธฐ์ค€์œผ๋กœ ๊ตฐ์ง‘์˜ ๋ฐ€์ง‘ ์ •๋„๋ฅผ ๊ณ„์‚ฐํ•จ
    ๊ตฐ์ง‘ ๋‚ด์˜ ๊ฑฐ๋ฆฌ, ๊ตฐ์ง‘ ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ถ„ํ•  ์„ฑ๊ณผ ํ‰๊ฐ€
    ์‘์ง‘๋„, ๋ถ„๋ฆฌ๋„๊ฐ€ ์ปค์ง€๋ฉฐ ์™„๋ณ€ํ•™ ๋ถ„๋ฆฌ์ผ ๊ฒฝ์šฐ 1์˜ ๊ฐ’์„ ๊ฐ€์ง
    • ๋ฐ์ดํ„ฐ ์‘์ง‘๋„(cohesion)
    • ๊ตฐ์ง‘๊ฐ„ ๋ถ„๋ฆฌ๋„(separation)
  • ๊ตฐ์ง‘ ๋ถ„๋ฆฌ ์•ˆ์ •์„ฑ ๊ฒ€ํ† : ๊ต์ฐจํƒ€๋‹น์„ฑ ์ด์šฉ
    ๊ต์ฐจํƒ€๋‹น์„ฑ: ๋‘ ์ง‘๋‹จ์œผ๋กœ ๋‚˜๋ˆ  ๊ฐ๊ฐ ๊ตฐ์ง‘๋ถ„์„ ํ›„ ํ•ฉ์ณ์„œ ์›๋ž˜ ๊ตฐ์ง‘๋ถ„์„๊ณผ ๋น„์Šทํ•œ์ง€ ๋น„๊ตํ•˜๋Š” ๋ฐฉ๋ฒ•
  • ๊ตฐ์ง‘ ๋ถ„๋ฆฌ ๋…ผ๋ฆฌ์„ฑ ๊ฒ€ํ† : ๊ตฐ์ง‘ ๊ฐ„ ๋ณ€๋™์˜ ํฌ๊ธฐ ์ฐจ์ด ๊ฒ€ํ† 
    ๊ตฐ์ง‘ ๋ถ„๋ฆฌ์— ๋Œ€ํ•ด ์•ˆ์ •์„ฑ๋„ ์ค‘์š”ํ•˜์ง€๋งŒ ํ•ด๋‹น ๊ตฐ์ง‘์— ๋Œ€ํ•œ ๋ถ„๋ฆฌ๊ฐ€ ๋…ผ๋ฆฌ์ ์œผ๋กœ ์„ค๋ช…๋˜๋Š” ๋ถ€๋ถ„์ด ๋” ์ค‘์š”ํ•จ

 

๊ตฐ์ง‘๋ถ„์„ ๊ฑฐ๋ฆฌ ๊ณ„์‚ฐ
๋ฐ์ดํ„ฐ ๊ฐ„ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•˜์—ฌ ์œ ์‚ฌ์„ฑ์„ ์ธก์ •ํ•˜๊ณ  ์ด๋ฅผ ๊ทผ๊ฑฐ๋กœ ๊ตฐ์ง‘ ํŒ๋‹จ

  • ์ˆ˜์น˜ํ˜•(์—ฐ์†ํ˜•) ๋ณ€์ˆ˜
    • ์œ ํด๋ฆฌ๋””์•ˆ(Euclidean) (ํ†ต๊ณ„์  ํŠน์„ฑ ๊ณ ๋ ค X)
      ๋‘ ์ ์„ ์ž‡๋Š” ๊ฐ€์žฅ ์งง์€ ์ง์„  ๊ฑฐ๋ฆฌ
      ๊ณตํ†ต์œผ๋กœ ์ ์ˆ˜๋ฅผ ๋งค๊ธด ํ•ญ๋ชฉ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ํ†ตํ•ด ํŒ๋‹จํ•จ
      $\sqrt{ \displaystyle\sum_{j=1}(x_j-y_j)^2\ }$
    • ํ‘œ์ค€ํ™” ๊ฑฐ๋ฆฌ(Statistical Distance)
    • ๋งˆํ• ๋ผ๋…ธ๋น„์Šค(Mahalanobis) (ํ†ต๊ณ„์  ํŠน์„ฑ ๊ณ ๋ ค O)
      ๋ณ€์ˆ˜์˜ ํ‘œ์ค€์˜ค์ฐจ, ์‚ฐํฌ, ๋ณ€์ˆ˜ ๊ฐ„ ์ƒ๊ด€์„ฑ๊นŒ์ง€ ๊ณ ๋ คํ•˜์—ฌ ํ‘œ์ค€ํ™”ํ•œ ๊ฑฐ๋ฆฌ
      • ํ‘œ์ค€ํ™” ๊ฑฐ๋ฆฌ + ์ƒ๊ด€์„ฑ ๊ณ ๋ ค
      • ํ‘œ๋ณธ๊ณต๋ถ„์‚ฐ์œผ๋กœ ๋‚˜๋ˆ ์ฃผ์–ด์•ผ
      • ๊ฐ ๋ณ€์ˆ˜๋ฅผ ํ‘œ์ค€ํŽธ์ฐจ๋กœ ๋ฐ”๊พธ๊ณ  ์œ ํด๋ฆฌ๋“œ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ‘œ์ค€ํ™”๋ฅผ ํ†ตํ•ด ์™œ๊ณก ์ค„์–ด๋“ฆ
        $\sqrt{(x-y)^T\ S^{-1}(x-y)}$
    • ์ฒด๋น„์…ฐํ”„(Chebychev)
    • ๋งจํ•˜ํƒ„(Manhattan)
      ๊ฐ ๋ฐฉํ–ฅ์˜ ์ง๊ฐ ์ด๋™ ๊ฑฐ๋ฆฌ์˜ ํ•ฉ
      $\displaystyle\sum_{j}|x_j-y_j|$
    • ์บ”๋ฒ„๋ผ(Canberra)
    • ๋ฏผ์ฝ”์šฐ์Šคํ‚ค(Minkowski) (์œ ํด๋ฆฌ๋””์•ˆ + ๋งจํ•˜ํƒ„)
      $(\ \displaystyle\sum_{j}|x_j-y_j|^m\ )^{1/m}$
  • ๋ฒ”์ฃผํ˜• ๋ณ€์ˆ˜
    • ์ž์นด๋“œ
      boolean ์†์„ฑ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋‘ ๊ฐ์ฒด ๊ฐ„ ์œ ์‚ฌ๋„ ์ธก์ •
      $1-J(A,B)=\frac{(|A \cup B|-|A\cap B|)}{|A \cup B|}$
    • ์ฝ”์‚ฌ์ธ (๋ฌธ์„œ ๊ฐ„ ์œ ์‚ฌ๋„ ๊ณ„์‚ฐํ•  ๋•Œ ๋งŽ์ด ์‚ฌ์šฉ)
      $1-\frac{A\cdotp B}{\lVert A\rVert_2 \cdotp \lVert B\rVert_2 }$

 

๊ณ„์ธต์  ๊ตฐ์ง‘๋ถ„์„

๋ฐ์ดํ„ฐ ๊ฐ„ ๊ณ„์ธต์  ๊ตฌ์กฐ ๋ฐ ๊ด€๊ณ„๋ฅผ ํŠธ๋ฆฌ ํ˜•ํƒœ๋กœ ํ‘œํ˜„

n๊ฐœ์˜ ๊ตฐ์ง‘์œผ๋กœ ์‹œ์ž‘ํ•ด ์ ์ฐจ ๊ตฐ์ง‘์˜ ๊ฐœ์ˆ˜๋ฅผ ์ค„์—ฌ๊ฐ€๋Š” ๋ฐฉ๋ฒ•

๊ตฐ์ง‘์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฏธ๋ฆฌ ์ •ํ•˜์ง€ ์•Š์•„๋„ ๋˜์–ด ํƒ์ƒ‰์  ๋ถ„์„์— ์‚ฌ์šฉํ•จ

๋™์ผํ•œ ๊ฑฐ๋ฆฌ ๊ณ„์‚ฐ๋ฒ•์„ ์ ์šฉํ•˜๋ฉด ๋ช‡ ๋ฒˆ์„ ์‹œํ–‰ํ•ด๋„ ๊ฒฐ๊ณผ๊ฐ€ ๋™์ผํ•จ

 

ํ˜•์„ฑ๋ฐฉ๋ฒ•์€ ๋ณ‘ํ•ฉ์  ๋ฐฉ๋ฒ•๊ณผ ๋ถ„ํ• ์  ๋ฐฉ๋ฒ•์ด ์žˆ์Œ

  • ํ•ฉ๋ณ‘ํ˜• ๋ฐฉ์‹(bottom up)
    ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ๊ฐ ๊ตฐ์ง‘์œผ๋กœ ๋ณด๊ณ  ์œ ์‚ฌํ•œ ๋ฐ์ดํ„ฐ๋ผ๋ฆฌ ๊ตฐ์ง‘ํ™”ํ•ด ๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹
    ๊ตฐ์ง‘ N๊ฐœ → $\cdot\cdot\cdot$ → ๊ตฐ์ง‘ 1๊ฐœ
  • ๋ถ„๋ฆฌํ˜• ๋ฐฉ์‹(top down)
    ํ•ฉ๋ณ‘ํ˜• ๋ฐฉ์‹๊ณผ ๋ฐ˜๋Œ€
    ๋ชจ๋“  ๋ฐ์ดํ„ฐ๋ฅผ ๋‹จ์ผ ๊ตฐ์ง‘์— ์†ํ•œ๋‹ค๊ณ  ์ •์˜ํ•˜๊ณ  ์‹œ์ž‘ํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ์ƒ์œ„ ๊ตฐ์ง‘์—์„œ ์ž˜๋ชป๋œ ๊ฒฐ์ •์„ ํ•˜๋ฉด ํ•˜์œ„ ๊ตฐ์ง‘์— ํŒŒ๊ธ‰๋˜๋Š” ์ •๋„๊ฐ€ ํฌ๋‹ค๋Š” ๋‹จ์ ์ด ์žˆ์Œ
  • ์ตœ๋‹จ ์—ฐ๊ฒฐ๋ฒ•(single linkage method) → ๊ตฐ์ง‘ ๋‚˜๋ˆ„๋Š” ๋ฌธ์ œ๋Š” ํ‰๋ฉด์— ์  ์ฐ์–ด์„œ ํ’€๊ธฐ
    ๋‹ค๋ฅธ ๊ตฐ์ง‘์— ์†ํ•œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๊ด€์ธก๊ฐ’ ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฐ์ง‘ ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋กœ ์ธก์ •ํ•˜๋Š” ๋ฐฉ์‹
    • ์‚ฌ์Šฌ ๋ชจ์–‘ ๊ตฐ์ง‘์ด ์ƒ๊ธธ ์ˆ˜ ์žˆ์Œ
    • ๊ณ ๋ฆฝ๋œ ๊ตฐ์ง‘์„ ์ฐพ๋Š”๋ฐ ์ค‘์ ์„ ๋‘” ๋ฐฉ๋ฒ•
  • ์ตœ์žฅ ์—ฐ๊ฒฐ๋ฒ•(complete linkage)
    ๋‹ค๋ฅธ ๊ตฐ์ง‘์— ์†ํ•œ ๊ฐ€์žฅ ๋จผ ๊ด€์ธก๊ฐ’ ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฐ์ง‘ ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋กœ ์ธก์ •ํ•˜๋Š” ๋ฐฉ์‹
  • ํ‰๊ท  ์—ฐ๊ฒฐ๋ฒ•(average linkage)
    ๋‹ค๋ฅธ ๊ตฐ์ง‘์— ์†ํ•œ ๊ด€์ธก๊ฐ’ ์Œ๋“ค์˜ ๋ชจ๋“  ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•˜๊ณ  ์ด์˜ ํ‰๊ท ๊ฐ’์„ ๊ตฐ์ง‘ ๊ฐ„ ๊ฑฐ๋ฆฌ๋กœ ์ธก์ •ํ•˜๋Š” ๋ฐฉ์‹
  • ์ค‘์‹ฌ ์—ฐ๊ฒฐ๋ฒ•(centroid linkage)
    ๊ฐ ๊ตฐ์ง‘์˜ ์ค‘์‹ฌ์œ„์น˜ ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฐ์ง‘ ๊ฐ„ ๊ฑฐ๋ฆฌ๋กœ ์ธก์ •ํ•˜๋Š” ๋ฐฉ์‹
  • ์™€๋“œ ์—ฐ๊ฒฐ๋ฒ•(Ward Linkage)
    • ๊ฐ ๊ตฐ์ง‘์˜ ๋ถ„์‚ฐ์„ ๊ณ ๋ คํ•˜์—ฌ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐ
    • ๊ตฐ์ง‘์„ ํ•ฉ์น˜๋ฉด์„œ ๊ตฐ์ง‘ ๋‚ด ๋ณ€๋™์ด ์ตœ์†Œํ™”๋˜๋„๋ก ์„ค๊ณ„
      ๋ณ‘ํ•ฉ ํ›„ ์˜ค์ฐจ์ œ๊ณฑํ•ฉ์˜ ์ฆ๊ฐ€ ์ •๋„๊ฐ€ ์ž‘์•„์ง
    • ๊ณ„์‚ฐ๋Ÿ‰์ด ๋งŽ์Œ
      ๊ตฐ์ง‘ ๋‚ด ํŽธ์ฐจ๋“ค์˜ ์ œ๊ณฑํ•ฉ์„ ๊ณ ๋ คํ•ด ๊ตฐ์ง‘ ๊ฐ„ ์ •๋ณด ์†์‹ค์„ ์ตœ์†Œํ™” ํ•˜๋Š” ๋ฐฉํ–ฅ์œผ๋กœ ๊ตฐ์ง‘ ํ˜•์„ฑ
  • ๊ตฐ์ง‘ํ™”
    ๋ด๋“œ๋กœ๊ทธ๋žจ์„ ํ†ตํ•ด ์ ์ ˆํ•œ ๊ตฐ์ง‘ ์ˆ˜ ์„ ์ •
    ๊ฐ€๋กœ์„ ์„ ๊ทธ์–ด ๊ตฐ์ง‘์„ ์ž๋ฅด๊ณ  ๊ทธ ์œ„๋ฅผ ๊ตฐ์ง‘ ์ˆ˜๋กœ ํ•จ

 

 

๋น„๊ณ„์ธต์  ๊ตฐ์ง‘๋ถ„์„
๊ณ„์ธต์ ์œผ๋กœ ๊ตฐ์ง‘์„ ํ˜•์„ฑํ•˜์ง€ ์•Š๊ณ  ์›ํ•˜๋Š” ๊ตฐ์ง‘์˜ ๊ฐœ์ˆ˜๋ฅผ ์‚ฌ์ „์— ์„ค์ •

  • ํผ์ง€ ๊ตฐ์ง‘ํ™”(Fuzzy clustering)
    ๊ด€์ธก๊ฐ’์ด ์—ฌ๋Ÿฌ ํด๋Ÿฌ์Šคํ„ฐ์— ๋™์‹œ์— ์†ํ•  ์ˆ˜ ์žˆ๋Š” ๊ตฐ์ง‘ํ™” ๋ฐฉ๋ฒ•๋ก 
    ๊ด€์ธก๊ฐ’๋งˆ๋‹ค ์—ฌ๋Ÿฌ ํด๋Ÿฌ์Šคํ„ฐ์— ์†ํ•  ํ™•๋ฅ ์„ ๊ณ„์‚ฐ
  • ๋ฐ€๋„ ๊ธฐ๋ฐ˜ ๊ตฐ์ง‘ํ™”
    ๋ฐ์ดํ„ฐ์˜ ๋ฐ€๋„(=๋ฐ€์ง‘๋„)๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๊ตฐ์ง‘ ํ˜•์„ฑ
    ์ž„์˜์ ์ธ(Arbitrarity) ๋ชจ์–‘์˜ ๊ตฐ์ง‘ ํƒ์ƒ‰
    • DBCAN, OPTICS, DENCLUE

 

K-ํ‰๊ท  ๊ตฐ์ง‘๋ถ„์„(K-Means Clustering)

๋ฐ์ดํ„ฐ๋ฅผ K๊ฐœ์˜ ๊ตฐ์ง‘์œผ๋กœ ๊ทธ๋ฃนํ™”ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

๊ตฐ์ง‘ ๋‚ด ๋ณ€๋™(์˜ค์ฐจ์ œ๊ณฑํ•ฉ)์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉํ–ฅ์œผ๋กœ ๊ตฐ์ง‘ํ™” ํ•˜๋ฏ€๋กœ ๊ตฐ์ง‘ ์ˆ˜๋ฅผ ์ •ํ•  ๋•Œ ์ง‘๋‹จ ๋‚ด ์ œ๊ณฑํ•ฉ ๊ทธ๋ž˜ํ”„๊ฐ€ ํ•„์š”ํ•จ

  • ์‚ฌํšŒ ์—ฐ๊ฒฐ๋ง ๋ถ„์„์—์„œ ์—ฐ๊ฒฐ๋ง์„ ํ‘œํ˜„ํ•˜๋Š” ๋ถ„์„ ๋ฐฉ๋ฒ•์ž„

์žฅ์ 

  • ๋Œ€์šฉ๋Ÿ‰ ๋ฐ์ดํ„ฐ์…‹์—์„œ๋„ ๋น ๋ฅด๊ฒŒ ์‹คํ–‰ ๊ฐ€๋Šฅ
  • ๋ถ„์„ ๋ฐฉ๋ฒ•์˜ ์ ์šฉ์ด ์šฉ์ดํ•จ
  • ์ƒ๋Œ€์ ์œผ๋กœ ๋‹จ์ˆœํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • ๋‹ค์–‘ํ•œ ํ˜•ํƒœ์— ์ ์šฉ ๊ฐ€๋Šฅ
  • ์‚ฌ์ „์ •๋ณด ์—†์ด๋„ ์˜๋ฏธ์žˆ๋Š” ๊ฒฐ๊ณผ ์ฐฝ์ถœ ๊ฐ€๋Šฅ

๋‹จ์ 

  • ์ด์ƒ์น˜, ์žก์Œ(noise)์— ์˜ํ–ฅ์„ ๋งŽ์ด ๋ฐ›์Œ ๊ตฐ์ง‘ ๊ฒฝ๊ณ„ ์„ค์ •์ด ์–ด๋ ค์›€
  • ์ดˆ๊นƒ๊ฐ’์— ์˜ํ–ฅ์„ ๋งŽ์ด ๋ฐ›์Œ
  • ๊ตฐ์ง‘ ๊ฐœ์ˆ˜๋ฅผ ์ง€์ •ํ•ด ์ค˜์•ผ ํ•จ
  • ๊ตฐ์ง‘์ด ์›ํ˜•์œผ๋กœ ๋‚˜๋ˆ ์ง€์ง€ ์•Š์€ ๊ฒฝ์šฐ ์ ์ ˆ์น˜ ์•Š์Œ
    ๋ณผ๋ก(convex)ํ•œ ํ˜•ํƒœ๊ฐ€ ์•„๋‹Œ ์˜ค๋ชฉํ•œ ํ˜•ํƒœ์˜ ๊ตฐ์ง‘์ด ์กด์žฌํ•˜๋ฉด ์„ฑ๋Šฅ์ด ๋–จ์–ด์ง
  • ์‚ฌ์ „์— ์ฃผ์–ด์ง„ ๋ชฉ์ ์ด ์—†์–ด ๊ฒฐ๊ณผ ํ•ด์„์ด ์–ด๋ ค์›€

 

K-ํ‰๊ท  ๊ตฐ์ง‘๋ถ„์„ - ํ”„๋กœ์„ธ์Šค

  1. K๊ฐ’ ์„ค์ •
  2. ์ค‘์‹ฌ ์ดˆ๊ธฐํ™”
    K๊ฐœ์˜ seed ์ค‘์‹ฌ์„ ์ž„์˜๋กœ ์„ ํƒ
    • ์ž„์˜๋กœ ์„ ํƒํ•˜๋ฏ€๋กœ ๊ตฐ์ง‘์ด ํ˜•์„ฑ๋˜์–ด๋„ ๊ตฐ์ง‘ ๋‚ด ๊ฐ์ฒด๋“ค์€ ๋‹ค๋ฅธ ๊ตฐ์ง‘์œผ๋กœ ์ด๋™ ๊ฐ€๋Šฅํ•จ
  3. ๊ตฐ์ง‘ ํ• ๋‹น
    ๊ฐ ๊ด€์ธก๊ฐ’์„ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์ค‘์‹ฌ์— ํ• ๋‹น
  4. ์—…๋ฐ์ดํŠธ
    ๊ตฐ์ง‘ํ™”๋œ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๊ฐ ๊ตฐ์ง‘์˜ ์ค‘์‹ฌ์„ ๋‹ค์‹œ ๊ณ„์‚ฐ
  5. ๋ชจ๋“  ๊ฐœ์ฒด๊ฐ€ ๊ตฐ์ง‘์œผ๋กœ ํ• ๋‹น๋  ๋•Œ๊นŒ์ง€ 3, 4๋ฒˆ ๋ฐ˜๋ณต
    ์ค‘์‹ฌ์˜ ์œ„์น˜๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๊ณ  ์ƒˆ๋กœ์šด ๊ตฐ์ง‘์— ํ• ๋‹น

 

PAM (Partitioning Around Medoids)
๊ตฐ์ง‘ํ™”(ํด๋Ÿฌ์Šคํ„ฐ๋ง) ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • K-means์™€ ์œ ์‚ฌํ•˜์ง€๋งŒ, ๊ตฐ์ง‘์˜ ์ค‘์‹ฌ(centroid)์„ ํ‰๊ท  ๋Œ€์‹  ๋ฐ์ดํ„ฐ์…‹์˜ ์ƒ˜ํ”Œ์„ ์‚ฌ์šฉํ•ด ๋ณด์™„ํ•œ ๋ฐฉ๋ฒ•
  • ์ค‘์•™๊ฐ’(Medoids) ์‚ฌ์šฉ: ๊ตฐ์ง‘์˜ ์ค‘์‹ฌ์ ์œผ๋กœ ๋ฐ์ดํ„ฐ์˜ ์ƒ˜ํ”Œ์„ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด์ƒ์น˜์— ๊ฐ•๊ฑดํ•˜์ง€๋งŒ ๊ณ„์‚ฐ๋Ÿ‰์ด ๋งŽ๋‹ค๋Š” ๋‹จ์ ์ด ์žˆ์Œ

 

ํ˜ผํ•ฉ ๋ถ„ํฌ ๊ตฐ์ง‘ (Gaussian Mixture Model)

ํ™•๋ฃฐ๋ถ„ํฌ๋ฅผ ๋„์ž…ํ•˜์—ฌ ๊ตฐ์ง‘์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋ชจํ˜• ๊ธฐ๋ฐ˜ ๊ตฐ์ง‘ ๋ฐฉ๋ฒ•

  • ๊ฐ€์ •: ๊ฐ ๊ตฐ์ง‘์˜ ๋ฐ์ดํ„ฐ ์ƒ˜ํ”Œ์„ ํ™•๋ฅ ๋ถ„ํฌ์—์„œ ์ƒ˜ํ”Œ๋ง
  • ํ†ต์ƒ ํ™•๋ฅ ๋ถ„ํฌ๋Š” ์ •๊ทœ๋ถ„ํฌ๋ฅผ ์‚ฌ์šฉ
  • K-means๋‚˜ PAM๊ณผ ๋‹ฌ๋ฆฌ ํ™•๋ฅ ๋ถ„ํฌ ๊ธฐ๋ฐ˜
  • ๊ตฐ์ง‘์˜ ํฌ๊ธฐ๊ฐ€ ๋„ˆ๋ฌด ์ž‘์œผ๋ฉด ์ถ”์ •์˜ ์ •๋„๊ฐ€ ๋–จ์–ด์ง€๊ฑฐ๋‚˜ ์–ด๋ ค์šธ ์ˆ˜ ์žˆ์Œ
  • ๊ตฐ์ง‘์„ ๋ช‡ ๊ฐœ์˜ ๋ชจ์ˆ˜๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Œ
  • ๋ชจ์ˆ˜ ์ถ”์ •์—์„œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ปค์ง€๋ฉด ์ˆ˜ํ–‰ํ•˜๋Š” ๋ฐ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆด ์ˆ˜ ์žˆ์Œ

 

ํ™•๋ฅ ๋ถ„ํฌ (๋ชจ์ˆ˜) ์ถ”์ • ๋ฐฉ๋ฒ•

EM ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ตœ๋Œ€ ๊ฐ€๋Šฅ๋„ ์ถ”์ •๋Ÿ‰(Maximum Likelihood Estimation)์„ ์œ„ํ•ด ์‚ฌ์šฉ๋˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • E-step: ์ž ์žฌ๋ณ€์ˆ˜ $Z$์˜ ๊ธฐ๋Œ“๊ฐ’ ๊ณ„์‚ฐ
    ๊ด€์ธก๊ฐ’์ด ํŠน์ • ๊ตฐ์ง‘์— ์†ํ•  ํ™•๋ฅ  ๊ณ„์‚ฐ
  • M-step: $Z$์˜ ๊ธฐ๋Œ“๊ฐ’์„ ํ†ตํ•œ ํŒŒ๋ผ๋ฏธํ„ฐ ์ถ”์ • (likelihood maximization)
  • E๋‹จ๊ณ„, M๋‹จ๊ณ„๋ฅผ ๋ฐ˜๋ณตํ•˜์—ฌ ํŒŒ๋ผ๋ฏธํ„ฐ๋ฅผ ์ˆ˜์ •

 

Self-Organizing Maps (SOM; ์ž๊ธฐ์กฐ์งํ™”์ง€๋„): ๊ณ ์ฐจ์›์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์ดํ•ดํ•˜๊ธฐ ์‰ฌ์šด ์ €์ฐจ์›์˜ ๋‰ด๋Ÿฐ์œผ๋กœ ์ •๋ ฌํ•ด ์ง€๋„ํ˜•ํƒœ๋กœ ํ˜•์ƒํ™” ํ•˜๋Š” ํด๋Ÿฌ์Šคํ„ฐ๋ง ๋ฐฉ๋ฒ•

์ž…๋ ฅ์ธต(Input Layer): ์ž…๋ ฅ ๋ฒกํ„ฐ๋ฅผ ๋ฐ›๋Š” ์ธต. ์ž…๋ ฅ ๋ณ€์ˆ˜์˜ ๊ฐœ์ˆ˜์™€ ๋™์ผํ•˜๊ฒŒ ๋‰ด๋Ÿฐ ์ˆ˜๊ฐ€ ์กด์žฌํ•จ

๊ฒฝ์Ÿ์ธต(Competitive Layer): 2์ฐจ์› ๊ฒฉ์ฐจ๋กœ ๊ตฌ์„ฑ๋œ ์ธต. ์ž…๋ ฅ ๋ฒกํ„ฐ์˜ ํŠน์„ฑ์— ๋”ฐ๋ผ ๋ฒกํ„ฐ๊ฐ€ ํ•œ ์ ์œผ๋กœ ํด๋Ÿฌ์Šคํ„ฐ๋ง ๋˜๋Š” ์ธต

  • ์—ญ์ „ํŒŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋Š” ์ธ๊ณต์‹ ๊ฒฝ๋ง๊ณผ ๋‹ฌ๋ฆฌ, ๋‹จ ํ•˜๋‚˜์˜ ์ „๋ฐฉ ํŒจ์Šค๋ฅผ ์‚ฌ์šฉํ•จ
  • ๊ฒฝ์Ÿํ•™์Šต์œผ๋กœ ๋‰ด๋Ÿฐ๊ณผ ์ž…๋ ฅ๋ฐฑํ„ฐ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•ด ์—ฐ๊ฒฐ๊ฐ•๋„๋ฅผ ๋ฐ˜๋ณต์ ์œผ๋กœ ์žฌ์กฐ์ •ํ•จ
    ์ž…๋ ฅํŒจํ„ด๊ณผ ์œ ์‚ฌํ•œ ๋‰ด๋Ÿฐ์ผ์ˆ˜๋ก ์—ฐ๊ฒฐ๊ฐ•๋„๊ฐ€ ์…ˆ
  • ์ž…๋ ฅ์ธต์˜ ๋‰ด๋Ÿฐ์€ ๊ฒฝ์Ÿ์ธต์— ์žˆ๋Š” ๋‰ด๋Ÿฐ๋“ค๊ณผ ์™„์ „์—ฐ๊ฒฐ(Fully Connected)๋˜์–ด ์žˆ์Œ
  • ์†๋„๊ฐ€ ๋น ๋ฅด๊ณ , ์‹ค์‹œ๊ฐ„ ํ•™์Šต์ฒ˜๋ฆฌ๊ฐ€ ๊ฐ€๋Šฅํ•จ
  • ์ž…๋ ฅ๋ณ€์ˆ˜์˜ ์œ„์น˜๊ด€๊ณ„๋ฅผ ๊ทธ๋Œ€๋กœ ๋ณด์กดํ•จ
๋ฐ˜์‘ํ˜•
LIST