07.02. Hiyerarşik kümeleme (Hierarchical Clustering): Ödev Benzerlikleri Üzerinden Kopya Gruplarını Bulma

k-means algoritmasının en kötü taraflarından biri küme sayısına karar vermenin zorluğudur. Küme sayısına ancak sistemi çok iyi bilen biri karar verebilir ki bu da probleme göre değişir. Örneğin bir ödev verdiniz ve hangi öğrencinin hangi öğrenciye yakın ödev yaptığını ve kaç küme oluştuğunu merak ettiğinizde küme sayısını önceden bilmenize olanak yoktur. Bir ödevde 3 küme çıkar, diğer ödevde 20 küme çıkabilir. İşte bu noktada x-means ve single pass gibi algoritmalar olsa da hiyerarşik kümeleme küme oluşturma için esnek bir yapı olması sebebiyle bir adım öne çıkar. 

Gözetimsiz öğrenme biri olan Hiyerarşik kümeleme, diğer kümeleme yöntemlerine göre daha bilgilendirici bir çıktı üretir. Hiyerarşik kümelemede, küme sayısı önceden belirlenmesi gerekmemektedir. Hiyerarşik kümeleme, birleştirici ve ayrıştırıcı hiyerarşik kümeleme yöntemleri olmak üzere iki türe sahiptir.  Birleştirici hiyerarşik kümelemede başlangıçta her bir değer bağımsız bir küme olarak değerlendirilir ve bu değerler çeşitli algoritmalarla birleştirilip her aşamada bir üst küme oluşturulur. Ayrıştırıcı kümelemede ise başlangıçta tüm değerler bir küme olarak değerlendirilip yine çeşitli ayrıştırma algoritmalarıyla alt kümeler elde edilir.  İşlem sonunda dendrogram denen tüm nesnelerin ilişkilerini gösteren bir ağaç yapısı oluşur [Johnson, 1967]. Genelde literatürde, bu çalışmada olduğu gibi birleştirici kümeleme yöntemi tercih edilmektedir (Manning ve ark., 2008).  Ayrıştırıcı hiyerarşik kümeleme yöntemin adımları ve akış şeması:

1. Her nesneler için değer oluştur ve her nesneyi bir küme olarak ata. (Bu durumda N tane nesne için N adet küme oluşur.) N x N bir matris oluştur.
2. En yakın olan iki nesneyi grupla. Matrisi kullanarak nesneler arası uzaklık değerlerini hesapla. 
3. N=N-1 boyutunda yeni matrisi oluştur. Taki N değeri 1 oluncaya kadar Adım 2. ye geri dön.

Verinin Hazırlaması ve matrisin oluşturulması

Veri hazırlama aşaması çalışma alanına göre farklılık gösterebilir. Bu kümeleme yönteminde  veriler arasındaki benzerlikleri içeren bir matris oluşturmalıyız. Örneğin gönderilen ödevleri için kelime veya karakter benzerliği kullanılabilir. (Bu konu doküman benzerliği konusudur. Bu konuda bir blog yazısı yazmayı planlıyorum.) Dokümanlar arasındaki benzerlikler bulunduktan sonra aşağıdaki gibi bir matris elde edebiliriz.

Tek bağlantı kümeleme, her adımda en küçük mesafeye sahip en yakın üyeler kullanarak iki kümenin birleştirilmesidir. Bu algoritmaya, en yakın komşu algoritması da denir. Tam bağlantı kümeleme, tek bağlantının tam tersine her adımda en büyük mesafeye sahip en uzak üyeler kullanılarak iki kümenin birleştirilmesidir. Bu algoritmaya bu sebepten dolayı en uzak komşu algoritması da denir. Ortalama grup algoritması ise iki karşılıklı küme arasındaki tüm mesafelerin ortalamasıdır. Bu algoritma ile tek bağlantı ve tam bağlantı algoritmalarında elde edilen değerlerin arasında bir değer elde edilir (Manning ve ark., 2008).

(4, 5) kümesi yapıldıktan sonra yeni değerler hesaplanmalıdır. Bu hesap sırasında Şekil 1’deki matris bilgileri kullanılır. Bu aşamada min, max veya avg algoritmalarından biri kullanılır. Bu örnekte min değerini kullanılacaktır. Min yani Tek Bağlantı hesabı:

Tek bağlantıya göre bu kümelerden en küçük değerler seçilir. İki ödev birbiriyle aynı olduğu için tüm benzerlikler aynı çıkmıştır. Şimdi ikinci döngüye geçelim. Yeni oluşan matriste en küçük değer 0.004’tür. Başka bir deyişle 3 ve 6’ıncı öğrencilerden yeni bir küme oluşturulacaktır.