뉴스 키워드 네트워크 분석 프로젝트

BigKinds 뉴스 데이터를 활용한 키워드 동시출현 네트워크 분석 및 그래프 알고리즘 적용 프로젝트

프로젝트 개요

이 프로젝트는 뉴스 기사에서 추출한 키워드 간의 동시출현 관계를 네트워크 그래프로 모델링하고, BFS, Dijkstra, MST, DFS 등 다양한 그래프 알고리즘을 적용하여 키워드 간의 관계를 분석합니다.

주요 기능

1. 데이터 전처리

• BigKinds 뉴스 데이터에서 키워드 자동 추출
• KoNLPy Okt 형태소 분석기를 사용한 명사 추출
• 불용어 제거 및 키워드 필터링
• 주차별 데이터 그룹핑

2. 그래프 구축

• 키워드 동시출현 네트워크 생성 (무향 가중치 그래프)
• 인접 리스트 기반 그래프 자료구조 구현
• 전체 기간 그래프 및 주차별 그래프 생성

3. 그래프 알고리즘 분석

BFS (Breadth First Search)

• 시간복잡도: O(V + E)
• 키워드 확산 분석
• 거리별 도달 노드 분포 계산
• 상위 10% 강한 연결만 사용한 sparse 네트워크 분석

Dijkstra

• 시간복잡도: O(E log V)
• 키워드 쌍 간 최단 경로 탐색
• 동시출현 빈도의 역수를 가중치로 사용
• 우선순위 큐를 사용한 최적화

MST (Maximum Spanning Tree)

• 시간복잡도: O(E log V)
• Prim / Kruskal 알고리즘 구현 및 비교
• 핵심 연결 구조 추출
• 허브 노드 탐지

DFS (Depth First Search)

• 시간복잡도: O(V + E)
• 연결 요소 탐지
• 밀집 서브그래프 탐지
• 의미적으로 강하게 연결된 키워드 군집 발견

4. 시각화

• 전체 네트워크 시각화
• MST 핵심 연결 구조
• 최단 경로 시각화
• BFS 확산 분석 (거리 분포)
• 밀집 키워드 군집
• 주차별 네트워크 변화
• 뉴스 발행량 추이
• 키워드 간 최단 거리 heatmap
• 알고리즘 성능 비교

기술 스택

• Python 3.x
• 데이터 처리: pandas, numpy
• 자연어 처리: KoNLPy (Okt)
• 그래프 분석: 자체 구현 + NetworkX (시각화용)
• 시각화: matplotlib

설치 방법

필수 패키지 설치

pip install pandas numpy konlpy matplotlib networkx openpyxl

KoNLPy 의존성 설치

Windows:

# JDK 설치 필요
pip install JPype1

Linux/Mac:

sudo apt-get install g++ openjdk-8-jdk python3-dev
pip install konlpy

프로젝트 구조

Algorithm/
├── 1_preprocess.py          # 데이터 전처리 및 키워드 추출
├── 2_build_graph.py          # 동시출현 네트워크 그래프 구축
├── 3_analyze_graph.py        # 그래프 알고리즘 분석 (BFS, Dijkstra, MST, DFS)
├── 4_visualize.py            # 시각화
├── graph_struct.py           # 그래프 자료구조 (인접 리스트)
├── data/                     # 데이터 디렉토리
│   ├── bigkinds_news.xlsx   # 원본 뉴스 데이터 (BigKinds 다운로드)
│   ├── news_keywords.csv    # 전처리된 키워드 데이터
│   ├── keyword_freq.csv     # 키워드 빈도
│   ├── graph_total.pkl      # 전체 기간 그래프
│   ├── graphs_weekly.pkl    # 주차별 그래프
│   ├── analysis_results.pkl # 분석 결과
│   └── analysis_summary.csv # 분석 요약
└── output/                   # 시각화 결과 이미지
    ├── network_total.png
    ├── mst_network.png
    ├── dijkstra_paths.png
    ├── bfs_spread.png
    ├── dense_clusters.png
    ├── weekly_networks.png
    ├── news_trend.png
    ├── keyword_distance_heatmap.png
    └── algorithm_comparison.png

사용 방법

1단계: 데이터 전처리

python 1_preprocess.py

• BigKinds에서 다운로드한 data/bigkinds_news.xlsx 파일 필요
• 키워드 추출 및 상위 100개 키워드 선정
• 출력: data/news_keywords.csv, data/keyword_freq.csv

2단계: 그래프 구축

python 2_build_graph.py

• 키워드 동시출현 네트워크 생성
• 전체 기간 그래프 및 주차별 그래프 구축
• 출력: data/graph_total.pkl, data/graphs_weekly.pkl

3단계: 그래프 알고리즘 분석

python 3_analyze_graph.py

• BFS, Dijkstra, MST, DFS 알고리즘 적용
• 키워드 확산, 최단 경로, 핵심 구조, 군집 분석
• 출력: data/analysis_results.pkl, data/analysis_summary.csv

4단계: 시각화

python 4_visualize.py

• 다양한 시각화 이미지 생성
• 출력: output/ 디렉토리에 PNG 파일들 저장

데이터 형식

입력 데이터 (bigkinds_news.xlsx)

BigKinds에서 다운로드한 뉴스 데이터로, 다음 열이 필요합니다:

• 제목: 뉴스 기사 제목
• 본문: 뉴스 기사 본문
• 일자: 날짜 (YYYYMMDD 형식)

출력 데이터

• news_keywords.csv: 전처리된 키워드 데이터
• keyword_freq.csv: 키워드 빈도
• analysis_summary.csv: 알고리즘 분석 요약

알고리즘 성능

• BFS: O(V + E) - 빠른 확산 분석
• DFS: O(V + E) - 빠른 연결 요소 탐지
• Dijkstra: O(E log V) - 효율적인 최단 경로
• MST: O(E log V) - Prim/Kruskal 최적화

주요 분석 결과

BFS 확산 분석

• 주요 키워드로부터의 확산 거리 측정
• 거리별 노드 분포 시각화
• 필터링된 sparse 네트워크에서 의미있는 연결 분석

Dijkstra 최단 경로

• 키워드 쌍 간 최단 연결 경로 탐색
• 동시출현 빈도가 높을수록 짧은 거리

MST 핵심 구조

• Prim/Kruskal 알고리즘 비교
• 허브 키워드 탐지
• 핵심 연결 구조 추출

DFS 군집 분석

• 밀집 키워드 군집 탐지
• 의미적으로 연관된 키워드 그룹 발견

활용 사례

• 뉴스 키워드 트렌드 분석
• 이슈 확산 경로 분석
• 연관 키워드 추천
• 토픽 클러스터링
• 시계열 키워드 네트워크 변화 분석

주의사항

• 한글 폰트 설정: Windows는 'Malgun Gothic', Mac은 'AppleGothic' 사용
• 데이터 파일 경로는 환경에 맞게 수정 필요
• 메모리 사용량: 큰 데이터셋의 경우 충분한 메모리 필요

개발자

김가은