34 Graflarda Kümeler Bulmak

k-means alternasyonu, graf Laplacian’ı ve Fiedler vektörüyle spektral kümeleme

Bölüm bilgisi

Sinyal/CNN/graf bloğunu kapatan ders: bir grafı bölmenin görünür kombinatoryal sorusunu sürekli bir özvektör problemine çeviren spektral kümeleme. Strang’in Ders 35 videosu (≈35 dk) ve OCW Lecture 35 temel alınmıştır. Okuma süresi ≈24 dk. Önkoşul Ders 4-6 (spektral teorem/PSD), Ders 19 (özvektör/maxmin) ve Ders 30-32 (sirkülant/Fourier/Kronecker — graf Laplacian’ı bu dünyaların graf hali).

34.1 Bu Derste Ne Var?

Bloğun graf kısmı: büyük bir grafı anlamlı kümelere ayırmak. İki nokta kümesine bölmek için üç yaklaşım var; en zarifi spektral kümeleme — graf Laplacian’ının Fiedler vektörü kümeleri doğrudan verir.

Beş sonuç:

Graf kümeleme problemi: Grafı iki (≈eşit boyutlu) kümeye ayır. Hedef: $\min \sum_{a_i \in A} \|a_i - x\|^2 + \sum_{b_i \in B} \|b_i - y\|^2$ (artı boyut dengesi).
k-means (k=2): Kümeler verilince centroid’leri ($x, y$) bul ↔︎ centroid’ler verilince her nokta en yakın merkeze; yakınsayana dek alternasyon.
Spektral kümeleme: “spektral” = özdeğer. Graf Laplacian’ı $L = A^T A = D - B$ (incidence$^T$ × incidence = derece − komşuluk); simetrik PSD.
$\lambda_1 = 0$ + Fiedler: $L$ tekildir, $L\mathbf{1}=0$ (özvektör tüm-birler). Fiedler vektörü = en küçük pozitif özdeğerin özvektörü.
Kümeler Fiedler işaretlerinden: Fiedler vektörünün pozitif bileşenleri bir küme, negatif bileşenleri öteki. (Fiedler $\perp \mathbf{1}$ olduğundan bileşenleri 0’a toplanır.)

flowchart TD
    C["grafi iki kumeye ayir"]

    C --> KM["k-means (k=2):<br/>centroid &lt;-&gt; en yakina ata<br/>(Lloyd alternasyonu)"]
    C --> SP["spektral kumeleme"]

    SP --> S1["dort matris: incidence A,<br/>degree D, adjacency B,<br/>Laplacian L = A^T A = D - B<br/>(simetrik PSD)"]
    SP --> S2["lambda_1 = 0:<br/>L 1 = 0 (sabit ozvektor)"]
    SP --> S3["Fiedler = en kucuk<br/>POZITIF ozdegerin ozvektoru"]
    SP --> S4["kumeler = Fiedler bilesen<br/>ISARETLERI (+ / -); dik 1 -&gt; dengeli"]

    K1["D5-6 PSD + D19 ozvektor"]
    K2["D31 graf Fourier + D32<br/>Kronecker Laplacian"]
    K3["GCN/GNN (NYU H13)"]
    K4["D36 Edelman/Julia SON DERS (sonraki)"]

    K1 --> S1
    K2 --> S1
    S3 --> K3
    S4 --> K4

    classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff;
    classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff;
    classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330;
    classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff;

    class C merkez;
    class KM,SP,S1,S2,S3,S4 dal;
    class K1,K2 vec;
    class K3,K4 teal;

Şekil 34.1: Ders 35 kavram haritasi: merkez bir grafi iki kumeye ayir. Iki yaklasim: k-means (k=2) centroid ile en yakina ata arasinda Lloyd alternasyonu; spektral kumeleme grafin matrislerini kullanir. Spektral dal: dort matris incidence A, degree D, adjacency B, Laplacian L = A^T A = D - B (simetrik PSD); lambda_1 = 0 cunku L 1 = 0 (sabit ozvektor); Fiedler = en kucuk POZITIF ozdegerin ozvektoru; kumeler Fiedler bilesen isaretlerinden (+ / -) okunur, dik 1 oldugundan dengeli boluner. Koprular: D5-6 PSD + D19 ozvektor; D31 graf Fourier + D32 Kronecker Laplacian; GCN/GNN (NYU H13); D36 Edelman/Julia SON DERS (sonraki).

Şekil 34.1 dersin iskeletini gösterir: merkezdeki grafi iki kümeye ayır düğümünden iki yol çıkar. İlk yol k-means (k=2) — centroid ile en yakına ata arasında Lloyd alternasyonu. İkinci yol spektral kümeleme; bu dal grafın matrislerini kullanır. Spektral dalın alt-dalları dört anahtar matrisi (incidence $A$, degree $D$, adjacency $B$, Laplacian $L = A^T A = D - B$, simetrik PSD), $\lambda_1 = 0$ özdeşliğini ($L\mathbf{1}=0$, sabit özvektör), Fiedler tanımını (en küçük pozitif özdeğerin özvektörü) ve son adımı (kümeler Fiedler bileşen işaretlerinden, $\perp \mathbf{1}$ olduğundan dengeli) gösterir. Köprü düğümleri dersi öncesine ve sonrasına bağlar: D5-6 PSD + D19 özvektör; D31 graf Fourier + D32 Kronecker Laplacian; GCN/GNN (NYU H13); ve D36 Edelman/Julia, kursun SON dersi (sonraki).

Builder Notu — Kombinatoriği Özdeğere Çevirmek

Graf Laplacian’ı = lineer cebir × graf teorisi köprüsü: dört anahtar matris — incidence (m×n), degree (köşegen), adjacency, Laplacian ($L=D-B=A^TA$).
Spektral kümeleme = özvektörle kümeleme: graf yapısını özdeğer/özvektöre çevirir; GNN/GCN’lerin (graf sinir ağları) matematiksel atası.
k-means = en temel denetimsiz öğrenme: centroid alternasyonu (Lloyd algoritması); yakınsama teorisi zayıf ama pratikte çok kullanılır.
Geriye köprü: Ders 5-6 (PSD/SVD), Ders 19 (maxmin/özvektör), Ders 30-31 (sirkülant/Fourier — graf Laplacian’ı döngüsel grafta sirkülant). Paralel: NYU H13 spektral GCN (Bresson, laplacian-smoothness/ChebNet), fast.ai embedding.

Bir grafı bölmek görünüşte kombinatoryal bir tercih (hangi düğüm hangi tarafta) gibidir; bu dersin numarası onu sürekli bir özvektör problemine çevirir. Okurken aynı $L=D-B$ matrisinin iki yüzünü ara: incidence çarpımı ($A^TA$) onu PSD yapar, derece-eksi-komşuluk biçimi ise $L\mathbf{1}=0$’ı görünür kılar.

34.2 1. Graf Kümeleme Problemi

Büyük bir grafın düğümlerini iki kümeye ayırmak istiyoruz — iki makul-eşit parça arasında iyi bir “cut” (kesim) bulan bir algoritma.

“…clustering for graphs. …you’ve got a giant graph. And then the job is to make some sense out of it.” — Strang, 0:00

Düğümleri A (merkez $x$) ve B (merkez $y$) olarak böl; amaç toplam uzaklık-karesini en aza indirmek:

\[\min \sum_{a_i \in A} \|a_i - x\|^2 + \sum_{b_i \in B} \|b_i - y\|^2\]

A ∪ B = tüm düğümler, A ∩ B = ∅. Ek koşul: |A| ≈ |B| (dengeli kümeler — yoksa “bir düğüm + gerisi” gibi değersiz bir kesim çıkar).

“…I probably want to impose some condition that the number of a’s is reasonably close to the number of b’s.” — Strang, 4:03

Builder Notu — İyi Kesim Dengeli Kesimdir

“Graf kümeleme = dengeli iyi kesim” temel bir ağ analizi problemi. ML köprüsü: topluluk tespiti (community detection) sosyal ağlarda, görüntü segmentasyonu (normalized cut), öneri sistemlerinde kullanıcı/ürün gruplama. Denge koşulu kritik — saf min-cut tek bir düğümü ayırarak hile yapabilir, bu yüzden dengeli kesim aranır.

34.3 2. k-means Algoritması (Centroid Alternasyonu)

İlk yöntem k-means (burada k=2: A ve B’ye bölme). İki adım arasında dönüşümlü çalışır.

Adım 1 — Kümeler verili → centroid’ler. A kümesi verilince en iyi $x$, A’nın centroid’idir (ağırlık merkezi): noktaların ortalaması.

“…X is the centroid of the a’s. …it’s the sum of the a’s… divided by the number of a’s.” — Strang, 6:07

\[x = \frac{1}{|A|}\sum_{a_i \in A} a_i, \qquad y = \frac{1}{|B|}\sum_{b_i \in B} b_i\]

Adım 2 — Centroid’ler verili → kümeler. Her düğümü, $x$ ile $y$’den hangisine yakınsa o kümeye ata.

“…each node goes with the closer of x and y.” — Strang, 10:20

Sonra Adım 1’e dön (yeni centroid’ler), tekrar Adım 2… Kümeler değişmeyince algoritma yakınsamıştır. Strang: düzgün bir yakınsama/yakınsama-hızı teorisi yok, ama çok popüler bir yöntem.

Kod

from matplotlib.patches import FancyBboxPatch

fig, axes = plt.subplots(1, 2, figsize=(10.5, 4))

# ---- Sol: Egz3 1D k-means ----
ax = axes[0]
labels, cx, cy, hist = kmeans2([1., 2, 9, 10], [1.], [10.])
pts = [1., 2., 9., 10.]
ax.scatter(pts, [0]*4, color=COL_PRIMARY, s=100, zorder=3)
for p in pts:
    ax.text(p, -0.32, f"{p:.0f}", ha="center", va="center", color=COL_TEXT, fontsize=11, fontweight="bold")
ax.scatter([1., 10.], [0.15, 0.15], marker="*", color=COL_VEC3, s=200, zorder=4, label="baslangic")
ax.scatter([1.5, 9.5], [-0.15, -0.15], marker="s", color=COL_TEAL, s=150, zorder=4, label="yeni centroid")
ax.annotate("atama: {1,2} sol kume, {9,10} sag kume — tek turda yakinsadi",
            xy=(5.5, 0.42), ha="center", va="center", color=COL_TEXT, fontsize=8.5)
ax.set_ylim(-0.6, 0.6)
ax.set_yticks([])
ax.legend(loc="lower center", fontsize=8, ncol=2, frameon=False)
ax.set_title("Egz3: tek turda yakinsadi", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax)

# ---- Sag: alternasyon dongusu ----
ax2 = axes[1]
ax2.axis("off")
ax2.set_xlim(0, 10); ax2.set_ylim(0, 10)
box1 = FancyBboxPatch((1.2, 6.6), 7.6, 1.9, boxstyle="round,pad=0.1",
                      facecolor=COL_PRIMARY, edgecolor=COL_PRIMARY, alpha=0.92, zorder=2)
ax2.add_patch(box1)
ax2.text(5.0, 7.55, "Adim 1: kumeler verili -> centroid = ortalama",
         ha="center", va="center", color=COL_WHITE, fontsize=9.5, fontweight="bold", zorder=3)
box2 = FancyBboxPatch((1.2, 1.5), 7.6, 1.9, boxstyle="round,pad=0.1",
                      facecolor=COL_VEC3, edgecolor=COL_VEC3, alpha=0.92, zorder=2)
ax2.add_patch(box2)
ax2.text(5.0, 2.45, "Adim 2: centroidler verili -> en yakina ata",
         ha="center", va="center", color=COL_WHITE, fontsize=9.5, fontweight="bold", zorder=3)
ax2.annotate("", xy=(7.6, 6.5), xytext=(7.6, 3.5),
             arrowprops=dict(arrowstyle="->", color=COL_TEXT, lw=1.8,
                             connectionstyle="arc3,rad=0.35"))
ax2.annotate("", xy=(2.4, 3.5), xytext=(2.4, 6.5),
             arrowprops=dict(arrowstyle="->", color=COL_TEXT, lw=1.8,
                             connectionstyle="arc3,rad=0.35"))
ax2.text(5.0, 5.0, "kumeler degismeyince DUR (Lloyd)",
         ha="center", va="center", color=COL_TEXT, fontsize=9, fontweight="bold", zorder=3)

fig.suptitle("k-means (k=2): ata ve yeniden-hesapla alternasyonu — yakinsama teorisi zayif ama pratikte cok populer",
             color=COL_TEXT, fontsize=11.5, fontweight="bold", y=1.02)
fig.tight_layout()
plt.show()

Şekil 34.2: k-means (k=2): ata ve yeniden-hesapla alternasyonu — yakinsama teorisi zayif ama pratikte cok populer. Sol: Egz3 {1,2,9,10}, baslangic centroidleri 1 ve 10 -> kumeler {1,2} ve {9,10}, yeni centroidler 1.5 ve 9.5, tek turda yakinsadi. Sag: Lloyd alternasyonu — Adim 1 (kumeler -> centroid = ortalama) ve Adim 2 (centroidler -> en yakina ata) doneru, kumeler degismeyince durur.

Şekil 34.2 Lloyd alternasyonunu hem somut bir örnekte hem şema olarak gösterir. Solda Egzersiz 3’ün durumu: doğru üzerindeki noktalar $\{1, 2, 9, 10\}$ (navy), başlangıç centroidleri $x=1$ ve $y=10$ (turuncu yıldız). Tek turda atama $\{1,2\}$’yi sol kümeye, $\{9,10\}$’u sağ kümeye gönderir; yeni centroidler ortalamalardır — 1.5 ve 9.5 (teal kareler). Bir sonraki atama hiçbir düğümü değiştirmez, yani algoritma tek turda yakınsadı. Sağdaki şema iki adımı kapatır: navy kutu “kümeler verili → centroid = ortalama”, turuncu kutu “centroidler verili → en yakına ata”; çift ok döngüyü, ortadaki not “kümeler değişmeyince DUR (Lloyd)” durdurma koşulunu gösterir. Yakınsama teorisi zayıf olsa da pratikte bu basit alternasyon her yerde kullanılır.

