ݺߣ

ݺߣShare a Scribd company logo

[4차]구글 알고리즘 분석(151106)

•
•
고려대학교 정보기술경영학회 : ITS
고려대학교 정보기술경영학회 : ITS

ITS 4차 메인 세미나_알고리즘(권성현, 김민희, 이상윤, 송서하, 정현정 | 최진호) 구글 알고리즘 분석(15.11.06) 고려대학교 정보기술경영학회 : ITS Web: http://itsociety.co.kr/ Mail: president@itsociety.co.kr

1 of 26
Downloaded 44 times
알고리즘 권성현, 김민희, 이상윤, 송서하, 정현정 디렉터 : 최진호
1. 구글과 알고리즘
알고리즘이란?1-1 알고리즘 : 업무의 프로세스에 따라 정의된 명령어들을 적절한 순서로 나열 후 이것을 정확하게 수행하면 같은 목표가 달성되도록 하는 방법. 입력 알고리즘 실행 결과물 출처 : http://backjooboo0410.tistory.com/52 3/26
구글의 핵심 알고리즘.1-2 구글의 핵심 역량 중 하나는 정교한 검색 알고리즘. 검색은 어떤 알고리즘으로 구성되었는가? 4/26
2. 검색엔진은 어떤 알고리즘으로 구성되는가
Find documents relevant to an information need from a large document set Document collection Info. need Query Answer list IR systemRetrieval 검색엔진이란?2-1 6/26
→Find documents relevant to an information need from a large document set Document collection Info. need Query Answer list IR systemRetrieval How? 검색엔진이란?2-1 7/26
Document collection Info. need Query Answer list IR systemRetrieval Indexing Process Query Process 검색엔진의 구조2-2 8/26
검색엔진의 구조 – 1) Indexing Process2-2 9/26
검색엔진의 구조 – 1) Indexing Process2-2 Text Acquisition Text Transformation Index Creation 10/26
Indexing Process – Text Acquisitoin2-3 Text Acquisition Text Transformation Index Creation Text Acquisition: Identifies and Stores document for Indexing 11/26
Indexing Process – Text Transformation2-3 Text Acquisition Text Transformation Index Creation Text Transformation : Transformsdocuments into Index terms - Area of Natural Language Processing(자연어 처리) Parser, Stopping, Stemming Link Analysis, Classifier 신문기사(원문) “새해 첫 증권시장 단일 장으로 열려” 새해 첫 증권시장이 3일 오전 11시부터 오후 1 시까지 2시간 동안 당일장으로 열렸다. <DOCID> HKIB94-15 <TI> 새해 새해/NNG 첫 첫/MM 증권시장 증권/NNG + 시장/NNG 단일장으로 단일/NNG + 장/NNG + 으로/JKB 열려 열리/VV + 어/EC <TEXT> 새해 새해/NNG 첫 첫/MM 증권시장이 증권/NNG + 시장/NNG + 이/JKS 3일 3/SN + 일/NNB 오전 오전/NNG 11시부터 11/SN + 시/NNB + 부터/JX 오후 오후/NNG 1시까지 1/SN + 시/NNB + 까지/JX 12/26
Index Creation Indexing Process –Index Creation2-3 Text Acquisition Text Transformation Index Creation : Take index terms and create data structures To support fast searching Doc. 1 한국 …… …. 대학 ….. 교육 …. 한국 Doc. 2 한국 …… 대학 ….. …. 교육 …. Doc. 3 역사 …… ….. 한국 ….. 고대 …. 고대 – Doc. 3 한국 - Doc. 1, Doc. 2, Doc. 3 교육 – Doc. 1, Doc. 2 대학 - Doc. 1, Doc. 2 새해 새해/NNG 첫 첫/MM 증권시장 증권/NNG + 시장/NNG 단일장으로 단일/NNG + 장/NNG + 으로 /JKB 열려 열리/VV + 어/EC Inverted Index Doc. 1 – 한국, 대학, 교육 Doc. 2 – 한국, 대학, 교육 Doc. 3 – 역사, 한국, 고대 Index 13/26
검색엔진의 구조 – 2) Query Process2-4 14/26
User Interaction Supports creation and Refinement of query & Display results Query Process – User Interaction2-4 Evaluation User Interaction Ranking 대표적인 알고리즘 : N-Gram 전체 문자열을 N개의 문자열로 나눈 후, 이 조각난 문자열들을 키워드로 검색수행, 검색 DB를 바탕으로 그 키워드 들 중 가장 높은 출현빈도를 가지는 결과물을 출력 한다. 오늘은기분이좋다 => A[오늘, 늘은, 은기, 기분, 분이, 이좋, 좋다] => P(오 늘은기 분이 좋다) < P(오늘은 기분이 좋다) 15/26
User Interaction Supports creation and Refinement of query & Display results Query Process – User Interaction2-4 Evaluation User Interaction Ranking 오늘은기분이좋다 => A[오늘, 늘은, 은기, 기분, 분이, 이좋, 좋다] => P(오 늘은기 분이 좋다) < P(오늘은 기분이 좋다) 대표적인 알고리즘 : N-Gram 전체 문자열을 N개의 문자열로 나눈 후, 이 조각난 문자열들을 키워드로 검색수행, 검색 DB를 바탕으로 그 키워드 들 중 가장 높은 출현빈도를 가지는 결과물을 출력 16/26
Query Process –Ranking2-2 Index Creation Text Transformation Text Acquisition Evaluation User Interaction Ranking 17/26
이 문서가 쿼리가 원하는(Relevant) 문서일 확률을 점수화(Scoring)하는 과정. Language Model (Algorithm) Query Likelihood Retrieval Model : ‘문서’와 ‘질문 문장’과의 언어적 유사도를 기준으로 확률을 계산, 랭킹을 매기는 모델. || )|( )|()|( , 1 D f DqP DqPDQP Dq i n i i i    𝒒𝒊 - 쿼리(query) 단어를 대표하고, 쿼리에 n개의 단어가 존재한다고 가정 𝒇 𝒒 𝒊,𝑫 - 문서 D에 존재하는 단어(명사) 중 쿼리 단어 𝑞𝑖 의 출현 빈도 𝑫 - 문서 D 내에 모든 단어(명사)의 수 Ex) Dirichlet Smoothing model Query Process –Ranking2-4 Evaluation User Interaction Ranking 18/26
B의 페이지랭크 =B를 링크하는 사이트들의 페이지 랭크의 총합 1. 각 페이지가 서로에게 가지는 링크들의 수를 계산 2. 위의 계산결과를 바탕으로 다시 한 번 페이지 랭크를 계산한다. Evaluation User Interaction Ranking Query Process –Ranking2-4 19/26
• PR(A) = (1-d)/n + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) 사이트 A의 페이지랭크 A를 링크하는 페이지 T1의 페이지랭크 페이지 T1의 총 링크 수 • 웹페이지의 T1부터 Tn까지의 페이지랭크/총링크수의 합 Query Process –Ranking2-4 Evaluation User Interaction Ranking 방문한 페이지에서 멈추고 다른 페이지로 넘어가지 않을 확률 20/26
• PR(A) = (1-d)/N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) Query Process –Ranking2-4 Evaluation User Interaction Ranking 영향력 있는 페이지가 인용할수록 페이지랭크는 올라간다 사람들이 올바르게 인용하지 않을 경우 페이지랭크는 작동하지 않는다. 21/26
Evaluation Monitors andmeasuresEffectivenessandefficiency 검색엔진의 구조 – 2) Query Process2-4 Evaluation User Interaction Ranking 클릭한 횟수 거주 시간 무슨 질문을 했는지? 어떤 사이트를 클릭했는지? 로그 데이터를 기반으로 검색결과를 최적화, 이 결과를 Ranking에 반영한다 22/26
3. 경쟁업체와의 비교
경쟁업체 - 야후3-1 글의 맥락을 파악하여 인간이 카테고리를 분류, 정렬. 전통적인 도서(미디어)분류 방법에 하이퍼텍스트 적용 24/26
경쟁업체 - 야후3-1 “야후는 기술기업이 아닌 미디어 기업이다.” 그러나 서브 카테고리가 2만개를 넘어서며 정렬에 한계 25/26
야후 VS 구글3-2 YAHOO Google 정보의 정렬 기계는 판단하지 못하는 맥락을 인간이 읽고, 이를 분류해야 한다. 모든 내용을 DB화, 그것에 순위를 매기는 방법 고안. 검색기능 초기에는 지원하지 않음. 서비스 개선을 위해 외부기술 도입 처음부터 검색이 핵심 사업구조 초기화면에 배너광고를 제공 검색결과에 광고를 제공. 핵심역량 주제에 따라 분류된 카테고리 효율적인 검색 알고리즘. ■야후 ■구글 구글 vs 야후의 순이익 비교 1996년 Q1부터 2011년 Q2까지 http://www.theguardian.com/uk/technology/blog/2011/jul/18/all 26/26

