https://ubuntu.com/download/server/thank-you?version=26.04&architecture=amd64&lts=true

1. 위 링크로 'download now' 하이퍼링크를 클릭하여 server용 ubuntu 26.04 LTS Download 링크 복사

2. Proxmox 페이지에서 'Datacenter-proxmox-local(proxmox)-ISO Images-Download from URL' 클릭

URL: 위에서 복사한 링크 붙여넣기 Filename: 식별 가능하도록 직접 지정

다운로드 버튼 클릭

로그에서 'TASK OK'가 뜨면 창 닫고 종료

VM 생성

상단 Create VM 버튼 클릭

우분투 설정

생성된 vm를 더블클릭하여 콘솔을 연 후 우분투 설정

네트워크의 경우 vmbr2(10.0.12.1/24)를 사용했으므로 아래 사진과 같이 설정함

proxy configuration은 비워두고 넘어가기

마지막에 아래와 같은 화면 나오면 'Reboot Now' 클릭하기

reboot 후 'Please remove the installation medium, then press ENTER'가 뜨면 잘 설치된 것으로 재설치 방지를 위해 엔터를 누르면 됨

만약 'Please remove the installation medium, then press ENTER'가 안뜨고 다시 재설치 화면이 나온다면 수동으로 ISO 미디어 제거해야함

- vm 강제 종료
- proxmox 홈화면에서 해당 vm 아이콘 클릭
- Hardware 탭 클릭
- CD/DVD Drive (ide2) 항목을 더블 클릭하거나 선택 후 Edit 누름
- Do not use any media를 선택하고 OK 누름

그 후 콘솔로 돌아와 엔터를 누르거나 VM을 Reboot 시킴

• Host-Only:외부 인터넷과 완전히 단절된 폐쇄적 네트워크로, 가상머신 내에 존재하는 머신들과 호스트PC끼리만 통신 가능
• Bridge: 가상머신이 호스트PC의 물리 랜카드에 직접 매달려 있는 형태로, 공유기(라우터)로부터 독립적인 IP 주소를 할당받음. 공유기를 통해 외부 네트워크 통신 가능
• NAT: 가상머신은 호스트PC로부터 사설 ip를 할당받고, 외부로 나갈 때는 호스트PC의 IP로 통신. 호스트PC가 가상 공유기 역할함. 외부에서 vm으로 들어오려면 포트포워딩 필수

OSI 7계층과 L2(스위치), L3(라우터)

1. OSI 7계층

2. L2 (2Layer, DataLink)

• 데이터링크 계층, 전송 단위: 프레임
• 대표 장비: 브릿지(옛날 장비), 스위치(요즘 장비)

  인터넷
    │
   [WAN 포트]
   라우터
   [LAN 포트]
    │
   [업링크 포트]
   스위치
   [포트 1~24]
    │ │ │ │
      랜선
    │ │ │ │
   PC들

• 식별자: MAC 주소 -> 네트워크 카드(NIC)에 MAC 주소가 정해짐
• 같은 네트워크 대역 안에서 장비들끼리 데이터 주고 받음, 같은 대역일때는 라우터를 거치지 않고 MAC 주소만으로 스위치를 통해 데이터를 주고 받음(그게 훨씬 빠름, 또한 스위치가 라우터에 비해 상대적으로 포트 개수가 많으므로 라우터에 스위치를 연결해서 사용하면 비용이 절감됨)

3. L3 (3Layer, Network)

• 네트워크 계층, 전송단위: 패킷
• 대표 장비: 라우터, L3 스위치
• 식별자: IP 주소
• 서로 다른 네트워크에서 데이터 주소 받음

Proxmox 설정

1. bridge 방식으로 가상 스위치인 vmbr0 설정

2. NAT 방식으로 가상 스위치인 vmbr2 설정

이후 Apply Configuration 클릭해서 적용하기

3. NAT 방식 적용을 위해 interfaces 파일 수정

• 'Datacenter-proxmox-System-Network-shell' 클릭하여 호스트pc 접속

• interfaces 파일 수정

  vi /etc/network/interfaces

  # vmbr2 부분을 다음과 같이 수정
  

auto vmbr2 iface vmbr2 inet static address 10.0.12.1/24 bridge-ports none bridge-stp off bridge-fd 0 #k8s 전용 NAT 설정 # 이 줄이 반드시 들어가야 인터넷이 됨 post-up echo 1 > /proc/sys/net/ipv4/ip_forward post-up iptables -t nat -A POSTROUTING -s '10.0.12.0/24' -o vmbr0 -j MASQUERADE post-down iptables -t nat -D POSTROUTING -s '10.0.12.0/24' -o vmbr0 -j MASQUERADE

- 네트워크 재시작하여 변경사항 반영하기

systemctl restart networking

