Examkin

Soru

Zorluk: ZorK-Ortalamalar (K-Means) Yöntemi

Bir araştırmacı, farklı ölçüm birimlerine sahip sürekli değişkenlerden oluşan bir veri setini K-Ortalamalar (K-Means) algoritması ile kümelere ayırmak istemektedir. Gözlemlerin merkezlere atanması aşamasında uzaklık ölçüsü olarak Öklid (Euclidean) uzaklığı tercih edilmiştir. Değişkenler herhangi bir standartlaştırma işlemine tabi tutulmadan (ham verilerle) analize dâhil edilmiştir. Araştırmacı, veri setindeki olası uç değerlerin (outliers) küme merkezlerini (centroid) aşırı derecede saptırmasını önlemek düşüncesiyle algoritmada bir modifikasyon yapmış; her iterasyon sonundaki merkez güncelleme adımında, ilgili kümeye düşen gözlemlerin aritmetik ortalaması yerine medyan (ortanca) değerini yeni merkez olarak belirlemiştir.

Buna göre, veri setinin yapısı ve yapılan bu modifikasyonun K-Ortalamalar algoritması üzerindeki etkisiyle ilgili aşağıdakilerden hangisi kesinlikle doğrudur?

  1. Atama adımında Öklid uzaklığı kullanılıp güncelleme adımında medyan alınması, algoritmanın minimize etmeye çalıştığı grup içi kareler toplamının iterasyonlar boyunca monoton olarak azalmasını engeller ve yakınsama garantisini ortadan kaldırır.Cevap
  2. B
    Medyan kullanımı, Öklid uzaklığı ile matematiksel olarak tam uyumlu olduğundan, algoritmanın yerel minimumlara (local minima) takılma problemini çözerek her zaman aynı sonuca ulaşmasını sağlar.
  3. C
    Veriler standartlaştırılmamış olsa da medyanın uç değerlere karşı dirençli yapısı sayesinde, büyük varyanslı değişkenlerin Öklid uzaklığı üzerindeki baskın (domine edici) etkisi tamamen nötralize edilir.
  4. D
    Kümeleme analizinde asıl amaç önceden bilinen kategorik bir bağımlı değişkene göre sınıflandırma yapmak olduğundan, merkezlerin ortalama veya medyan ile güncellenmesi sınıflandırma doğruluğunu etkilemez.
  5. E
    Medyan ile merkez güncelleme kuralı, hiyerarşik kümelemedeki tek bağlantı (single linkage) yöntemine benzer bir şekilde zincirleme (chaining) etkisi yaratarak kümelerin uzamasına neden olur.

Cevap

Atama adımında Öklid uzaklığı kullanılırken güncelleme adımında medyan alınması, amaç fonksiyonu ile güncelleme kuralı arasındaki matematiksel uyumu bozarak iterasyonlarda grup içi kareler toplamının monoton azalmasını engeller.
K-Ortalamalar algoritmasının iterasyon sürecinde her adımın, grup içi hata kareler toplamını (WCSS) daha da küçültmesi veya sabit bırakması gerekir. Matematiksel olarak, belirli bir noktalar kümesi için uzaklıkların kareleri toplamını minimum yapan tek merkez noktası o noktaların aritmetik ortalamasıdır. Medyan ise mutlak uzaklıkların (Manhattan uzaklığı) toplamını minimize eder. Atama adımında noktalar Öklid uzaklığına (uzaklıkların karesine) göre kümelenip, ardından merkezler medyan olarak güncellenirse; medyan, ataması yapılmış noktaların Öklid uzaklıkları kareleri toplamını optimize etmediğinden algoritmanın monotonik olarak yakınsama (convergence) garantisi bozulur.

Adım Adım Çözüm

1
K-Ortalamalar algoritmasının amaç fonksiyonunu ve standart güncelleme kuralını tanımlama.
Standart K-Ortalamalar algoritması, ∑i=1k∑x∈Ci∣∣x−μi∣∣2\sum_{i=1}^{k} \sum_{x \in C_i} ||x - \mu_i||^2 ile ifade edilen grup içi hata kareler toplamını (WCSS) minimize etmeyi amaçlar. Bu karesel amaç fonksiyonunu belirli bir küme için minimum yapan merkez noktası (μi\mu_i) matematiksel olarak aritmetik ortalamadır.
Algoritmanın matematiksel temelini anlamak, yapılan modifikasyonun etkisini değerlendirebilmek için gereklidir.
2
Medyan kullanımının hangi uzaklık ölçüsüyle uyumlu olduğunu belirleme.
Medyan (ortanca) değeri, K-Medians algoritmasında olduğu gibi ∑∣x−μ∣\sum |x - \mu| ile ifade edilen mutlak farkların toplamını (Manhattan veya L1L_1 normu) minimize eden optimal noktadır.
Medyanın sahip olduğu optimizasyon özelliğini saptamak.
3
Atama adımı ile güncelleme adımı arasındaki uyumsuzluğun sonucunu analiz etme.
Atama adımında gözlemler Öklid uzaklığına (L2L_2 normu) göre en yakın merkeze atanıp, merkezler L1L_1 normunu minimize eden medyan ile güncellendiğinde; her iki adım farklı amaç fonksiyonlarını optimize etmeye çalışır. Bu yapısal çelişki nedeniyle WCSS'nin her iterasyonda (Lloyd algoritmasında) istikrarlı biçimde azalacağı garanti edilemez ve algoritma yakınsamadan osilasyona uğrayabilir.
Amaç fonksiyonu uyumsuzluğunun algoritmanın yakınsama (convergence) garantisine olan etkisini ortaya koymak.

Anahtar Kavram

K-Ortalamalar Algoritmasında Amaç Fonksiyonu ve Yakınsama (Convergence) Garantisi
Bu soruyu puanla

Konular

K-Ortalamalar (K-Means) Yöntemi

Bu konudan daha fazla soru