[AI] 이산수학·그래프와 머신러닝

※ 이산수학이란?

이산수학(Discrete Mathematics)은
"끊어져 있는 것(Discrete)"을 다루는 수학이다.
즉, 연속적인 곡선이나 면적(미적분)이 아니라,
하나하나의 '요소'(데이터, 노드, 연결 등)를 다룬다.

예를 들어,
· 친구 관계 (A와 B가 친구인지 아닌지)
· 컴퓨터 네트워크 (서버들이 연결되어 있는 구조)
· SNS 팔로잉 관계 (누가 누구를 팔로우하는가)

이런 것들은 모두 연속적이지 않은 데이터(이산 데이터)이다.
머신러닝에서도 이런 구조를 이해하고 계산하는 데 이산수학이 꼭 필요하다.

※ 왜 머신러닝에 필요할까?

머신러닝은 "데이터의 패턴을 이해하는 기술"이다.
그런데 데이터는 숫자뿐만 아니라 '관계'도 가지고 있다.
이산수학은 바로 이 '관계'와 '구조'를 분석하는 언어이다.

분야	이산수학 개념	머신러닝 활용 예시
집합(Set)	데이터의 모임	중복 제거, 범주형 데이터 처리
논리(Logic)	참/거짓 판단	조건문, 분류 기준 설정
그래프(Graph)	관계 구조	추천 시스템, 네트워크 분석
조합(Combinatorics)	가능한 경우의 수	모델 탐색, 최적화 문제
행렬과 그래프 연결	노드 간 연결 표현	그래프 신경망(GNN)

※ 그래프(그래프 이론)는 관계를 시각화한 '지도'

그래프 이론은 이산수학의 한 분야로,
사람이나 사물 간의 관계를 '점(노드)'과 '선(간선)'으로 표현하는 수학이다.

예를 들어, SNS를 생각해보면

A —— B —— C
  \
   D

 

· A, B, C, D : 사람(노드)
· 선(Line) : 친구 관계(간선)

이게 바로 그래프(Graph) 구조이다.

※ 머신러닝에서 그래프가 꼭 필요한 이유

현실의 많은 데이터가 관계 중심으로 되어 있기 때문이다.

실제 예시	그래프 구조로 표현
SNS 추천 시스템	"친구의 친구"를 추천 (Facebook, Instagram)
제품 추천	"이 상품을 본 사람은 이런 것도 봤어요" (쿠팡, 아마존)
지하철 경로 탐색	역(노드)과 노선(간선)을 이용해 최단 거리 계산
지식 그래프	"사람-회사-도시" 관계를 이해 (Google 검색 엔진)
AI 모델 구조	신경망(Neural Network) 자체가 그래프 구조

 

즉, 그래프는 데이터의 관계를 이해하는 눈이다.
그래프를 잘 다루면 "연결된 세상 속에서 패턴을 찾는 능력"을 얻을 수 있다.

※ 일상 비유로 이해하기

이산수학은 "조립 설명서"이다.
→ 어떤 조각들이 있고, 어떻게 조합되는지를 알려준다.

그래프 이론은 "지도"이다.
→ 조각들(노드)이 어떻게 연결되어 있는지를 보여준다.

머신러닝은 이 두 가지를 이용해
"데이터라는 조각들을 어떻게 연결해야 세상을 이해할 수 있을까?"를 고민하는 과정이다.

※ 요약

이산수학은 데이터의 '논리', 그래프는 데이터의 '관계'를 다룬다.
머신러닝은 이 둘을 이용해 세상 속 연결 구조를 이해하고 예측하는 기술이다.

---

1) 이산수학·그래프 기본 개념

---

2) 이산수학·그래프 기본 수식

---

3) 기본 수식 활용 파이썬 코드

import numpy as np
import itertools

# 1) 조합, 순열 계산
n, r = 5, 3
nCr = np.math.factorial(n) / (np.math.factorial(r) * np.math.factorial(n - r))
nPr = np.math.factorial(n) / np.math.factorial(n - r)
print(f"{n}C{r} =", nCr)
print(f"{n}P{r} =", nPr)

# 2) 그래프 인접 행렬
A = np.array([
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [0, 1, 1, 0]
])
print("인접 행렬:\n", A)

# 3) 차수 계산
degrees = np.sum(A, axis=1)
print("정점별 차수:", degrees)
print("차수 합:", np.sum(degrees), "→ 2|E| =", np.sum(A))

---

4) 머신러닝에 필요한 수식

---

5) 머신러닝에 필요한 수식 활용 파이썬 코드

▶ 그래프 라플라시안 계산

import numpy as np

# 인접 행렬 (undirected graph)
A = np.array([
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [0, 1, 1, 0]
])

D = np.diag(np.sum(A, axis=1))  # 차수 행렬
L = D - A                       # 라플라시안
print("차수 행렬 D:\n", D)
print("라플라시안 L:\n", L)

 

▶ 스펙트럴 클러스터링 예시 (고유벡터 기반)

import numpy as np

A = np.array([
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0]
])

D = np.diag(np.sum(A, axis=1))
L = D - A
eigvals, eigvecs = np.linalg.eig(L)

# 두 번째로 작은 고유값의 고유벡터 → Fiedler vector
idx = np.argsort(eigvals)
fiedler = eigvecs[:, idx[1]]
print("고유값:", np.round(eigvals, 3))
print("Fiedler vector:", np.round(fiedler, 3))

 

▶ PageRank 간단 구현

import numpy as np

# 인접 행렬 (방향 그래프)
A = np.array([
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [1, 0, 0, 1],
    [0, 0, 0, 0]
])

n = A.shape[0]
d = 0.85
A_norm = A / np.maximum(A.sum(axis=0), 1)
PR = np.ones(n) / n

for _ in range(20):
    PR = (1 - d) / n + d * A_norm @ PR

print("PageRank 값:", np.round(PR, 3))

 

▶ 마르코프 체인 확률 전이

import numpy as np

P = np.array([
    [0.7, 0.3],
    [0.4, 0.6]
])

state = np.array([1, 0])  # 초기 상태: S0
for t in range(5):
    state = state @ P
    print(f"{t+1}단계 후 상태 확률:", np.round(state, 3))

 

▶ KNN 거리 기반 그래프 만들기

import numpy as np
from sklearn.metrics import pairwise_distances

X = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
dist = pairwise_distances(X)

# 가우시안 가중치 그래프
sigma = 1.0
W = np.exp(-(dist**2) / (2 * sigma**2))
print("가중 그래프 W:\n", np.round(W, 3))