```

proxmox vm 생성하는 게시물에 이번에 만든 가상 네트워크를 활용하는 방법 나와있습니다.
https://velog.io/@vinyl-bin/Proxmox-VM-%EC%83%9D%EC%84%B1

참고

• https://hg2lee.tistory.com/entry/Network-%EA%B0%80%EC%83%81%EB%A8%B8%EC%8B%A0%EC%97%90%EC%84%9C-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%EC%9D%98-%EC%A2%85%EB%A5%98-Bridged-NAT-Host-onl
• https://shlee0882.tistory.com/110

SSH 패스키 설정은 원격서버 ssh 접속 시 패스워드 로그인을 차단하고 등록된 key로만 접속하도록 설정하는 것입니다.

ssh key는 private key와 public key로 나누어져 있습니다.

• private key: 로컬pc 위치, 절대 타인에게 노출X, 확장자X
  • 단 private key 권한은 600이어야 함.(chmod 600 ~/.ssh/id_ed25519)
• public key: 원격서버 ~/.ssh/authorized_keys 파일에 한 줄로 위치, 공개되어도 상관없음, .pub확장자

SSH Key 설정

로컬 PC 설정

1. key 생성 (private, public 모두 생성됨)

보통 기본경로인 ~/.ssh/id_ed25519 에 생성됨

ssh-keygen -t ed25519 -C "내이름_또는_이메일"

• -t ed25519 : 알고리즘 타입
• -C "주석" : 식별용 주석

2. 원격서버로 public key 전송

아래 방법 중 하나 선택해서 사용

2-1. 직접 복사해서 원격서버 ~/.ssh/authorized_keys 파일 다음 줄에 붙여넣기 후 원격서버에서 권한 설정

chmod 700 ~/.ssh
chmod 600 ~/.ssh/authorized_keys

2-2. 로컬pc에서 ssh-copy-id 명령어 사용

ssh-copy-id -i ~/.ssh/id_ed25519.pub 사용자계정@서버IP

원격 서버 설정

1. ssh 설정 변경

sudo vi /etc/ssh/sshd_config

PubkeyAuthentication yes       # 공개키 인증 허용
PasswordAuthentication no      # 패스워드 인증 비활성화
ChallengeResponseAuthentication no  # 시도-응답 인증 비활성화

sudo sshd -t              # 문법 검사 (아무 출력 없으면 정상)
sudo systemctl restart ssh

원격접속 테스트

ssh -i ./id_ed25519 사용자계정@서버IP

또는

ssh -i ./id_ed25519 -p 포트 사용자계정@서버IP  #포트포워딩 했을 경우

• 위 그림과 같이 가중치를 어떻게 초기화 하냐에 따라 많은 성능 차이가 나므로 가중치 초기화는 중요
• 초기 가중치를 잘못 설정하면 layer(층)이 깊어질수록 문제 발생
  • 기울기 소멸: 역전파 과정에서 가중치의 작은 값들이 계속 곱해지면서 입력층으로 갈수록 기울기가 0에 수렴하게 되어 학습이 제대로 안됨
  • 기울기 폭발: 역전파 과정에서 가중치의 큰 값들이 계속 곱해지면서 입력층으로 갈수록 기울기가 기하급수적으로 커져 학습이 제대로 안됨
• 따라서 기울기가 0에 수렴하거나 발산하지 않기 위해 가중치의 분산 정도를 적절히 조절하는 것이 필요

  2. 사전 기본 개념

  (1) 표준편차

• 데이터가 평균으로부터 얼마나 퍼져있는지 나타내는 수치
• 표준편차가 작으면 데이터가 평균 근처에 모여있음
• 표준편차가 크면 데이터가 평균과 멀리 퍼져있음

(2) 68-95-99.7 규칙

• 정규분포의 특징 중 하나

=> 68%의 관측값이 평균으로부터 양쪽으로 표준편차가 떨어져 있는 곳 내에 분포 => 95%의 관측값이 평균으로부터 양쪽으로 2표준편차가 떨어져있는곳 내에 분포 => 99.7%의 관측값이 평균으로부터 양쪽으로 3표준편차가 떨어져있는곳 내에 분포

• 예시: 평균이 0이고 표준편차가 0.1인 분포는 랜덤하게 숫자를 뽑으면 95% 확률로 -0.2 ~ 0.2 사이의 값이 나옴

(3) 여러 활성화 함수

3. Xavier 초기화

• 각 층의 가중치를 그 층의 입력 노드 수와 출력 노드 수에 기반하여 조절된 분산을 가진 분포에서 무작위로 선택하여 초기화하는 방법
• 주로 tanh(탄젠트) 또는 sigmoid(시그모이드) 같은 선형적 활성화 함수에 적합
  • 실제로 탄젠트와 시그모이드 함수는 비선형 함수이지만 초기화 범위가 0 근처이므로 초기화 시점에서는 이 함수들이 선형과 비슷하게 행동한다고 가정함 (0 근처에서는 선형과 비슷하다는 성질 활용)

(1) Xavier Normal(정규분포 초기화)

• 평균이 0이고 표준편차(σ)가 아래와 같은 정규분포를 따름

(2) Xavier Uniform(균일분포 초기화)

• 아래 범위 내에서 균일하게 값 추출함

4. He 초기화

• xavier 초기화 한계점
  • Xavier 초기화는 활성화 함수가 선형(Linear)이라는 가정하에 유도됨
  • 하지만 ReLU 함수는 입력값이 음수일 때 0을 출력하는 비선형성을 가짐
  • 이로 인해 ReLU 층을 통과할 때마다 출력값의 분산이 입력값 분산의 약 절반으로 줄어드는 현상이 발생하며, 층이 깊어질수록 활성화 값의 분포가 0으로 수렴함
• He 초기화
  • ReLU 함수를 통과하면 음수 영역이 0이 되어 출력의 분산이 입력 분산의 절반(1/2)이 된다는 점에 착안
  • 이를 상쇄하기 위해 가중치의 분산을 인위적으로 2배로 설정
  • 주로 ReLU 및 그 변형들 (Leaky ReLU 등) 같은 비선형 활성화 함수에 적합
  • 출력 노드는 분산 보존에 영향을 주지 않는다고 가정하여 무시하고, 입력 노드 수만을 변수로 사용

(1) He Normal(정규분포 초기화)

• 평균이 0이고 표준편차(σ)가 아래와 같은 정규분포를 따름

(2) He Uniform(균일분포 초기화)

• 아래 범위 내에서 균일하게 값 추출함

** 참고

• https://guru.tistory.com/69
• https://jangpiano-science.tistory.com/126
• https://resultofeffort.tistory.com/114
• https://heeya-stupidbutstudying.tistory.com/entry/ML-%ED%99%9C%EC%84%B1%ED%99%94-%ED%95%A8%EC%88%98Activation-Function

(1) 네트워크 정보 확인

• cmd 관리자 권한으로 실행 - 'ipconfig -all' 명령어 실행 - 원하는 네트워크 정보 확인
• 서브넷 마스크, 기본 게이트웨이, dns 서버 정보 확인

(2) 네트워크 연결 설정 접속

• 원하는 네트워크 선택 - 속성 - '인터넷 프로토콜 버전 4(TCP/IPv4)' 클릭 후 속성 선택 - 다음 ip 주소 사용 선택
• (1)에서 확인한 정보 기입
• 고정 ip는 대역대에 맞는 ip 기입

2. 다른 대역대 고정 ip 설정

(1) 네트워크 연결 설정 접속 및 고정 ip 설정

• 원하는 네트워크 선택 - 속성 - '인터넷 프로토콜 버전 4(TCP/IPv4)' 클릭 후 속성 선택 - 고정 ip 대역대에 맞게 설정

(2) 보조 ip 설정

• 원하는 네트워크 선택 - 속성 - ‘인터넷 프로토콜 버전 4(TCP/IPv4)' 클릭 후 속성 선택 - '고급’ - ip 주소 - 추가 - 다른 대역대의 ip주소와 서브넷 마스크 입력
• 보조 ip로 설정된 웹에 들어가려면 localhost 대신 해당 보조 ip 입력해야함
• cmd에서 ipconfig로 설정 적용 확인

주의사항

• 물리적으로는 여전히 LAN 케이블 하나
• 그래서 실제로 다른 대역(B망, 예: 10.0.0.x)에 있는 장치와 통신하려면 그 쪽으로 라우팅 경로가 있어야함

3. 고정 ip 설정 후 다른 와이파이 접속 시 오류 해결법

• 고정 ip 설정 후 다른 와이파이에 접속하면 오류가 생김
• 고정 ip가 필요하다면 위와 같이 설정하고 아니라면 다음과 같이 설정

(1) 네트워크 연결 설정 접속

• 원하는 네트워크 선택 - 속성 - ‘인터넷 프로토콜 버전 4(TCP/IPv4)' 클릭 후 속성 선택 - 자동으로 ip 주소 받기

(2) wifi 설정 접속

• 설정 - 네트워크 및 인터넷 - Wi-Fi - 현재 접속 wifi 선택
  • '모든 WiFi 네트워크에 대한 IP 설정 변경' 칸의 편집 선택- 자동(DHCP)로 변경
  • '모든 WiFi 네트워크에 대한 DNS 설정 변경' 칸의 편집 선택- 자동(DHCP)로 변경

1-1. MF (Matrix Factorization)

• 기존 협업 필터링으로 정적 임베딩 후 사후 연산 방식

• 순전파 단계에서 유저 벡터와 아이템 벡터가 서로 독립적

• 예측 점수를 계산할 때 단순 내적을 수행하므로 그래프 구조나 이웃 정보가 임베딩 변화에 관여하지 않음

  class MatrixFactorization(nn.Module):
    def __init__(self, num_users, num_items, embed_dim):
        super().__init__()
  
        # Lookup Table 생성
        self.user_embedding = nn.Embedding(num_users, embed_dim)
        self.item_embedding = nn.Embedding(num_items, embed_dim)
  
    def forward(self, user_idx, item_idx):
        # 1. 단순히 ID에 해당하는 벡터를 꺼내옴 (Lookup)
        # 이 시점에서 u_emb는 어떤 그래프 정보도 포함하지 않음.
        u_emb = self.user_embedding(user_idx) 
        i_emb = self.item_embedding(item_idx)
  
        # 2. 내적 수행 (Linear Interaction)
        prediction = (u_emb * i_emb).sum(dim=1)
        return prediction

• 단순히 lookup(특정 벡터 꺼내옴) 후 내적을 수행하므로 이웃의 정보를 학습하지 못함

1-2. NGCF

• 추천 시스템에 GCN(Graph Convolution Network)를 처음 제대로 도입
• MF는 자신의 정보(user와 item)만 학습하여 이웃의 정보를 고려하지 않았지만, NGCF의 경우 layer의 개수만큼(여러 hop만큼) 이웃의 정보를 Aggregate(집계)해서 update하여 propagate(전파)할 수 있음

    def forward(self, users, pos_items, neg_items, drop_flag=True):

        # 노드 드롭아웃 적용 (Graph Structure Learning 효과)
        # 인접 행렬의 일부 연결을 무작위로 제거하여 과적합 방지
        # drop_flag가 True일 때만 노드 드롭아웃 적용 -> 학습 시에만 적용하고 테스트 시에는 적용하지 않음
        A_hat = self.sparse_dropout(self.sparse_norm_adj,
                                    self.node_dropout,
                                    self.sparse_norm_adj._nnz()) if drop_flag else self.sparse_norm_adj

        # 초기 임베딩 (Layer 0) - 사용자와 아이템 임베딩을 결합
        # 학습 가능한 파라미터인 유저와 아이템의 ID 임베딩을 하나로 합침
        # ego_embeddings shape: [유저수 + 아이템수, 임베딩 차원]
        ego_embeddings = torch.cat([self.embedding_dict['user_emb'],
                                    self.embedding_dict['item_emb']], 0)

        # 각 레이어(Layer 0, 1, 2...)에서 나온 임베딩을 모두 저장할 리스트
        # 나중에 이들을 모두 이어 붙여(Concat) 최종 임베딩으로 씀
        all_embeddings = [ego_embeddings]

        # 레이어 수만큼 임베딩 전파
        for k in range(len(self.layers)):
            # --- [A] 정보 집계 (Aggregation) ---
            # 인접 행렬과 현재 임베딩을 곱하여 이웃 노드의 정보를 가져옴
            # side_embeddings: 이웃 노드들의 임베딩 가중합
            side_embeddings = torch.sparse.mm(A_hat, ego_embeddings)

            # --- [B] Feature Transformation (가중치 변환) ---
            # 이웃에서 가져온 정보를 단순히 더하는 게 아니라, 학습 가능한 가중치(W1)를 곱해 유의미한 특징을 추출
            sum_embeddings = torch.matmul(side_embeddings, self.weight_dict['W_gc_%d' % k]) \
                                             + self.weight_dict['b_gc_%d' % k]

            # --- [C] Bi-Interaction (상호작용 항) ---
            # NGCF의 핵심 특징. 나와 이웃의 특징을 Element-wise Product(⊙)로 곱함
            # "나와 비슷한 특징을 가진 이웃의 정보는 더 강하게 받아들이겠다"는 의도
            bi_embeddings = torch.mul(ego_embeddings, side_embeddings)
            bi_embeddings = torch.matmul(bi_embeddings, self.weight_dict['W_bi_%d' % k]) \
                                            + self.weight_dict['b_bi_%d' % k]

            # --- [D] 비선형 활성화 (Non-linearity) ---
            # Sum 정보와 Bi 정보(상호작용)를 합쳐서 비선형 변환
            ego_embeddings = nn.LeakyReLU(negative_slope=0.2)(sum_embeddings + bi_embeddings)

            # --- [E] 메시지 드롭아웃 (Message Dropout) ---
            # 계산된 임베딩 값의 일부를 랜덤하게 0으로 만듦 (Feature level dropout)
            ego_embeddings = nn.Dropout(self.mess_dropout[k])(ego_embeddings)

            # --- [F] 정규화 (Normalization) ---
            # 임베딩 벡터의 크기(Norm)를 1로 맞춰 학습 발산을 막습니다.
            norm_embeddings = F.normalize(ego_embeddings, p=2, dim=1)

            # 현재 레이어의 결과 임베딩을 리스트에 저장
            all_embeddings += [norm_embeddings]

        # 모든 레이어의 임베딩을 결합 (Concatenation)
        all_embeddings = torch.cat(all_embeddings, 1)

        # 결합된 전체 임베딩을 다시 사용자와 아이템 부분으로 분리
        u_g_embeddings = all_embeddings[:self.n_user, :]
        i_g_embeddings = all_embeddings[self.n_user:, :]


        u_g_embeddings = u_g_embeddings[users, :]
        pos_i_g_embeddings = i_g_embeddings[pos_items, :]
        neg_i_g_embeddings = i_g_embeddings[neg_items, :]

        return u_g_embeddings, pos_i_g_embeddings, neg_i_g_embeddings

1-3. LightGCN

• NGCF는 가중치(W)와 비선형성(σ) 계산을 수행하느라 무겁고 학습 오래 걸림
• LightGCN은 가중치와 비선형성 계산을 제거하여 성능과 학습 속도 향상함
  • 이미지의 경우 노드 즉, 픽셀 값 자체에 의미가 없으므로 특징을 만들어내기 위해 가중치(W)와 비선형성(σ) 필수
  • 추천 시스템의 경우 각 노드는 그 자체로 의미가 있는 특징이므로, 가중치(W)와 비선형성(σ)은 과적합 가능성을 향상 시키고 학습이 오래걸리고 무거움

def computer(self):
    """
    LightGCN의 핵심: Embedding Propagation (임베딩 전파)
    NGCF와 달리 가중치 행렬(W)이나 활성화 함수(ReLU) 없이
    오직 그래프 구조(인접 행렬)만을 이용해 임베딩을 확산
    """       
    # 1. 초기 임베딩 (Layer 0) 준비
    # 학습 가능한 유일한 파라미터인 유저/아이템 ID 임베딩을 가져옵니다.
    users_emb = self.embedding_user.weight
    items_emb = self.embedding_item.weight

    # 유저와 아이템을 하나의 행렬로 합침 (Shape: [N+M, Embedding_Dim])
    all_emb = torch.cat([users_emb, items_emb])

    # 각 레이어별 임베딩을 저장할 리스트 (Layer 0 저장)
    embs = [all_emb]

    # 2. Graph Dropout
    # 과적합 방지를 위해 엣지(Edge)를 랜덤하게 끊어버린 그래프를 사용할지 결정
    if self.config['dropout']:
        if self.training:
            # 학습 중일 때만 드롭아웃 적용
            g_droped = self.__dropout(self.keep_prob)
        else:
            # 테스트 중일 때는 원본 그래프 사용
            g_droped = self.Graph        
    else:
        # 드롭아웃 미사용 시 미리 계산된 정규화 인접 행렬(Normalized Adj) 사용
        g_droped = self.Graph    

    # 3. Light Graph Convolution (레이어 통과)
    # 설정한 레이어 수(n_layers)만큼 반복하며 정보를 멀리까지 전파
    for layer in range(self.n_layers):
        if self.A_split:
            # (대용량 데이터 처리를 위해 그래프를 쪼개서 연산하는 경우)
            temp_emb = []
            for f in range(len(g_droped)):
                temp_emb.append(torch.sparse.mm(g_droped[f], all_emb))
            side_emb = torch.cat(temp_emb, dim=0)
            all_emb = side_emb
        else:
            # [핵심 로직] Linear Propagation
            #   - sparse.mm: 행렬 곱을 수행하여 "이웃의 정보를 가중 합(Weighted Sum)"함.
            #   - 중요: NGCF와 달리 W(가중치)를 곱하거나 ReLU를 씌우지 않음!
            all_emb = torch.sparse.mm(g_droped, all_emb)

        # 이번 레이어에서 확산된 임베딩을 리스트에 저장
        embs.append(all_emb)

    # 4. Layer Combination (최종 임베딩 생성)
    # embs 리스트 구조: [E^0, E^1, E^2, ...]
    # stack: 텐서를 쌓아서 차원 추가 (N+M, Layer+1, Dim)
    embs = torch.stack(embs, dim=1)

    # [LightGCN의 특징] 가중 합 대신 단순 평균(Mean) 사용
    # 이유: 
    #   - Layer 0 (본연의 특성)과 Layer K (이웃의 특성)를 골고루 반영하기 위함.
    #   - 학습 파라미터(Attention 등)를 줄여서 일반화 성능을 높임.
    light_out = torch.mean(embs, dim=1)

    # 최종 계산된 임베딩을 다시 유저용과 아이템용으로 분리하여 반환
    users, items = torch.split(light_out, [self.num_users, self.num_items])
    return users, items

1-4. SGL

• LightGCN 구조를 사용하면서 데이터를 스스로 증강하여 희소성 문제를 해결함

• 매 에폭마다 원본 그래프를 변형(Edge Dropout)하여 서로 다른 2개의 그래프 뷰(View 1, View 2)를 생성 (model.graph_reconstruction)

• 두 뷰(View 1, View 2)를 이용해 다음과 같은 대조 학습(Contrastive Learning)을 수행(model.cal_cl_loss)

  • 임베딩 추출: 두 뷰를 LightGCN에 각각 통과시켜, 동일한 유저에 대한 두 개의 임베딩 벡터(e1​,e2​)를 얻음 (model.forward)

  • Positive Pair 학습 (Alignment): e1​과 e2​는 비록 다른 그래프에서 나왔지만, 태생이 같은 유저이므로 임베딩 공간에서 서로 가까워지도록(Pull) 학습 (InfoNCE - 분자 부분)

  • Negative Pair 학습 (Uniformity): 반면, 다른 유저들의 임베딩과는 서로 멀어지도록(Push) 학습 (InfoNCE - 분모 부분)

• 위 과정을 통해 모델은 특정 엣지(구매 이력)가 우연히 없더라도 유저 고유의 특성을 파악할 수 있음 -> 하지만 매 에폭마다 그래프를 생성하므로 연산 비용 up

(1) 그래프 증강

def random_graph_augment(self):
        """
        [SGL의 핵심 1] 그래프 증강(Augmentation) 함수

        SGL은 학습 시 원본 그래프를 그대로 쓰지 않고, 
        노드나 엣지를 무작위로 제거하여 '어려운 문제'를 만듭니다.
        이를 통해 모델이 노이즈에 강해지고(Robust), 데이터 희소성을 극복하게 합니다.
        """
        dropped_mat = None

        # 1. 노드 드롭아웃 (Node Dropout)
        # 특정 유저나 아이템 노드를 아예 삭제해버림. (가장 강력한 변형)
        if self.aug_type == 0:
            dropped_mat = GraphAugmentor.node_dropout(self.data.interaction_mat, self.drop_rate)

        # 2. 엣지 드롭아웃 (Edge Dropout) - 논문에서 가장 성능이 좋았던 방식
        # 유저-아이템 간의 연결 선만 끊어냄.
        elif self.aug_type == 1 or self.aug_type == 2:
            dropped_mat = GraphAugmentor.edge_dropout(self.data.interaction_mat, self.drop_rate)

        # 3. 정규화 (Normalization)
        # 변형된 그래프도 GCN 연산을 위해 라플라시안 행렬(D^-0.5 A D^-0.5)로 변환
        dropped_mat = self.data.convert_to_laplacian_mat(dropped_mat)

        # PyTorch 텐서로 변환하여 GPU로 올림
        return TorchGraphInterface.convert_sparse_mat_to_tensor(dropped_mat).cuda()

(2) 대조 학습 손실 계산(Contrastive Loss)

def forward(self, perturbed_adj=None):
        ego_embeddings = torch.cat([self.embedding_dict['user_emb'], self.embedding_dict['item_emb']], 0)
        all_embeddings = [ego_embeddings]
        for k in range(self.n_layers):
            if perturbed_adj is not None:
                # 증강된 그래프 사용 (대조 학습용)
                if isinstance(perturbed_adj, list):
                    # 레이어별 다른 증강 그래프 사용 (aug_type=2)
                    ego_embeddings = torch.sparse.mm(perturbed_adj[k], ego_embeddings)
                else:
                    # 모든 레이어에서 같은 증강 그래프 사용 (aug_type=0,1)
                    ego_embeddings = torch.sparse.mm(perturbed_adj, ego_embeddings)
            else:
                # 원본 그래프 사용 (추천 손실 계산용)
                ego_embeddings = torch.sparse.mm(self.sparse_norm_adj, ego_embeddings)
            all_embeddings.append(ego_embeddings)

        # 모든 레이어 출력을 스택하고 평균
        all_embeddings = torch.stack(all_embeddings, dim=1)
        all_embeddings = torch.mean(all_embeddings, dim=1)
        user_all_embeddings, item_all_embeddings = torch.split(all_embeddings, [self.data.user_num, self.data.item_num])
        return user_all_embeddings, item_all_embeddings


def cal_cl_loss(self, idx, perturbed_mat1, perturbed_mat2):
        """
        [SGL의 핵심 2] InfoNCE Loss 계산 (대조 학습)

        서로 다르게 망가뜨린 두 그래프(View 1, View 2)에서 
        동일한 유저(u)의 임베딩은 가까워져야 하고(Positive Pair),
        다른 유저들과는 멀어져야 한다(Negative Pair)는 법칙을 수식화한 것입니다.
        """
        # 현재 배치의 유저와 아이템 인덱스
        u_idx = torch.unique(torch.Tensor(idx[0]).type(torch.long)).cuda()
        i_idx = torch.unique(torch.Tensor(idx[1]).type(torch.long)).cuda()

        # View 1 그래프를 통과시켜 얻은 임베딩
        user_view_1, item_view_1 = self.forward(perturbed_mat1)

        # View 2 그래프를 통과시켜 얻은 임베딩
        user_view_2, item_view_2 = self.forward(perturbed_mat2)

        # 계산 효율성을 위해 유저와 아이템 임베딩을 하나로 합침
        # view1: [유저_임베딩_1; 아이템_임베딩_1]
        # view2: [유저_임베딩_2; 아이템_임베딩_2]
        view1 = torch.cat((user_view_1[u_idx], item_view_1[i_idx]), 0)
        view2 = torch.cat((user_view_2[u_idx], item_view_2[i_idx]), 0)

        # InfoNCE Loss 계산
        # - 분자: 내 분신(view1의 나, view2의 나) 간의 유사도 (높여야 함)
        # - 분모: 나랑 다른 모든 노드들과의 유사도 합 (낮춰야 함)
        return InfoNCE(view1, view2, self.temp)

(3) 핵심 함수 InfoNCE

def InfoNCE(view1, view2, temperature: float, b_cos: bool = True):
    """
    InfoNCE (Information Noise Contrastive Estimation) 손실 함수

    대조 학습(Contrastive Learning)의 핵심 손실 함수로,
    같은 샘플의 서로 다른 뷰(양성 쌍)는 가깝게,
    다른 샘플의 뷰(음성 쌍)는 멀게 학습시킵니다.


    Args:
        view1: (torch.Tensor - N x D)
        view2: (torch.Tensor - N x D)
        temperature: float
        b_cos (bool)

    Return: Average InfoNCE Loss
    """
    if b_cos:
        view1, view2 = F.normalize(view1, dim=1), F.normalize(view2, dim=1)

    pos_score = (view1 @ view2.T) / temperature
    score = torch.diag(F.log_softmax(pos_score, dim=1))
    return -score.mean()

(4) 학습 루프

def train(self):
        """
        모델 학습 메서드

        학습 흐름:
        1. 각 에폭 시작 시 두 개의 증강된 그래프 생성
        2. 미니배치 단위로:
           - 원본 그래프로 추천 손실 계산
           - 증강된 그래프들로 대조 학습 손실 계산
           - 총 손실로 역전파 및 가중치 업데이트
        3. 에폭 5 이후부터 검증 평가 수행
        """
        # 모델을 GPU로 이동
        model = self.model.cuda()
        optimizer = torch.optim.Adam(model.parameters(), lr=self.lRate)
        for epoch in range(self.maxEpoch):
            # ==========================================================
            # [Step 1] 매 에폭마다 새로운 뷰(View) 생성
            # SGL이 느린 이유: 학습 할 때마다 그래프를 새로 그려야 함 (Reconstruction)
            # ==========================================================
            dropped_adj1 = model.graph_reconstruction() # 뷰 1 생성
            dropped_adj2 = model.graph_reconstruction() # 뷰 2 생성

            for n, batch in enumerate(next_batch_pairwise(self.data, self.batch_size)):
                user_idx, pos_idx, neg_idx = batch

                # [Step 2] Main Task: 추천 성능 학습 (BPR Loss)
                # 원본 그래프를 사용하여 "유저가 좋아한 아이템"을 맞추도록 학습
                rec_user_emb, rec_item_emb = model()
                user_emb, pos_item_emb, neg_item_emb = rec_user_emb[user_idx], rec_item_emb[pos_idx], rec_item_emb[neg_idx]
                rec_loss = bpr_loss(user_emb, pos_item_emb, neg_item_emb)

                # [Step 3] Self-supervised Task: 대조 학습 (Contrastive Learning)
                # 두 개의 증강된 그래프를 사용하여 노드끼리 가깝게, 다른 노드와는 멀게 학습
                cl_loss = self.cl_rate * model.cal_cl_loss([user_idx,pos_idx],dropped_adj1,dropped_adj2)

                # [Step 4] Joint Learning (최종 학습)
                # 추천도 잘하고(rec_loss) + 본질도 잘 파악해라(cl_loss)
                batch_loss =  rec_loss + l2_reg_loss(self.reg, user_emb, pos_item_emb,neg_item_emb) + cl_loss

                # 역전파 (Backpropagation)
                optimizer.zero_grad()
                batch_loss.backward()
                optimizer.step()
                if n % 100==0 and n>0:
                    print('training:', epoch + 1, 'batch', n, 'rec_loss:', rec_loss.item(), 'cl_loss', cl_loss.item())
            with torch.no_grad():
                self.user_emb, self.item_emb = self.model()
            if epoch>=5:
                self.fast_evaluation(epoch)
        self.user_emb, self.item_emb = self.best_user_emb, self.best_item_emb

1-5. SimGCL

• SGL은 매 에폭마다 그래프를 다시 만드는 과정이 느림
• SimGCL은 그래프 변형 대신, 임베딩 벡터에 노이즈를 더하는 방식 사용
  • SGL은 구조적 증강 -> 인접행렬을 변형
  • SimGCL은 특징 증강 -> user임베딩과 item임베딩에 변형
• 증강 방식: 임베딩 벡터 자체에 미세한 랜덤 노이즈를 추가하여 서로 다른 2개의 뷰(View 1, View 2)를 생성 (model.forward(perturbed=True))
• 대조학습은 SGL과 동일
• SGL 대비 매 에폭마다 그래프 생성 과정이 없으므로 학습 속도가 빠르고 메모리 효율적임

(1) 노이즈 주입

def forward(self, perturbed=False):
        """
        [SimGCL의 핵심 1] 노이즈 주입을 통한 임베딩 증강

        Args:
            perturbed (bool): True일 경우 대조 학습을 위해 노이즈를 추가함
        """
        # 1. 초기 임베딩 가져오기
        ego_embeddings = torch.cat([self.embedding_dict['user_emb'], 
                                    self.embedding_dict['item_emb']], 0)

        all_embeddings = []

        # 2. 레이어별 전파 (Graph Propagation)
        for k in range(self.n_layers):
            # 기본 LightGCN 전파: 이웃 정보 집계
            ego_embeddings = torch.sparse.mm(self.sparse_norm_adj, ego_embeddings)

            # -----------------------------------------------------------
            # [여기가 SGL과 다른 점!] 
            # 그래프 구조를 바꾸는 대신, 전파된 임베딩에 '노이즈'를 섞습니다.
            # -----------------------------------------------------------
            if perturbed:
                # (1) 랜덤 노이즈 생성 (0~1 사이 값)
                random_noise = torch.rand_like(ego_embeddings).cuda()

                # (2) 노이즈 스케일링 및 주입
                # torch.sign(ego): 원본 임베딩의 부호(방향)는 유지하되,
                # F.normalize(noise): 노이즈의 크기를 정규화하고,
                # self.eps: 아주 작은 값(예: 0.1)만큼만 흔들어줍니다.
                # 결과: "원래 위치에서 아주 살짝만 벗어난 임베딩" 생성
                ego_embeddings += torch.sign(ego_embeddings) * F.normalize(random_noise, dim=-1) * self.eps

            all_embeddings.append(ego_embeddings)

        # 3. 레이어 합치기 (Mean Aggregation)
        all_embeddings = torch.stack(all_embeddings, dim=1)
        all_embeddings = torch.mean(all_embeddings, dim=1)

        user_all_embeddings, item_all_embeddings = torch.split(all_embeddings, [self.data.user_num, self.data.item_num])
        return user_all_embeddings, item_all_embeddings

(2) 대조 학습 수행

def cal_cl_loss(self, idx):
        """
        [SimGCL의 핵심 2] 노이즈 뷰를 이용한 InfoNCE Loss 계산

        SGL은 그래프를 다시 만들어서 forward를 돌려야 했지만,
        SimGCL은 단순히 forward(perturbed=True)를 두 번 호출하면 끝입니다.
        """
        # 현재 배치의 유저/아이템 인덱스
        u_idx = torch.unique(torch.Tensor(idx[0]).type(torch.long)).cuda()
        i_idx = torch.unique(torch.Tensor(idx[1]).type(torch.long)).cuda()

        # [View 1 생성] 첫 번째 랜덤 노이즈가 섞인 임베딩
        user_view_1, item_view_1 = self.model(perturbed=True)

        # [View 2 생성] 두 번째 랜덤 노이즈가 섞인 임베딩 (노이즈 값이 다름)
        user_view_2, item_view_2 = self.model(perturbed=True)

        # [InfoNCE Loss]
        # 같은 유저(u_idx)의 view1과 view2는 서로 당기고(Pull),
        # 다른 유저들과는 서로 밀어냄(Push).
        # 이를 통해 임베딩 공간이 고르게 퍼지고(Uniformity), 표현력이 강해짐.
        user_cl_loss = InfoNCE(user_view_1[u_idx], user_view_2[u_idx], 0.2)
        item_cl_loss = InfoNCE(item_view_1[i_idx], item_view_2[i_idx], 0.2)

        return user_cl_loss + item_cl_loss

(3) 핵심 함수 InfoNCE

def InfoNCE(view1, view2, temperature: float, b_cos: bool = True):
    """
    InfoNCE (Information Noise Contrastive Estimation) 손실 함수

    대조 학습(Contrastive Learning)의 핵심 손실 함수로,
    같은 샘플의 서로 다른 뷰(양성 쌍)는 가깝게,
    다른 샘플의 뷰(음성 쌍)는 멀게 학습시킵니다.


    Args:
        view1: (torch.Tensor - N x D)
        view2: (torch.Tensor - N x D)
        temperature: float
        b_cos (bool)

    Return: Average InfoNCE Loss
    """
    if b_cos:
        view1, view2 = F.normalize(view1, dim=1), F.normalize(view2, dim=1)

    pos_score = (view1 @ view2.T) / temperature
    score = torch.diag(F.log_softmax(pos_score, dim=1))
    return -score.mean()

** github 링크

• https://github.com/huangtinglin/NGCF-PyTorch (NGCF)

• https://github.com/gusye1234/LightGCN-PyTorch (LightGCN)

• https://github.com/Coder-Yu/SELFRec/tree/main (SGL, SimGCL)

• 기존 범주형변수를 one-hot 인코딩하면 대부분의 값이 0이므로 매우 sparse해짐
• 위의 문제를 해결하기 위하여 임의의 길이의 실수 벡터로 밀집되게 표현하는 일련의 방법을 임베딩(embedding)이라 하고, 각 카테고리가 나타내는 실수 벡터를 임베딩 벡터라 함

• 관련 예시 코드 및 설명

  # 임베딩 벡터를 생성한 전체 범주의 개수가 10이고, 임베딩 벡터 차원이 3이므로 10*3 크기의 행렬 생성됨 -> 정규분포를 따르는 랜덤값으로 초기화됨
  embedding = nn.Embedding(10, 3)
  

이미 만들어진 embedding에서 2개의 샘플을 복사해서 가져오는 Lookup 작업을 함.

이때 1번째 샘플은 embedding 행렬의 1,2,4,5 행의 임베딩 벡터를 가져오고,

2번째 샘플은 4,3,2,9 행의 임베딩 벡터를 가져옴

input = torch.LongTensor([[1, 2, 4, 5], [4, 3, 2, 9]]) embedding(input)

결과값

tensor([[[-0.0251, -1.6902, 0.7172], [-0.6431, 0.0748, 0.6969], [ 1.4970, 1.3448, -0.9685], [-0.3677, -2.7265, -0.1685]],

    [[ 1.4970,  1.3448, -0.9685],
     [ 0.4362, -0.4004,  0.9400],
     [-0.6431,  0.0748,  0.6969],
     [ 0.9124, -2.3616,  1.1151]]])

## - nn.init
- 가중치 초기화 관련 기본 개념 정리
    - https://velog.io/@vinyl-bin/%EB%94%A5%EB%9F%AC%EB%8B%9D-%EA%B0%80%EC%A4%91%EC%B9%98-%EC%B4%88%EA%B8%B0%ED%99%94-Xavier-He-%EC%B4%88%EA%B8%B0%ED%99%94

### (1) Xavier 초기화

import torch

빈 텐서 생성

tensor_uniform = torch.empty(3, 5) tensor_normal = torch.empty(3, 5)

균등 분포로 초기화

torch.nn.init.xavier_uniform_(tensor_uniform, gain=1.0, generator=None) print(f'균등 분포 ', tensor_uniform )

정규 분포로 초기화

torch.nn.init.xavier_normal_(tensor_normal, gain=1.0) print(f'정규 분포',tensor_normal)

균등 분포 tensor([[-0.5576, -0.7264, 0.2654, -0.7511, -0.3088], [ 0.7059, 0.6009, -0.6884, -0.0664, 0.7435], [ 0.5134, 0.6118, 0.2403, 0.0801, 0.7607]]) 정규 분포 tensor([[ 0.9741, 0.1742, -1.0699, -0.1486, 0.2731], [-0.2109, -0.2306, 0.7515, -0.9540, 1.0228], [-0.4853, 0.2636, 0.6432, -0.1358, -0.4924]])

출처: https://resultofeffort.tistory.com/114 [resultofeffort:티스토리]

#### 파라미터 설명
- tensor_uniform : 가중치 초기화할 타겟 행렬
- gain(float, optional) : 기본값 1.0으로, 초기화 값의 크기를 조절하는 배율
![](https://velog.velcdn.com/images/vinyl-bin/post/a8750cac-994e-4701-bfd9-d85ea0d468ed/image.png)
- generator(optional) : 기본값 None으로, 난수 생성할 때 사용하는 시드 생성기, 해당 generator를 넣으면 항상 똑같은 랜덤값을 나오게 고정할 수 있음(재현성 보장) 

### (2) He 초기화

import torch

tensor_uniform = torch.empty(3, 5) torch.nn.init.kaiming_uniform_(tensor_uniform, mode='fan_in', nonlinearity='relu', generator=None) print(f'균등 분포 ', tensor_uniform )

tensor_normal = torch.empty(3, 5) torch.nn.init.kaiming_normal_(tensor_normal, mode='fan_in', nonlinearity='relu', generator=None) print(f'정규 분포',tensor_normal)

출처: https://resultofeffort.tistory.com/114 [resultofeffort:티스토리]

#### 파라미터 설명
- tensor_uniform : 가중치 초기화할 타겟 행렬
- mode : 기본값 fan_in, He 초기화 공식에서 분모에 넣을 값 정함
    - fan_in : 들어오는 노드 수를 기준으로 분산 맞춤
    - fan_out : 나가는 노드 수를 기준으로 분산 맞춤
- nonlinearity : 기본값 relu, 어떤 활성화 함수를 사용할지 적으면 적절한 gain 값을 계산해서 적용
- generator(optional) : 기본값 None으로, 난수 생성할 때 사용하는 시드 생성기, 해당 generator를 넣으면 항상 똑같은 랜덤값을 나오게 고정할 수 있음(재현성 보장) 

## - torch.cat
- Concatenate의 약자로, 주어진 차원(dim)을 기준으로 텐서들을 이어 붙임
- 연결하려는 차원을 제외한 나머지 차원의 크기가 반드시 같아야 함

import torch

t1 = torch.tensor([[1, 2], [3, 4]]) # (2, 2) t2 = torch.tensor([[5, 6], [7, 8]]) # (2, 2)

dim=0 (행 기준, 세로로 붙이기)

cat_0 = torch.cat([t1, t2], dim=0)

dim=1 (열 기준, 가로로 붙이기)

cat_1 = torch.cat([t1, t2], dim=1)

print("dim=0:", cat_0) print("dim=1:", cat_1)

결과값

dim=0: tensor([[1, 2], [3, 4], [5, 6], [7, 8]]) dim=1: tensor([[1, 2, 5, 6], [3, 4, 7, 8]])

## - torch.stack
- 새로운 차원을 생성하며 텐서들을 결합함
- cat은 기존 차원을 늘리는 것이고, stack은 새로운 차원을 하나 더 만드는 것이 차이점
- 모든 입력 텐서의 크기(shape)가 정확히 같아야 함

import torch

t1 = torch.tensor([1, 2]) t2 = torch.tensor([3, 4])

dim=0에 쌓기 (새로운 차원 추가)

t1, t2는 (2,) 크기 -> stack 후 (2, 2) 크기가 됨

stacked = torch.stack([t1, t2], dim=0) print(stacked)

결과값

tensor([[1, 2], [3, 4]])

## - torch.matmul
- 두 텐서의 행렬 곱(Matrix Multiplication)을 수행
- 더 자세한 설명 : https://velog.io/@passiona2z/%EC%9E%91%EC%84%B1%EC%A4%91-PyTorch-%ED%85%90%EC%84%9C%EA%B0%84%EC%9D%98-%EA%B3%B1%EC%85%88 

import torch

mat1 = torch.tensor([[1, 2], [3, 4]]) # (2, 2) mat2 = torch.tensor([[1, 0], [0, 1]]) # (2, 2) 단위 행렬

행렬 곱

result = torch.matmul(mat1, mat2) print(result)

결과값

tensor([[1, 2], [3, 4]])

## - torch.sparse.mm
- 희소 행렬(Sparse Matrix)과 밀집 행렬(Dense Matrix)의 곱셈을 수행
- 추천 시스템이나 GNN에서 인접 행렬(Adjacency Matrix)은 대부분 0인 희소 행렬이므로, 메모리 효율을 위해 일반 matmul 대신 사용함
- mat1은 희소 텐서(Sparse Tensor), mat2는 밀집 텐서(Dense Tensor)여야 함

import torch

1. 희소 텐서 생성 (Indices와 Values로 정의)

(0, 1) 위치에 3, (1, 2) 위치에 4가 있는 2x3 행렬

i = torch.LongTensor([[0, 1], [1, 2]]) v = torch.FloatTensor([3, 4]) sparse_mat = torch.sparse_coo_tensor(i, v, (2, 3))

2. 밀집 텐서 생성 (3x2 행렬)

dense_mat = torch.tensor([[1, 0], [0, 1], [1, 0]], dtype=torch.float32)

3. 행렬 곱 (2x3) @ (3x2) -> (2x2)

res = torch.sparse.mm(sparse_mat, dense_mat) print(res)

결과값

[0행] (0,1)값 3 * [1행] (0,1) -> 30 + 31 = 3

tensor([[0., 3.], [4., 0.]])

## - torch.mul
- 두 텐서의 원소별 곱셈(Element-wise multiplication) 을 수행
- 행렬 곱(matmul)이 아님. 같은 위치에 있는 원소끼리 곱함

import torch

a = torch.tensor([[1, 2], [3, 4]]) b = torch.tensor([[2, 2], [2, 2]])

원소별 곱셈 (12, 22, 32, 42)

result = torch.mul(a, b) print(result)

결과값

tensor([[2, 4], [6, 8]])

## - torch.split
- 텐서를 특정 크기(size) 혹은 섹션 개수로 나눔
- torch.cat의 반대 연산

import torch

t = torch.tensor([1, 2, 3, 4, 5, 6])

2개씩 자르기

split_t = torch.split(t, 2) print(split_t)

리스트 형태로 각 텐서 반환

결과값

(tensor([1, 2]), tensor([3, 4]), tensor([5, 6]))

## - torch.rand_like
- 입력 텐서와 동일한 크기(Shape) 와 데이터 타입(dtype) 을 가지는 텐서를 생성하되, 값은 0~1 사이의 랜덤 값으로 채움
- torch.rand(input.size(), dtype=input.dtype, ...)와 동일함

import torch

input_tensor = torch.empty(2, 3) # (2, 3) 크기 random_tensor = torch.rand_like(input_tensor)

print(random_tensor)

결과값 (랜덤)

tensor([[0.8231, 0.4123, 0.1982], [0.2141, 0.6521, 0.9812]])

## - torch.sign
- 입력 텐서 각 요소의 부호(Sign) 를 반환함
- 양수면 1, 음수면 -1, 0이면 0을 반환

import torch

t = torch.tensor([10, -5, 0, 3.5, -0.1]) result = torch.sign(t)

print(result)

결과값

tensor([ 1., -1., 0., 1., -1.])

## - nn.Sequential
- 여러 nn.Module들을 순차적으로 포장하는 컨테이너
- 내부에 정의된 순서대로 데이터가 통과하며, forward() 메서드를 직접 정의할 필요 없이 자동으로 순전파가 실행됨
- 가독성이 좋고 코드가 간결해지지만, 분기(Branching)나 반복문 등 복잡한 제어 흐름을 구현하기에는 제한적임

import torch import torch.nn as nn

model = nn.Sequential( nn.Linear(10, 20), nn.ReLU(), nn.Linear(20, 10) )

print(model)

## - nn.ModuleList
- nn.Module들을 파이썬 리스트(List)처럼 인덱싱으로 관리하는 컨테이너
- nn.Sequential과 달리 자동으로 연결되지 않음. 따라서 forward() 메서드에서 반복문이나 인덱싱을 통해 직접 실행 순서를 정의해야 함
- 파이썬의 기본 list 대신 사용하는 이유는, nn.ModuleList에 넣어야만 PyTorch가 해당 모듈들의 파라미터(가중치)를 모델의 학습 대상으로 인식하기 때문임

import torch import torch.nn as nn

class MyModel(nn.Module): def init(self): super(MyModel, self).init() self.layers = nn.ModuleList([ nn.Linear(10, 20), nn.ReLU(), nn.Linear(20, 10) ])

def forward(self, x):
    for layer in self.layers:
        x = layer(x)
    return x

model = MyModel() print(model)

## - nn.ModuleDict
- nn.Module들을 파이썬 딕셔너리(Dictionary)처럼 키(Key)와 값(Value)으로 관리하는 컨테이너
- 데이터의 타입이나 조건에 따라 서로 다른 레이어를 선택적으로 실행해야 할 때 유용함
- nn.ModuleList와 마찬가지로 forward()에서 실행 로직을 직접 구현해야 함

import torch import torch.nn as nn

class MyModel(nn.Module): def init(self): super(MyModel, self).init() self.layers = nn.ModuleDict({ 'fc1': nn.Linear(10, 20), 'relu': nn.ReLU(), 'fc2': nn.Linear(20, 10) })

def forward(self, x):
    x = self.layers['fc1'](x)
    x = self.layers['relu'](x)
    x = self.layers['fc2'](x)
    return x

model = MyModel() print(model)

## - nn.Parameter
- Tensor의 하위 클래스로, nn.Module 안에서 속성으로 할당될 때 자동 학습 대상 리스트인 parameter에 등록되는 변수
- 일반 Tensor 대신 nn.Parameter를 사용해야 단순 데이터가 아닌 학습시켜야할 가중치인 것을 인식함
- forward 함수에서 수식을 작성하면 pytorch에서 자동으로 역전파 시 가중치 업데이트 함

import torch import torch.nn as nn

class MyModel(nn.Module): def init(self): super().init() # Case 1: 일반 Tensor로 선언 # 모델은 이것을 그냥 '고정된 숫자 데이터'로 취급함 (학습 X, 상수로 변하지 않음) self.my_tensor = torch.randn(1)

    # Case 2: nn.Parameter로 감싸서 선언
    # 모델은 이것을 '학습해야 할 가중치'로 등록함 (학습 O)
    self.my_param = nn.Parameter(torch.randn(1))

def forward(self, x):
    # 우리는 그저 수식만 적으면 됨 (어떻게 학습할지는 PyTorch가 알아서 함)
    # y = x * W + b 형태
    return x * self.my_param + self.my_tensor

model = MyModel()

모델이 인식한 '학습 대상' 목록 확인

print(f"학습 대상 파라미터: {list(model.parameters())}")

결과값

my_tensor는 무시되고, my_param만 리스트에 존재함!

>> 학습 대상 파라미터: [Parameter containing: tensor([-0.5421], requires_grad=True)]

## - nn.ParameterDict
- nn.Parameter을 key와 value 형태의 딕셔너리로 관리하는 컨테이너
- 노드 타입이나 엣지 타입별로 서로 다른 가중치를 이름으로 구분하여 관리할 때 사용

import torch import torch.nn as nn

class GNNLayer(nn.Module): def init(self): super().init() # 타입별로 다른 가중치를 딕셔너리로 관리 self.weights = nn.ParameterDict({ 'user': nn.Parameter(torch.randn(5, 5)), 'item': nn.Parameter(torch.randn(5, 5)) })

def forward(self, x, node_type):
    # 입력된 node_type('user' or 'item')에 맞는 파라미터를 꺼내서 연산
    # 마찬가지로 수식만 적으면 해당 파라미터만 자동으로 학습됨
    w = self.weights[node_type]
    return torch.matmul(x, w)

model = GNNLayer()

'user' 타입 가중치 확인

print(f"User Weights Size: {model.weights['user'].size()}")

결과값

>> User Weights Size: torch.Size([5, 5])

## - 그 외 궁금점
#### (1) nn.Parameter를 안쓰면 가중치(w)와 편향(b)은 어디서 정해지고 학습되는지?
- 보통 nn.Linear에서 내부적으로 알아서 nn.Parameter를 생성해줌. 만약 nn.Linear를 사용하지 않으면 nn.Parameter로 정해줘야 함.

#### (2) (x×W+b)/d 와 같은 커스텀 수식 코드
- d도 학습시켜서 최적의 값을 찾아야 할 때 

class MyModel(nn.Module): def init(self): super().init() self.W = nn.Parameter(torch.randn(1)) # 가중치 (학습 O) self.b = nn.Parameter(torch.randn(1)) # 편향 (학습 O) self.d = nn.Parameter(torch.randn(1)) # 나누는 값 (학습 O)

def forward(self, x):
    # 수식 그대로 작성
    return (x * self.W + self.b) / self.d

- d는 상수로 학습을 안시켜도 될 때

class MyModel(nn.Module): def init(self): super().init() self.W = nn.Parameter(torch.randn(1)) self.b = nn.Parameter(torch.randn(1)) # d는 학습 안 함 (상수) self.d = 2.0

def forward(self, x):
    return (x * self.W + self.b) / self.d

```