Builder Notu — Ata ve Yeniden Hesapla

“k-means = ata ↔︎ yeniden-hesapla alternasyonu” denetimsiz öğrenmenin klasiğidir (Lloyd algoritması). ML köprüsü: kümeleme (müşteri segmentasyonu, görüntü renk nicemleme), vektör nicemleme (VQ) ve embedding kümeleme. Zayıflıkları: yerel minimuma takılır (başlangıca duyarlı; k-means++ ile iyileştirilir), küme sayısı k önceden verilmelidir. EM algoritmasının sert-atama (hard assignment) halidir.

34.4 3. Spektral Kümeleme ve Spektral Teorem

İkinci yöntem spektral kümeleme. Önce: “spektral” ne demek?

“…spectral clustering is using the eigenvalues of some matrix.” — Strang, 12:20

Spektrum = bir matrisin özdeğerleri. Spektral kümeleme, grafa bağlı bir matrisin özdeğer/özvektörlerini kullanır. Dayanağı spektral teorem: simetrik bir $S$ için özdeğerler gerçeldir, özvektörler ortogonaldir — $\lambda=5$ dört kez tekrarlasa bile, ona karşılık dört bağımsız ve ortogonal özvektör bulunur (yalnız simetrik matrislerde garanti).

“…for a symmetric matrix S, the eigenvalues are real, and the eigenvectors are orthogonal.” — Strang, 14:21

Builder Notu — Adını Özdeğerden Alır

“Spektral = özdeğer dünyası” — ad buradan gelir. ML köprüsü: spektral kümeleme, spektral graf teorisi ve PCA (Ders 7) hep “doğru matrisin özvektörleri yapıyı açığa çıkarır” fikrini paylaşır. Spektral teoremin ortogonal-özvektör garantisi (Ders 4-5) bu yöntemleri sağlam kılar — kümeleri ortogonal eksenlere yansıtırsın.

34.5 4. Graf Laplacian’ı: Dört Anahtar Matris

Spektral kümeleme graf Laplacian’ı ile başlar — lineer cebirin graf teorisine en önemli köprüsü. Her grafın dört temel matrisi vardır:

Incidence (geliş) matrisi A: m×n (kenar × düğüm); her satır bir kenar, başladığı düğümde −1, bittiği düğümde +1.
Degree (derece) matrisi D: n×n köşegen; her düğümün kenar sayısı.
Adjacency (komşuluk) matrisi B: n×n; köşegen 0, bağlı düğüm çiftinde 1.
Laplacian L: iki eşdeğer biçim —

\[L = A^T A = D - B\]

“…this Laplacian is symmetric, positive, semi-definite.” — Strang, 16:25

A incidence matrisi olduğundan $A^T A$ simetrik PSD’dir; aynı matris $D-B$’ye (derece eksi komşuluk) eşittir. Köşegende dereceler, köşegen-dışında bağlı çiftlerde −1 oturur.

Kod

A, D, B, L = graph_matrices(4, EDGES_EX1)

fig, axes = plt.subplots(1, 4, figsize=(12.5, 3.4))
heatmap(axes[0], A, title="incidence A (5x4)", cmap=DIVERGE, fmt="{:.0f}")
heatmap(axes[1], D, title="degree D = diag(2,3,3,2)", fmt="{:.0f}")
heatmap(axes[2], B, title="adjacency B", fmt="{:.0f}")
heatmap(axes[3], L, title="L = D - B = A^T A", cmap=DIVERGE, fmt="{:.0f}")
fig.suptitle("Bir grafin dort matrisi (Egz1 grafi): L = A^T A = D - B BIREBIR — simetrik PSD, satir toplamlari 0",
             color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.93])
plt.show()

Şekil 34.3: Bir grafın dört matrisi (Egz1 grafı): L = AᵀA = D − B BİREBİR — simetrik PSD, satır toplamları 0.

Şekil 34.3 Egzersiz 1 grafının (kenarlar (1-2),(1-3),(2-3),(2-4),(3-4)) dört matrisini yan yana koyar. Soldaki incidence $A$ ($5\times4$) her satırda bir kenarı kodlar — başlangıçta −1, bitişte +1 (turuncu/navy diverging renk). Derece matrisi $D = \mathrm{diag}(2,3,3,2)$ köşegende düğüm derecelerini taşır; adjacency $B$ bağlı çiftleri işaretler. Sağdaki Laplacian $L = D - B = A^T A$ iki yoldan da birebir aynı çıkar: köşegende dereceler, köşegen-dışında bağlı çiftlerde −1; her satır toplamı sıfır. $A^TA$ biçimi onu simetrik PSD yapar, $D-B$ biçimi $L\mathbf{1}=0$’ı görünür kılar — bir sonraki bölümün başlangıç noktası.

Builder Notu — Bir Grafın Dört Matrisi

“L = AᵀA = D − B” graf teorisinin lineer cebir kalbidir. ML köprüsü: graf sinir ağları (GCN) tam bu Laplacian’ı (ya da normalize edilmiş halini) kullanır — komşu bilgisini toplama (message passing) bir Laplacian çarpımıdır. Spektral graf teorisi; ağ analizi (PageRank akrabası), kümeleme ve yarı-denetimli öğrenmenin temelidir.

34.6 5. λ₁ = 0 ve Fiedler Vektörü

$L$ PSD’dir, ama tekil mi? $Lx=0$’ın sıfırdan farklı çözümü var mı?

“…the vector of all 1’s will be a solution to Lx equals 0.” — Strang, 20:32

Evet: tüm-birler vektörü $(1,1,\dots,1)$ her zaman $Lx=0$ sağlar (her satırın toplamı sıfır — derece eksi komşu sayısı). Yani:

\[L\mathbf{1} = 0, \qquad \lambda_1 = 0\]

ve karşılık gelen özvektör sabittir $(C,C,\dots,C)$. Bu, her bağlı grafta olur (boş-uzay boyutu 1). Graf kümelemenin fikri: bir sonraki özvektöre bak — en küçük pozitif özdeğerin ($\lambda_2$) özvektörü:

“…this is called the Fiedler vector, named after the Czech mathematician.” — Strang, 22:38

Bu Fiedler vektörü (Çek matematikçi Fiedler’den). $\lambda_2$ ve özvektörü, grafın bağlantı yapısını taşır.

Kod

fig, (axL, axR) = plt.subplots(1, 2, figsize=(10.5, 4.2))

# ---- Sol: Egz1 grafı spektrumu ----
_, _, _, L = graph_matrices(4, EDGES_EX1)
lam = np.linalg.eigvalsh(L)            # (0, 2, 4, 4)
colors = [COL_VEC3, COL_TEAL, COL_PRIMARY, COL_PRIMARY]
axL.bar(range(4), lam, color=colors, edgecolor=COL_TEXT, linewidth=0.8)
axL.text(0, 0.18, "λ₁ = 0\n(L·1 = 0)", ha="center", va="bottom", color=COL_VEC3, fontsize=9, fontweight="bold")
axL.text(1, lam[1] + 0.12, "Fiedler\nözdeğeri", ha="center", va="bottom", color=COL_TEAL, fontsize=9, fontweight="bold")
for k in (2, 3):
    axL.text(k, lam[k] + 0.12, f"{lam[k]:.0f}", ha="center", va="bottom", color=COL_PRIMARY, fontsize=9, fontweight="bold")
axL.set_xticks(range(4)); axL.set_xticklabels(["λ₁", "λ₂", "λ₃", "λ₄"])
axL.set_ylim(0, 4.8); axL.set_ylabel("özdeğer")
axL.set_title("Egz1 grafı spektrumu", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(axL)

# ---- Sağ: yol-grafı 1−2−3−4 ----
_, _, _, Lp = graph_matrices(4, EDGES_PATH4)
lam2p, fp, _ = fiedler(Lp)             # λ₂ = 2−√2 ≈ 0.586, işaretler (+,+,-,-)
node_x = np.arange(4)
node_cols = [COL_PRIMARY if fp[i] > 0 else COL_VEC3 for i in range(4)]
# üst şerit: düğümler + kenar çizgileri
y_top = 0.9
for a, b in EDGES_PATH4:
    axR.plot([node_x[a], node_x[b]], [y_top, y_top], color=COL_ACCENT, linewidth=2.0, zorder=1)
axR.scatter(node_x, [y_top] * 4, c=node_cols, s=260, edgecolors=COL_TEXT, linewidths=1.0, zorder=2)
for i in range(4):
    axR.text(node_x[i], y_top, str(i + 1), ha="center", va="center", color=COL_WHITE, fontsize=9, fontweight="bold", zorder=3)
# alt: Fiedler bileşenleri bar
axR.bar(node_x, fp, color=node_cols, edgecolor=COL_TEXT, linewidth=0.8, width=0.55, zorder=2)
axR.axhline(0, color=COL_TEXT, linewidth=0.9)
axR.annotate("işaretler (+,+,−,−) → kümeler {1,2} {3,4};\nλ₂ = 2 − √2 = 0.586",
             xy=(1.5, fp.min()), xytext=(1.5, -1.15), ha="center", va="top",
             color=COL_TEXT, fontsize=8.5, fontweight="bold")
axR.set_xticks(node_x); axR.set_xticklabels(["1", "2", "3", "4"])
axR.set_ylim(-1.45, 1.25); axR.set_xlabel("düğüm")
axR.set_title("yol-grafı 1−2−3−4: Fiedler vektörü", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(axR)

fig.suptitle("λ₁ = 0 daima (tüm-birler); sıradaki özvektör FIEDLER — bileşenleri 0'a toplanır (dik 1), işaretler kümeyi söyler",
             color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 34.4: λ₁ = 0 daima (tüm-birler özvektörü); sıradaki özvektör FIEDLER — bileşenleri 0’a toplanır (1’e dik), işaretleri kümeyi söyler. Sol: Egz1 grafının spektrumu (0, 2, 4, 4) — λ₂ = 2 Fiedler özdeğeri. Sağ: yol-grafı 1−2−3−4’te Fiedler işaretleri (+,+,−,−) → kümeler {1,2} ve {3,4}, λ₂ = 2 − √2 = 0.586.

Şekil 34.4 $\lambda_1=0$’dan Fiedler’e geçişi iki grafta gösterir. Solda Egzersiz 1 grafının spektrumu: özdeğerler $(0, 2, 4, 4)$. İlk bar (turuncu) $\lambda_1=0$ — tüm-birler özvektörü, $L\mathbf{1}=0$; ikinci bar (teal) $\lambda_2=2$, Fiedler özdeğeri; kalan ikisi (navy) $\lambda_3=\lambda_4=4$. Sağda yol-grafı 1−2−3−4: üstteki şerit dört düğümü çizgisel bağlar, düğüm renkleri Fiedler işaretine göredir (pozitif navy / negatif turuncu); alttaki bar Fiedler bileşenlerini gösterir. İşaretler (+,+,−,−) çıkar — yani kümeler $\{1,2\}$ ve $\{3,4\}$, yolu tam ortasından keser. Fiedler vektörü $\mathbf{1}$’e dik olduğundan bileşenleri 0’a toplanır; $\lambda_2 = 2 - \sqrt{2} \approx \textbf{0.586}$ (bilinen kapalı-form, motorla birebir).

Builder Notu — Sıfırdan Sonraki İlk Özvektör

“λ₁=0 (sabit özvektör), λ₂ = Fiedler” graf Laplacian’ının imzasıdır. ML köprüsü: λ₂ (cebirsel bağlantısallık, algebraic connectivity) grafın ne kadar “iyi bağlı” olduğunu ölçer — 0’a yakınsa graf neredeyse iki parçaya ayrık demektir. Fiedler vektörü, manifold öğrenmede (Laplacian eigenmaps) ve GCN’de en düşük-frekanslı graf modudur (Ders 31 Fourier ile akraba: Laplacian özvektörleri = graf Fourier tabanı).

$\lambda_2$’nin “cebirsel bağlantısallık” olduğunu somutlaştırmak için, planted (iki-topluluk) grafı köprülü ve köprüsüz haliyle yan yana koyalım:

Kod

n, edges, truth = make_two_community()
_, _, _, L1 = graph_matrices(n, edges)
lamA = np.linalg.eigvalsh(L1)[:5]

edges_cut = [e for e in edges if not (e[0] < 6 <= e[1])]
_, _, _, L2m = graph_matrices(n, edges_cut)
lamB = np.linalg.eigvalsh(L2m)[:5]

fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4))

# Sol: köprülü graf spektrumu (ilk 5)
colsA = [COL_VEC3, COL_TEAL, COL_PRIMARY, COL_PRIMARY, COL_PRIMARY]
axL.bar(range(1, 6), lamA, color=colsA, edgecolor=COL_TEXT, linewidth=0.8)
axL.text(1, lamA[0] + 0.05, "lambda_1=0", ha="center", va="bottom", color=COL_VEC3, fontsize=9, fontweight="bold")
axL.text(2, lamA[1] + 0.05, "lambda_2 = 0.536", ha="center", va="bottom", color=COL_TEAL, fontsize=9, fontweight="bold")
axL.set_title("koprulu graf: lambda_2 > 0", color=COL_TEXT, fontsize=12, fontweight="bold")
axL.set_xlabel("ozdeger indeksi"); axL.set_ylabel("ozdeger")
apply_style(axL)

# Sağ: köprüler kesik graf spektrumu (ilk 5)
colsB = [COL_VEC3, COL_VEC3, COL_PRIMARY, COL_PRIMARY, COL_PRIMARY]
axR.bar(range(1, 6), lamB, color=colsB, edgecolor=COL_TEXT, linewidth=0.8)
axR.annotate("bos-uzay boyutu 2 = iki ayri bilesen", xy=(1.5, 0.02), xytext=(2.4, max(lamB) * 0.5),
             ha="center", color=COL_TEXT, fontsize=9, fontweight="bold",
             arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.4))
