Ağaç yapılı öbekleme (Hierarchical Clustering) ve DBSCAN

Hierarchical Clustering

Elimizde N-tane nokta olsun. Ağaç yapılı öbekleme algoritmasını aşağıdaki gibi özetleyebiliriz:

  1. Her bir nokta, ayrı bir öbek olarak işaretlenir. Yani, elimizdeki N-tane nokta için N-tane öbek elde ederiz.
  2. En yakın 2 öbek bulunur ve birleştirilir. Elimizdeki öbek sayısı 1 azalmış olur.
  3. Yeni elde ettiğimiz öbekle diğer öbekler arasındaki uzaklıklar hesaplanır.
  4. Tüm noktalar tek bir öbekte olana kadar 2. ve 3. adımlar tekrar edilir.

DBSCAN (Density-based spatial clustering of applications with noise)

Algoritmayı anlatmadan önce algoritmanın dayandığı iki kavramdan bahsetmemiz gerekiyor:

Tanım 1 (Density Reachability). p noktası, q noktasının \epsilon komşuluğunda ve q noktası, \epsilon komşuluğunda yeteri kadar komşu içeriyorsa, p noktası,q noktasından “yoğun erişebilir (dense reachable)” denir.

Tanım 2 (Density Connectivity). Eğer p ve q noktaları bir \epsilon yarıçaplı çember içerisinde ve bu iki noktaya komşu olan bir r noktası var ise, p ve q noktaları “yoğun bağlıdır(dense connected)” denir.

Elimizde yine N-tane nokta olsun. DBSCAN algoritması, iki parametre gerektirir: \epsilon ve bir öbek oluşturmak için gereken minimum nokta sayısı (minPts):

  1. Daha önce “ziyaret edilmemiş” keyfi bir başlangıç noktası seçilir.
  2. Bu noktanın \epsilon komşuluğundaki noktalar bulunur.
  3. Eğer komşu sayısı yeterli ise öbekleme işlemine başlanır ve bu nokta “ziyaret edildi” olarak işaretlenir; komşu sayısı yeterli değil ise de “gürültü (noise)” olarak işaretlenir (Gürültü olarak işaretlenen noktalar daha sonra bir öbeğe ait olabilir).
  4. Eğer bir öbeğe ait bir nokta bulunur ise, bu noktanın \epsilon komşuluğu da öbeğe dahil edilir ve 2.adım komşuluktaki tüm noktalar için tekrar edilir.
  5. Yeni bir ziyaret edilmemiş nokta bulunur ve işlenir (gürültü ya da ziyaret edildi olarak işaretlenir.).
  6. Tüm noktalar ziyaret edildi olarak işaretlenene kadar bu işlemler tekrar edilir.

Kaynaklar

  1. https://sites.google.com/site/dataclusteringalgorithms/density-based-clustering-algorithm
Reklamlar

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google fotoğrafı

Google hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Connecting to %s