서술에서 주장한 것을 하나씩 재 본다.
가 정말 간선마다의 차이 제곱을 더한 것인가
영공간의 차원이 정말 연결 성분의 개수인가
가 맞는가, 레일리 몫이 정말 거기서 멈추는가
벡터에서 인가
노드 60개짜리 그래프를 피들러 벡터로 자르면 무작위보다 얼마나 나은가
RatioCut 과 Ncut 은 정말 다른 자를 쓰는가
import itertools
import numpy as np
np.set_printoptions(precision=4, suppress=True, linewidth=110)
def 결합행렬(n, 간선):
A = np.zeros((len(간선), n))
for k, (i, j) in enumerate(간선):
A[k, i] = -1.0
A[k, j] = +1.0
return A
def 라플라시안(n, 간선):
A = 결합행렬(n, 간선)
return A.T @ A
def 절단크기(간선, 한쪽):
return sum(1 for i, j in 간선 if (i in 한쪽) != (j in 한쪽))간선 = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 4), (4, 5), (3, 5)]
n = 6
A = 결합행렬(n, 간선)
L = 라플라시안(n, 간선)
print("결합행렬 A (7 x 6) — 행 하나가 간선 하나다")
print(A.astype(int))
print()
print("L = A^T A")
print(L.astype(int))결합행렬 A (7 x 6) — 행 하나가 간선 하나다
[[-1 1 0 0 0 0]
[ 0 -1 1 0 0 0]
[-1 0 1 0 0 0]
[ 0 0 -1 1 0 0]
[ 0 0 0 -1 1 0]
[ 0 0 0 0 -1 1]
[ 0 0 0 -1 0 1]]
L = A^T A
[[ 2 -1 -1 0 0 0]
[-1 2 -1 0 0 0]
[-1 -1 3 -1 0 0]
[ 0 0 -1 3 -1 -1]
[ 0 0 0 -1 2 -1]
[ 0 0 0 -1 -1 2]]
print("행마다의 합 :", L.sum(axis=1).astype(int), "-> 전부 0이면 L 1 = 0")
print("L @ 1 :", (L @ np.ones(n)).astype(int))
print()
차수 = L.diagonal().astype(int)
값, 벡 = np.linalg.eigh(L)
print(f"tr L = {np.trace(L):.0f}")
print(f"차수의 합 = {차수.sum()}")
print(f"2 |E| = {2 * len(간선)}")
print(f"고윳값의 합 = {값.sum():.10f}")행마다의 합 : [0 0 0 0 0 0] -> 전부 0이면 L 1 = 0
L @ 1 : [0 0 0 0 0 0]
tr L = 14
차수의 합 = 14
2 |E| = 14
고윳값의 합 = 14.0000000000
셋이 전부 14다. 고윳값을 다 더하면 간선 수의 두 배라는 것이 (9)였다.
그러면 본론이다. 아무 나 넣어 두 가지 방법으로 세어 본다. 왼쪽은 행렬로, 오른쪽은 간선을 하나씩 돌면서.
난수 = np.random.default_rng(37)
print(f"{'행렬로 xT L x':>16} {'간선을 돌면서':>16} {'차이':>10}")
for _ in range(6):
x = 난수.normal(size=n)
행렬로 = x @ L @ x
간선으로 = sum((x[i] - x[j]) ** 2 for i, j in 간선)
print(f"{행렬로:16.10f} {간선으로:16.10f} {abs(행렬로 - 간선으로):10.1e}") 행렬로 xT L x 간선을 돌면서 차이
11.6623833292 11.6623833292 3.6e-15
31.7853075737 31.7853075737 0.0e+00
12.5432845829 12.5432845829 3.6e-15
7.5857268937 7.5857268937 8.9e-16
18.3450048613 18.3450048613 7.1e-15
4.1059508325 4.1059508325 0.0e+00
소수점 열 자리까지 같다. (5)의 등식이 확인됐다.
그림 1에 쓴 세 가지 도 재 보자.
보기 = [("상수 x ", np.array([2.0, 2, 2, 2, 2, 2])),
("완만한 x ", np.array([0.0, 0.2, 0.4, 1.6, 1.8, 2.0])),
("들쭉날쭉한 x ", np.array([0.0, 2.0, 0.0, 2.0, 0.0, 2.0]))]
for 이름, x in 보기:
어긋난것 = [(i, j) for i, j in 간선 if abs(x[i] - x[j]) > 1e-12]
print(f"{이름} xT L x = {x @ L @ x:6.2f} 어긋난 간선 "
f"{len(어긋난것)}/{len(간선)}개")상수 x xT L x = 0.00 어긋난 간선 0/7개
완만한 x xT L x = 1.92 어긋난 간선 7/7개
들쭉날쭉한 x xT L x = 20.00 어긋난 간선 5/7개
여기서 조심할 것이 하나 있다. 완만한 는 일곱 간선이 모두 어긋났는데도 1.92뿐이고, 들쭉날쭉한 는 다섯만 어긋났는데 20이다. 개수가 아니라 어긋난 크기가 제곱되어 들어가기 때문이다. 완만한 의 간선별 차이는 이고 제곱해 더하면 1.92다. 들쭉날쭉한 는 다섯 간선에서 차이가 2씩이라 이다. 차이가 열 배면 값은 백 배가 된다.
여기서 준정부호도 확인해 둔다. 제곱의 합이니 음수가 나올 수 없다.
최소 = min(x @ L @ x for x in 난수.normal(size=(20000, n)))
print(f"무작위 20000개 중 최솟값 : {최소:.6f} (음수면 준정부호가 아니다)")
print(f"고윳값 : {값}")
print(f"전부 0 이상인가 : {bool((값 > -1e-12).all())}")무작위 20000개 중 최솟값 : 0.178396 (음수면 준정부호가 아니다)
고윳값 : [0. 0.4384 3. 3. 3. 4.5616]
전부 0 이상인가 : True
def 성분개수(n, 간선):
부모 = list(range(n))
def 뿌리(a):
while 부모[a] != a:
부모[a] = 부모[부모[a]]
a = 부모[a]
return a
for i, j in 간선:
부모[뿌리(i)] = 뿌리(j)
return len({뿌리(k) for k in range(n)})
기본 = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 4), (4, 5), (3, 5),
(5, 6), (6, 7), (7, 8), (6, 8)]
끊기 = [[], [(2, 3)], [(2, 3), (5, 6)], [(2, 3), (5, 6), (7, 8), (6, 8)]]
print(f"{'끊은 간선':>10} {'성분 수':>8} {'0인 고윳값':>10} 작은 고윳값 넷")
for 뺄것 in 끊기:
남 = [e for e in 기본 if e not in 뺄것]
Lc = 라플라시안(9, 남)
wc = np.linalg.eigvalsh(Lc)
영 = int((np.abs(wc) < 1e-10).sum())
print(f"{len(뺄것):>10} {성분개수(9, 남):>8} {영:>10} {np.round(wc[:4], 4)}") 끊은 간선 성분 수 0인 고윳값 작은 고윳값 넷
0 1 1 [0. 0.2087 0.6972 3. ]
1 2 2 [-0. 0. 0.4384 3. ]
2 3 3 [-0. -0. -0. 3.]
4 4 4 [-0. -0. 0. 0.]
성분 수와 0의 개수가 매번 같다. 마지막 줄에서 노드 8이 혼자 떨어져 나가 성분이 4개, 0도 4개다.
영공간의 기저도 확인하자. 각 성분의 지시벡터여야 한다((12)).
남 = [e for e in 기본 if e not in [(2, 3), (5, 6)]]
Lc = 라플라시안(9, 남)
wc, Vc = np.linalg.eigh(Lc)
영공간 = Vc[:, np.abs(wc) < 1e-10]
print("수치로 얻은 영공간 기저 (열이 기저벡터)")
print(영공간)
성분 = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
지시 = np.zeros((9, 3))
for c, 무리 in enumerate(성분):
지시[무리, c] = 1.0
print()
print("지시벡터를 넣으면 에너지가 0인가 :",
[f"{지시[:, c] @ Lc @ 지시[:, c]:.1e}" for c in range(3)])
P = 영공간 @ 영공간.T
남은것 = 지시 - P @ 지시
print(f"지시벡터를 영공간에 사영하고 남은 크기 : {np.linalg.norm(남은것):.2e}")수치로 얻은 영공간 기저 (열이 기저벡터)
[[ 0.5774 -0. -0. ]
[ 0.5774 -0. -0. ]
[ 0.5774 -0. -0. ]
[-0. 0.5774 -0. ]
[-0. 0.5774 -0. ]
[-0. 0.5774 -0. ]
[-0. -0. 0.5774]
[-0. -0. 0.5774]
[-0. -0. 0.5774]]
지시벡터를 넣으면 에너지가 0인가 : ['0.0e+00', '0.0e+00', '0.0e+00']
지시벡터를 영공간에 사영하고 남은 크기 : 1.04e-15
지시벡터를 영공간에 사영하면 하나도 남지 않는다. 두 공간이 같다는 뜻이다.
수치로 얻은 기저가 지시벡터 자체는 아닌데, 그것은 eigh 가 고른 기저가 다를 뿐이고
펼치는 공간은 같다. L05에서 본 대로다.
L12의 오일러 공식도 성분 수만큼 늘어나야 한다((13)).
print(f"{'성분 c':>7} {'rank A':>8} {'n-c':>6} {'dim N(A^T)':>11} {'m-n+c':>7}")
for 뺄것 in 끊기:
남 = [e for e in 기본 if e not in 뺄것]
Ac = 결합행렬(9, 남)
c = 성분개수(9, 남)
m = len(남)
r = np.linalg.matrix_rank(Ac)
print(f"{c:>7} {r:>8} {9 - c:>6} {m - r:>11} {m - 9 + c:>7}") 성분 c rank A n-c dim N(A^T) m-n+c
1 8 8 3 3
2 7 7 3 3
3 6 6 3 3
4 5 5 2 2
rank A = n - c 와 dim N(A^T) = m - n + c 가 네 줄 모두 맞는다.
3. 피들러 값과 피들러 벡터¶
앵커의 를 서술에서 손으로 풀었다((21)). 반대칭 꼴 를 넣어 을 얻은 것이었다.
값, 벡 = np.linalg.eigh(L)
이론 = (5 - np.sqrt(17)) / 2
print("고윳값 전부 :", 값)
print()
print(f"손으로 푼 값 (5 - sqrt(17))/2 = {이론:.15f}")
print(f"수치로 얻은 lambda_2 = {값[1]:.15f}")
print(f"차이 = {abs(이론 - 값[1]):.2e}")
print(f"가장 큰 값도 : (5 + sqrt(17))/2 = {(5 + np.sqrt(17)) / 2:.10f}"
f" vs {값[-1]:.10f}")고윳값 전부 : [0. 0.4384 3. 3. 3. 4.5616]
손으로 푼 값 (5 - sqrt(17))/2 = 0.438447187191170
수치로 얻은 lambda_2 = 0.438447187191170
차이 = 3.33e-16
가장 큰 값도 : (5 + sqrt(17))/2 = 4.5615528128 vs 4.5615528128
소수점 열다섯 자리까지 맞는다. 반대칭 꼴을 넣은 짐작이 옳았다는 뜻이다.
피들러 벡터를 보자.
f = 벡[:, 1]
f = f * np.sign(f[-1]) # 부호는 아무래도 좋다. 마지막을 양수로 맞춘다
print("피들러 벡터 :", f)
print(f"1과의 내적 : {f @ np.ones(n):.2e} (0이어야 한다)")
print(f"L f - lam f : {np.linalg.norm(L @ f - 값[1] * f):.2e}")
print()
쪽 = {k for k in range(n) if f[k] < 0}
print(f"부호로 가른 결과 : {sorted(쪽)} | {sorted(set(range(n)) - 쪽)}")
print(f"자른 간선 : {[e for e in 간선 if (e[0] in 쪽) != (e[1] in 쪽)]}")피들러 벡터 : [-0.4647 -0.4647 -0.261 0.261 0.4647 0.4647]
1과의 내적 : 3.16e-15 (0이어야 한다)
L f - lam f : 7.74e-16
부호로 가른 결과 : [0, 1, 2] | [3, 4, 5]
자른 간선 : [(2, 3)]
왼쪽 삼각형이 전부 음수, 오른쪽이 전부 양수다. 그리고 자른 간선은 다리 하나뿐이다.
그 다리가 정말 유일한 최선인지 전수 조사한다. 노드 6개면 분할이 31가지뿐이다.
전부 = []
for r in range(1, n):
for S in itertools.combinations(range(n), r):
if 0 not in S:
continue # 뒤집힌 같은 분할은 한 번만
전부.append((절단크기(간선, set(S)), S))
전부.sort()
print(f"공집합이 아닌 분할 {len(전부)}가지")
print("가장 적게 자르는 것 다섯")
for c, S in 전부[:5]:
print(f" cut {c} {S}")
print()
print(f"cut = 1 인 분할 : {[S for c, S in 전부 if c == 1]}")공집합이 아닌 분할 31가지
가장 적게 자르는 것 다섯
cut 1 (0, 1, 2)
cut 2 (0,)
cut 2 (0, 1)
cut 2 (0, 1, 2, 3)
cut 2 (0, 1, 2, 3, 4)
cut = 1 인 분할 : [(0, 1, 2)]
31가지 중 딱 하나가 간선 1개만 자른다. 피들러 벡터가 그것을 찾았다.
레일리 몫이 정말 거기서 멈추는가¶
(17)의 주장이다. 제약이 없으면 0까지 내려가고, 이면 에서 멈춰야 한다.
샘플 = 난수.normal(size=(200000, n))
자유 = np.einsum("ij,jk,ik->i", 샘플, L, 샘플) / np.einsum("ij,ij->i", 샘플, 샘플)
수직 = 샘플 - 샘플.mean(axis=1, keepdims=True) # 1 성분을 뺀다
제약 = np.einsum("ij,jk,ik->i", 수직, L, 수직) / np.einsum("ij,ij->i", 수직, 수직)
print(f"제약 없음 : 최소 {자유.min():.6f} (lambda_1 = 0 으로 내려간다)")
print(f"x _|_ 1 : 최소 {제약.min():.6f} (lambda_2 = {값[1]:.6f} 에서 멈춘다)")
print(f"lambda_2 보다 작은 표본 : {(제약 < 값[1] - 1e-12).sum()}개 / 200000")
print(f"최댓값도 lambda_max 아래인가 : {제약.max():.6f} <= {값[-1]:.6f} "
f"{bool(제약.max() <= 값[-1] + 1e-12)}")제약 없음 : 최소 0.018341 (lambda_1 = 0 으로 내려간다)
x _|_ 1 : 최소 0.442526 (lambda_2 = 0.438447 에서 멈춘다)
lambda_2 보다 작은 표본 : 0개 / 200000
최댓값도 lambda_max 아래인가 : 4.556962 <= 4.561553 True
20만 개를 뽑아도 하나도 아래로 내려가지 못한다. 최솟값이 아직 에 닿지 못한 것은 무작위로 정확히 피들러 방향을 맞히기가 어렵기 때문이다. 정확히 를 넣으면 닿는다.
print(f"q_2 를 그대로 넣으면 : {f @ L @ f / (f @ f):.15f}")
print(f"lambda_2 : {값[1]:.15f}")q_2 를 그대로 넣으면 : 0.438447187191170
lambda_2 : 0.438447187191170
print(f"{'분할':>22} {'cut':>4} {'xT L x':>8} {'4 x cut':>8}")
어긋남 = 0
for c, S in 전부:
x = np.array([1.0 if k in S else -1.0 for k in range(n)])
에너지 = x @ L @ x
if abs(에너지 - 4 * c) > 1e-9:
어긋남 += 1
if len(S) == 3:
print(f"{str(S):>22} {c:>4} {에너지:>8.1f} {4 * c:>8}")
print()
print(f"31가지 전부에서 어긋난 것 : {어긋남}개") 분할 cut xT L x 4 x cut
(0, 1, 2) 1 4.0 4
(0, 1, 4) 4 16.0 16
(0, 1, 5) 4 16.0 16
(0, 2, 3) 4 16.0 16
(0, 4, 5) 4 16.0 16
(0, 1, 3) 5 20.0 20
(0, 2, 4) 5 20.0 20
(0, 2, 5) 5 20.0 20
(0, 3, 4) 5 20.0 20
(0, 3, 5) 5 20.0 20
31가지 전부에서 어긋난 것 : 0개
전부 맞는다. 그리고 3대3 분할 열 가지 중 만 1을 자르고 나머지는 4 이상이다.
큰 그래프에서¶
노드 60개를 두 덩어리로 만들고, 덩어리 안은 촘촘히(35%), 사이는 성기게(2%) 이었다.
r3 = np.random.default_rng(37)
간선큰 = []
for i in range(30):
for j in range(i + 1, 30):
if r3.random() < 0.35:
간선큰.append((i, j))
for i in range(30, 60):
for j in range(i + 1, 60):
if r3.random() < 0.35:
간선큰.append((i, j))
다리 = 0
for i in range(30):
for j in range(30, 60):
if r3.random() < 0.02:
간선큰.append((i, j))
다리 += 1
Lg = 라플라시안(60, 간선큰)
print(f"노드 60개, 간선 {len(간선큰)}개, 그중 두 덩어리를 잇는 다리 {다리}개")
wg, Vg = np.linalg.eigh(Lg)
print(f"작은 고윳값 넷 : {np.round(wg[:4], 4)}")
print(f"lambda_2 = {wg[1]:.4f} 로 작다 -> 끊어질 뻔한 그래프다")노드 60개, 간선 320개, 그중 두 덩어리를 잇는 다리 15개
작은 고윳값 넷 : [-0. 0.8402 4.0176 4.5678]
lambda_2 = 0.8402 로 작다 -> 끊어질 뻔한 그래프다
fg = Vg[:, 1]
찾은쪽 = {k for k in range(60) if fg[k] > 0}
if 0 not in 찾은쪽:
찾은쪽 = set(range(60)) - 찾은쪽
진짜쪽 = set(range(30))
피들러절단 = 절단크기(간선큰, 찾은쪽)
print(f"피들러가 고른 쪽 : {len(찾은쪽)}개 / {60 - len(찾은쪽)}개")
print(f"참 분할과 같은가 : {찾은쪽 == 진짜쪽}")
print(f"자른 간선 : {피들러절단} (참 다리 개수 {다리})")피들러가 고른 쪽 : 30개 / 30개
참 분할과 같은가 : True
자른 간선 : 15 (참 다리 개수 15)
정확히 맞혔다. 30 대 30으로 갈렸고, 자른 간선이 참 다리 개수와 같다.
무작위로 반반 나눈 것과 겨뤄 본다.
무작위 = []
for _ in range(5000):
쪽무 = set(r3.permutation(60)[:30].tolist())
무작위.append(절단크기(간선큰, 쪽무))
무작위 = np.array(무작위)
print(f"{'':>24} {'자른 간선':>10}")
print(f"{'피들러':>24} {피들러절단:>10}")
print(f"{'무작위 5000개 중 최선':>24} {무작위.min():>10}")
print(f"{'무작위 5000개 중앙값':>24} {int(np.median(무작위)):>10}")
print(f"{'무작위 5000개 중 최악':>24} {무작위.max():>10}")
print()
print(f"무작위가 피들러 이하로 내려간 횟수 : {(무작위 <= 피들러절단).sum()} / 5000") 자른 간선
피들러 15
무작위 5000개 중 최선 125
무작위 5000개 중앙값 163
무작위 5000개 중 최악 192
무작위가 피들러 이하로 내려간 횟수 : 0 / 5000
무작위 최선조차 피들러에 여러 배 밀린다. 5000번 중 한 번도 따라잡지 못했다.
고윳값 하나를 구한 것이 전부다.
5. RatioCut 과 Ncut 은 다른 자를 쓴다¶
(30)의 항등식부터 확인한다. 크기 인 분할에 와 를 넣으면 레일리 몫이 정확히 RatioCut 이어야 한다.
def ratiocut벡터(n, S):
a = len(S)
b = n - a
return np.array([np.sqrt(b / a) if k in S else -np.sqrt(a / b)
for k in range(n)])
어긋남 = 0
센것 = 0
for 시도 in range(300):
m = int(난수.integers(6, 14))
후 = [(i, j) for i in range(m) for j in range(i + 1, m)
if 난수.random() < 0.45]
if len(후) < m - 1:
continue
Lr = 라플라시안(m, 후)
if np.linalg.eigvalsh(Lr)[1] < 1e-9:
continue # 끊긴 그래프는 넘긴다
r = int(난수.integers(1, m))
S = set(난수.permutation(m)[:r].tolist())
a, b = len(S), m - len(S)
x = ratiocut벡터(m, S)
좌 = x @ Lr @ x / (x @ x)
우 = 절단크기(후, S) * (1 / a + 1 / b)
센것 += 1
if abs(좌 - 우) > 1e-9 or abs(x.sum()) > 1e-9 or abs(x @ x - m) > 1e-9:
어긋남 += 1
print(f"연결된 그래프 {센것}건에서 어긋난 것 : {어긋남}건")
print(" 확인한 것 : x _|_ 1, |x|^2 = n, 레일리 몫 = cut (1/a + 1/b)")연결된 그래프 265건에서 어긋난 것 : 0건
확인한 것 : x _|_ 1, |x|^2 = n, 레일리 몫 = cut (1/a + 1/b)
반례가 없다. 를 구하는 것은 RatioCut 을 완화해 푸는 것이라는 게 이 항등식의 뜻이다.
이제 과 이 다른 답을 내는 그래프를 본다. 에 꼬리를 매단 것이다. 꼬리 마디는 차수가 2뿐이고 덩어리 쪽은 9다.
def 꼬리그래프(꼬리):
m = 10 + 꼬리
후 = [(i, j) for i in range(10) for j in range(i + 1, 10)]
후 += [(0, 10)] + [(10 + t, 11 + t) for t in range(꼬리 - 1)]
return m, 후
def 두라플라시안(n, 간선):
Lp = 라플라시안(n, 간선)
d = Lp.diagonal()
Dm = np.diag(1.0 / np.sqrt(d))
return Lp, Dm @ Lp @ Dm
def 부호쪽(v, n):
S = {k for k in range(n) if v[k] > 0}
return S if 0 in S else set(range(n)) - S
def 재기(m, 후, d, S):
a, b = len(S), m - len(S)
T = set(range(m)) - S
c = 절단크기(후, S)
va, vb = d[sorted(S)].sum(), d[sorted(T)].sum()
return c, c * (1 / a + 1 / b), c * (1 / va + 1 / vb)
for 꼬리 in (2, 3, 6):
m, 후 = 꼬리그래프(꼬리)
Lp, Ls = 두라플라시안(m, 후)
d = Lp.diagonal()
S1 = 부호쪽(np.linalg.eigh(Lp)[1][:, 1], m)
S2 = 부호쪽(np.linalg.eigh(Ls)[1][:, 1], m)
c1, rc1, nc1 = 재기(m, 후, d, S1)
c2, rc2, nc2 = 재기(m, 후, d, S2)
print(f"K10 + 꼬리 {꼬리}")
print(f" L : 작은쪽 {min(len(S1), m - len(S1))}개 cut {c1:2d} "
f"RatioCut {rc1:.4f} Ncut {nc1:.4f}")
print(f" L_sym : 작은쪽 {min(len(S2), m - len(S2))}개 cut {c2:2d} "
f"RatioCut {rc2:.4f} Ncut {nc2:.4f}")K10 + 꼬리 2
L : 작은쪽 2개 cut 1 RatioCut 0.6000 Ncut 0.3443
L_sym : 작은쪽 3개 cut 9 RatioCut 4.0000 Ncut 0.8034
K10 + 꼬리 3
L : 작은쪽 3개 cut 1 RatioCut 0.4333 Ncut 0.2110
L_sym : 작은쪽 4개 cut 9 RatioCut 3.2500 Ncut 0.7111
K10 + 꼬리 6
L : 작은쪽 5개 cut 1 RatioCut 0.2909 Ncut 0.1219
L_sym : 작은쪽 6개 cut 1 RatioCut 0.2667 Ncut 0.1019
꼬리가 짧을 때는 두 답이 크게 다르다. 그러면 각자의 목적함수 기준으로 누가 잘했는지 전수 조사해 보자.
for 꼬리 in (2, 6):
m, 후 = 꼬리그래프(꼬리)
Lp, Ls = 두라플라시안(m, 후)
d = Lp.diagonal()
모두 = []
for r in range(1, m):
for S in itertools.combinations(range(m), r):
if 0 not in S:
continue
모두.append(재기(m, 후, d, set(S)))
rc최적 = min(v[1] for v in 모두)
nc최적 = min(v[2] for v in 모두)
_, rc피, _ = 재기(m, 후, d, 부호쪽(np.linalg.eigh(Lp)[1][:, 1], m))
_, _, nc피 = 재기(m, 후, d, 부호쪽(np.linalg.eigh(Ls)[1][:, 1], m))
print(f"K10 + 꼬리 {꼬리} (분할 {len(모두)}가지 전수 조사)")
print(f" RatioCut : L 의 부호 자름 {rc피:.4f} 최적 {rc최적:.4f} "
f"맞혔나 {abs(rc피 - rc최적) < 1e-9}")
print(f" Ncut : L_sym 의 부호 자름 {nc피:.4f} 최적 {nc최적:.4f} "
f"맞혔나 {abs(nc피 - nc최적) < 1e-9}")K10 + 꼬리 2 (분할 2047가지 전수 조사)
RatioCut : L 의 부호 자름 0.6000 최적 0.6000 맞혔나 True
Ncut : L_sym 의 부호 자름 0.8034 최적 0.3443 맞혔나 False
K10 + 꼬리 6 (분할 32767가지 전수 조사)
RatioCut : L 의 부호 자름 0.2909 최적 0.2667 맞혔나 False
Ncut : L_sym 의 부호 자름 0.1019 최적 0.1019 맞혔나 True
정확히 엇갈렸다. 꼬리가 2일 때는 이 RatioCut 최적을 맞히고 이 Ncut 최적을 놓쳤고, 꼬리가 6일 때는 그 반대다. 서술의 주의 상자가 말한 그대로다.
완화해서 푼 답의 부호를 취하는 것이니 최적이라는 보장이 없다. 그래도 60개짜리 큰 그래프에서 본 것처럼 대개는 아주 잘한다.
정리¶
| 확인한 것 | 결과 |
|---|---|
| 소수점 열 자리까지 일치 | |
| 셋 다 14 | |
| 성분 수 | 성분 1,2,3,4 모두 일치 |
| 영공간 기저 지시벡터 | 사영하고 남는 것이 없음 |
| 소수점 열다섯 자리 일치 | |
| 이면 레일리 몫 | 20만 개 중 위반 0 |
| 에서 | 31가지 전부 일치 |
| 앵커의 최선 절단 | 31가지 중 하나, 피들러가 그것을 찾음 |
| 60노드 그래프 | 피들러가 참 분할을 정확히 회복 |
| RatioCut 항등식 | 무작위 표본에서 반례 0 |
| 부호 자름이 늘 최적인가 | 아니다 — 꼬리 길이에 따라 놓친다 |
마지막 줄이 이 실습의 정직한 결론이다. 스펙트럴 클러스터링은 완화이지 정답이 아니다. 그런데도 그렇게 잘 듣는 이유는, 덩어리가 실제로 있는 그래프에서는 가 작고 피들러 벡터의 부호가 그 덩어리를 그대로 베끼기 때문이다.
여기서 이 시리즈가 끝난다. 고윳값 하나로 그래프를 잘랐다.