7.2. 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.
Adım 1:

 

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.

 

 
Birinci matris ödevler ve ödevler arasındaki benzerlikleri göstermektedir. Örneğin 1 ve 2 nolu öğrenciler 0.458 oranında bir benzeşim bulunmaktadır. Tabii, 2 – 1 nolu bakışta aynıdır, yani simetriktir ve 1-1 nolu dokümanlar ise beklenildiği aynı dokümanlar olduğu için hiç bakmaya gerek yoktur. Bu noktada sadece matris-2’deki verileri kullanılabilir. (iç içe olan for döngüsü üzerinde bir düzenleme ile veya bir if şartı ile gereksiz ver benzerlikleri kolayca göz ardı edilebilir.)
Adım 2:
Matris üzerinde en küçük değer (maksimum benzerlik) 4 ve 5. öğrenci ödevlerinin benzerlik oranını gösteren 0 değeridir. Başka bir deyişle bu iki öğrencinin ödevleri tamamen aynıdır. 4 ve 5’ten yeni bir küme üretilebilir. Şimdi birleştirme işlemini yapalım ve yeni matrisimizi oluşturalım.
4 ve 5. kişiler birinci kümemiz oldu ve birleşti. “???” li kısımların hesabını yapalım. Bu noktada “???” kısımlar farklı şekillerde hesaplanabilir.
Hiyerarşik Kümeleme Hesaplama Yöntemleri: Tek Bağlantı (Single-Link), Tam Bağlantı (Complete-Link) ve Ortalama Bağlantı (Average-Link) Kriterleri 
Hiyerarşik kümelemede, sayısal değerler üzerinden farklı hesaplama yöntemlerine göre bir küme üretilir. Bu noktada üç farklı Tek Bağlantı, Tam Bağlantı ve Ortalama Grup yöntemlerinden biri kullanılabilir.
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.
Adım 3:
Her döngünün sonunda küme sayısı 1 azalır ve küme sayısı 1 oluncaya kadar aynı işlemler tekrar eder. Her adım sonunda bir birleşim işlemi olur. Adım adım oluşan kümeler / ilişkileri ve seçilen minimum değerler aşağıda verilmiştir.
Bu aşamada küme sayısına karar vermek gerekir. Küme sayısı karar vermek için dendrogram kullanılır.
Dendrogram
Dendrogram tüm nesnelerin ilişkilerini gösteren bir ağaç yapısı oluşur. Bu grafik, küme sayısını belirlemede kolaylık sağlar. Küme sayısı belirlemek için kesme değeri belirlenmelidir. Ödevlerde benzerlik kaçınılmaz bir
Öncelikle (4, 5)’in 0 değeri çizilmiş ardından (3, 6)’nın 0.004 değeri çizilmiştir. Bu şekilde tüm kümeleme sonuçlarının çizimini yapılır. Ödev değerlendirmede dendrogram sayesinde öğretim üyesi çok rahat şekilde yapılan ödevleri yorumlayabilir. Örneğin 4 ve 5 nolu öğrencilerin aynı ödevi gönderdiği 3 ile 6 nolu öğrencilerin ise çok az bir farklılık içerdiğini görmektedir. 1 nolu öğrencinin 3 ve 6 nolu öğrencilere benzer bir ödev yaptığı görülmektedir. Bu benzerlik öğretim üyesi tarafından kopya oluşturacağı düşünülürse 0.161 büyük bir kesme değeri seçilebilir. Eğer farklı bir ödev yaptığı düşüncesinde ise şekildeki gibi 0.15 kesme değerini seçebilir. Bu kesme değeri kullanıldığında 1, (3, 6), 2, (4, 5) olmak üzere 4 adet küme oluşmaktadır. 1 ve 2 nolu öğrenciler orjinal ödev yaptığı görülmektedir.
Cophenetic Korelasyon Katsayısı
Örnekte tek bağlantı kriterini kullandık. Ancak, bu yöntemin tüm problemlere karşı en iyi kriter olduğunu söylemek zordur. Bu noktada tam bağlantı ve ortalama kriterlerini de hesaba katıp en iyi kriteri seçmek için cophenetic korelasyon sayısı kullanılır. Bu katsayıyı hesaplamak için aşağıdaki formül kullanılır.
Y ve Z hiyerarşik kümelemeden çıkan sonuçlardan elde edilen matristir. ks matris içinde i<j bölümünde bulunan eleman sayısıdır. Bu değerler üzerinden cophenetic korelasyon katsayısına (c) hesaplanır. Hiyerarşik kümeleme işlemindeki örnek veriler üzerinden cophenetic korelasyon katsayısı bulalım.
Y matrisi başlangıç değerlerini içerir. Z matrisi oluşturulurken ise Tablo 1’deki değerler göz önüne alınır. Örneğin 1, (3, 6) değeri 0.161 Z matrisindeki (1,3) ve (1,6)’ya yazılır. Bu örnek için c değeri %87.02’dir. Hiyerarşik kümelemede metotların ve algoritmaların uygunluğu c değerinin yüksek çıkması ile ölçülebilir.
Hiyerarşik kümeleme çok farklı alanlarda kullanılabilecek bir kümeleme algoritmasıdır. ADYS (Akıllı Ders Yönetim Sistemi) geliştirilirken en önemli parçalarından biri olan ödev değerlendirme sürecinde bu algoritma kullanılmıştır. Bu algoritma sayesinde ödevleri değerlendirme ve orjinal ödevleri tespit etme süreci çok hızlanmıştır.
Teşekkür
Namık Kemal Üniversitesi Rektörlüğüne, Bilimsel Araştırma Projelerine (NKUBAP.00.17.AR.13.15), Bölümüme, Bilgi İşlem Daire Başkanlığı’na, uygulama için önerilerde bulunan hocalarımıza ve projeyi değerlendiren hakemlere desteklerinden dolayı  teşekkür eder,  geliştirilen yazılımın tüm üniversitemizde eğitime olumlu bir etki yapmasını dileriz.
Referanslar