페이지 랭크(PR, PageRank) 알고리즘은 구글 검색엔진의 핵심이다. 요약하자면 하이퍼텍스트 정보를 이용하여 웹페이지 사이 연결정보로 검색 결과를 향상시키기 위한 알고리즘이다. 연결정보로부터 특정 페이지를 다른 페이지들이 얼마나 인용하는지 세는 방식이다. 예를 들어, A 페이지를 B, C 페이지에서 인용하고 있다고 가정하자. 이 때, B 페이지에서 전체 인용 링크 수 5개 중 1개가 A 페이지인 경우 PR(B) / L(B) = 1 / 5 가 된다. PR(B)의 경우 초기값은 1이고, 재귀적으로 반복 계산되어 수렴되는 PR 을 사용한다. N은 전체 문서 수, L은 인용 수, d는 Damping Factor 값(Random Surfer)이다. 여기서 Random Surfer는 사용자가 해당 페이지에 만..

21.2 PageRank 웹 그래프에 있는 모든 정점에 대해 0과 1 사이의 수치화된 점수를 할당하는 것 용어 근접성(Term proximity)과 코사인 유사도(Cosine similarity) 계산 방법 등을 이용하여 웹 페이지의 합산 점수를 계산함 텔레포트(Teleport) 웹 서퍼가 어떤 정점에서 웹 그래프 내의 다른 어떤 정점으로든지 이동할 수 있음 텔레포트 연산 서퍼는 정점 내에 인출-링크가 있을 때에 텔레포트 연산을 지시함 서퍼는 외부로 나가는 링크를 갖는 정점에서 0~1 사이의 확률로 텔레포트 연산을 수행함 21.2 Markov 연쇄 Markov 연쇄(Markov chain) 이산 확률 과정(discrete-time stochastic process)임 N 개의 상태(State)로 구성되며..

20.1 개요 수집기가 제공해야하는 자질들 견고성(Robustness) 웹 스파이더와 같은 함정으로부터 원상복귀 될 수 있도록 설계되어야 함 웹스파이더(Spider trap) 웹에서 수집기가 특정 도메인으로부터 무한한 수의 페이지를 가져오는 과정에서 정지하도록 유도하는 웹 페이지들을 생성함 공손함(Politeness) 웹 서버는 수집기가 자신들이 방문할 수 있는 빈도를 통제하는 명시적이고 묵시적인 정책을 가지고 있음 수집기가 제공하면 좋은 특징 분산성(Distributed) 크기 조정성(Scalable) 성능 및 효율성(Performance and efficiency) 우수성(Quality) 최신성(Freshness) 확장성(Extensible) 20.2 수집 URL 프론티어(URL frontier) 수..

18.4 잠재 의미 색인 잠재 의미 색인(LSI, Latent Semantic Indexing) 혹은 잠재 의미 분석(LSA, Latent Semantic Analysis) 기존의 벡터 공간 표현은 자연어에서 발생하는 동의어(Synonymy), 다의어(Polysemy)와 같은 문제를 다룰 수 없음 질의어들을 저계수 근사 표현으로 만들어 질의어-문헌의 일치 정도를 저계수 표현으로 계산할 수 있음 LSI의 특징 SVD 계산에 소요되는 비용이 너무 큼 k를 감소하면 예상대로 재현율이 증가함 적절한 k값이 있으면 LSI 접근이 동의어 문제의 대안이 될 수 있음 LSI는 질의어와 문헌들 사이에 중첩이 거의 없는 경우에 가장 잘 작동함 19.2 웹의 특징 SCC(Strongly Connected Component)..

계층 군집화(Hierarchical clustering) 군집화 결과로 계층적인 구조를 생성하며, 일반적으로 계층적인 구조는 평면적인 구조에 비해 더 유용함 미리 군집 수를 정할 필요가 없음 알고리즘 복잡도가 문헌 수의 제곱에 비례하여 효율성이 떨어짐 K-means와 EM의 복잡도는 문헌 수에 비례함 17.1 계층 병합 군집화 상향식 계층 병합 군집화(HAC, Hierarchical Agglomerative Clustering) 각 문헌이 독립된 하나의 군집이 된 후, 가장 유사한 두 군집을 하나의 군집으로 병합하면서 모든 문헌이 하나의 군집에 포함될 때까지 반복함 단조성(Monotonicity) 병합이 단조 연산임 17.2 단일 및 완전-연결 군집화 단일 연결 군집화(Single-link cluster..

비지도 학습(Unsupervised learning) 문헌을 범주로 분류하는 전문가가 없음 평면 군집화(Flat clustering) 군집화 결과가 평면적으로만 분리되어 있으며 어떤 형태의 구조를 가지지는 않음 계층 군집화(Hierarchic clustering) 군집화 결과가 계층 구조를 가짐 16.1 정보 검색의 군집화 군집 가설(Cluster hypothesis) 같은 군집에 있는 문헌들은 정보 요구에 대한 적합성이 비슷함 16.2 문제 정의 평면적 경군집화의 요소 문헌 집합 원하는 군집 수 군집의 질을 평가하는 목적 함수(Objective function) 경군집하는 한 문헌이 하나 혹은 그 이상의 군집에 완전히 속할 수 있음 분할 군집화(Partitional clustering) 각 문헌은 정확..