tag GrafTeori

Spectral Clustering (Spektral Kümeleme)

Bu sayfada GrafTeori (Spectral Clustering (Spektral Kümeleme)) etiketi ile işaretlenmiş 1 yapay zeka kavramını bulabilirsiniz.

Spektral kümeleme, geleneksel mesafe tabanlı yöntemlerin yetersiz kaldığı karmaşık ve iç içe geçmiş veri yapılarını tespit edebilen, grafik teorisi ile lineer cebiri birleştiren bir kümeleme algoritmasıdır. Temel fikri, veri noktaları arasındaki benzerlik ilişkilerini bir grafik olarak modellemek ve bu grafiğin Laplacian matrisinin özvektörlerini düşük boyutlu kümeleme için kullanmaktır. Algoritmanın kökeni, 1970'lerin grafik kesim (graph partitioning) problemlerine dayanır; ancak makine öğrenmesine yönelik modern biçimlenmesi Shi ve Malik'in 2000 tarihli "Normalized Cuts and Image Segmentation" çalışmasıyla ivme kazandı. Ng, Jordan ve Weiss ise 2002'de yöntemi yaygın kullanılan standart hale getirdi. Spektral kümeleme üç temel aşamada çalışır. İlk aşamada her veri noktasını bir düğüm, iki nokta arasındaki benzerliği ise (Gauss/RBF çekirdeği ya da k-NN yöntemiyle hesaplanmış) bir kenar ağırlığı olarak tanımlayan W benzerlik matrisi oluşturulur. İkinci aşamada grafik Laplacian'ı (L = D − W veya normalize biçimi) hesaplanır ve ilk k özvektörü çıkarılır; bu özvektörler orijinal verinin küme yapısını koruyarak düşük boyutlu uzayda temsil eder. Üçüncü aşamada bu özvektör uzayındaki noktalar K-Means ile kümelenir. Bu son adım, doğrusal olmayan sınırlara sahip kümelerin bile ayrılabilir hale gelmesini sağlar. Algoritmanın en önemli avantajı şekil bağımsızlığıdır: ay biçimli (crescent), halka (ring) veya iç içe geçmiş spiral veri kümeleri gibi K-Means'in başarısız olduğu durumlarda üstün performans gösterir. Görüntü bölütleme, sosyal ağ topluluk tespiti, biyoinformatik gen ifadesi analizi ve belge kümeleme başlıca uygulama alanları arasındadır. scikit-learn kütüphanesindeki SpectralClustering sınıfı Python ekosisteminde standart uygulamayı sunar. Temel sınırlılık ölçeklenebilirlik sorunudur: Laplacian özdeğer ayrışımının O(n³) zaman karmaşıklığı büyük veri kümelerinde hesaplama yükünü artırır. Bu sorunu gidermek için Nyström yaklaşımı ve Landmark-based Spectral Clustering gibi yaklaşık yöntemler geliştirilmiştir. Küme sayısı k'nın önceden belirlenmesi zorunludur; eigengap heuristiği ile özvektörler arasındaki en büyük boşluğa bakarak k tahmini yapılabilir. Modern derin öğrenme alanında spektral yöntemler grafik sinir ağlarının (GNN) teorik temelini oluşturmaktadır: GCN (Graph Convolutional Network), ChebNet ve Graph Attention Network mimarileri doğrudan spektral grafik teorisinden türemektedir.

code_blocks

Spectral Clustering (Spektral Kümeleme)

Spektral kümeleme, geleneksel mesafe tabanlı yöntemlerin yetersiz kaldığı karmaşık ve iç içe geçmiş veri yapılarını tespit edebilen, grafik teorisi ile lineer cebiri birleştiren bir kümeleme algoritmasıdır. Temel fikri, veri noktaları arasındaki benzerlik ilişkilerini bir grafik olarak modellemek ve bu grafiğin Laplacian matrisinin özvektörlerini düşük boyutlu kümeleme için kullanmaktır. Algoritmanın kökeni, 1970'lerin grafik kesim (graph partitioning) problemlerine dayanır; ancak makine öğrenmesine yönelik modern biçimlenmesi Shi ve Malik'in 2000 tarihli "Normalized Cuts and Image Segmentation" çalışmasıyla ivme kazandı. Ng, Jordan ve Weiss ise 2002'de yöntemi yaygın kullanılan standart hale getirdi. Spektral kümeleme üç temel aşamada çalışır. İlk aşamada her veri noktasını bir düğüm, iki nokta arasındaki benzerliği ise (Gauss/RBF çekirdeği ya da k-NN yöntemiyle hesaplanmış) bir kenar ağırlığı olarak tanımlayan W benzerlik matrisi oluşturulur. İkinci aşamada grafik Laplacian'ı (L = D − W veya normalize biçimi) hesaplanır ve ilk k özvektörü çıkarılır; bu özvektörler orijinal verinin küme yapısını koruyarak düşük boyutlu uzayda temsil eder. Üçüncü aşamada bu özvektör uzayındaki noktalar K-Means ile kümelenir. Bu son adım, doğrusal olmayan sınırlara sahip kümelerin bile ayrılabilir hale gelmesini sağlar. Algoritmanın en önemli avantajı şekil bağımsızlığıdır: ay biçimli (crescent), halka (ring) veya iç içe geçmiş spiral veri kümeleri gibi K-Means'in başarısız olduğu durumlarda üstün performans gösterir. Görüntü bölütleme, sosyal ağ topluluk tespiti, biyoinformatik gen ifadesi analizi ve belge kümeleme başlıca uygulama alanları arasındadır. scikit-learn kütüphanesindeki SpectralClustering sınıfı Python ekosisteminde standart uygulamayı sunar. Temel sınırlılık ölçeklenebilirlik sorunudur: Laplacian özdeğer ayrışımının O(n³) zaman karmaşıklığı büyük veri kümelerinde hesaplama yükünü artırır. Bu sorunu gidermek için Nyström yaklaşımı ve Landmark-based Spectral Clustering gibi yaklaşık yöntemler geliştirilmiştir. Küme sayısı k'nın önceden belirlenmesi zorunludur; eigengap heuristiği ile özvektörler arasındaki en büyük boşluğa bakarak k tahmini yapılabilir. Modern derin öğrenme alanında spektral yöntemler grafik sinir ağlarının (GNN) teorik temelini oluşturmaktadır: GCN (Graph Convolutional Network), ChebNet ve Graph Attention Network mimarileri doğrudan spektral grafik teorisinden türemektedir.

arrow_forward