*참고

• https://docs.pytorch.org/docs/stable/generated/torch.nn.Embedding.html
• https://hongl.tistory.com/244
• https://resultofeffort.tistory.com/114
• https://ds31x.tistory.com/266

• 데이터 전처리(Preprocessing)와 데이터 증강(Augmentation)을 수행

1-1. 관련 코드

# pytorch pre-loaded 데이터 로딩 코드

import torch
from torchvision import datasets
from torchvision.transforms import ToTensor, Lambda

ds = datasets.FashionMNIST(
    root="data",
    train=True,
    download=True,
    transform=ToTensor(),
    target_transform=Lambda(lambda y: torch.zeros(10, dtype=torch.float).scatter_(0, torch.tensor(y), value=1))
)

• ToTensor() 함수 : 데이터를 Pytorch 텐서(Tensor)로 변환하고, 픽셀 값을 0.0~1.0 범위로 스케일링

  transform=ToTensor()

• PIL Image/Numpy를 PyTorch의 기본 단위인 FloatTensor로 바꾸면서 특성스케일링인 정규화(값의 범위를 0.0 ~ 1.0으로) 진행

• 차원 변경 : (높이, 너비, 채널) -> (채널, 높이, 너비) ```

• Lambda() 함수 : 사용자 정의 함수(lambda)를 적용하여 정답 데이터를 변형

  target_transform=Lambda(lambda y: torch.zeros(10, dtype=torch.float).scatter_(0, torch.tensor(y), value=1))

• 해당 코드에서는 원-핫 인코딩 수행

• y : 정답 라벨

• torch.zeros(10, dtype=torch.float) : (1차원)길이가 10인 float 0으로 채워진 벡터 생성

• .scatter_(0, torch.tensor(y), value=1) : 0번째 차원(1차원) 기준으로, 앞서 torch.zeros에서 만든 벡터의 y번째 인덱스에 value 1를 할당

2. nn.Module(신경망 모델 구성)

• 신경망을 구성하는데 필요한 모든 구성 요소 제공 (레이어, 활성화 함수, 손실함수 등)

• 더 자세한 함수 https://docs.pytorch.org/docs/stable/nn.html

예시 코드

import os
import torch
from torch import nn
from torch.utils.data import DataLoader
from torchvision import datasets, transforms

device = (
    "cuda"
    if torch.cuda.is_available()
    else "mps"
    if torch.backends.mps.is_available()
    else "cpu"
)
print(f"Using {device} device")

class NeuralNetwork(nn.Module):
    def __init__(self):
        super().__init__()
        self.flatten = nn.Flatten()
        self.linear_relu_stack = nn.Sequential(
            nn.Linear(28*28, 512),
            nn.ReLU(),
            nn.Linear(512, 512),
            nn.ReLU(),
            nn.Linear(512, 10),
        )

    def forward(self, x):
        x = self.flatten(x)
        logits = self.linear_relu_stack(x)
        return logits

model = NeuralNetwork().to(device)
print(model)

X = torch.rand(1, 28, 28, device=device)
logits = model(X)
pred_probab = nn.Softmax(dim=1)(logits)
y_pred = pred_probab.argmax(1)
print(f"Predicted class: {y_pred}")

2-1. 코드 설명

- __init__

• 사용할 레이어들을 선언 (신경망 계층 초기화)

  - forward()

• 순전파, __init__에서 선언한 레이어 사용

• 주의: model.forward()는 직접 호출하면 안됨, 무조건 model를 사용해야함

  - nn.Flatten()

• 평탄화 계층

• n차원을 1차원 배열로 변환 -> 다음 레이어인 nn.Linear는 1차원 데이터만 받을 수 있기 때문

  - nn.Sequential()

• 내부에 정의된 레이어를 순서대로 실행해주는 컨테이너

  - nn.Linear()

• 선형 변환 적용 계층 -> 1차원 데이터만 받을 수 있음

• 가중치와 편향을 사용하여 입력에 선형 변환 적용

  - nn.ReLU()

• 활성화 함수 -> 보통 은닉층에서 사용됨 -> 특징 잘 학습하기 위해

• 비선형성 적용 계층

• 입력과 출력 사이에 복잡한 관계(mapping) 만듬

  - nn.Softmax()

• 활성화 함수 -> 보통 출력층에서 사용됨 -> 최종 결과를 확률로 해석하기 위해

• softmax(다중분류), sigmoid(이진분류)에 사용됨

  - 전체 코드 설명

  # 1. 신경망 모델 정의 (nn.Module을 상속받아야 함)
  class NeuralNetwork(nn.Module):
    def __init__(self):
        super().__init__() # 부모 클래스(nn.Module) 초기화 (필수!)
  
        # 평탄화 계층: 28x28(2차원) 이미지를 784(1차원) 벡터로 쫙 펴주는 역할
        self.flatten = nn.Flatten()
  
        # 순차 컨테이너: 내부에 정의된 층들을 순서대로 통과시킴
        self.linear_relu_stack = nn.Sequential(
            nn.Linear(28*28, 512), # 입력층 -> 은닉층1 (입력 784개, 출력 512개)
            nn.ReLU(),             # 활성화 함수 (비선형성 추가)
            nn.Linear(512, 512),   # 은닉층1 -> 은닉층2 (입력 512개, 출력 512개)
            nn.ReLU(),             # 활성화 함수
            nn.Linear(512, 10),    # 은닉층2 -> 출력층 (출력 10개 = 클래스 개수)
        )
  
    # 순전파(Forward): 데이터가 모델을 통과하는 경로 정의
    def forward(self, x):
        x = self.flatten(x)                # 1. 이미지를 1차원으로 폄
        logits = self.linear_relu_stack(x) # 2. 신경망 층을 통과 (결과값은 Logits)
        return logits                      # 3. Logits 반환 (아직 확률 아님)
  

2. 모델 인스턴스 생성 및 장치(CPU/GPU)로 이동

device 변수는 앞서 정의되어 있어야 함 (예: "cuda" or "cpu")

model = NeuralNetwork().to(device) print(model) # 모델 구조 출력 확인

3. 모델 테스트 (추론)

더미(가짜) 입력 데이터 생성 (배치크기 1, 28x28 이미지)

X = torch.rand(1, 28, 28, device=device)

모델에 입력 데이터 넣고 예측 실행

주의: model.forward(X)가 아니라 model(X)로 호출해야 함!

logits = model(X)

예측 결과(Logits)를 확률(Probability)로 변환

dim=1은 클래스 차원을 기준으로 합이 1이 되게 하라는 뜻

pred_probab = nn.Softmax(dim=1)(logits)

가장 높은 확률을 가진 클래스의 인덱스(번호) 추출

y_pred = pred_probab.argmax(1)

print(f"Predicted class: {y_pred}")

## 3. Optimization(최적화)
- 준비된 데이터와 모델을 활용하여 매개변수 최적화하여 모델 학습, 검증, 테스트 진행
    - epoch -> 반복
    - loss -> 추측과 정답 사이 오류
    - optimize -> 오류의 도함수를 수집한 뒤 경사하강법을 사용하여 파라미터 최적화
    - train_loop -> model, loss, backward, optimizer.step 실행
       - model은 문제풀기(답을 찍는 행동)
       - loss는 정답지와 비교하여 틀린 점수 확인
       - backward는 loss를 미분하여 틀린 부분 찾는 과정 -> 미분으로 기울기 계산
       - optimizer는 가중치 수정하여 잘 맞히도록 수정 -> 계산된 기울기만큼 가중치 수정

- 더 자세한 설명 : https://tutorials.pytorch.kr/beginner/basics/optimization_tutorial.html

예시 코드

import torch from torch import nn from torch.utils.data import DataLoader from torchvision import datasets from torchvision.transforms import ToTensor

학습 데이터 로드

training_data = datasets.FashionMNIST( root="data", train=True, download=True, transform=ToTensor() )

테스트 데이터 로드

test_data = datasets.FashionMNIST( root="data", train=False, download=True, transform=ToTensor() )

train_dataloader = DataLoader(training_data, batch_size=64) test_dataloader = DataLoader(test_data, batch_size=64)

device = "cuda" if torch.cuda.is_available() else "cpu"

모델 구성

class NeuralNetwork(nn.Module): def init(self): super().init() self.flatten = nn.Flatten() self.linear_relu_stack = nn.Sequential( nn.Linear(28*28, 512), nn.ReLU(), nn.Linear(512, 512), nn.ReLU(), nn.Linear(512, 10), )

# 순전파 실행
def forward(self, x):
    x = self.flatten(x)
    logits = self.linear_relu_stack(x)
    return logits

model = NeuralNetwork().to(device)

실제 학습 실행 (데이터, 모델, 손실함수, 옵티마이저를 매개변수로)

def train_loop(dataloader, model, loss_fn, optimizer): size = len(dataloader.dataset) model.train() for batch, (X, y) in enumerate(dataloader): X, y = X.to(device), y.to(device)

    pred = model(X)
    loss = loss_fn(pred, y)

    loss.backward()
    optimizer.step()
    optimizer.zero_grad()

    if batch % 100 == 0:
        loss, current = loss.item(), batch * len(X)
        print(f"loss: {loss:>7f}  [{current:>5d}/{size:>5d}]")

테스트 실행 (데이터, 모델, 손실함수)

def test_loop(dataloader, model, loss_fn): model.eval() size = len(dataloader.dataset) num_batches = len(dataloader) test_loss, correct = 0, 0

with torch.no_grad():
    for X, y in dataloader:
        X, y = X.to(device), y.to(device)
        pred = model(X)
        test_loss += loss_fn(pred, y).item()
        correct += (pred.argmax(1) == y).type(torch.float).sum().item()

test_loss /= num_batches
correct /= size
print(f"Test Error: \n Accuracy: {(100*correct):>0.1f}%, Avg loss: {test_loss:>8f} \n")

learning_rate = 1e-3 batch_size = 64 loss_fn = nn.CrossEntropyLoss() optimizer = torch.optim.SGD(model.parameters(), lr=learning_rate)

epochs = 10 for t in range(epochs): print(f"Epoch {t+1}\n-------------------------------") train_loop(train_dataloader, model, loss_fn, optimizer) test_loop(test_dataloader, model, loss_fn)

print("Done!")

```