More Related Content

[4차]구글 알고리즘 분석(151106)

  • 1. 알고리즘 권성현, 김민희, 이상윤, 송서하, 정현정 디렉터 : 최진호
  • 3. 알고리즘이란?1-1 알고리즘 : 업무의 프로세스에 따라 정의된 명령어들을 적절한 순서로 나열 후 이것을 정확하게 수행하면 같은 목표가 달성되도록 하는 방법. 입력 알고리즘 실행 결과물 출처 : http://backjooboo0410.tistory.com/52 3/26
  • 4. 구글의 핵심 알고리즘.1-2 구글의 핵심 역량 중 하나는 정교한 검색 알고리즘. 검색은 어떤 알고리즘으로 구성되었는가? 4/26
  • 5. 2. 검색엔진은 어떤 알고리즘으로 구성되는가
  • 6. Find documents relevant to an information need from a large document set Document collection Info. need Query Answer list IR systemRetrieval 검색엔진이란?2-1 6/26
  • 7. →Find documents relevant to an information need from a large document set Document collection Info. need Query Answer list IR systemRetrieval How? 검색엔진이란?2-1 7/26
  • 9. 검색엔진의 구조 – 1) Indexing Process2-2 9/26
  • 10. 검색엔진의 구조 – 1) Indexing Process2-2 Text Acquisition Text Transformation Index Creation 10/26
  • 11. Indexing Process – Text Acquisitoin2-3 Text Acquisition Text Transformation Index Creation Text Acquisition: Identifies and Stores document for Indexing 11/26
  • 12. Indexing Process – Text Transformation2-3 Text Acquisition Text Transformation Index Creation Text Transformation : Transformsdocuments into Index terms - Area of Natural Language Processing(자연어 처리) Parser, Stopping, Stemming Link Analysis, Classifier 신문기사(원문) “새해 첫 증권시장 단일 장으로 열려” 새해 첫 증권시장이 3일 오전 11시부터 오후 1 시까지 2시간 동안 당일장으로 열렸다. <DOCID> HKIB94-15 <TI> 새해 새해/NNG 첫 첫/MM 증권시장 증권/NNG + 시장/NNG 단일장으로 단일/NNG + 장/NNG + 으로/JKB 열려 열리/VV + 어/EC <TEXT> 새해 새해/NNG 첫 첫/MM 증권시장이 증권/NNG + 시장/NNG + 이/JKS 3일 3/SN + 일/NNB 오전 오전/NNG 11시부터 11/SN + 시/NNB + 부터/JX 오후 오후/NNG 1시까지 1/SN + 시/NNB + 까지/JX 12/26
  • 13. Index Creation Indexing Process –Index Creation2-3 Text Acquisition Text Transformation Index Creation : Take index terms and create data structures To support fast searching Doc. 1 한국 …… …. 대학 ….. 교육 …. 한국 Doc. 2 한국 …… 대학 ….. …. 교육 …. Doc. 3 역사 …… ….. 한국 ….. 고대 …. 고대 – Doc. 3 한국 - Doc. 1, Doc. 2, Doc. 3 교육 – Doc. 1, Doc. 2 대학 - Doc. 1, Doc. 2 새해 새해/NNG 첫 첫/MM 증권시장 증권/NNG + 시장/NNG 단일장으로 단일/NNG + 장/NNG + 으로 /JKB 열려 열리/VV + 어/EC Inverted Index Doc. 1 – 한국, 대학, 교육 Doc. 2 – 한국, 대학, 교육 Doc. 3 – 역사, 한국, 고대 Index 13/26
  • 14. 검색엔진의 구조 – 2) Query Process2-4 14/26
  • 15. User Interaction Supports creation and Refinement of query & Display results Query Process – User Interaction2-4 Evaluation User Interaction Ranking 대표적인 알고리즘 : N-Gram 전체 문자열을 N개의 문자열로 나눈 후, 이 조각난 문자열들을 키워드로 검색수행, 검색 DB를 바탕으로 그 키워드 들 중 가장 높은 출현빈도를 가지는 결과물을 출력 한다. 오늘은기분이좋다 => A[오늘, 늘은, 은기, 기분, 분이, 이좋, 좋다] => P(오 늘은기 분이 좋다) < P(오늘은 기분이 좋다) 15/26
  • 16. User Interaction Supports creation and Refinement of query & Display results Query Process – User Interaction2-4 Evaluation User Interaction Ranking 오늘은기분이좋다 => A[오늘, 늘은, 은기, 기분, 분이, 이좋, 좋다] => P(오 늘은기 분이 좋다) < P(오늘은 기분이 좋다) 대표적인 알고리즘 : N-Gram 전체 문자열을 N개의 문자열로 나눈 후, 이 조각난 문자열들을 키워드로 검색수행, 검색 DB를 바탕으로 그 키워드 들 중 가장 높은 출현빈도를 가지는 결과물을 출력 16/26
  • 18. 이 문서가 쿼리가 원하는(Relevant) 문서일 확률을 점수화(Scoring)하는 과정. Language Model (Algorithm) Query Likelihood Retrieval Model : ‘문서’와 ‘질문 문장’과의 언어적 유사도를 기준으로 확률을 계산, 랭킹을 매기는 모델. || )|( )|()|( , 1 D f DqP DqPDQP Dq i n i i i    𝒒𝒊 - 쿼리(query) 단어를 대표하고, 쿼리에 n개의 단어가 존재한다고 가정 𝒇 𝒒 𝒊,𝑫 - 문서 D에 존재하는 단어(명사) 중 쿼리 단어 𝑞𝑖 의 출현 빈도 𝑫 - 문서 D 내에 모든 단어(명사)의 수 Ex) Dirichlet Smoothing model Query Process –Ranking2-4 Evaluation User Interaction Ranking 18/26
  • 19. B의 페이지랭크 =B를 링크하는 사이트들의 페이지 랭크의 총합 1. 각 페이지가 서로에게 가지는 링크들의 수를 계산 2. 위의 계산결과를 바탕으로 다시 한 번 페이지 랭크를 계산한다. Evaluation User Interaction Ranking Query Process –Ranking2-4 19/26
  • 20. • PR(A) = (1-d)/n + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) 사이트 A의 페이지랭크 A를 링크하는 페이지 T1의 페이지랭크 페이지 T1의 총 링크 수 • 웹페이지의 T1부터 Tn까지의 페이지랭크/총링크수의 합 Query Process –Ranking2-4 Evaluation User Interaction Ranking 방문한 페이지에서 멈추고 다른 페이지로 넘어가지 않을 확률 20/26
  • 21. • PR(A) = (1-d)/N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) Query Process –Ranking2-4 Evaluation User Interaction Ranking 영향력 있는 페이지가 인용할수록 페이지랭크는 올라간다 사람들이 올바르게 인용하지 않을 경우 페이지랭크는 작동하지 않는다. 21/26
  • 22. Evaluation Monitors andmeasuresEffectivenessandefficiency 검색엔진의 구조 – 2) Query Process2-4 Evaluation User Interaction Ranking 클릭한 횟수 거주 시간 무슨 질문을 했는지? 어떤 사이트를 클릭했는지? 로그 데이터를 기반으로 검색결과를 최적화, 이 결과를 Ranking에 반영한다 22/26
  • 24. 경쟁업체 - 야후3-1 글의 맥락을 파악하여 인간이 카테고리를 분류, 정렬. 전통적인 도서(미디어)분류 방법에 하이퍼텍스트 적용 24/26
  • 25. 경쟁업체 - 야후3-1 “야후는 기술기업이 아닌 미디어 기업이다.” 그러나 서브 카테고리가 2만개를 넘어서며 정렬에 한계 25/26
  • 26. 야후 VS 구글3-2 YAHOO Google 정보의 정렬 기계는 판단하지 못하는 맥락을 인간이 읽고, 이를 분류해야 한다. 모든 내용을 DB화, 그것에 순위를 매기는 방법 고안. 검색기능 초기에는 지원하지 않음. 서비스 개선을 위해 외부기술 도입 처음부터 검색이 핵심 사업구조 초기화면에 배너광고를 제공 검색결과에 광고를 제공. 핵심역량 주제에 따라 분류된 카테고리 효율적인 검색 알고리즘. ■야후 ■구글 구글 vs 야후의 순이익 비교 1996년 Q1부터 2011년 Q2까지 http://www.theguardian.com/uk/technology/blog/2011/jul/18/all 26/26