axR.set_title("kopruler kesik: lambda_2 = 0", color=COL_TEXT, fontsize=12, fontweight="bold")
axR.set_xlabel("ozdeger indeksi"); axR.set_ylabel("ozdeger")
apply_style(axR)

fig.suptitle("lambda_2 = cebirsel baglantisallik: 0 a yaklastikca graf kopmaya yaklasir — Fiedler ozdegerinin anlami",
             color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout()
plt.show()

Şekil 34.5: λ₂ = cebirsel bağlantısallık: köprülü grafta λ₂ = 0.536 > 0; köprüler kesilince λ₁ = λ₂ = 0 (boş-uzay boyutu 2 = iki ayrı bileşen). Sıfıra yaklaşan λ₂, grafın kopmaya yaklaştığını söyler — Fiedler özdeğerinin anlamı.

Şekil 34.5 $\lambda_2$’nin grafın “ne kadar bağlı” olduğunu nasıl ölçtüğünü doğrudan gösterir. Solda iki-topluluk grafının ilk beş özdeğeri: $\lambda_1=0$ (turuncu), $\lambda_2 = \textbf{0.536}$ (teal) — köprü kenarları zayıf olduğundan $\lambda_2$ küçük ama pozitif kalır; graf tek parçadır. Sağda aynı graftan iki köprü kenarı kesilmiştir: şimdi $\lambda_1 = \lambda_2 = \textbf{0}$ (iki turuncu bar) — boş-uzay boyutu 2’ye çıkar, çünkü graf iki ayrı bileşene düşmüştür. Bu, “$\lambda_2$ bağlantıyı ölçer” tanığının çekirdeğidir: $\lambda_2$ sıfıra yaklaştıkça graf kopmaya yaklaşır, sıfıra ulaştığında kopmuştur.

34.7 6. Neden “Laplacian”? (Laplace Denklemi)

İsim nereden geliyor? Laplace’ın diferansiyel denkleminden.

“…it connects to Laplace’s finite difference equation.” — Strang, 24:38

Bir kare-ızgara (grid) grafında iç düğümün derecesi 4’tür; $L$’nin tipik satırı: köşegende 4, dört komşuda −1. Bu, ikinci türevlerin ayrık (finite difference) halidir:

\[\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0 \;\longrightarrow\; Lu = 0\]

İkinci x-türevi (−1, 2, −1) ile değişir, ikinci y-türevi (−1, 2, −1) ile; toplamı 5-nokta şablonu (köşegende 4, dört komşuda −1). Yani graf Laplacian’ı = ayrık Laplace operatörü.

Kod

off_defect, Lg, Lk = grid_vs_kron_defect(3)

fig, axes = plt.subplots(1, 3, figsize=(12, 4))

# --- Sol: 3x3 ızgara graf şeması ---
ax = axes[0]
coords = {}
for r in range(3):
    for c in range(3):
        coords[(r, c)] = (c, 2 - r)   # satır 0 üstte
# kenarlar (steel çizgiler)
for r in range(3):
    for c in range(3):
        if c + 1 < 3:
            (x0, y0), (x1, y1) = coords[(r, c)], coords[(r, c + 1)]
            ax.plot([x0, x1], [y0, y1], color=COL_ACCENT, lw=1.6, zorder=1)
        if r + 1 < 3:
            (x0, y0), (x1, y1) = coords[(r, c)], coords[(r + 1, c)]
            ax.plot([x0, x1], [y0, y1], color=COL_ACCENT, lw=1.6, zorder=1)
center = (1, 1)
neighbors = [(0, 1), (2, 1), (1, 0), (1, 2)]
for (r, c), (x, y) in coords.items():
    if (r, c) == center:
        ax.scatter([x], [y], s=160, color=COL_VEC3, zorder=3)
        ax.text(x, y, "4", ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold", zorder=4)
    else:
        ax.scatter([x], [y], s=120, color=COL_PRIMARY, zorder=3)
# dört komşuya "-1" turuncu etiket
for (r, c) in neighbors:
    x, y = coords[(r, c)]
    cx, cy = coords[center]
    lx, ly = x + 0.18 * (x - cx), y + 0.18 * (y - cy)
    ax.text(lx, ly, "-1", ha="center", va="center", color=COL_VEC3, fontsize=11, fontweight="bold", zorder=5)
ax.set_title("izgara grafi: ic dugum derecesi 4", color=COL_TEXT, fontsize=12, fontweight="bold")
ax.set_xlim(-0.6, 2.6); ax.set_ylim(-0.6, 2.6); ax.set_aspect("equal"); ax.axis("off")

# --- Orta: Lg heatmap ---
heatmap(axes[1], Lg, title="graf Laplacian (9x9)", cmap=DIVERGE, fmt="{:.0f}", fontsize=8)

# --- Sağ: Lk heatmap ---
heatmap(axes[2], Lk, title="Kron(A,I)+Kron(I,A) — D32", cmap=DIVERGE, fmt="{:.0f}", fontsize=8)
axes[2].annotate("kosegen-disi BIREBIR (fark 0.0); sinirda kosegen: graf 2-3 vs Dirichlet 4",
                 xy=(0.5, -0.13), xycoords="axes fraction", ha="center", va="top",
                 fontsize=8, color=COL_TEXT)

fig.suptitle("Graf Laplacian = ayrik Laplace operatoru: ic dugumde 5-nokta sablonu (4, dort -1) — D32 Kronecker toplaminin graf hali",
             color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 34.6: Graf Laplacian = ayrık Laplace operatörü: iç düğümde 5-nokta şablonu (4, dört −1) — D32 Kronecker toplamının graf hali. Sol: 3×3 ızgara grafında iç (merkez) düğümün derecesi 4, dört komşusuna −1. Orta: ızgara graf Laplacian’ı $L_g$ (9×9). Sağ: $\mathrm{Kron}(A,I)+\mathrm{Kron}(I,A)$ (D32). Köşegen-dışı BİREBİR (fark 0.0); fark yalnız sınır köşegeninde (graf derecesi 2–3 vs Dirichlet 4).

Şekil 34.6 graf Laplacian’ının ayrık Laplace operatörü olduğunu üç panelde gösterir. Solda $3\times3$ ızgara grafı: merkez (iç) düğüm derecesi 4 (turuncu), dört komşusuna −1 etiketli — tam 5-nokta şablonu. Ortada bu grafın Laplacian’ı $L_g$ ($9\times9$ heatmap), sağda Ders 32’nin Kronecker toplamı $\mathrm{Kron}(A,I)+\mathrm{Kron}(I,A)$. İki matris köşegen-dışında BİREBİR aynıdır — fark 0.0 (motor tanığı); iç düğüm satırı her ikisinde de aynı (köşegende 4, dört komşuda $-1$) şablonunu taşır. Tek fark sınır köşegenindedir: graf Laplacian’ı sınır düğümün gerçek derecesini (2 veya 3) köşegene yazarken, Dirichlet ayrık-Laplace (Kron toplamı) köşegeni hep 4 tutar. Yani köprü dürüst-etiketlidir — gövde (köşegen-dışı + iç düğümler) tıpatıp aynı, ayrılık yalnızca sınır düzeltmesinde.

Builder Notu — Izgarada Laplace ile Buluşma

“Graf Laplacian’ı = ayrık Laplace operatörü (−1,2,−1)” sürekli ile ayrık dünyanın buluştuğu yer. ML köprüsü: bu bağlantı graf üzerinde difüzyon (heat kernel), graf sinyal işleme ve fizik-bilgili ağların (PINN) PDE çözücüleriyle akrabadır. Ders 32’deki 2B Laplacian = Kron(A,I)+Kron(I,A) tam bu 5-nokta şablonun Kronecker halidir — burada gördüğümüz gibi, köşegen-dışı birebir, fark yalnız sınırda.

34.8 7. Kümeleri Fiedler İşaretlerinden Bulmak

Son adım: Fiedler vektörü kümeleri nasıl verir?

“…the positive components of x… and there are negative components… And those are the two clusters.” — Strang, 28:46

Fiedler vektörünün pozitif bileşenleri bir kümeye, negatif bileşenleri öteki kümeye gider. Her düğümün Fiedler bileşeninin işaretine bakarsın — artılar A, eksiler B.

Neden mantıklı? Fiedler vektörü, sabit $(1,\dots,1)$ özvektörüne ortogonaldir (simetrik matrisin farklı özdeğerli özvektörleri ortogonaldir):

“…to be orthogonal to this guy means that your components add to 0.” — Strang, 30:46

\[x_2 \perp \mathbf{1} \;\Rightarrow\; \sum_i (x_2)_i = 0\]

Yani pozitif ve negatif bileşenler aynı toplam büyüklüğe sahiptir → doğal olarak ~dengeli iki küme. Daha çok küme istersen ilk k özvektörü kullanırsın ($\lambda_1=0$’ı atlayıp sonrakileri).

Kod

n, edges, truth = make_two_community()
acc, fv, l2 = spectral_cluster_accuracy(n, edges, truth)
pos = community_layout(n, truth)

fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 4.6))

# Sol: graf çizimi — köprü kenarları turuncu kalın, düğümler Fiedler işaret renkleri
for e in edges:
    a, b = e
    if e[0] < 6 <= e[1]:
        axL.plot([pos[a, 0], pos[b, 0]], [pos[a, 1], pos[b, 1]], color=COL_VEC3, lw=2.5, zorder=1)
    else:
        axL.plot([pos[a, 0], pos[b, 0]], [pos[a, 1], pos[b, 1]], color=COL_ACCENT, lw=0.8, zorder=1)
node_colors = [COL_PRIMARY if fv[i] > 0 else COL_VEC3 for i in range(n)]
axL.scatter(pos[:, 0], pos[:, 1], c=node_colors, s=160, zorder=3, edgecolors=COL_WHITE, linewidths=1.2)
for i in range(n):
    axL.text(pos[i, 0], pos[i, 1], str(i + 1), ha="center", va="center", color=COL_WHITE, fontsize=8, fontweight="bold", zorder=4)
axL.set_title("iki-topluluk grafı: Fiedler 12/12 doğru (acc 1.0)", color=COL_TEXT, fontsize=12, fontweight="bold")
axL.set_aspect("equal")
apply_style(axL)
axL.set_xticks([]); axL.set_yticks([])

# Sağ: Fiedler bileşenleri bar (aynı işaret renkleri)
axR.bar(range(n), fv, color=node_colors)
axR.axhline(0, color=COL_STEEL_300, lw=1.0)
axR.annotate("lambda_2 = 0.536 (zayıf köprü)", xy=(0.5, 0.92), xycoords="axes fraction", ha="left", va="top", fontsize=10, color=COL_TEXT, fontweight="bold")
axR.set_xlabel("düğüm")
axR.set_ylabel("Fiedler bileşeni")
axR.set_title("işaretler kümeleri TAM ayırır", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(axR)

fig.suptitle("Spektral kümeleme: Laplacian'ın ikinci özvektörü (Fiedler) graf yapısını taşır — kombinatorik problem lineer cebire döner", color=COL_TEXT, fontsize=12, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 34.7: Spektral kümeleme (iki-topluluk grafı): Fiedler vektörünün işaretleri 12/12 düğümü doğru kümeler (acc 1.0); zayıf köprülerle λ₂ = 0.536, köprüsüz iki bileşende λ₂ = 0 — Laplacian’ın ikinci özvektörü graf yapısını taşır, kombinatorik kümeleme problemi lineer cebire döner.

Şekil 34.7 dersin flagship sonucudur: Fiedler işaretleri gerçek kümeleri tam ayırır. Solda iki-topluluk grafı — iki yoğun (tam-bağlı) altıdüğüm bloğu, aralarında iki zayıf köprü kenarı (turuncu kalın); düğüm renkleri Fiedler işaretine göredir (pozitif navy / negatif turuncu). On iki düğümün hepsi doğru kümeye düşer: acc = 1.0, yani $12/12$ düğüm doğru sınıflanır. Sağda Fiedler bileşenleri bar olarak çizilir; işaretler temiz biçimde iki gruba ayrılır — ilk altı düğüm bir işarette, son altı düğüm tersinde, sıfır çizgisinin iki yanında. Köprüler zayıf olduğundan $\lambda_2 = \textbf{0.536}$ küçük ama pozitiftir; köprüler tümüyle kesilse graf iki bileşene düşer ve $\lambda_2 = 0$ olurdu (önceki Şekil 34.5’nin sonucu). Görünüşte kombinatoryal olan “hangi düğüm hangi tarafta” sorusu, tek bir özvektörün işaretine indirgenir.

Builder Notu — İşaretler Kümeleri Söyler

“Kümeler = Fiedler bileşen işaretleri” zarif bir hile. ML köprüsü: bu, spektral kümelemenin özüdür — Laplacian’ın düşük özvektörleri düğümleri düşük-boyutlu bir uzaya gömer, orada işaret (ya da k-means) kümeleri ayırır. scikit-learn SpectralClustering tam bunu yapar; görüntü segmentasyonu (normalized cut) ve topluluk tespitinde standarttır. ⊥(1,…,1) koşulu dengeli kesimi otomatik teşvik eder.

34.9 Bu Dersin Özeti

Graf kümeleme: grafı 2 dengeli kümeye böl; $\min \sum \|a_i - x\|^2 + \sum \|b_i - y\|^2$ ($|A| \approx |B|$).
k-means (k=2): centroid hesapla ↔︎ en yakına yeniden ata, yakınsayana dek alternasyon (Lloyd algoritması).
Graf Laplacian: $L = A^T A = D - B$ (incidence/degree/adjacency); simetrik PSD. Dört anahtar graf matrisi.
λ₁=0: $L\mathbf{1}=0$, özvektör sabit $(1,\dots,1)$; Fiedler = en küçük pozitif özdeğerin ($\lambda_2$) özvektörü.
Spektral kümeleme: Fiedler bileşen işaretleri iki kümeyi verir ($\perp(1,\dots,1)$ → dengeli). Daha çok küme için ilk k özvektör.
Neden Laplacian: grid’de 5-nokta şablon (köşegen 4, dört −1) = ayrık Laplace operatörü.

Tek Bir Cümle

Bir grafı iki kümeye ayırmak için ya k-means (centroid alternasyonu) ya da spektral kümeleme kullanılır; spektral yöntem graf Laplacian’ı $L=D-B=A^TA$’nın Fiedler vektörünü ($\lambda_1=0$’dan sonraki en küçük pozitif özdeğer) hesaplayıp düğümleri bu vektörün bileşen işaretlerine göre ($\perp(1,\dots,1)$ olduğundan dengeli) böler.

34.10 Kontrol Soruları

Soru 1 — Graf kümeleme problemi nedir; denge koşulu neden gerekir

Grafın düğümlerini iki kümeye (A, B) ayırıp toplam uzaklık-karesini en aza indirmek: $\min \sum_{a_i} \|a_i-x\|^2 + \sum_{b_i} \|b_i-y\|^2$, burada $x$ ve $y$ küme merkezleri. Denge koşulu ($|A| \approx |B|$) gereklidir çünkü olmazsa çözüm “tek bir düğüm A, geri kalan hepsi B” gibi dejenere bir kesime kayar — bu kümeleme açısından değersizdir.

Soru 2 — k-means’in iki adımı nedir; ne zaman durur

Adım 1: kümeler verili → her kümenin centroid’ini (noktaların ortalaması) merkez olarak hesapla. Adım 2: centroid’ler verili → her düğümü en yakın centroid’in kümesine yeniden ata. İki adım dönüşümlü tekrarlanır; kümeler bir turda değişmezse algoritma yakınsamıştır (durur). Yerel minimuma takılabilir ve başlangıca duyarlıdır.

Soru 3 — Graf Laplacian’ı nedir; neden λ₁=0

$L = A^T A = D - B$ — A incidence, D derece (köşegen), B komşuluk matrisi; L simetrik ve pozitif yarı-tanımlıdır. $\lambda_1=0$’dır çünkü tüm-birler vektörü $(1,\dots,1)$ her zaman $L\mathbf{1}=0$ sağlar: L’nin her satırı, o düğümün derecesi eksi komşu sayısı = 0’a toplanır. Sabit vektör sıfır özdeğerli özvektördür (bağlı grafta boş-uzay boyutu 1).

Soru 4 — Fiedler vektörü kümeleri nasıl verir; sonuç neden dengeli olur

Fiedler vektörü = en küçük pozitif özdeğerin ($\lambda_2$) özvektörü. Bileşenlerinin işaretine bakarsın: pozitif bileşenli düğümler bir küme, negatif bileşenliler öteki küme. Sonuç dengeye yatkındır çünkü Fiedler vektörü sabit $(1,\dots,1)$ özvektörüne ortogonaldir → bileşenleri 0’a toplanır ($\sum_i (x_2)_i = 0$), yani pozitif ve negatif kütleler eşittir.

34.11 Egzersizler

Küçük Laplacian. 4 düğümlü graf; kenarlar (1-2), (1-3), (2-3), (2-4), (3-4). Derece matrisi $D$, komşuluk matrisi $B$ ve Laplacian $L = D - B$’yi yaz. $L$’nin her satır toplamının 0 olduğunu doğrula. (Motor tanığı: $D = \mathrm{diag}(2,3,3,2)$; $L = A^T A$ birebir (incidence kimliği); satır toplamları 0; spektrum $\lambda(L) = (0, 2, 4, 4)$.)
λ₁=0. Yukarıdaki $L$ için $(1,1,1,1)$ vektörünün $L\mathbf{1} = 0$ sağladığını göster. Bu neden her grafta olur (satır toplamı argümanı)? (Motor tanığı: $L\mathbf{1} = 0$; $\lambda_1 \approx 0$, $\lambda_2 = 2 > 0$ — graf bağlı.)
k-means elle. Doğru üzerindeki noktalar $\{1, 2, 9, 10\}$. Başlangıç centroidleri $x=1$, $y=10$. Bir tam k-means turu çalıştır (önce atama, sonra centroid güncelleme); ortaya çıkan iki küme ve yeni centroidler ne olur? (Motor tanığı: atama → kümeler $\{1,2\}$ ve $\{9,10\}$; yeni centroidler 1.5 ve 9.5; tek turda yakınsadı.)
Fiedler işareti. Bir yol-grafı 1−2−3−4’ün Fiedler vektörü kabaca $(-, -, +, +)$ işaretlidir. Hangi iki kümeyi önerir? Bu, grafın yapısına göre mantıklı mı? (Motor tanığı: işaretler $(+,+,-,-)$ (eşdeğer $-,-,+,+$) → kümeler $\{1,2\}$ ve $\{3,4\}$, yolu ortadan keser; Fiedler $\perp \mathbf{1}$ (toplam 0); $\lambda_2 = 2 - \sqrt{2} \approx \textbf{0.5858}$.)
(Ders 36 habercisi) Backprop’u (Ders 27) bir kez daha göreceğiz — ama bu kez Julia diliyle, “lineer cebir olarak temiz”. Edelman’ın yaklaşımı backprop’u neyi sadeleştirerek anlatabilir? Bir tahmin yaz — Ders 36 (son ders) Alan Edelman + Julia dilini (otomatik türev) işliyor.

34.12 Sonraki Ders

Ders 36: Alan Edelman ve Julia Dili (SON DERS). Konuk Prof. Alan Edelman, backpropagation’a (Ders 27) Julia diliyle yeni ve temiz bir bakış sunar — otomatik türevin lineer cebir olarak açık ifadesi. Kursun kapanışı; Phase 2’nin “aynı yere giden yollar” izleğinin (Karpathy micrograd + fast.ai + NYU + Strang matris-zinciri) olası beşinci bakışı.

Hazırlık

Bu dersin Egzersiz 5’inin sorduğu soruyu zihninde tut: backprop’u (Ders 27) Julia diliyle, “lineer cebir olarak temiz” yeniden görsek neyi sadeleşir? Ders 36 Alan Edelman + Julia dilini (otomatik türev) işler — kursu kapatan SON derstir. Bu derste graf yapısını özvektöre çevirdiğimiz gibi, orada da türev zincirini matris çarpımına çeviren bir bakış göreceğiz.

34.13 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
Graf kümeleme	$\min \sum \lVert a_i-x\rVert^2 + \sum \lVert b_i-y\rVert^2$ ($\lvert A\rvert \approx \lvert B\rvert$)	2m02
k-means (k=2)	centroid ↔︎ en yakına ata, alternasyon	6m07
Graf Laplacian	$L = A^T A = D - B$ (simetrik PSD)	16m25
λ₁ = 0	$L\mathbf{1} = 0$, özvektör $(1,\dots,1)$	20m32
Fiedler vektörü	$\lambda_2$ özvektörü (en küçük pozitif özdeğer)	22m38
Spektral kümeleme	Fiedler bileşen işaretleri → 2 küme	28m46

34.14 ML Bağlantıları Özeti

Graf Laplacian: GCN/GNN’in çekirdeği (message passing = Laplacian çarpımı); spektral graf teorisinin temeli.
Spektral kümeleme: scikit-learn SpectralClustering, normalized cut (görüntü segmentasyonu), topluluk tespiti.
k-means: en temel denetimsiz öğrenme (Lloyd); vektör nicemleme, müşteri segmentasyonu; EM’in sert-atama hali.
Fiedler / λ₂: cebirsel bağlantısallık; Laplacian eigenmaps (manifold öğrenme); graf Fourier tabanı (Ders 31 ile akraba).
Laplacian = ayrık Laplace: heat kernel/difüzyon, fizik-bilgili ağlar (PINN), Ders 32’nin Kronecker 2B Laplacian’ı.
Geriye köprü: Ders 5-6 (PSD/SVD), Ders 19 (özvektör/maxmin), Ders 30-32 (sirkülant/Fourier/Kronecker). Paralel: NYU H13 spektral GCN, fast.ai embedding.

Kapanış

“…those two sets of components are your… two clusters in spectral clustering.” — Strang, 30:46

Bir grafı bölmek görünüşte kombinatoryal bir problemdir; spektral kümeleme onu lineer cebire çevirir — Laplacian’ın ikinci özvektörünün (Fiedler) işaretleri kümeyi verir. Graf teorisiyle özdeğerlerin buluştuğu, Phase 2’nin sinyal/CNN/graf bloğunu kapatan nokta.

--- title: "Graflarda Kümeler Bulmak" subtitle: "k-means alternasyonu, graf Laplacian'ı ve Fiedler vektörüyle spektral kümeleme" --- ::: {.callout-note title="Bölüm bilgisi"} Sinyal/CNN/graf bloğunu kapatan ders: bir grafı bölmenin görünür kombinatoryal sorusunu sürekli bir özvektör problemine çeviren spektral kümeleme. Strang'in [Ders 35 videosu](https://www.youtube.com/watch?v=cxTmmasBiC8) (≈35 dk) ve [OCW Lecture 35](https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-35-finding-clusters-in-graphs-second-project-handwriting/) temel alınmıştır. Okuma süresi ≈24 dk. Önkoşul Ders 4-6 (spektral teorem/PSD), Ders 19 (özvektör/maxmin) ve Ders 30-32 (sirkülant/Fourier/Kronecker — graf Laplacian'ı bu dünyaların graf hali). ::: ```{python} #| echo: false """ _engine35.py — MIT 18.065 Ders 35 (Graflarda Kümeler: k-means + Spektral/Fiedler) motor + viz. Zincir: kümeleme hedefi → k-means alternasyonu (Lloyd) → dört graf matrisi (incidence/degree/ adjacency/Laplacian L=AᵀA=D−B) → λ₁=0, Fiedler → işaretlerden kümeler + grid=ayrık-Laplace köprüsü. Setup hücresi = cat. Figür testi `from _engine35 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap COL_PRIMARY = "#1f4e79"; COL_ACCENT = "#2e75b6"; COL_TEXT = "#13243a" COL_BG = "#eaf1f8"; COL_STEEL_300 = "#aac4dd"; COL_SKY_400 = "#6fa8dc" COL_WHITE = "#ffffff" COL_VEC1 = "#1f4e79"; COL_VEC2 = "#2e75b6"; COL_VEC3 = "#e67e22" COL_TEAL = "#17a2b8"; COL_PURPLE = "#6f42c1" NAVY_CMAP = LinearSegmentedColormap.from_list("strang_navy", ["#ffffff", "#cfe0f0", "#6fa8dc", "#2e75b6", "#1f4e79"]) DIVERGE = LinearSegmentedColormap.from_list("div", [COL_VEC3, "#ffffff", COL_PRIMARY]) def apply_style(ax): ax.set_facecolor(COL_WHITE); ax.grid(True, alpha=0.25, color=COL_STEEL_300, linewidth=0.8) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.tick_params(colors=COL_TEXT); ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT) return ax def heatmap(ax, M, title=None, cmap=None, annotate=True, fmt="{:.2g}", vmin=None, vmax=None, fontsize=10, text_thresh=None): M = np.asarray(M, dtype=float) if cmap is None: cmap = NAVY_CMAP if vmin is None: vmin = float(np.min(M)) if vmax is None: vmax = float(np.max(M)) if abs(vmax - vmin) < 1e-12: vmax = vmin + 1.0 ax.imshow(M, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal"); nr, nc = M.shape if text_thresh is None: text_thresh = vmin + 0.62*(vmax-vmin) if annotate and nr*nc <= 100: for i in range(nr): for j in range(nc): v = M[i, j] ax.text(j, i, fmt.format(v), ha="center", va="center", color=COL_WHITE if v >= text_thresh else COL_TEXT, fontsize=fontsize, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") # ============ GRAF MATRİSLERİ: INCIDENCE / DEGREE / ADJACENCY / LAPLACIAN ============ def graph_matrices(n, edges): """Dört anahtar matris: A (incidence m×n: −1 başlangıç, +1 bitiş), D (derece), B (komşuluk), L = D − B.""" m = len(edges) A = np.zeros((m, n)); B = np.zeros((n, n)) for k, (i, j) in enumerate(edges): A[k, i] = -1.0; A[k, j] = 1.0 B[i, j] = 1.0; B[j, i] = 1.0 D = np.diag(B.sum(axis=1)) L = D - B return A, D, B, L EDGES_EX1 = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] # Egz1 grafı (1-2),(1-3),(2-3),(2-4),(3-4) EDGES_PATH4 = [(0, 1), (1, 2), (2, 3)] # yol-grafı 1−2−3−4 (Egz4) def fiedler(L): """λ₂ (en küçük POZİTİF özdeğer) ve Fiedler vektörü — bileşen işaretleri kümeleri verir.""" lam, V = np.linalg.eigh(np.asarray(L, float)) return float(lam[1]), V[:, 1], lam # ============ k-MEANS (LLOYD ALTERNASYONU, k=2) ============ def kmeans2(points, c0, c1, iters=20): """k=2 Lloyd: ata (en yakın centroid) ↔ yeniden-hesapla (ortalama); etiket+centroid geçmişi döner.""" P = np.asarray(points, float) if P.ndim == 1: P = P[:, None] cx, cy = np.asarray(c0, float).ravel(), np.asarray(c1, float).ravel() history = [(cx.copy(), cy.copy())] labels = None for _ in range(iters): d0 = np.sum((P - cx) ** 2, axis=1); d1 = np.sum((P - cy) ** 2, axis=1) new_labels = (d1 < d0).astype(int) # 0 → cx kümesi, 1 → cy kümesi if labels is not None and np.array_equal(new_labels, labels): break # kümeler değişmedi → yakınsadı labels = new_labels if labels.sum() in (0, len(P)): # boş küme koruması break cx = P[labels == 0].mean(axis=0); cy = P[labels == 1].mean(axis=0) history.append((cx.copy(), cy.copy())) return labels, cx, cy, history # ============ İKİ-TOPLULUK (PLANTED) GRAF + SPEKTRAL KÜMELEME DEMO ============ def make_two_community(n_half=6, p_in=1.0, n_bridge=2, seed=35): """İki yoğun topluluk (tam-bağlı) + az sayıda köprü kenarı; gerçek etiketler bilinir.""" rng = np.random.default_rng(seed) n = 2 * n_half edges = [] for grp in (range(n_half), range(n_half, n)): grp = list(grp) for i in range(len(grp)): for j in range(i + 1, len(grp)): if rng.uniform() < p_in: edges.append((grp[i], grp[j])) left = rng.choice(n_half, n_bridge, replace=False) right = rng.choice(np.arange(n_half, n), n_bridge, replace=False) for a, b in zip(left, right): edges.append((int(a), int(b))) truth = np.array([0] * n_half + [1] * n_half) return n, edges, truth def spectral_cluster_accuracy(n, edges, truth): """Fiedler işaretlerinden kümeler; gerçek etiketlerle doğruluk (etiket takası dahil).""" _, _, _, L = graph_matrices(n, edges) lam2, f, lam = fiedler(L) pred = (f > 0).astype(int) acc = max(float(np.mean(pred == truth)), float(np.mean((1 - pred) == truth))) return acc, f, lam2 def community_layout(n, truth, seed=35): """Çizim için: iki topluluğu sol/sağ kümelenmiş 2D konumlara yerleştir.""" rng = np.random.default_rng(seed) pos = np.zeros((n, 2)) for i in range(n): cx = -1.6 if truth[i] == 0 else 1.6 ang = 2 * np.pi * (i % (n // 2)) / (n // 2) pos[i] = [cx + 0.85 * np.cos(ang), 0.85 * np.sin(ang)] return pos + rng.normal(0, 0.04, (n, 2)) # ============ GRID GRAFI = AYRIK LAPLACE (D32 KRONECKER KÖPRÜSÜ) ============ def grid_graph_edges(rows, cols): """rows×cols ızgara grafının kenarları (yatay + dikey komşuluklar).""" edges = [] for r in range(rows): for c in range(cols): u = r * cols + c if c + 1 < cols: edges.append((u, u + 1)) if r + 1 < rows: edges.append((u, u + cols)) return edges def lap1d(n): """1B Laplacian (−1, 2, −1) — D32 motoruyla aynı (Kronecker köprü tanığı).""" return 2 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1) def grid_vs_kron_defect(n): """[KÖPRÜ TANIĞI] n×n ızgara graf Laplacian'ı == Kron(A,I)+Kron(I,A) + SINIR FARKI. Not: graf Laplacian'ında sınır düğümün derecesi 2-3; Dirichlet ayrık-Laplace (Kron toplamı) köşegeni hep 4 tutar — fark yalnız KÖŞEGENDE (sınır düzeltmesi), köşegen-dışı BİREBİR.""" _, _, _, Lg = graph_matrices(n * n, grid_graph_edges(n, n)) Lk = np.kron(lap1d(n), np.eye(n)) + np.kron(np.eye(n), lap1d(n)) off_g = Lg - np.diag(np.diag(Lg)); off_k = Lk - np.diag(np.diag(Lk)) return float(np.max(np.abs(off_g - off_k))), Lg, Lk ``` ## Bu Derste Ne Var? {#sec-bu-derste-d35} Bloğun graf kısmı: büyük bir grafı anlamlı kümelere ayırmak. İki nokta kümesine bölmek için üç yaklaşım var; en zarifi **spektral kümeleme** — graf Laplacian'ının **Fiedler vektörü** kümeleri doğrudan verir. Beş sonuç: 1. **Graf kümeleme problemi:** Grafı iki (≈eşit boyutlu) kümeye ayır. Hedef: $\min \sum_{a_i \in A} \|a_i - x\|^2 + \sum_{b_i \in B} \|b_i - y\|^2$ (artı boyut dengesi). 2. **k-means (k=2):** Kümeler verilince centroid'leri ($x, y$) bul ↔ centroid'ler verilince her nokta en yakın merkeze; yakınsayana dek **alternasyon**. 3. **Spektral kümeleme:** "spektral" = özdeğer. Graf Laplacian'ı $L = A^T A = D - B$ (incidence$^T$ × incidence = derece − komşuluk); simetrik PSD. 4. $\lambda_1 = 0$ **+ Fiedler:** $L$ tekildir, $L\mathbf{1}=0$ (özvektör tüm-birler). **Fiedler vektörü** = en küçük **pozitif** özdeğerin özvektörü. 5. **Kümeler Fiedler işaretlerinden:** Fiedler vektörünün **pozitif** bileşenleri bir küme, **negatif** bileşenleri öteki. (Fiedler $\perp \mathbf{1}$ olduğundan bileşenleri 0'a toplanır.) ```{mermaid} %%| label: fig-kavram-haritasi-l35 %%| fig-cap: "Ders 35 kavram haritasi: merkez bir grafi iki kumeye ayir. Iki yaklasim: k-means (k=2) centroid ile en yakina ata arasinda Lloyd alternasyonu; spektral kumeleme grafin matrislerini kullanir. Spektral dal: dort matris incidence A, degree D, adjacency B, Laplacian L = A^T A = D - B (simetrik PSD); lambda_1 = 0 cunku L 1 = 0 (sabit ozvektor); Fiedler = en kucuk POZITIF ozdegerin ozvektoru; kumeler Fiedler bilesen isaretlerinden (+ / -) okunur, dik 1 oldugundan dengeli boluner. Koprular: D5-6 PSD + D19 ozvektor; D31 graf Fourier + D32 Kronecker Laplacian; GCN/GNN (NYU H13); D36 Edelman/Julia SON DERS (sonraki)." %%| echo: false flowchart TD C["grafi iki kumeye ayir"] C --> KM["k-means (k=2): centroid <-> en yakina ata (Lloyd alternasyonu)"] C --> SP["spektral kumeleme"] SP --> S1["dort matris: incidence A, degree D, adjacency B, Laplacian L = A^T A = D - B (simetrik PSD)"] SP --> S2["lambda_1 = 0: L 1 = 0 (sabit ozvektor)"] SP --> S3["Fiedler = en kucuk POZITIF ozdegerin ozvektoru"] SP --> S4["kumeler = Fiedler bilesen ISARETLERI (+ / -); dik 1 -> dengeli"] K1["D5-6 PSD + D19 ozvektor"] K2["D31 graf Fourier + D32 Kronecker Laplacian"] K3["GCN/GNN (NYU H13)"] K4["D36 Edelman/Julia SON DERS (sonraki)"] K1 --> S1 K2 --> S1 S3 --> K3 S4 --> K4 classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff; classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff; classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330; classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff; class C merkez; class KM,SP,S1,S2,S3,S4 dal; class K1,K2 vec; class K3,K4 teal; ``` @fig-kavram-haritasi-l35 dersin iskeletini gösterir: merkezdeki **grafi iki kümeye ayır** düğümünden iki yol çıkar. İlk yol k-means (k=2) — centroid ile en yakına ata arasında Lloyd alternasyonu. İkinci yol spektral kümeleme; bu dal grafın matrislerini kullanır. Spektral dalın alt-dalları dört anahtar matrisi (incidence $A$, degree $D$, adjacency $B$, Laplacian $L = A^T A = D - B$, simetrik PSD), $\lambda_1 = 0$ özdeşliğini ($L\mathbf{1}=0$, sabit özvektör), Fiedler tanımını (en küçük pozitif özdeğerin özvektörü) ve son adımı (kümeler Fiedler bileşen işaretlerinden, $\perp \mathbf{1}$ olduğundan dengeli) gösterir. Köprü düğümleri dersi öncesine ve sonrasına bağlar: D5-6 PSD + D19 özvektör; D31 graf Fourier + D32 Kronecker Laplacian; GCN/GNN (NYU H13); ve D36 Edelman/Julia, kursun SON dersi (sonraki). ::: {.callout-tip title="Builder Notu — Kombinatoriği Özdeğere Çevirmek"} - **Graf Laplacian'ı = lineer cebir × graf teorisi köprüsü:** dört anahtar matris — incidence (m×n), degree (köşegen), adjacency, Laplacian ($L=D-B=A^TA$). - **Spektral kümeleme = özvektörle kümeleme:** graf yapısını özdeğer/özvektöre çevirir; GNN/GCN'lerin (graf sinir ağları) matematiksel atası. - **k-means = en temel denetimsiz öğrenme:** centroid alternasyonu (Lloyd algoritması); yakınsama teorisi zayıf ama pratikte çok kullanılır. - **Geriye köprü:** Ders 5-6 (PSD/SVD), Ders 19 (maxmin/özvektör), Ders 30-31 (sirkülant/Fourier — graf Laplacian'ı döngüsel grafta sirkülant). Paralel: NYU H13 spektral GCN (Bresson, laplacian-smoothness/ChebNet), fast.ai embedding. Bir grafı bölmek görünüşte kombinatoryal bir tercih (hangi düğüm hangi tarafta) gibidir; bu dersin numarası onu sürekli bir özvektör problemine çevirir. Okurken aynı $L=D-B$ matrisinin iki yüzünü ara: incidence çarpımı ($A^TA$) onu PSD yapar, derece-eksi-komşuluk biçimi ise $L\mathbf{1}=0$'ı görünür kılar. ::: ## 1. Graf Kümeleme Problemi {#sec-problem} Büyük bir grafın düğümlerini iki kümeye ayırmak istiyoruz — iki makul-eşit parça arasında iyi bir "cut" (kesim) bulan bir algoritma. > *"...clustering for graphs. ...you've got a giant graph. And then the job is to make some sense out of it." — Strang, 0:00* Düğümleri A (merkez $x$) ve B (merkez $y$) olarak böl; amaç toplam uzaklık-karesini en aza indirmek: $$\min \sum_{a_i \in A} \|a_i - x\|^2 + \sum_{b_i \in B} \|b_i - y\|^2$$ A ∪ B = tüm düğümler, A ∩ B = ∅. Ek koşul: |A| ≈ |B| (dengeli kümeler — yoksa "bir düğüm + gerisi" gibi değersiz bir kesim çıkar). > *"...I probably want to impose some condition that the number of a's is reasonably close to the number of b's." — Strang, 4:03* ::: {.callout-tip title="Builder Notu — İyi Kesim Dengeli Kesimdir"} "Graf kümeleme = dengeli iyi kesim" temel bir ağ analizi problemi. ML köprüsü: topluluk tespiti (community detection) sosyal ağlarda, görüntü segmentasyonu (normalized cut), öneri sistemlerinde kullanıcı/ürün gruplama. Denge koşulu kritik — saf min-cut tek bir düğümü ayırarak hile yapabilir, bu yüzden dengeli kesim aranır. ::: ## 2. k-means Algoritması (Centroid Alternasyonu) {#sec-kmeans} İlk yöntem **k-means** (burada k=2: A ve B'ye bölme). İki adım arasında dönüşümlü çalışır. **Adım 1 — Kümeler verili → centroid'ler.** A kümesi verilince en iyi $x$, A'nın **centroid'idir** (ağırlık merkezi): noktaların ortalaması. > *"...X is the centroid of the a's. ...it's the sum of the a's... divided by the number of a's." — Strang, 6:07* $$x = \frac{1}{|A|}\sum_{a_i \in A} a_i, \qquad y = \frac{1}{|B|}\sum_{b_i \in B} b_i$$ **Adım 2 — Centroid'ler verili → kümeler.** Her düğümü, $x$ ile $y$'den **hangisine yakınsa** o kümeye ata. > *"...each node goes with the closer of x and y." — Strang, 10:20* Sonra Adım 1'e dön (yeni centroid'ler), tekrar Adım 2… Kümeler değişmeyince algoritma yakınsamıştır. Strang: düzgün bir yakınsama/yakınsama-hızı teorisi yok, ama çok popüler bir yöntem. ```{python} #| label: fig-kmeans #| fig-cap: "k-means (k=2): ata ve yeniden-hesapla alternasyonu — yakinsama teorisi zayif ama pratikte cok populer. Sol: Egz3 {1,2,9,10}, baslangic centroidleri 1 ve 10 -> kumeler {1,2} ve {9,10}, yeni centroidler 1.5 ve 9.5, tek turda yakinsadi. Sag: Lloyd alternasyonu — Adim 1 (kumeler -> centroid = ortalama) ve Adim 2 (centroidler -> en yakina ata) doneru, kumeler degismeyince durur." #| fig-width: 10.5 #| fig-height: 4 #| code-fold: true from matplotlib.patches import FancyBboxPatch fig, axes = plt.subplots(1, 2, figsize=(10.5, 4)) # ---- Sol: Egz3 1D k-means ---- ax = axes[0] labels, cx, cy, hist = kmeans2([1., 2, 9, 10], [1.], [10.]) pts = [1., 2., 9., 10.] ax.scatter(pts, [0]*4, color=COL_PRIMARY, s=100, zorder=3) for p in pts: ax.text(p, -0.32, f"{p:.0f}", ha="center", va="center", color=COL_TEXT, fontsize=11, fontweight="bold") ax.scatter([1., 10.], [0.15, 0.15], marker="*", color=COL_VEC3, s=200, zorder=4, label="baslangic") ax.scatter([1.5, 9.5], [-0.15, -0.15], marker="s", color=COL_TEAL, s=150, zorder=4, label="yeni centroid") ax.annotate("atama: {1,2} sol kume, {9,10} sag kume — tek turda yakinsadi", xy=(5.5, 0.42), ha="center", va="center", color=COL_TEXT, fontsize=8.5) ax.set_ylim(-0.6, 0.6) ax.set_yticks([]) ax.legend(loc="lower center", fontsize=8, ncol=2, frameon=False) ax.set_title("Egz3: tek turda yakinsadi", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax) # ---- Sag: alternasyon dongusu ---- ax2 = axes[1] ax2.axis("off") ax2.set_xlim(0, 10); ax2.set_ylim(0, 10) box1 = FancyBboxPatch((1.2, 6.6), 7.6, 1.9, boxstyle="round,pad=0.1", facecolor=COL_PRIMARY, edgecolor=COL_PRIMARY, alpha=0.92, zorder=2) ax2.add_patch(box1) ax2.text(5.0, 7.55, "Adim 1: kumeler verili -> centroid = ortalama", ha="center", va="center", color=COL_WHITE, fontsize=9.5, fontweight="bold", zorder=3) box2 = FancyBboxPatch((1.2, 1.5), 7.6, 1.9, boxstyle="round,pad=0.1", facecolor=COL_VEC3, edgecolor=COL_VEC3, alpha=0.92, zorder=2) ax2.add_patch(box2) ax2.text(5.0, 2.45, "Adim 2: centroidler verili -> en yakina ata", ha="center", va="center", color=COL_WHITE, fontsize=9.5, fontweight="bold", zorder=3) ax2.annotate("", xy=(7.6, 6.5), xytext=(7.6, 3.5), arrowprops=dict(arrowstyle="->", color=COL_TEXT, lw=1.8, connectionstyle="arc3,rad=0.35")) ax2.annotate("", xy=(2.4, 3.5), xytext=(2.4, 6.5), arrowprops=dict(arrowstyle="->", color=COL_TEXT, lw=1.8, connectionstyle="arc3,rad=0.35")) ax2.text(5.0, 5.0, "kumeler degismeyince DUR (Lloyd)", ha="center", va="center", color=COL_TEXT, fontsize=9, fontweight="bold", zorder=3) fig.suptitle("k-means (k=2): ata ve yeniden-hesapla alternasyonu — yakinsama teorisi zayif ama pratikte cok populer", color=COL_TEXT, fontsize=11.5, fontweight="bold", y=1.02) fig.tight_layout() plt.show() ``` @fig-kmeans Lloyd alternasyonunu hem somut bir örnekte hem şema olarak gösterir. Solda Egzersiz 3'ün durumu: doğru üzerindeki noktalar $\{1, 2, 9, 10\}$ (navy), başlangıç centroidleri $x=1$ ve $y=10$ (turuncu yıldız). Tek turda atama $\{1,2\}$'yi sol kümeye, $\{9,10\}$'u sağ kümeye gönderir; yeni centroidler ortalamalardır — **1.5** ve **9.5** (teal kareler). Bir sonraki atama hiçbir düğümü değiştirmez, yani algoritma **tek turda yakınsadı**. Sağdaki şema iki adımı kapatır: navy kutu "kümeler verili → centroid = ortalama", turuncu kutu "centroidler verili → en yakına ata"; çift ok döngüyü, ortadaki not "kümeler değişmeyince DUR (Lloyd)" durdurma koşulunu gösterir. Yakınsama teorisi zayıf olsa da pratikte bu basit alternasyon her yerde kullanılır. ::: {.callout-tip title="Builder Notu — Ata ve Yeniden Hesapla"} "k-means = ata ↔ yeniden-hesapla alternasyonu" denetimsiz öğrenmenin klasiğidir (Lloyd algoritması). ML köprüsü: kümeleme (müşteri segmentasyonu, görüntü renk nicemleme), vektör nicemleme (VQ) ve embedding kümeleme. Zayıflıkları: yerel minimuma takılır (başlangıca duyarlı; k-means++ ile iyileştirilir), küme sayısı k önceden verilmelidir. EM algoritmasının sert-atama (hard assignment) halidir. ::: ## 3. Spektral Kümeleme ve Spektral Teorem {#sec-spektral-teorem} İkinci yöntem **spektral kümeleme**. Önce: "spektral" ne demek? > *"...spectral clustering is using the eigenvalues of some matrix." — Strang, 12:20* Spektrum = bir matrisin **özdeğerleri**. Spektral kümeleme, grafa bağlı bir matrisin özdeğer/özvektörlerini kullanır. Dayanağı **spektral teorem**: simetrik bir $S$ için özdeğerler gerçeldir, özvektörler ortogonaldir — $\lambda=5$ dört kez tekrarlasa bile, ona karşılık dört bağımsız ve ortogonal özvektör bulunur (yalnız simetrik matrislerde garanti). > *"...for a symmetric matrix S, the eigenvalues are real, and the eigenvectors are orthogonal." — Strang, 14:21* ::: {.callout-tip title="Builder Notu — Adını Özdeğerden Alır"} "Spektral = özdeğer dünyası" — ad buradan gelir. ML köprüsü: spektral kümeleme, spektral graf teorisi ve PCA (Ders 7) hep "doğru matrisin özvektörleri yapıyı açığa çıkarır" fikrini paylaşır. Spektral teoremin ortogonal-özvektör garantisi (Ders 4-5) bu yöntemleri sağlam kılar — kümeleri ortogonal eksenlere yansıtırsın. ::: ## 4. Graf Laplacian'ı: Dört Anahtar Matris {#sec-dort-matris} Spektral kümeleme **graf Laplacian'ı** ile başlar — lineer cebirin graf teorisine en önemli köprüsü. Her grafın dört temel matrisi vardır: - **Incidence (geliş) matrisi A:** m×n (kenar × düğüm); her satır bir kenar, başladığı düğümde −1, bittiği düğümde +1. - **Degree (derece) matrisi D:** n×n köşegen; her düğümün kenar sayısı. - **Adjacency (komşuluk) matrisi B:** n×n; köşegen 0, bağlı düğüm çiftinde 1. - **Laplacian L:** iki eşdeğer biçim — $$L = A^T A = D - B$$ > *"...this Laplacian is symmetric, positive, semi-definite." — Strang, 16:25* A incidence matrisi olduğundan $A^T A$ simetrik PSD'dir; aynı matris $D-B$'ye (derece eksi komşuluk) eşittir. Köşegende dereceler, köşegen-dışında bağlı çiftlerde −1 oturur. ```{python} #| label: fig-dort-matris #| fig-cap: "Bir grafın dört matrisi (Egz1 grafı): L = AᵀA = D − B BİREBİR — simetrik PSD, satır toplamları 0." #| fig-width: 12.5 #| fig-height: 3.4 #| code-fold: true A, D, B, L = graph_matrices(4, EDGES_EX1) fig, axes = plt.subplots(1, 4, figsize=(12.5, 3.4)) heatmap(axes[0], A, title="incidence A (5x4)", cmap=DIVERGE, fmt="{:.0f}") heatmap(axes[1], D, title="degree D = diag(2,3,3,2)", fmt="{:.0f}") heatmap(axes[2], B, title="adjacency B", fmt="{:.0f}") heatmap(axes[3], L, title="L = D - B = A^T A", cmap=DIVERGE, fmt="{:.0f}") fig.suptitle("Bir grafin dort matrisi (Egz1 grafi): L = A^T A = D - B BIREBIR — simetrik PSD, satir toplamlari 0", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.93]) plt.show() ``` @fig-dort-matris Egzersiz 1 grafının (kenarlar (1-2),(1-3),(2-3),(2-4),(3-4)) dört matrisini yan yana koyar. Soldaki incidence $A$ ($5\times4$) her satırda bir kenarı kodlar — başlangıçta −1, bitişte +1 (turuncu/navy diverging renk). Derece matrisi $D = \mathrm{diag}(2,3,3,2)$ köşegende düğüm derecelerini taşır; adjacency $B$ bağlı çiftleri işaretler. Sağdaki Laplacian $L = D - B = A^T A$ iki yoldan da **birebir** aynı çıkar: köşegende dereceler, köşegen-dışında bağlı çiftlerde −1; her satır toplamı sıfır. $A^TA$ biçimi onu simetrik PSD yapar, $D-B$ biçimi $L\mathbf{1}=0$'ı görünür kılar — bir sonraki bölümün başlangıç noktası. ::: {.callout-tip title="Builder Notu — Bir Grafın Dört Matrisi"} "L = AᵀA = D − B" graf teorisinin lineer cebir kalbidir. ML köprüsü: graf sinir ağları (GCN) tam bu Laplacian'ı (ya da normalize edilmiş halini) kullanır — komşu bilgisini toplama (message passing) bir Laplacian çarpımıdır. Spektral graf teorisi; ağ analizi (PageRank akrabası), kümeleme ve yarı-denetimli öğrenmenin temelidir. ::: ## 5. λ₁ = 0 ve Fiedler Vektörü {#sec-fiedler} $L$ PSD'dir, ama tekil mi? $Lx=0$'ın sıfırdan farklı çözümü var mı? > *"...the vector of all 1's will be a solution to Lx equals 0." — Strang, 20:32* Evet: tüm-birler vektörü $(1,1,\dots,1)$ her zaman $Lx=0$ sağlar (her satırın toplamı sıfır — derece eksi komşu sayısı). Yani: $$L\mathbf{1} = 0, \qquad \lambda_1 = 0$$ ve karşılık gelen özvektör sabittir $(C,C,\dots,C)$. Bu, her bağlı grafta olur (boş-uzay boyutu 1). **Graf kümelemenin fikri**: bir sonraki özvektöre bak — en küçük **pozitif** özdeğerin ($\lambda_2$) özvektörü: > *"...this is called the Fiedler vector, named after the Czech mathematician." — Strang, 22:38* Bu **Fiedler vektörü** (Çek matematikçi Fiedler'den). $\lambda_2$ ve özvektörü, grafın bağlantı yapısını taşır. ```{python} #| label: fig-fiedler #| fig-cap: "λ₁ = 0 daima (tüm-birler özvektörü); sıradaki özvektör FIEDLER — bileşenleri 0'a toplanır (1'e dik), işaretleri kümeyi söyler. Sol: Egz1 grafının spektrumu (0, 2, 4, 4) — λ₂ = 2 Fiedler özdeğeri. Sağ: yol-grafı 1−2−3−4'te Fiedler işaretleri (+,+,−,−) → kümeler {1,2} ve {3,4}, λ₂ = 2 − √2 = 0.586." #| fig-width: 10.5 #| fig-height: 4.2 #| code-fold: true fig, (axL, axR) = plt.subplots(1, 2, figsize=(10.5, 4.2)) # ---- Sol: Egz1 grafı spektrumu ---- _, _, _, L = graph_matrices(4, EDGES_EX1) lam = np.linalg.eigvalsh(L) # (0, 2, 4, 4) colors = [COL_VEC3, COL_TEAL, COL_PRIMARY, COL_PRIMARY] axL.bar(range(4), lam, color=colors, edgecolor=COL_TEXT, linewidth=0.8) axL.text(0, 0.18, "λ₁ = 0\n(L·1 = 0)", ha="center", va="bottom", color=COL_VEC3, fontsize=9, fontweight="bold") axL.text(1, lam[1] + 0.12, "Fiedler\nözdeğeri", ha="center", va="bottom", color=COL_TEAL, fontsize=9, fontweight="bold") for k in (2, 3): axL.text(k, lam[k] + 0.12, f"{lam[k]:.0f}", ha="center", va="bottom", color=COL_PRIMARY, fontsize=9, fontweight="bold") axL.set_xticks(range(4)); axL.set_xticklabels(["λ₁", "λ₂", "λ₃", "λ₄"]) axL.set_ylim(0, 4.8); axL.set_ylabel("özdeğer") axL.set_title("Egz1 grafı spektrumu", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(axL) # ---- Sağ: yol-grafı 1−2−3−4 ---- _, _, _, Lp = graph_matrices(4, EDGES_PATH4) lam2p, fp, _ = fiedler(Lp) # λ₂ = 2−√2 ≈ 0.586, işaretler (+,+,-,-) node_x = np.arange(4) node_cols = [COL_PRIMARY if fp[i] > 0 else COL_VEC3 for i in range(4)] # üst şerit: düğümler + kenar çizgileri y_top = 0.9 for a, b in EDGES_PATH4: axR.plot([node_x[a], node_x[b]], [y_top, y_top], color=COL_ACCENT, linewidth=2.0, zorder=1) axR.scatter(node_x, [y_top] * 4, c=node_cols, s=260, edgecolors=COL_TEXT, linewidths=1.0, zorder=2) for i in range(4): axR.text(node_x[i], y_top, str(i + 1), ha="center", va="center", color=COL_WHITE, fontsize=9, fontweight="bold", zorder=3) # alt: Fiedler bileşenleri bar axR.bar(node_x, fp, color=node_cols, edgecolor=COL_TEXT, linewidth=0.8, width=0.55, zorder=2) axR.axhline(0, color=COL_TEXT, linewidth=0.9) axR.annotate("işaretler (+,+,−,−) → kümeler {1,2} {3,4};\nλ₂ = 2 − √2 = 0.586", xy=(1.5, fp.min()), xytext=(1.5, -1.15), ha="center", va="top", color=COL_TEXT, fontsize=8.5, fontweight="bold") axR.set_xticks(node_x); axR.set_xticklabels(["1", "2", "3", "4"]) axR.set_ylim(-1.45, 1.25); axR.set_xlabel("düğüm") axR.set_title("yol-grafı 1−2−3−4: Fiedler vektörü", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(axR) fig.suptitle("λ₁ = 0 daima (tüm-birler); sıradaki özvektör FIEDLER — bileşenleri 0'a toplanır (dik 1), işaretler kümeyi söyler", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-fiedler $\lambda_1=0$'dan Fiedler'e geçişi iki grafta gösterir. Solda Egzersiz 1 grafının spektrumu: özdeğerler $(0, 2, 4, 4)$. İlk bar (turuncu) $\lambda_1=0$ — tüm-birler özvektörü, $L\mathbf{1}=0$; ikinci bar (teal) $\lambda_2=2$, Fiedler özdeğeri; kalan ikisi (navy) $\lambda_3=\lambda_4=4$. Sağda yol-grafı 1−2−3−4: üstteki şerit dört düğümü çizgisel bağlar, düğüm renkleri Fiedler işaretine göredir (pozitif navy / negatif turuncu); alttaki bar Fiedler bileşenlerini gösterir. İşaretler **(+,+,−,−)** çıkar — yani kümeler $\{1,2\}$ ve $\{3,4\}$, yolu tam ortasından keser. Fiedler vektörü $\mathbf{1}$'e dik olduğundan bileşenleri 0'a toplanır; $\lambda_2 = 2 - \sqrt{2} \approx \textbf{0.586}$ (bilinen kapalı-form, motorla birebir). ::: {.callout-tip title="Builder Notu — Sıfırdan Sonraki İlk Özvektör"} "λ₁=0 (sabit özvektör), λ₂ = Fiedler" graf Laplacian'ının imzasıdır. ML köprüsü: λ₂ (cebirsel bağlantısallık, algebraic connectivity) grafın ne kadar "iyi bağlı" olduğunu ölçer — 0'a yakınsa graf neredeyse iki parçaya ayrık demektir. Fiedler vektörü, manifold öğrenmede (Laplacian eigenmaps) ve GCN'de en düşük-frekanslı graf modudur (Ders 31 Fourier ile akraba: Laplacian özvektörleri = graf Fourier tabanı). ::: $\lambda_2$'nin "cebirsel bağlantısallık" olduğunu somutlaştırmak için, planted (iki-topluluk) grafı köprülü ve köprüsüz haliyle yan yana koyalım: ```{python} #| label: fig-lambda2-baglanti #| fig-cap: "λ₂ = cebirsel bağlantısallık: köprülü grafta λ₂ = 0.536 > 0; köprüler kesilince λ₁ = λ₂ = 0 (boş-uzay boyutu 2 = iki ayrı bileşen). Sıfıra yaklaşan λ₂, grafın kopmaya yaklaştığını söyler — Fiedler özdeğerinin anlamı." #| fig-width: 10 #| fig-height: 4 #| code-fold: true n, edges, truth = make_two_community() _, _, _, L1 = graph_matrices(n, edges) lamA = np.linalg.eigvalsh(L1)[:5] edges_cut = [e for e in edges if not (e[0] < 6 <= e[1])] _, _, _, L2m = graph_matrices(n, edges_cut) lamB = np.linalg.eigvalsh(L2m)[:5] fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4)) # Sol: köprülü graf spektrumu (ilk 5) colsA = [COL_VEC3, COL_TEAL, COL_PRIMARY, COL_PRIMARY, COL_PRIMARY] axL.bar(range(1, 6), lamA, color=colsA, edgecolor=COL_TEXT, linewidth=0.8) axL.text(1, lamA[0] + 0.05, "lambda_1=0", ha="center", va="bottom", color=COL_VEC3, fontsize=9, fontweight="bold") axL.text(2, lamA[1] + 0.05, "lambda_2 = 0.536", ha="center", va="bottom", color=COL_TEAL, fontsize=9, fontweight="bold") axL.set_title("koprulu graf: lambda_2 > 0", color=COL_TEXT, fontsize=12, fontweight="bold") axL.set_xlabel("ozdeger indeksi"); axL.set_ylabel("ozdeger") apply_style(axL) # Sağ: köprüler kesik graf spektrumu (ilk 5) colsB = [COL_VEC3, COL_VEC3, COL_PRIMARY, COL_PRIMARY, COL_PRIMARY] axR.bar(range(1, 6), lamB, color=colsB, edgecolor=COL_TEXT, linewidth=0.8) axR.annotate("bos-uzay boyutu 2 = iki ayri bilesen", xy=(1.5, 0.02), xytext=(2.4, max(lamB) * 0.5), ha="center", color=COL_TEXT, fontsize=9, fontweight="bold", arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.4)) axR.set_title("kopruler kesik: lambda_2 = 0", color=COL_TEXT, fontsize=12, fontweight="bold") axR.set_xlabel("ozdeger indeksi"); axR.set_ylabel("ozdeger") apply_style(axR) fig.suptitle("lambda_2 = cebirsel baglantisallik: 0 a yaklastikca graf kopmaya yaklasir — Fiedler ozdegerinin anlami", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout() plt.show() ``` @fig-lambda2-baglanti $\lambda_2$'nin grafın "ne kadar bağlı" olduğunu nasıl ölçtüğünü doğrudan gösterir. Solda iki-topluluk grafının ilk beş özdeğeri: $\lambda_1=0$ (turuncu), $\lambda_2 = \textbf{0.536}$ (teal) — köprü kenarları zayıf olduğundan $\lambda_2$ küçük ama **pozitif** kalır; graf tek parçadır. Sağda aynı graftan iki köprü kenarı kesilmiştir: şimdi $\lambda_1 = \lambda_2 = \textbf{0}$ (iki turuncu bar) — boş-uzay boyutu **2**'ye çıkar, çünkü graf iki ayrı bileşene düşmüştür. Bu, "$\lambda_2$ bağlantıyı ölçer" tanığının çekirdeğidir: $\lambda_2$ sıfıra yaklaştıkça graf kopmaya yaklaşır, sıfıra ulaştığında kopmuştur. ## 6. Neden "Laplacian"? (Laplace Denklemi) {#sec-laplace} İsim nereden geliyor? Laplace'ın diferansiyel denkleminden. > *"...it connects to Laplace's finite difference equation." — Strang, 24:38* Bir kare-ızgara (grid) grafında iç düğümün derecesi 4'tür; $L$'nin tipik satırı: köşegende **4**, dört komşuda **−1**. Bu, ikinci türevlerin ayrık (finite difference) halidir: $$\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0 \;\longrightarrow\; Lu = 0$$ İkinci x-türevi (−1, 2, −1) ile değişir, ikinci y-türevi (−1, 2, −1) ile; toplamı 5-nokta şablonu (köşegende 4, dört komşuda −1). Yani graf Laplacian'ı = **ayrık Laplace operatörü**. ```{python} #| label: fig-grid-laplacian #| fig-cap: "Graf Laplacian = ayrık Laplace operatörü: iç düğümde 5-nokta şablonu (4, dört −1) — D32 Kronecker toplamının graf hali. Sol: 3×3 ızgara grafında iç (merkez) düğümün derecesi 4, dört komşusuna −1. Orta: ızgara graf Laplacian'ı $L_g$ (9×9). Sağ: $\\mathrm{Kron}(A,I)+\\mathrm{Kron}(I,A)$ (D32). Köşegen-dışı BİREBİR (fark 0.0); fark yalnız sınır köşegeninde (graf derecesi 2–3 vs Dirichlet 4)." #| fig-width: 12 #| fig-height: 4 #| code-fold: true off_defect, Lg, Lk = grid_vs_kron_defect(3) fig, axes = plt.subplots(1, 3, figsize=(12, 4)) # --- Sol: 3x3 ızgara graf şeması --- ax = axes[0] coords = {} for r in range(3): for c in range(3): coords[(r, c)] = (c, 2 - r) # satır 0 üstte # kenarlar (steel çizgiler) for r in range(3): for c in range(3): if c + 1 < 3: (x0, y0), (x1, y1) = coords[(r, c)], coords[(r, c + 1)] ax.plot([x0, x1], [y0, y1], color=COL_ACCENT, lw=1.6, zorder=1) if r + 1 < 3: (x0, y0), (x1, y1) = coords[(r, c)], coords[(r + 1, c)] ax.plot([x0, x1], [y0, y1], color=COL_ACCENT, lw=1.6, zorder=1) center = (1, 1) neighbors = [(0, 1), (2, 1), (1, 0), (1, 2)] for (r, c), (x, y) in coords.items(): if (r, c) == center: ax.scatter([x], [y], s=160, color=COL_VEC3, zorder=3) ax.text(x, y, "4", ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold", zorder=4) else: ax.scatter([x], [y], s=120, color=COL_PRIMARY, zorder=3) # dört komşuya "-1" turuncu etiket for (r, c) in neighbors: x, y = coords[(r, c)] cx, cy = coords[center] lx, ly = x + 0.18 * (x - cx), y + 0.18 * (y - cy) ax.text(lx, ly, "-1", ha="center", va="center", color=COL_VEC3, fontsize=11, fontweight="bold", zorder=5) ax.set_title("izgara grafi: ic dugum derecesi 4", color=COL_TEXT, fontsize=12, fontweight="bold") ax.set_xlim(-0.6, 2.6); ax.set_ylim(-0.6, 2.6); ax.set_aspect("equal"); ax.axis("off") # --- Orta: Lg heatmap --- heatmap(axes[1], Lg, title="graf Laplacian (9x9)", cmap=DIVERGE, fmt="{:.0f}", fontsize=8) # --- Sağ: Lk heatmap --- heatmap(axes[2], Lk, title="Kron(A,I)+Kron(I,A) — D32", cmap=DIVERGE, fmt="{:.0f}", fontsize=8) axes[2].annotate("kosegen-disi BIREBIR (fark 0.0); sinirda kosegen: graf 2-3 vs Dirichlet 4", xy=(0.5, -0.13), xycoords="axes fraction", ha="center", va="top", fontsize=8, color=COL_TEXT) fig.suptitle("Graf Laplacian = ayrik Laplace operatoru: ic dugumde 5-nokta sablonu (4, dort -1) — D32 Kronecker toplaminin graf hali", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-grid-laplacian graf Laplacian'ının ayrık Laplace operatörü olduğunu üç panelde gösterir. Solda $3\times3$ ızgara grafı: merkez (iç) düğüm derecesi **4** (turuncu), dört komşusuna **−1** etiketli — tam 5-nokta şablonu. Ortada bu grafın Laplacian'ı $L_g$ ($9\times9$ heatmap), sağda Ders 32'nin Kronecker toplamı $\mathrm{Kron}(A,I)+\mathrm{Kron}(I,A)$. İki matris **köşegen-dışında BİREBİR** aynıdır — fark **0.0** (motor tanığı); iç düğüm satırı her ikisinde de aynı (köşegende 4, dört komşuda $-1$) şablonunu taşır. Tek fark sınır köşegenindedir: graf Laplacian'ı sınır düğümün gerçek derecesini (2 veya 3) köşegene yazarken, Dirichlet ayrık-Laplace (Kron toplamı) köşegeni hep 4 tutar. Yani köprü dürüst-etiketlidir — gövde (köşegen-dışı + iç düğümler) tıpatıp aynı, ayrılık yalnızca sınır düzeltmesinde. ::: {.callout-tip title="Builder Notu — Izgarada Laplace ile Buluşma"} "Graf Laplacian'ı = ayrık Laplace operatörü (−1,2,−1)" sürekli ile ayrık dünyanın buluştuğu yer. ML köprüsü: bu bağlantı graf üzerinde difüzyon (heat kernel), graf sinyal işleme ve fizik-bilgili ağların (PINN) PDE çözücüleriyle akrabadır. Ders 32'deki 2B Laplacian = Kron(A,I)+Kron(I,A) tam bu 5-nokta şablonun Kronecker halidir — burada gördüğümüz gibi, köşegen-dışı birebir, fark yalnız sınırda. ::: ## 7. Kümeleri Fiedler İşaretlerinden Bulmak {#sec-fiedler-isaret} Son adım: Fiedler vektörü kümeleri nasıl verir? > *"...the positive components of x... and there are negative components... And those are the two clusters." — Strang, 28:46* Fiedler vektörünün **pozitif** bileşenleri bir kümeye, **negatif** bileşenleri öteki kümeye gider. Her düğümün Fiedler bileşeninin işaretine bakarsın — artılar A, eksiler B. Neden mantıklı? Fiedler vektörü, sabit $(1,\dots,1)$ özvektörüne **ortogonaldir** (simetrik matrisin farklı özdeğerli özvektörleri ortogonaldir): > *"...to be orthogonal to this guy means that your components add to 0." — Strang, 30:46* $$x_2 \perp \mathbf{1} \;\Rightarrow\; \sum_i (x_2)_i = 0$$ Yani pozitif ve negatif bileşenler aynı toplam büyüklüğe sahiptir → doğal olarak ~dengeli iki küme. Daha çok küme istersen ilk k özvektörü kullanırsın ($\lambda_1=0$'ı atlayıp sonrakileri). ```{python} #| label: fig-spektral-kumeleme #| fig-cap: "Spektral kümeleme (iki-topluluk grafı): Fiedler vektörünün işaretleri 12/12 düğümü doğru kümeler (acc 1.0); zayıf köprülerle λ₂ = 0.536, köprüsüz iki bileşende λ₂ = 0 — Laplacian'ın ikinci özvektörü graf yapısını taşır, kombinatorik kümeleme problemi lineer cebire döner." #| fig-width: 11.5 #| fig-height: 4.6 #| code-fold: true n, edges, truth = make_two_community() acc, fv, l2 = spectral_cluster_accuracy(n, edges, truth) pos = community_layout(n, truth) fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 4.6)) # Sol: graf çizimi — köprü kenarları turuncu kalın, düğümler Fiedler işaret renkleri for e in edges: a, b = e if e[0] < 6 <= e[1]: axL.plot([pos[a, 0], pos[b, 0]], [pos[a, 1], pos[b, 1]], color=COL_VEC3, lw=2.5, zorder=1) else: axL.plot([pos[a, 0], pos[b, 0]], [pos[a, 1], pos[b, 1]], color=COL_ACCENT, lw=0.8, zorder=1) node_colors = [COL_PRIMARY if fv[i] > 0 else COL_VEC3 for i in range(n)] axL.scatter(pos[:, 0], pos[:, 1], c=node_colors, s=160, zorder=3, edgecolors=COL_WHITE, linewidths=1.2) for i in range(n): axL.text(pos[i, 0], pos[i, 1], str(i + 1), ha="center", va="center", color=COL_WHITE, fontsize=8, fontweight="bold", zorder=4) axL.set_title("iki-topluluk grafı: Fiedler 12/12 doğru (acc 1.0)", color=COL_TEXT, fontsize=12, fontweight="bold") axL.set_aspect("equal") apply_style(axL) axL.set_xticks([]); axL.set_yticks([]) # Sağ: Fiedler bileşenleri bar (aynı işaret renkleri) axR.bar(range(n), fv, color=node_colors) axR.axhline(0, color=COL_STEEL_300, lw=1.0) axR.annotate("lambda_2 = 0.536 (zayıf köprü)", xy=(0.5, 0.92), xycoords="axes fraction", ha="left", va="top", fontsize=10, color=COL_TEXT, fontweight="bold") axR.set_xlabel("düğüm") axR.set_ylabel("Fiedler bileşeni") axR.set_title("işaretler kümeleri TAM ayırır", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(axR) fig.suptitle("Spektral kümeleme: Laplacian'ın ikinci özvektörü (Fiedler) graf yapısını taşır — kombinatorik problem lineer cebire döner", color=COL_TEXT, fontsize=12, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-spektral-kumeleme dersin **flagship** sonucudur: Fiedler işaretleri gerçek kümeleri tam ayırır. Solda iki-topluluk grafı — iki yoğun (tam-bağlı) altıdüğüm bloğu, aralarında iki zayıf köprü kenarı (turuncu kalın); düğüm renkleri Fiedler işaretine göredir (pozitif navy / negatif turuncu). On iki düğümün hepsi doğru kümeye düşer: **acc = 1.0**, yani $12/12$ düğüm doğru sınıflanır. Sağda Fiedler bileşenleri bar olarak çizilir; işaretler temiz biçimde iki gruba ayrılır — ilk altı düğüm bir işarette, son altı düğüm tersinde, sıfır çizgisinin iki yanında. Köprüler zayıf olduğundan $\lambda_2 = \textbf{0.536}$ küçük ama pozitiftir; köprüler tümüyle kesilse graf iki bileşene düşer ve $\lambda_2 = 0$ olurdu (önceki @fig-lambda2-baglanti'nin sonucu). Görünüşte kombinatoryal olan "hangi düğüm hangi tarafta" sorusu, tek bir özvektörün işaretine indirgenir. ::: {.callout-tip title="Builder Notu — İşaretler Kümeleri Söyler"} "Kümeler = Fiedler bileşen işaretleri" zarif bir hile. ML köprüsü: bu, spektral kümelemenin özüdür — Laplacian'ın düşük özvektörleri düğümleri düşük-boyutlu bir uzaya gömer, orada işaret (ya da k-means) kümeleri ayırır. scikit-learn `SpectralClustering` tam bunu yapar; görüntü segmentasyonu (normalized cut) ve topluluk tespitinde standarttır. ⊥(1,…,1) koşulu dengeli kesimi otomatik teşvik eder. ::: ## Bu Dersin Özeti {#sec-ozet-d35} - **Graf kümeleme:** grafı 2 dengeli kümeye böl; $\min \sum \|a_i - x\|^2 + \sum \|b_i - y\|^2$ ($|A| \approx |B|$). - **k-means (k=2):** centroid hesapla ↔ en yakına yeniden ata, yakınsayana dek alternasyon (Lloyd algoritması). - **Graf Laplacian:** $L = A^T A = D - B$ (incidence/degree/adjacency); simetrik PSD. Dört anahtar graf matrisi. - **λ₁=0:** $L\mathbf{1}=0$, özvektör sabit $(1,\dots,1)$; Fiedler = en küçük pozitif özdeğerin ($\lambda_2$) özvektörü. - **Spektral kümeleme:** Fiedler bileşen işaretleri iki kümeyi verir ($\perp(1,\dots,1)$ → dengeli). Daha çok küme için ilk k özvektör. - **Neden Laplacian:** grid'de 5-nokta şablon (köşegen 4, dört −1) = ayrık Laplace operatörü. ::: {.callout-important title="Tek Bir Cümle"} Bir grafı iki kümeye ayırmak için ya k-means (centroid alternasyonu) ya da spektral kümeleme kullanılır; spektral yöntem graf Laplacian'ı $L=D-B=A^TA$'nın Fiedler vektörünü ($\lambda_1=0$'dan sonraki en küçük pozitif özdeğer) hesaplayıp düğümleri bu vektörün bileşen işaretlerine göre ($\perp(1,\dots,1)$ olduğundan dengeli) böler. ::: ## Kontrol Soruları {#sec-sorular-d35} ::: {.callout-note collapse="true" title="Soru 1 — Graf kümeleme problemi nedir; denge koşulu neden gerekir"} Grafın düğümlerini iki kümeye (A, B) ayırıp toplam uzaklık-karesini en aza indirmek: $\min \sum_{a_i} \|a_i-x\|^2 + \sum_{b_i} \|b_i-y\|^2$, burada $x$ ve $y$ küme merkezleri. Denge koşulu ($|A| \approx |B|$) gereklidir çünkü olmazsa çözüm "tek bir düğüm A, geri kalan hepsi B" gibi dejenere bir kesime kayar — bu kümeleme açısından değersizdir. ::: ::: {.callout-note collapse="true" title="Soru 2 — k-means'in iki adımı nedir; ne zaman durur"} Adım 1: kümeler verili → her kümenin centroid'ini (noktaların ortalaması) merkez olarak hesapla. Adım 2: centroid'ler verili → her düğümü en yakın centroid'in kümesine yeniden ata. İki adım dönüşümlü tekrarlanır; kümeler bir turda değişmezse algoritma yakınsamıştır (durur). Yerel minimuma takılabilir ve başlangıca duyarlıdır. ::: ::: {.callout-note collapse="true" title="Soru 3 — Graf Laplacian'ı nedir; neden λ₁=0"} $L = A^T A = D - B$ — A incidence, D derece (köşegen), B komşuluk matrisi; L simetrik ve pozitif yarı-tanımlıdır. $\lambda_1=0$'dır çünkü tüm-birler vektörü $(1,\dots,1)$ her zaman $L\mathbf{1}=0$ sağlar: L'nin her satırı, o düğümün derecesi eksi komşu sayısı = 0'a toplanır. Sabit vektör sıfır özdeğerli özvektördür (bağlı grafta boş-uzay boyutu 1). ::: ::: {.callout-note collapse="true" title="Soru 4 — Fiedler vektörü kümeleri nasıl verir; sonuç neden dengeli olur"} Fiedler vektörü = en küçük **pozitif** özdeğerin ($\lambda_2$) özvektörü. Bileşenlerinin işaretine bakarsın: pozitif bileşenli düğümler bir küme, negatif bileşenliler öteki küme. Sonuç dengeye yatkındır çünkü Fiedler vektörü sabit $(1,\dots,1)$ özvektörüne ortogonaldir → bileşenleri 0'a toplanır ($\sum_i (x_2)_i = 0$), yani pozitif ve negatif kütleler eşittir. ::: ## Egzersizler {#sec-egzersizler-d35} 1. **Küçük Laplacian.** 4 düğümlü graf; kenarlar (1-2), (1-3), (2-3), (2-4), (3-4). Derece matrisi $D$, komşuluk matrisi $B$ ve Laplacian $L = D - B$'yi yaz. $L$'nin her satır toplamının 0 olduğunu doğrula. (Motor tanığı: $D = \mathrm{diag}(2,3,3,2)$; $L = A^T A$ **birebir** (incidence kimliği); satır toplamları 0; spektrum $\lambda(L) = (0, 2, 4, 4)$.) 2. **λ₁=0.** Yukarıdaki $L$ için $(1,1,1,1)$ vektörünün $L\mathbf{1} = 0$ sağladığını göster. Bu neden her grafta olur (satır toplamı argümanı)? (Motor tanığı: $L\mathbf{1} = 0$; $\lambda_1 \approx 0$, $\lambda_2 = 2 > 0$ — graf bağlı.) 3. **k-means elle.** Doğru üzerindeki noktalar $\{1, 2, 9, 10\}$. Başlangıç centroidleri $x=1$, $y=10$. Bir tam k-means turu çalıştır (önce atama, sonra centroid güncelleme); ortaya çıkan iki küme ve yeni centroidler ne olur? (Motor tanığı: atama → kümeler $\{1,2\}$ ve $\{9,10\}$; yeni centroidler **1.5** ve **9.5**; tek turda yakınsadı.) 4. **Fiedler işareti.** Bir yol-grafı 1−2−3−4'ün Fiedler vektörü kabaca $(-, -, +, +)$ işaretlidir. Hangi iki kümeyi önerir? Bu, grafın yapısına göre mantıklı mı? (Motor tanığı: işaretler $(+,+,-,-)$ (eşdeğer $-,-,+,+$) → kümeler $\{1,2\}$ ve $\{3,4\}$, yolu ortadan keser; Fiedler $\perp \mathbf{1}$ (toplam 0); $\lambda_2 = 2 - \sqrt{2} \approx \textbf{0.5858}$.) 5. **(Ders 36 habercisi)** Backprop'u (Ders 27) bir kez daha göreceğiz — ama bu kez Julia diliyle, "lineer cebir olarak temiz". Edelman'ın yaklaşımı backprop'u neyi sadeleştirerek anlatabilir? Bir tahmin yaz — Ders 36 (son ders) Alan Edelman + Julia dilini (otomatik türev) işliyor. ## Sonraki Ders {#sec-sonraki-d35} **Ders 36: Alan Edelman ve Julia Dili (SON DERS).** Konuk Prof. Alan Edelman, backpropagation'a (Ders 27) Julia diliyle yeni ve temiz bir bakış sunar — otomatik türevin lineer cebir olarak açık ifadesi. Kursun kapanışı; Phase 2'nin "aynı yere giden yollar" izleğinin (Karpathy micrograd + fast.ai + NYU + Strang matris-zinciri) olası beşinci bakışı. ::: {.callout-warning title="Hazırlık"} Bu dersin Egzersiz 5'inin sorduğu soruyu zihninde tut: backprop'u (Ders 27) Julia diliyle, "lineer cebir olarak temiz" yeniden görsek neyi sadeleşir? Ders 36 Alan Edelman + Julia dilini (otomatik türev) işler — kursu kapatan SON derstir. Bu derste graf yapısını özvektöre çevirdiğimiz gibi, orada da türev zincirini matris çarpımına çeviren bir bakış göreceğiz. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d35} | Kavram | Formül / Fikir | Strang (dk) | |---|---|---| | Graf kümeleme | $\min \sum \lVert a_i-x\rVert^2 + \sum \lVert b_i-y\rVert^2$ ($\lvert A\rvert \approx \lvert B\rvert$) | 2m02 | | **k-means (k=2)** | centroid ↔ en yakına ata, alternasyon | 6m07 | | Graf Laplacian | $L = A^T A = D - B$ (simetrik PSD) | 16m25 | | λ₁ = 0 | $L\mathbf{1} = 0$, özvektör $(1,\dots,1)$ | 20m32 | | Fiedler vektörü | $\lambda_2$ özvektörü (en küçük pozitif özdeğer) | 22m38 | | Spektral kümeleme | Fiedler bileşen işaretleri → 2 küme | 28m46 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d35} - **Graf Laplacian:** GCN/GNN'in çekirdeği (message passing = Laplacian çarpımı); spektral graf teorisinin temeli. - **Spektral kümeleme:** scikit-learn `SpectralClustering`, normalized cut (görüntü segmentasyonu), topluluk tespiti. - **k-means:** en temel denetimsiz öğrenme (Lloyd); vektör nicemleme, müşteri segmentasyonu; EM'in sert-atama hali. - **Fiedler / λ₂:** cebirsel bağlantısallık; Laplacian eigenmaps (manifold öğrenme); graf Fourier tabanı (Ders 31 ile akraba). - **Laplacian = ayrık Laplace:** heat kernel/difüzyon, fizik-bilgili ağlar (PINN), Ders 32'nin Kronecker 2B Laplacian'ı. - **Geriye köprü:** Ders 5-6 (PSD/SVD), Ders 19 (özvektör/maxmin), Ders 30-32 (sirkülant/Fourier/Kronecker). Paralel: NYU H13 spektral GCN, fast.ai embedding. ::: {.callout-important title="Kapanış"} > *"...those two sets of components are your... two clusters in spectral clustering." — Strang, 30:46* Bir grafı bölmek görünüşte kombinatoryal bir problemdir; spektral kümeleme onu lineer cebire çevirir — Laplacian'ın ikinci özvektörünün (Fiedler) işaretleri kümeyi verir. Graf teorisiyle özdeğerlerin buluştuğu, Phase 2'nin sinyal/CNN/graf bloğunu kapatan nokta. :::