참고

• https://tutorials.pytorch.kr/beginner/basics/intro.html
• https://aitechmind.tistory.com/entry/%ED%8C%8C%EC%9D%B4%ED%86%A0%EC%B9%98-%ED%8A%9C%ED%86%A0%EB%A6%AC%EC%96%BC-%EA%B8%B0%EC%B4%88%EB%B6%80%ED%84%B0-%EC%8B%A4%EC%A0%84%EA%B9%8C%EC%A7%80

• 배열(array)이나 행렬(matrix)과 매우 유사한 특수한 자료구조
• GPU 연산이 가능, 자동 미분(Autograd) 지원

1-1. 함수

• torch.zeros(): 0으로 채워진 텐서
• torch.ones(): 1로 채워진 텐서
• torch.randn(): 정규분포를 따르는 랜덤 텐서
• torch.tensor(): 리스트나 배열을 텐서로 변환
• tensor.shape : 텐서 모양
• tensor.dtype : 텐서 자료형
• tensor.device : 텐저 장치
• • 실제로 코드를 작성할 때 차원이 맞지 않아서 생기는 오류가 많으므로 텐서의 shape과 dtype을 항상 확인!

1-2. 텐서 연산

• https://docs.pytorch.org/docs/stable/torch.html

  tensor = torch.ones(4, 4)
  print(f"First row: {tensor[0]}")
  print(f"First column: {tensor[:, 0]}")
  print(f"Last column: {tensor[..., -1]}")
  tensor[:,1] = 0
  print(tensor)
  

