Kümeleme yöntemi, bir dizi nesneyi, aynı gruptaki diğer sektörlerdeki nesnelere göre birbirine daha çok benzeyecek şekilde gruplandırma görevidir. Veri madenciliğinin birincil görevidir ve makine öğrenimi, örüntü tanıma, görüntü tanıma, bilgi alma, veri sıkıştırma ve bilgisayar grafikleri dahil olmak üzere birçok alanda kullanılan genel bir istatistiksel analiz tekniğidir.
Optimizasyon sorunu
Kümeleme yönteminin kendisi belirli bir algoritma değil, çözülmesi gereken genel bir görevdir. Bu, bir grubu neyin oluşturduğunu ve onu verimli bir şekilde nasıl bulacağını anlamada önemli ölçüde farklılık gösteren çeşitli algoritmalarla başarılabilir. Metakonuların oluşumu için kümeleme yönteminin kullanımı, bir grubun kullanımını içerir.üyeler arasındaki küçük mesafeler, yoğun uzay bölgeleri, aralıklar veya belirli istatistiksel dağılımlar. Bu nedenle, kümeleme çok amaçlı bir optimizasyon problemi olarak formüle edilebilir.
Uygun yöntem ve parametre ayarları (kullanılacak mesafe işlevi, yoğunluk eşiği veya beklenen kümelerin sayısı gibi öğeler dahil), bireysel veri kümesine ve sonuçların kullanım amacına bağlıdır. Analiz, otomatik bir görev değil, yinelemeli bir bilgi keşfi veya etkileşimli çok amaçlı optimizasyon sürecidir. Bu kümeleme yöntemi, deneme yanılma denemelerini içerir. Sonuç istenen özellikleri elde edene kadar genellikle veri ön işleme ve model parametrelerini değiştirmek gerekir.
"Kümeleme" terimine ek olarak, otomatik sınıflandırma, sayısal taksonomi, hemrioloji ve tipolojik analiz dahil olmak üzere benzer anlamlara sahip birkaç kelime vardır. Küçük farklılıklar genellikle metakonu ilişkileri oluşturmak için kümeleme yönteminin kullanımında yatmaktadır. Veri çıkarmada ortaya çıkan gruplar ilgi çekerken, otomatik sınıflandırmada zaten bu işlevleri gerçekleştiren ayırt edici güçtür.
Küme analizi, 1932'de Kroeber'in çok sayıda çalışmasına dayanıyordu. Psikolojiye 1938'de Zubin ve 1939'da Robert Tryon tarafından tanıtıldı. Ve bu çalışmalar Cattell tarafından 1943'ten beri teoride kümeleme yöntemlerinin sınıflandırılmasını belirtmek için kullanılmaktadır.
Dönem
"Küme" kavramı tam olarak tanımlanamaz. Bu kadar çok kümeleme yönteminin olmasının nedenlerinden biri de budur. Ortak bir payda vardır: bir grup veri nesnesi. Ancak, farklı araştırmacılar farklı modeller kullanır. Ve kümeleme yöntemlerinin bu kullanımlarının her biri farklı verileri içerir. Çeşitli algoritmalar tarafından bulunan konsept, özellikleri bakımından önemli ölçüde farklılık gösterir.
Kümeleme yöntemini kullanmak, talimatlar arasındaki farkları anlamanın anahtarıdır. Tipik küme desenleri şunları içerir:
- Centroid s. Bu, örneğin, k-ortalama kümelemesinin her kümeyi bir ortalama vektörle temsil etmesi durumudur.
- Bağlantı modeli s. Bu, örneğin, uzak bağlantıya dayalı modeller oluşturan hiyerarşik kümelemedir.
- Dağıtım modeli s. Bu durumda, kümeler, metakonu istatistiksel dağılımlarını oluşturmak için kümeleme yöntemi kullanılarak modellenir. Beklenti maksimizasyon algoritması için geçerli olan çok değişkenli normal ayırma gibi.
- Yoğunluk modeli s. Bunlar, örneğin, kümeleri veri alanında birbirine bağlı yoğun bölgeler olarak tanımlayan DBSCAN (Gürültü ile Mekansal Kümeleme Algoritması) ve OPTICS (Yapı Algılama için Sipariş Noktaları)'dir.
- Altuzay modeli c. İkili kümelemede (birlikte kümeleme veya iki mod olarak da bilinir), gruplar her iki öğeyle ve uygun niteliklerle modellenir.
- Modeller. Bazı algoritmalarmeta-konu sonuçları oluşturmak ve basitçe bilgi gruplaması sağlamak için kümeleme yöntemleri için rafine ilişki.
- Grafiklere dayalı model. Bir klik, yani kenar kısımdaki her iki bağlantının küme şeklinin bir prototipi olarak kabul edilebileceği şekilde düğümlerin bir alt kümesi. Toplam talebin zayıflaması yarı klikler olarak bilinir. HCS kümeleme algoritmasında tam olarak aynı ad sunulur.
- Sinir modelleri s. En iyi bilinen denetimsiz ağ, kendi kendini organize eden haritadır. Ve genellikle, meta-konu sonuçlarının oluşturulması için yukarıdaki kümeleme yöntemlerinden bir veya daha fazlasına benzer olarak karakterize edilebilen bu modellerdir. Sinir ağları gerekli temel veya bağımsız bileşen analizi biçimini uyguladığında alt uzay sistemlerini içerir.
Bu terim aslında, genellikle veri kümeleme yöntemleri kümesindeki tüm nesneleri içeren bu tür gruplar kümesidir. Ek olarak, kümelerin birbirleriyle olan ilişkisini, örneğin birbirine yerleşik sistemler hiyerarşisini gösterebilir. Gruplandırma aşağıdaki yönlere ayrılabilir:
- Sert merkezi kümeleme yöntemi. Burada her nesne bir gruba aittir veya onun dışındadır.
- Yumuşak veya bulanık sistem. Bu noktada, her nesne zaten belirli bir ölçüde herhangi bir kümeye aittir. Ayrıca c-aracı bulanık kümeleme yöntemi olarak da adlandırılır.
Ve daha ince farklılıklar da mümkündür. Örneğin:
- Sıkı bölümleme kümeleme. Buradaher nesne tam olarak bir gruba aittir.
- Aykırı değerlerle katı bölümleme kümeleme. Bu durumda nesneler de herhangi bir kümeye ait olmayabilir ve gereksiz olarak kabul edilebilir.
- Örtüşen kümeleme (ayrıca, birden çok görünümle alternatif). Burada nesneler birden fazla şubeye ait olabilir. Tipik olarak katı kümeler içerir.
- Hiyerarşik kümeleme yöntemleri. Bir alt gruba ait olan nesneler de ana alt sisteme aittir.
- Altuzay oluşumu. Eşsiz olarak tanımlanmış bir sistem içinde, çakışan kümelere benzer olsa da, karşılıklı gruplar çakışmamalıdır.
Talimatlar
Yukarıda belirtildiği gibi, kümeleme algoritmaları küme modellerine göre sınıflandırılabilir. Aşağıdaki inceleme, bu talimatların yalnızca en belirgin örneklerini listeleyecektir. 100'den fazla yayınlanmış algoritma olabileceğinden, hepsi kümeleri için model sağlamaz ve bu nedenle kolayca sınıflandırılamaz.
Objektif olarak doğru bir kümeleme algoritması yoktur. Ancak, yukarıda belirtildiği gibi, talimat her zaman gözlemcinin görüş alanındadır. Belirli bir problem için en uygun kümeleme algoritması, bir modeli diğerine tercih etmek için matematiksel bir neden olmadıkça, genellikle deneysel olarak seçilmelidir. Tek bir tür için tasarlanmış bir algoritmanın genellikle çalışmadığına dikkat edilmelidir.kökten farklı bir konu içeren bir veri kümesi. Örneğin, k-araçları dışbükey olmayan grupları bulamaz.
Bağlantı tabanlı kümeleme
Bu birlik aynı zamanda hiyerarşik model adıyla da bilinir. Nesnelerin çok daha uzaktakilerden çok komşu parçalara bağlı olduğu tipik fikrine dayanır. Bu algoritmalar nesneleri birbirine bağlayarak uzaklıklarına bağlı olarak farklı kümeler oluşturur. Bir grup, esas olarak, kümenin farklı kısımlarını birbirine bağlamak için gereken maksimum mesafe ile tanımlanabilir. Mümkün olan tüm mesafelerde, bir dendrogram kullanılarak temsil edilebilecek başka gruplar oluşacaktır. Bu, "hiyerarşik kümeleme" ortak adının nereden geldiğini açıklar. Yani, bu algoritmalar veri kümesinin tek bir bölümünü sağlamaz, bunun yerine kapsamlı bir yetki düzeni sağlar. Belli mesafelerde birbiri ile dren olması onun sayesindedir. Bir dendrogramda, y ekseni, kümelerin bir araya geldiği mesafeyi gösterir. Ve nesneler, grupların karışmaması için X çizgisi boyunca düzenlenir.
Bağlantıya dayalı kümeleme, mesafeleri hesaplama şekillerinde farklılık gösteren bütün bir yöntem ailesidir. Mesafe fonksiyonlarının olağan seçimine ek olarak, kullanıcının bağlantı kriterine de karar vermesi gerekir. Bir küme birkaç nesneden oluştuğundan, onu hesaplamak için birçok seçenek vardır. Popüler bir seçim, tek kollu gruplama olarak bilinir, yöntem budurUPGMA veya WPGMA (ortalama bağlantı kümeleme olarak da bilinen aritmetik ortalamalı ağırlıksız veya ağırlıklı çiftler topluluğu) içeren tam bağlantı. Ek olarak, hiyerarşik sistem kümeleyici (bireysel öğelerle başlayıp bunları gruplar halinde birleştirerek) veya bölücü (tam bir veri kümesiyle başlayıp bölümlere ayırarak) olabilir.
Dağıtılmış kümeleme
Bu modeller, bölünmelere dayalı istatistiklerle en yakından ilişkilidir. Kümeler, büyük olasılıkla aynı dağılıma ait olan nesneler olarak kolayca tanımlanabilir. Bu yaklaşımın kullanışlı bir özelliği, yapay veri kümelerinin oluşturulma şekline çok benzer olmasıdır. Bir dağıtımdan rastgele nesneleri örnekleyerek.
Bu yöntemlerin teorik temeli mükemmel olsa da, modelin karmaşıklığına sınırlar getirilmedikçe, fazla uydurma olarak bilinen bir anahtar sorundan muzdariptirler. Daha büyük bir ilişkilendirme genellikle verileri daha iyi açıklayarak doğru yöntemi seçmeyi zorlaştırır.
Gauss karışım modeli
Bu yöntem her türlü beklenti maksimizasyon algoritmasını kullanır. Burada, veri kümesi genellikle rastgele başlatılan ve parametreleri veri kümesine daha iyi uyacak şekilde yinelemeli olarak optimize edilen sabit sayıda (geçersiz kılmayı önlemek için) Gauss dağılımıyla modellenir. Bu sistem yerel bir optimuma yakınsar. Bu yüzden birkaç koşu verebilirfarklı sonuçlar. En sıkı kümelemeyi elde etmek için, özellikler genellikle ait oldukları Gauss dağılımına atanır. Daha yumuşak gruplar için bu gerekli değildir.
Dağıtım tabanlı kümeleme, nitelikler arasındaki korelasyonu ve bağımlılığı eninde sonunda yakalayabilen karmaşık modeller oluşturur. Ancak bu algoritmalar kullanıcıya ek bir yük getirmektedir. Birçok gerçek dünya veri seti için, kısaca tanımlanmış bir matematiksel model olmayabilir (örneğin, bir Gauss dağılımını varsaymak oldukça güçlü bir varsayımdır).
Yoğunluğa dayalı kümeleme
Bu örnekte, gruplar temel olarak veri kümesinin geri kalanından daha yüksek geçirimsizliğe sahip alanlar olarak tanımlanır. Tüm bileşenleri ayırmak için gerekli olan bu nadir parçalardaki nesneler genellikle gürültü ve kenar noktaları olarak kabul edilir.
En popüler yoğunluğa dayalı kümeleme yöntemi DBSCAN'dır (Uzamsal Gürültü Kümeleme Algoritması). Birçok yeni yöntemin aksine, "yoğunluk erişilebilirliği" adı verilen iyi tanımlanmış bir küme bileşenine sahiptir. Bağlantı tabanlı kümelemeye benzer şekilde, belirli mesafe eşikleri içindeki bağlantı noktalarına dayanır. Ancak bu yöntem, yalnızca yoğunluk kriterini karşılayan öğeleri toplar. Bu yarıçaptaki minimum diğer nesne sayısı olarak tanımlanan orijinal versiyonda, küme tüm nesnelerden oluşur.yoğunlukla ilgili öğeler (diğer birçok yöntemin aksine serbest biçimli bir grup oluşturabilir) ve izin verilen aralıktaki tüm nesneler.
DBSCAN'ın bir başka ilginç özelliği de karmaşıklığının oldukça düşük olmasıdır - veritabanına karşı doğrusal sayıda aralık sorgusu gerektirir. Ayrıca, her çalıştırmada temelde aynı sonuçları bulması da olağandışıdır (bu, çekirdek ve gürültü noktaları için belirleyicidir, ancak sınır öğeleri için değildir). Bu nedenle, birden çok kez çalıştırmanıza gerek yoktur.
DBSCAN ve OPTICS'in ana dezavantajı, küme sınırlarını algılamak için yoğunlukta bir miktar düşüş beklemeleridir. Örneğin, çakışan Gauss dağılımlarına sahip veri kümelerinde (yapay nesneler için yaygın bir kullanım durumu) bu algoritmalar tarafından oluşturulan küme sınırları genellikle keyfi görünür. Bunun nedeni, grupların yoğunluğunun sürekli olarak azalmasıdır. Ve bir Gauss karışım veri kümesinde, bu algoritmalar neredeyse her zaman bu tür sistemleri doğru bir şekilde modelleyebilen EM kümeleme gibi yöntemlerden daha iyi performans gösterir.
Ortalama yer değiştirme, tüm çekirdeğin bir tahminine dayalı olarak her nesnenin komşuluktaki en yoğun alana hareket ettiği bir kümeleme yaklaşımıdır. Sonunda, nesneler yerel nüfuz edilemezlik maksimumuna yakınsar. k-araç kümelemeye benzer şekilde, bu "yoğunluk çekicileri" bir veri kümesi için temsilciler olarak hizmet edebilir. Ama ortalama kaymaDBSCAN'a benzer şekilde rastgele şekillendirilmiş kümeleri algılayabilir. Pahalı yinelemeli prosedür ve yoğunluk tahmini nedeniyle, ortalama yer değiştirme genellikle DBSCAN veya k-Means'ten daha yavaştır. Ek olarak, küme kuyruklarının aşırı parçalanmasına yol açan çekirdek yoğunluğu tahmininin düzgün olmayan davranışı nedeniyle tipik kaydırma algoritmasının yüksek boyutlu verilere uygulanabilirliği zordur.
Derecelendirme
Kümeleme sonuçlarını doğrulamak, kümelemenin kendisi kadar zordur. Popüler yaklaşımlar arasında "iç" puanlama (sistemin tek bir kalite ölçüsüne indirgendiği) ve tabii ki "dış" puanlama (kümelemenin mevcut bir "temel gerçek" sınıflandırmasıyla karşılaştırıldığı) yer alır. Ve insan uzmanın manuel puanı ve dolaylı puanı, amaçlanan uygulamada kümelemenin kullanışlılığı incelenerek bulunur.
Dahili bayrak ölçümleri, kümeleme hedefleri olarak kabul edilebilecek özellikleri temsil etme probleminden muzdariptir. Örneğin, Silhouette katsayısı tarafından verilen verileri gruplamak mümkündür, ancak bunu yapmak için bilinen verimli bir algoritma yoktur. Değerlendirme için böyle bir dahili ölçü kullanmak, optimizasyon problemlerinin benzerliğini karşılaştırmak daha iyidir.
Dış işarette de benzer sorunlar var. Bu tür "temel gerçek" etiketleri varsa, kümelemeye gerek yoktur. Ve pratik uygulamalarda genellikle böyle bir kavram yoktur. Öte yandan, etiketler veri kümesinin yalnızca bir olası bölümünü yansıtır; bu,başka (belki daha da iyi) kümeleme yoktur.
Yani bu yaklaşımların hiçbiri nihai olarak gerçek kaliteyi yargılayamaz. Ancak bu, son derece öznel olan insan değerlendirmesini gerektirir. Bununla birlikte, bu tür istatistikler, kötü kümeleri belirlemede bilgilendirici olabilir. Ancak bir kişinin öznel değerlendirmesini küçümsememek gerekir.
İç işaret
Bir kümelemenin sonucu, kendisi kümelenmiş verilere dayalı olarak değerlendirildiğinde, buna bu terim denir. Bu yöntemler genellikle en iyi sonucu, gruplar içinde yüksek ve gruplar arası benzerliği düşük olan gruplar oluşturan bir algoritmaya atar. Küme değerlendirmesinde dahili kriterleri kullanmanın dezavantajlarından biri, yüksek puanların mutlaka etkili bilgi erişim uygulamalarına yol açmamasıdır. Ayrıca, bu puan aynı modeli kullanan algoritmalara yöneliktir. Örneğin, k-ortalama kümeleme, özellik mesafelerini doğal olarak optimize eder ve buna dayalı bir iç kriter, sonuçta ortaya çıkan kümelemeyi muhtemelen olduğundan fazla tahmin edebilir.
Bu nedenle, bu değerlendirme önlemleri, bir algoritmanın diğerinden daha iyi performans gösterdiği durumlar hakkında fikir edinmek için en uygun olanıdır. Ancak bu, her bir bilginin diğerlerinden daha güvenilir sonuçlar verdiği anlamına gelmez. Böyle bir indeks tarafından ölçülen geçerlilik süresi, yapının veri setinde var olduğu iddiasına bağlıdır. Bazı türler için geliştirilen bir algoritmanın, kümenin radikal bir şekilde içermesi durumunda şansı yoktur.farklı kompozisyon veya değerlendirme farklı kriterleri ölçüyorsa. Örneğin, k-ortalama kümeleme yalnızca dışbükey kümeleri bulabilir ve birçok puan indeksi aynı formatı varsayar. Dışbükey olmayan modellere sahip bir veri kümesinde, k-ortalamaları ve tipik değerlendirme kriterlerini kullanmak uygun değildir.
Dış değerlendirme
Bu tür top oluşturma ile kümeleme sonuçları, gruplama için kullanılmayan verilere dayalı olarak değerlendirilir. Yani, bilinen sınıf etiketleri ve harici testler gibi. Bu tür sorular, önceden sınıflandırılmış bir dizi maddeden oluşur ve genellikle uzmanlar (insanlar) tarafından oluşturulur. Bu nedenle, referans kitleri değerlendirme için altın standart olarak görülebilir. Bu tür puanlama yöntemleri, kümelemenin verilen referans sınıflarına ne kadar yakın olduğunu ölçer. Ancak son zamanlarda bunun gerçek veriler için mi yoksa sadece gerçek temel gerçeği olan sentetik kümeler için mi yeterli olduğu tartışıldı. Sınıflar iç yapı içerebileceğinden ve mevcut öznitelikler kümelerin ayrılmasına izin vermeyebilir. Ayrıca, bilgi keşfi bakış açısından, bilinen gerçekleri yeniden üretmek, her zaman beklenen sonucu vermeyebilir. Gruplama sürecinde meta bilgilerin (sınıf etiketleri gibi) zaten kullanıldığı özel bir kısıtlı kümeleme senaryosunda, değerlendirme amacıyla tüm bilgileri saklamak önemsiz değildir.
Artık kümeleme yöntemlerine neyin uygulanmadığı ve bu amaçlar için hangi modellerin kullanıldığı açık.