출력값 First row: tensor([1., 1., 1., 1.]) First column: tensor([1., 1., 1., 1.]) Last column: tensor([1., 1., 1., 1.]) tensor([[1., 0., 1., 1.], [1., 0., 1., 1.], [1., 0., 1., 1.], [1., 0., 1., 1.]])

## 2. Autograd(자동 미분)
- 역전파 알고리즘을 수행하기 위해 손실함수의 그레디언트(기울기)를 구해야함
- Autograd를 활용하여 그레디언트(손실함수의 변화도)를 구함

### 2-1. 예시
- 단층 퍼셉트론 코드 및 그래프

import torch

x = torch.ones(5) # input tensor y = torch.zeros(3) # expected output w = torch.randn(5, 3, requires_grad=True) b = torch.randn(3, requires_grad=True) z = torch.matmul(x, w)+b loss = torch.nn.functional.binary_cross_entropy_with_logits(z, y)

![](https://velog.velcdn.com/images/vinyl-bin/post/25ff62bb-3e83-425e-8396-4b898ab8f1f1/image.png)

- 코드 설명

1. 입력 데이터 x = torch.ones(5)

• x = [1, 1, 1, 1, 1]

2. 정답 데이터 y = torch.zeros(3)

• y = [0, 0, 0]

3. 학습을 통해 맞춰나가야할 가중치(weight) w = torch.randn(5, 3, requires_grad=True)

• 5행 3열 행렬 (입력 5개일 때 출력 3개로)
• randn:평균이 0이고 표준편차가 1인 정규분포에서 랜덤한 숫자 뽑음
• requires_grad=True : Autograd(자동미분) 실행, 나중에 역전파로 w 학습을 하기 위해 미분(기울기)값 기록함

4. 학습을 통해 맞춰나가야할 편향(bias) b = torch.randn(3, requires_grad=True)

• 1행 3열 행렬
• randn:평균이 0이고 표준편차가 1인 정규분포에서 랜덤한 숫자 뽑음
• requires_grad=True : Autograd(자동미분) 실행, 나중에 역전파로 b 학습을 하기 위해 미분(기울기)값 기록함

5. 곱하기 더하기 연산 z = torch.matmul(x, w)+b

• 입력(x)에 가중치 w를 곱하고 편향 b를 더함(z = wx + b)

6. 오차 계산 loss = torch.nn.functional.binary_cross_entropy_with_logits(z, y)

• 예측값 z와 정답 y가 얼마나 차이나는지 계산
• CE는 Cross Entropy를 말함, 다른 오차 함수로는 MSE가 있음

즉, requires_grad=True 이 설정으로 Autograd 적용함

## 3. Dataset과 DataLoader
- 데이터 샘플을 처리하는 코드는 지저분(messy)하고 유지보수가 어려울 수 있음
- 데이터셋 코드를 모델 학습 코드로부터 분리하는 것이 이상적

### 3-1. Dataset
- torch.utils.data.Dataset
- 샘플과 정답(label) 지정
- 미리 준비해둔(pre-loaded) 데이터셋이 존재함

import torch from torch.utils.data import Dataset from torchvision import datasets from torchvision.transforms import ToTensor import matplotlib.pyplot as plt

training_data = datasets.FashionMNIST( root="data", train=True, download=True, transform=ToTensor() )

test_data = datasets.FashionMNIST( root="data", train=False, download=True, transform=ToTensor() )

- 사용자가 준비한(사용자 정의) 데이터셋 사용 가능
    - 사용자 정의 Dataset 클래스는 반드시 3개 함수를 구현해야 함
    ```__init__, __len__, __getitem__```

import os import pandas as pd from torchvision.io import read_image

class CustomImageDataset(Dataset): def init(self, annotations_file, img_dir, transform=None, target_transform=None): self.img_labels = pd.read_csv(annotations_file, names=['file_name', 'label']) self.img_dir = img_dir self.transform = transform self.target_transform = target_transform

def __len__(self):
    return len(self.img_labels)

def __getitem__(self, idx):
    img_path = os.path.join(self.img_dir, self.img_labels.iloc[idx, 0])
    image = read_image(img_path)
    label = self.img_labels.iloc[idx, 1]
    if self.transform:
        image = self.transform(image)
    if self.target_transform:
        label = self.target_transform(label)
    return image, label

### 3-2. DataLoader
- torch.utils.data.DataLoader
- Dataset 을 샘플에 쉽게 접근할 수 있도록 순회 가능한 객체(iterable)로 감쌈
- 미니배치(minibatch)로 전달하고, 매 에폭(epoch)마다 데이터를 다시 섞어서 과적합(overfit)을 막고, Python의 multiprocessing 을 사용하여 데이터 검색 속도를 높임

from torch.utils.data import DataLoader

train_dataloader = DataLoader(training_data, batch_size=64, shuffle=True) test_dataloader = DataLoader(test_data, batch_size=64, shuffle=True)

```

*. 관련 개념

- 선형 변환(Linear Transformation)

• 데이터를 이동시키고 늘리는 가장 기초적인 작업
• 수식: y = wx + b (항상 수식이 동일함)
• 의미: 입력 데이터(x)에 가중치(w)를 곱하고 편향(b)을 더함
• 특징:그래프로 그리면 무조건 '직선'이나 '평면' 형태가 나옴

  - 비선형 변환(Non-linear Transformation)

• 직선(선형변환 결과)을 구부려서 복잡한 문제를 풀게 함
• 활성화 함수가 이 역할을 함
• 종류: Sigmoid, ReLU, Tanh 등
• 의미: 선형 변환된 결과값을 구부러지거나 꺾인 형태로 바꿈
• 특징:
  • 직선을 곡선으로 만들어 줌
  • 이 과정이 있어야 신경망이 복잡한 데이터(사람 얼굴, 자연어 등)의 경계선을 그려낼 수 있음

참고

• https://sig413.tistory.com/98
• https://aitechmind.tistory.com/entry/%ED%8C%8C%EC%9D%B4%ED%86%A0%EC%B9%98-%ED%8A%9C%ED%86%A0%EB%A6%AC%EC%96%BC-%EA%B8%B0%EC%B4%88%EB%B6%80%ED%84%B0-%EC%8B%A4%EC%A0%84%EA%B9%8C%EC%A7%80
• https://tutorials.pytorch.kr/

- 활성화함수

• 뉴런에서 출력값을 변경시키는 함수, 비선형함수
• 입력 신호의 총합을 출력 신호로 변환하는 함수로, 입력 받은 신호를 얼마나 출력할지 결정하고 네트워크에 층을 쌓아 비선형성을 표현
• 시그모이드 함수, 소프트맥스 함수, 하이퍼볼릭탄젠트 함수, 렐루 함수

- 옵티마이저(Optimizer)

• loss 함수의 최소값을 찾아가는(최적화) 알고리즘
• 계산된 그레디언트를 바탕으로 실제로 가중치를 어떻게 갱신할지 결정

- 순전파(Forward Propagation)

• 입력층에서 출력층 방향으로 연산 전개

  - 역전파(Back Propagation)

• 출력층에서 계산된 오차를 입력층 방향으로 거꾸로 전파하여 각 가중치의 그레디언트를 구하는 알고리즘

  - 가중치

• 입력 신호가 출력에 미치는 크기
• 신경망에서 학습한다는 것은 가중치 값들을 최적의 값으로 조정하는 과정을 말함

  - 은닉층

• 입력층과 출력층 사이에 있는 층

  - 손실함수

• 신경망이 예측한 값과 실제 값 사이의 오차 측정
• 학습의 최종 목표는 손실함수 값을 0에 가깝게 최소화 하는 것

  - 그레디언트(기울기)

• 손실함수를 가중치로 미분한 값
• 오차 줄이기 위해 가중치를 어떤 방향으로 얼마나 움직여야 하는지 나타냄
• 기울기가 가파르면 오차 줄일 여지가 많음

참고

• https://222ys.tistory.com/19
• https://velog.io/@nayeon_p00/%EB%94%A5%EB%9F%AC%EB%8B%9D-%EA%B8%B0%EC%B4%88%EA%B0%9C%EB%85%90-%EC%B5%9C%EC%A0%81%ED%99%94-Optimization
• https://heeya-stupidbutstudying.tistory.com/entry/ML-%ED%99%9C%EC%84%B1%ED%99%94-%ED%95%A8%EC%88%98Activation-Function

• 명시적인 프로그래밍 없이 컴퓨터가 학습하는 능력을 갖추게 하는 것

• 학습 지도 방식에 따른 머신러닝 종류

  • 지도 학습
  • 비지도 학습
  • 준지도 학습
  • 강화 학습

• 점진 적 학습 가능 여부에 따른 머신러닝 종류

  • 배치 학습
  • 온라인 학습

2. 데이터 학습 및 평가에 사용되는 용어

- 회귀

• 출력값이 연속된 구간의 숫자 값

  - 분류

• 출력값이 범주 또는 클래스
• 해당 경우에는 원-핫 인코딩으로 표현

  - 원-핫 인코딩(one-hot encoding)

• 범주 개수만큼의 차원으로 구성된 벡터에서 각 범주에 해당하는 원소 값 하나만 1로, 나머지는 0으로 구성

  - 특성 스케일링

• 특성들을 동일한 범위로 조정
• 정규화(normalization) : 최대, 최소 값을 이용하여 0~1 범위로 스케일링 조정

• 이상치 영향 많이 받음

• (x - 최소값)/(최대값 - 최소값)

• 표준화(standardization) : 평균이 0, 분산이 1이 되도록 조정

• 이상치 영향을 덜 받음

• (x-평균)/표준편차

  - 일반화 오차(Generalization Error)

  다음 3가지의 오차 합으로 표현
• 편향(bias)
• 분산(variance)
• 줄일 수 없는 오차(irreducible error)

모델 복잡도up -> 과대적합, 분산up, 편향down 모델 복잡도down -> 과소적합, 분산down, 편향up

- 하이퍼파라미터(hyperparameter)

• 모델 학습하면서 바뀌는 모델의 파라미터가 아니라 학습 전 미리 지정되어 학습 알고리즘으로부터 영향을 받지 않는 파라미터

- 혼동행렬(오차행렬)(contingency table)

• 이진 분류 모델의 성능 평가

• 정확도(accuracy)

  • 예측한 전체 건수 중에 맞춘 건수의 비율

• 정밀도(precision)

  • 양성이라고 예측한 것 중 맞은 비율

• 재현율(recall)(= 민감도sensitivity)

  • 실제 양성인 것 중 예측했을 때 맞은 비율
  • ex) 모두 암인 환자를 검진했을 때, 암 환자를 얼마나 맞췄는지

• F1 점수(F1-Score)

  • 정밀도와 재현율은 트레이드오프 관계
  • 정밀도와 재현율의 조화 평균, 높을수록 좋은 모델

참고

• https://m.blog.naver.com/snowstormaw/223131968524
• https://velog.io/@ljs7463/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-%EB%AA%A8%EB%8D%B8-%ED%8F%89%EA%B0%80%EC%A0%95%EB%B0%80%EB%8F%84%EC%9E%AC%ED%98%84%EC%9C%A8f1-score%EB%93%B1

1-1. 조회 (Top-Down)

• 기존 개념에서는 top-down 방식
• 코드 구현 방식에서도 top-down 방식

→ 조회 알고리즘

• 이중 for문으로
  • 안쪽 for문에서 현재 노드에 찾는 키가 있는지 탐색하고
  • 바깥 for문에서 찾는 키가 없다면 현재 노드를 자식노드로 바꿈

1-2. 삽입

• 기존 개념에서는 bottom-up 방식
• 코드 구현 방식에서는
  • 리프노드 찾는 조회에서 top-down 방식
  • 리프노드에서 삽입 후 노드 넘치는걸 확인해서 분할할때는 bottom-up

→ 삽입 알고리즘

• 루트 노드에서부터 삽입을 시도하고
  • 현재 노드가 리프노드라면
    • 삽입하고
    • 만약 노드가 넘치면 노드를 분할하는 작업 실행
  • 현재 노드가 리프노드가 아니라면
    • 재귀적으로 자식노드를 매개변수로 넣어서 현재 함수 실행함
    • 만약 재귀 밖으로 나온 노드가 넘치면 분할하는 작업 수행

1-3. 삭제 (Top-Down)

• 기존 개념에서는 bottom-up 방식
• 코드 구현 방식에서는 top-down 방식

→ 삭제 알고리즘

• 루트에서부터 삭제 시도 (이때 deleteValFromNode)
  • 현재 노드에서 삭제할 키가 있다면
    • 현재 노드가 리프노드일때
      • 바로 삭제
    • 리프 노드가 아닐 때 (이때 deleteInnerNode 실행됨)
      • 내부 노드에서 키를 삭제
        • 선임자나 후임자의 키 개수가 최소범위보다 많을 때
          • 삭제할 키를 선임자나 후임자로 키 내용을 변경하고
          • 삭제 키를 선임자나 후임자로 변경후 현재 노드의 자식 노드부터 변경된 삭제키를 삭제하도록 함 (deleteValFromNode(cessor,cur_node->child[cur_node_pos]))
        • 선임자와 후임자 모두 키 개수가 최소범위일 때 (이때 mergeChildNode 실행됨)
          • 현재 노드의 삭제할 키를 왼쪽 자식 노드 가장 오른쪽에 넣음
          • 오른쪽 자식 노드의 키를 왼쪽 자식 노드 키로 옮김
          • 오른쪽 자식노드의 자식들을 왼쪽 자식 노드의 자식 배열로 옮김
          • 현재 노드의 삭제할 키를 키 재배열로 삭제시킴
          • 현재 노드의 자식노드 중 오른쪽 자식 노드는 왼쪽 자식 노드와 합쳐져서 없으므로 자식 배열 재배열을 통해 해당 키의 오른쪽 자식 노드를 삭제함
          • → mergeChildNode끝나고
          • 삭제키를 자식노드에 병합했으므로 현재노드의 자식노드로부터 삭제키를 삭제하도록 함 (deleteValFromNode(deletion_for_merge, cur_node->child[cur_node_pos]);)
  • 현재 노드에서 삭제할 키가 없다면
    • 현재 노드가 리프노드일때
      • 삭제할 키가 없다는 문구 출력 후 종료
    • 리프노드가 아닐 때
      • 재귀적으로 자식노드를 매개변수로 넣어서 현재 함수(deleteValFromNode) 실행
  • (항상 위에 작업이 끝나면 이 부분 확인함) 현재 노드의 자식 노드 키 개수가 최소값보다 적을 때 (이때 balanceNode 실행됨)
    • 오른쪽 또는 왼쪽 형제에게 키를 빌릴 수 있으면 키 빌리고 현재 노드의 최소값 문제 해결
    • 형제도 키가 여유가 없는 상황이면 부모에게 빌리기 (이때 mergeNode 실행됨)
      • 항상 왼쪽 형제와 현재노드를 병합함
      • 왼쪽 형제 노드의 마지막 키 바로 오른쪽에 부모에게 빌린 키 넣음
      • 왼쪽 형제 노드에 현재 노드(부모의 오른쪽 자식 노드)의 모든 키 옮기
      • 현재 노드 삭제
      • 왼쪽 형제 노드에 현재 노드의 모든 자식 노드 옮기기
      • 부모노드에서 빌린 키 부분 자리가 비어있으므로 key 재배열로 정리함
      • 부모노드에서 자식 하나가 사라졌으므로(현재 노드가 삭제되어서) 자식 배열도 재배열

2. 알고리즘 절차 정리

2-1. 구조체

0. BTreeNode

• leaf 여부
• key 담을 배열 (한 개 더 넘치게 설정, 노드가 넘칠때를 대비해서)
• key 개수
• 자식노드 담을 배열 (한 개 더 넘치게 설정, 노드가 넘칠 때 자식노드도 하나 넘쳐서)
• 자식노드 개수

2-2. 조회 관련 함수

0. searchNode

• 매개변수: 루트노드, 찾을 키(val)
• 간단 설명: 루트노드부터 자식노드까지 차례대로 키(val) 찾음
  • 이중 반복문
  • 가장 안쪽 반복문
    • 노드의 키 개수만큼 키를 하나씩 val과 비교
    • 만약 노드의 특정키와 val이 같다면 그대로 문구 출력 후 종료
    • 만약 val이 노드의 특정 키보다 작다면 바로 break → 그러면 바로 그 특정 키 인덱스와 동일한 자식노드(해당 키의 왼쪽 자식 노드)로 조회해야하기 때문
    • for문이 다 지나도록 if문에 하나도 안걸리면 인덱스는 자동으로 cnt_key와 동일해지므로 가장 오른쪽 자식노드를 조회하게 됨
  • 가장 바깥쪽 반복문
    • 인덱스 변수 지정(pos)
    • 안쪽 반복문에서 pos 값을 정하고 나옴 → pos값은 몇번째 자식 노드를 탐색할지 정함
    • 만약 현재 노드가 리프노드이면 반복문 종료 후 바깥에서 키를 찾지 못했다고 출력
    • 리프노드가 아니면 노드(level)를 자식노드(pos위치 자식노드)로 지정해서 자식노드를 안쪽 반복문에서 탐색하도록 함

2-3. 삽입 관련 함수

0. insert

• 매개변수: 넣을 키(val)
• 간단 설명: 키를 insertNode함수를 이용해서 넣음
  • 루트가 없으면 루트를 생성하고 val를 넣음
  • 루트가 있으면 insertNode에 매개변수 root와 val를 넣고 실행시킴
    • 루트의 첫번째 키부터 탐색해서 val를 넣도록 매개변수 지정

0. insertNode

• 매개변수: 부모노드에서 탐색할 키 위치, 삽입할 키(val), 현재 노드, 부모노드
• 간단 설명: 리프노드이면 키를 삽입하고 아니면 재귀적으로 자식노드로 들어감
  • 현재노드 키 위치(pos) 변수 지정
  • 현재 노드에서 키 탐색
    • 동일한 키가 있으면 중복이므로 오류 문자 출력 후 현재 노드 반환하여 종료 → (재귀함수로 나중에 루트가 사라질 수도 있어서 루트 노드를 항상 반환하도록함, 이때 루트가 아니어도 이미 재귀를 통해 내부 노드로 들어갔을것이고 내부 노드에서 나오면서 노드가 계속 바뀌면서 최종적으로 루트 노드가 됨)
    • 현재노드 키가 val보다 크면 반복문 종료 → pos는 딱 val보다 큰 키의 인덱스가 됨 → 이 뜻은 그 키의 왼쪽 자식 노드(더 작은 키가 저장되어 있는 자식노드) 위치와 동일함
    • 아무 조건문에 걸리지 않고 반복문이 끝나면 pos는 자연스럽게 해당 노드의 가장 오른쪽 자식노드(가장 큰 키가 저장되어 있는 자식노드)의 위치가 됨
  • 리프노드가 아니면
    • 현재노드의 자식노드(pos위치)를 현재노드로, 현재노드를 부모노드로 지정한 현재 함수 insertNode를 다시 실행 후 반환값을 node로 저장 → 더 아래의 자식 노드로 들어가면서 리프 노드까지 도달하도록함
    • 위의 재귀 함수가 끝난 후 반환된 현재 노드의 키 개수가 초과하면 분리함수 splitNode 실행하고 반환값을 node로 저장
  • 리프 노드일 때
    • 삽입할 키가 들어갈 자리를 만들기 위해 pos 기준 오른쪽 키들을 한칸씩 오른쪽으로 옮김
    • 자식들도 부모 키 위치를 따라가도록 pos 기준으로 오른쪽 자식 위치를 한칸씩 오른쪽으로 옮김
    • 현재 노드 pos 위치에 삽입할 값(val)를 넣음
    • 현재 노드 키 개수 증가시킴
    • 만약 현재 노드의 키 개수가 넘치면 분리함수 splitNode를 실행하고 반환값을 node로 저장
  • node 반환 → 최종적으로 이 노드가 루트가 됨
    • 이걸 반환하는 이유는 재귀 함수에서 나올때 현재 노드가 무엇인지 알 수 있도록 하는 이유가 있고
    • 또, 삽입 과정에서 splitNode를 하면서 새로운 루트노드가 생길 수 있기 때문에 함

0. splitNode

• 매개변수: 현재노드가 부모노드의 몇번째 자식인지(pos), 현재노드, 부모노드
• 간단 설명: 현재 노드가 넘칠때 가운데 키를 부모 노드로 승진
  • 현재 노드 중앙키 구하고 오른쪽 노드를 새로 만듬 → 현재 노드가 왼쪽 노드가 됨
  • 오른쪽 노드에 현재 노드 절반 기준 오른쪽 키를 옮겨줌
    • 이 과정에서 현재노드에 중앙키가 항상 있음
  • 현재 노드가 리프가 아니라면 자식 노드도 오른쪽 노드에 옮겨줌
  • 만약 현재 노드가 루트라면
    • 부모노드가 없으므로 새로운 부모 노드 생성
    • 부모 노드에 중앙키(현재 노드의 가장 오른쪽 키) 승진
    • 부모 노드 자식에 현재노드와 오른쪽 노드 포인터 저장
  • 현재 노드가 루트가 아니라면
    • 원래 있던 부모 노드에 pos 부분 자리 비우기 위해 pos 기준 오른쪽 키를 한칸씩 오른쪽으로 옮기기
    • 자식 배열도 똑같이 오른쪽으로 한칸씩 옮기기
    • 부모 노드 pos자리에 중앙키 넣고 오른쪽 노드를 자식노드로 추가

2-4. 삭제 관련 함수

0. delete

0. deleteValFromNode

0. deleteInnerNode

0. overrideWithSuccessor

0. findSuccessor

0. overrideWithPredecessor

0. findPredecessor

0. mergeChildNode

0. balanceNode

0. borrowFromRight

0. borrowFromLeft

0. mergeNode

3. 구현 코드

• 해당 코드에 주석 추가함 https://github.com/vinyl-bin/btree_implementation

** 출처

**관련 자료

• B-Tree 시뮬레이션 사이트 https://www.cs.usfca.edu/~galles/visualization/BTree.html
• B-Tree top-down 방식 https://velog.io/@mongle/Data-structure-B-tree-B-tree
• python B-Tree 코드 https://blog.naver.com/nabilera1/223457915464

**핵심 자료

• 코드출처 https://github.com/seanlion/btree_implementation/blob/main/btree_imple.c
• 코드출처 블로그 https://velog.io/@seanlion/btreeimplementation

1-1. 자료구조란

• 자료구조: 자료들을 정리하고 조직화하는 구조

자료구조 |--- 단순 자료구조
       |                           |--- 직접 접근  
       |--- 복합 자료구조 --자료접근방법--|
                      |            |--- 순서 접근
                      |
                      |--데이터 나열 방식-----|---- 선형 구조
                                          |
                                          |---- 비선형 구조

• 단순 자료구조 : 정수, 실수, 문자와 같이 프로그래밍 언어에서 기본적으로 제공하는 데이터 타입
• 복합 자료구조 : 단순 자료구조를 기반으로 만들어낸 배열, 스택, 트리와 같은 자료 구조
• 직접 접근 : 한 번만에 접근
• 순서 접근(순차 접근) : 시작 노드부터 순차적으로 접근
• 선형 구조 : 데이터가 순차적으로 나열 {배열, 연결 리스트, 스택, 큐, 덱}
• 비선형 구조 : 하나의 데이터 뒤에 여러 개의 데이터가 올 수 있는 구조 {트리, 그래프}
• 알고리즘 : 문제를 해결하는 절차

1-2. 트리

• 계층적 자료 표현하는 자료 구조

(1) 트리 용어

        A         <- 루트 노드
       / \
      B   C       <- 내부 노드 (자식 있음)
     / \   \
    D   E   F     <- 리프 노드 (자식 없음)

• 노드
• 루트 노드
• 내부 노드 : 자식 노드가 있는 노드 (루트 노드도 포함)
• 서브 트리
• 엣지
• 부모노드
• 자식 노드
• 형제
• 조상 노드
• 자손 노드
• 단말노드(리프노드 leaf node) : 자식 없는 노드
• 비단말 노드
• 차수 : 어떤 노드가 가지고 있는 자식의 수 → 트리의 차수 : 노드 차수 중 가장 큰 값
• 레벨(0부터 시작) → 트리의 높이: 트리 최대 레벨
  • 논문이나 자료마다 0부터 시작하는지 1부터 시작하는지 다름
• 포레스트 : 트리들 집합

1-3. 이진 탐색 트리(BST)

• 부모 노드를 기준으로 왼쪽노드는 항상 작고 오른쪽 노드 항상 큼
• 자녀노드는 최대 두개까지

2. B-Tree 개념 및 특징

2-1. 개념

• 이진 탐색 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리
  • 데이터베이스와 파일 시스템에 널리 사용되는 트리 자료구조의 일종
• 이진 트리와 다르게 하나의 노드에 많은 수의 정보(데이터 ⇒ key)를 가질 수 있음 → 노드에 정렬된 키 값과 포인터 가짐, 각 노드는 특정 범위의 값을 관리, key는 정렬된 상태로 저장됨
  • 데이터와 key가 혼재되어 사용되지만, 사실 B-Tree는 데이터의 특정 키를 인덱스로 지정하고 해당 인덱스를 계층적인 구조로 정렬한 것이기 때문에 데이터보다는 key라는 표현이 더 정확함
• 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 함
• Binary Search Tree를 일반화한 tree라고 할 수 있음 → 자녀노드의 최대 개수를 정할 수 있어서

2-2. 특징

1. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.
2. 내부 노드는 ceil(M/2) ~ M개의 자식노드를 가질 수 있다. → ceil 올림 함수

3. 특정 노드의 데이터(key)가 k개라면 자식 노드의 개수는 k+1개여야 한다.
   • 노드가 최소 하나의 KEY는 가지기 때문에 몇 차 인지에 상관없이 internal 노드는 최소 두개의 자녀는 가진다.

4. 특정 노드의 왼쪽 서브 트리는 특정 노드의 key보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.
   • 10의 왼쪽 서브 트리는 10보다 작은 값이 위치하고, (10,21) 사이의 서브 트리는 10보다 크지만 21보다 작은 값들이 위치하고, 21 오른쪽 서브 트리는 21보다 큰 값이 위치한다.

5. 노드 내의 데이터(key)는 ceil(M/2)-1개부터 최대 M-1개까지 포함될 수 있다.
   • 3차 B트리는 1~2개의 노드 내 데이터를 가짐
6. 모든 리프 노드들은 같은 레벨에 존재한다.

• balanced tree(모든 서브 트리의 높이 차이가 최대 하나인 이진트리) → 검색 평균,최악 모두 O(log N)을 가지게 됨

→ 불만족 예시

3. B-Tree 조회 삽입 삭제

3-1. 조회(검색)

• k 값을 조회한다면
• 루트노드에서 하위 노드로 조회를 한다
• k가 해당 노드보다 작으면 포인터를 따라 왼쪽 자식 노드로 이동
• k가 해당 노드보다 크면 포인터를 따라 오른쪽 자식 노드로 이동

3-2. 삽입

• 데이터 추가는 항상 리프노드에 한다. → 이때 조회를 통해 적절한 리프 노드에 추가한다.
• 노드가 넘치면 가운데 key를 기준으로 좌우 key들을 분할하고 가운데 key는 승진한다.
  • 부모 노드에 자리가 있으면 부모 노드로 승진
  • 부모 노드에 승진 시키고 부모 노드가 넘치면 가운데 key 기준으로 좌우 분할 후 가운데 key 승진
• 노드가 넘친다 = 각 노드의 최대 key값을 넘치는 경우, M-1값을 넘는 경우

예시 → 2추가

예시 → 10추가

3-3. 삭제

(1) 리프노드에서 삭제 발생

• 데이터 삭제는 항상 리프노드에서 발생

• 삭제 후 최소 key 수보다 적어지면 재조정한다. → 최소 key 수 = ceil(M/2) -1 (루트노드 제외)

  • 재조정

    (1) key 수가 여유있는 형제의 지원 받는다.

    • 먼저 동생(왼쪽 형제)부터 지원받는거 시도

    • 형제에게 지원 받은 키를 부모 키 자리로 올리고 부모의 키를 현재 노드의 부족한 곳에 채운다

      

    ![](https://velog.velcdn.com/images/vinyl-bin/post/e0f37676-6d1c-4876-b708-099857f79360/image.png)


    ![](https://velog.velcdn.com/images/vinyl-bin/post/150a7463-9bbe-4779-be7c-e26d90fd8fdf/image.png)


    (2) (1)번이 불가능하면 부모의 지원을 받고 형제와 합친다.(합칠때 왼쪽으로 합치기) → 부모에게 지원받는 키는 형제노드와 삭제가 진행되는 노드의 포인터 중간에 있는 키임

    - 먼저 동생(왼쪽 형제)부터 합치는거 시도
    - 부모에게 지원받은 키를 왼쪽 동생에게 합치고 삭제가 진행된 현재 노드의 남은 내용도 왼쪽 동생에게 합친다.

    ![](https://velog.velcdn.com/images/vinyl-bin/post/953a9cdf-55b3-47e7-8161-c79c32769170/image.png)


    ![](https://velog.velcdn.com/images/vinyl-bin/post/4f27cca6-abcc-4a54-916f-adf3c75731db/image.png)


    ![](https://velog.velcdn.com/images/vinyl-bin/post/3a9429d5-0c07-49fd-a868-2b15e416a858/image.png)


    (3) (2)번 후 부모에 문제가 생기면 거기서 다시 재조정한다. 

    - 위 (1)(2)번 재조정을 부모 노드에서 다시 시작한다.
    - 재조정 과정에서 root 노드가 비어있으면 삭제하고 직전에 합쳐진 노드가 root가 된다. → root 노드는 최소 key 수를 만족하지 않아도 괜찮음

    ![](https://velog.velcdn.com/images/vinyl-bin/post/351cc3b5-d349-403b-8de0-b3af9fb57c0c/image.png)


    ![](https://velog.velcdn.com/images/vinyl-bin/post/3ddc689a-bdca-425b-9b1c-e0c7750806ce/image.png)


    ![](https://velog.velcdn.com/images/vinyl-bin/post/61e1c614-d03e-4e85-8cd1-2030bbb77686/image.png)

(2) 내부(internal) 노드에서 삭제 발생

• 리프 노드와 삭제되는 내부 노드 위치 교체
• 삭제할 데이터의 선임자나 후임자와 위치 교체
  • 선임자 : predecessor 나보다 작은 데이터 중 가장 큰 값
  • 후임자 : successor 나보다 큰 데이터 중 가장 작은 값
• 즉, 데이터 삭제는 항상 리프노드에서 발생

하지만 코드에서 구현할 때는 조금 다름

• 삭제할 키가 있는 노드가 리프노드일 때

  • 현재 노드에서 바로 삭제

• 삭제할 키가 있는 노드가 리프노드가 아닐 때

  • 선임자가 여유 키를 가진 경우 (> min_keys) → Predecessor로 교체 후, 왼쪽 서브트리에서 predecessor 재귀 삭제 → 최종적으로 리프 노드에서 삭제됨

  • 후임자가 여유 키를 가진 경우 (> min_keys) → Successor로 교체 후, 오른쪽 서브트리에서 successor 재귀 삭제 → 최종적으로 리프 노드에서 삭제됨

  • 선임자, 후임자 모두 최소 키만 가진 경우 (= min_keys) → 양쪽 자식과 삭제할 키를 병합(Merge) → 병합된 노드에서 삭제 (리프가 아닐 수도 있음)

    • 예시

                         [10, 20, 30]  ← 20 삭제
               /    |    |   \
              [5] [15] [25] [35]
                 ↑    ↑
            양쪽 모두 키 1개 (= min_keys)
      
        Step 1: 병합
        - [15] + 20 + [25] = [15, 20, 25]
      
                [10, 30]
               /    |    \
            [5] [15,20,25] [35]
                 ↑
            병합된 노드 (리프일 수도, 아닐 수도)
      
        Step 2: 병합된 노드에서 20 삭제
                [10, 30]
               /    |    \
            [5] [15,25] [35]

• (항상 확인) 삭제 진행 후 현재 노드의 키가 최소보다 작을 때

  • 형제에게 키 빌릴 수 있으면 빌리기
  • 형제에게 못빌릴때 부모에게 빌리고 부모키 왼쪽 오른쪽 자식(현재 노드와 형제노드)끼리 병합

4. B-Tree 시간복잡도

• 시간복잡도 계산
  • N: 전체 key(데이터)의 개수, m : B-Tree의 차수(최대 자식 개수), h : B-Tree 높이
  • m^h ≥ N
  • h ≤ logₘ N ⇒ h ≈ logₘ N
  • 이때 탐색 시간은 트리 높이에 비례함. 즉, 시간복잡도는 logₘ N에 비례
  • logₘ N에서 m은 상수로 1로 취급 logₘ N ⇒ log N
  • 시간 복잡도 = log N
• 시간복잡도 평균 최악이 같은 이유
  • B-Tree는 항상 균형을 유지하므로 모든 리프 노드가 같은 깊이
  • 같은 깊이 = 같은 시간복잡도

5. 데이터베이스에서 사용되는 방식

(1) 기본 데이터베이스 개념

• database는 보조저장장치에 위치함

• 데이터를 읽고 쓸 때 원하는 부분만 가져오는 것이 아니라 block 단위로 가져다 씀

• 보조기억장치에 최대한 적게 접근하고 연관된 데이터가 가까이 모아서 저장되면 더 효율적임

(2) DB에 B Tree 계열을 사용하는 이유

• 자녀 노드의 개수, 노드의 데이터 수를 많이 가질 수 있으므로 storage 접근 횟수가 줄어들고 Block 단위의 저장 공간을 알차게 사용할 수 있음 → 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있음
• DBMS에서는 ‘하나의 B-Tree 노드 = 하나의 디스크 블록’으로 설계되므로 같은 노드의 key들은 항상 같은 블록에 존재

(3) B-Tree best case

(4) B-Tree worst case

• 파라미터
  • 최소 루트 노드 key 개수 : 1
  • 최소 루트 자식 노드 개수 : 2
  • 최소 노드 key 개수 : 50
  • 최소 자식 노드 개수 : 51

6. 나오게 된 배경, 다른 B+Tree, B*Tree와의 차이점

• 창시자
  • 루돌프 바이어(독일)가 새롭게 만듬
• 배경
  • 디스크를 위한 트리를 위해 만들어진 것으로 디스크의 느린 I/O와 블록 단위의 데이터 읽기를 고려하고 만들어짐
• 차이점
  • B-Tree는 데이터가 내부 노드에도 존재 가능 → 디스크 I/O 많이 발생
  • B-Tree는 리프노드 연결X → 범위 검색 시 모든 노드 순회 필요

*그 외

*-1. 문자열은 단순 자료구조인지 복합 자료구조인지

• 내부적 구현 관점에서 보면 문자가 연속된 메모리 공간에 저장되어 복합적 구조이지만 일반 프로그래밍 언어에서 기본적으로 제공하는 데이터 타입이므로 논리적으로는 단순 자료구조임

*-2. 배열과 리스트 차이

배열, 동적배열, 리스트, 연결리스트

• 배열
  • 선언 시 크기 고정, 연속된 메모리 공간
  • 직접 접근 O(1) but, 중간 삽입삭제 느림 O(n)
• 동적 배열
  • 크기 조절 가능한 배열 → 공간이 부족하면 더 큰 메모리를 새로 할당하고 기존 데이터 복사 (여전히 연속된 메모리 공간)
  • 직접 접근 but, 중간 삽입삭제 느림
• 연결 리스트
  • 각 노드가 데이터+포인터(다음 노드 주소) 저장, 비연속 메모리 공간
  • 순차 접근 O(n) but, 중간 삽입삭제 빠름 O(1)
• 리스트 → 동적 배열 또는 연결 리스트

*-3. 힙 트리와 일반 트리 차이

(1) 완전 이진 트리

• 높이가 k인 트리에서 레벨 1부터 k-1까지 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

(2) 힙

• 완전 이진 트리 형태를 가지며, 부모 자식 간의 값 크기 관계를 만족하는 트리
• 최대 힙 : 부모 노드 ≥ 자식 노드
• 최소 힙 : 부모노드 ≤ 자식 노드
• 왼쪽 노드가 오른쪽 노드보다 크거나 작아야 한다는 규칙 없음.
  • 단, 삭제 연산 시 루트 노드 삭제 후 제일 말단 노드를 루트로 올려서 자식 노드 중 더 크거나 작은 노드와 교환해야함.

*-4. 알고리즘의 자세한 정의

• 문제를 해결하기 위한 명확하고 순서있는 절차
  • 입력, 출력, 명확성, 유한성, 효율성

*-5. 멀티 레벨 인덱스

(1) 인덱스

• ‘검색키의 값’과 ‘그 값이 있는 레코드 주소(포인터)’를 묶어둔 자료구조
• https://jaehee1007.tistory.com/131

• 클러스터형 인덱스 : 데이터 행 순서대로 저장되는 인덱스, 각 테이블 당 하나
  • 테이블 생성 시 기본키를 기준으로 하나의 클러스터형 인덱스 가짐
• 보조형 인덱스 : 기준이 되는 컬럼을 기준으로 별도의 순서로 저장되는 인덱스, 각 테이블 당 여러개 가능
  • 테이블의 컬럼에 ‘유일값을 가지게 하는 UNIQUE’로 설정하면 그 컬럼 기준으로 하나의 보조형 인덱스 가짐

(2) 멀티 레벨 인덱스

• 인덱스를 위한 인덱스를 두는 계층적 구조

• 단일 인덱스와 비교해서 멀티 레벨 인덱스를 사용하면 인덱스 저장 파일 크기는 동일하지만 검색 속도가 빨라짐 (단일 O(n), 멀티레벨 O(log n))

*-6. 해시 테이블

• https://mangkyu.tistory.com/102

*-7. 파일 시스템

• 파일시스템 개념 : https://velog.io/@yuseogi0218/File-System-파일-시스템
• 파일시스템 종류 : https://wikidocs.net/232344

B-Tree를 사용하는 파일 시스템은 Btrfs(B-Tree File System)

(1) Btrfs

• https://m.blog.naver.com/cchkill/222935539514

**용어

0. 검색키

인덱스가 기준으로 삼는 필드

0. 필드, 레코드

필드 = 컬럼 = 열

레코드 = 행

0. 실린더(Cylinder)

• 물리적인 하드디스크 저장 구조 단위
• 하드디스크에는 원판이 여러개 있고 각 원판에는 트랙이 있음
• 같은 위치의 트랙들을 위아래로 합친 것을 실린더라함
• 즉, 디스크에서 데이터를 연속적으로 읽을 수 있는 최소 단위

참고 자료

• https://code-lab1.tistory.com/217
• B-tree 개념, 데이터 삽입 영상 https://www.youtube.com/watch?v=bqkcoSm_rCs
• B-tree 삭제 방식 영상 https://www.youtube.com/watch?v=H_u28u0usjA
• B-tree 시간복잡도, secondary storage, DB index 영상 https://www.youtube.com/watch?v=liPSnc6Wzfk