web search engine UIC
1.0.0
CS 582 시카고 일리노이 대학교의 정보 검색 과정에 대한 최종 프로젝트
터미널에서 프로그램을 실행하려면 명령을 사용하십시오.
Python main.py
검색 엔진의 기능과 UI를 더 잘 설명하기위한 보고서가 제공됩니다. 참조하십시오.
보고서 .pdf
이 문서는 시카고 일리노이 대학교의 CS 582 정보 검색의 최종 프로젝트에 대한 보고서입니다. 이 프로젝트는 UIC 도메인을위한 웹 검색 엔진을 처음부터 구축하는 것으로 구성되었습니다. 이 소프트웨어는 웹 크롤링에서 시작하여 모듈 식으로 구축되었으며, 페이지 전처리, 인덱싱 및 마지막으로 그래픽 사용자 인터페이스를 추가하는 페이지를 살펴 보았습니다. 또한, 우리가 발명 한 맞춤형 "스마트"구성 요소는 필수였습니다.
나는 사용자의 쿼리에서 광범위한 컨텍스트 를 얻으려고 시도하는 의사 관련 피드백 접근법을 기반으로 쿼리 확장을 사용하여 검색 엔진 최적화를 실험하기로 결정했습니다. 이것은 검색 엔진에 주로 두 가지 유형의 개선 사항을 추가해야합니다.
모든 결과를 쿼리의 단어에만 초점을 맞추지 말고 검색된 페이지 세트에 다양하고 관련 컨텐츠를 포함하십시오.
쿼리에있는 단어가 포함되어 있지 않지만 동일한 주제를 처리하기 때문에 여전히 사용자에게 관심을 가질 수있는 웹 페이지를 포함하여 총 결과 수를 확장합니다.
페이지 순위 구현도 통합되어 애플리케이션 UI에서 켜거나 끌 수 있습니다. 두 스마트 구성 요소에 대한 자세한 내용은이 문서에서 뒷부분에서 찾을 수 있습니다.
소프트웨어가 포함 된 저장소는 github at : 다음을 통해 액세스 할 수 있습니다.
https://github.com/mirkomantovani/web-search-engine-uic
이 소프트웨어는 Python3로 객체 지향 프로그래밍 방식으로 작성되어 미래를 쉽게 확장 할 수 있습니다. 광범위하고 시간이 많이 걸리는 크롤링 및 페이지 전처리를 수행하지 않고도 코드를 쉽게 다운로드하고 테스트 할 수 있도록 UIC 도메인에서 10000 페이지가 포함 된 데이터 세트 : https://www.uic.edu/ 및 필요한 파일 및 필요한 파일 (인덱스 인덱스, tf-idf 점수, 문서 길이,). 저장소에 포함되어 있습니다. 이러한 방식으로 저장소를 클로닝하여 main.py를 실행할 수 있으며 1 초 이내에 검색 엔진이 입력을 얻을 수 있습니다. 그러나 크롤링 및 전처리를 실행하는 스크립트도 다음 하위 섹션에 다른 구성 요소와 함께 포함되어 설명됩니다.
웹 크롤링은 스크립트 multithreaded_crawling.py 를 실행하여 수행 할 수 있습니다. 크롤링은 큐 모듈을 사용하여 동기화 된 방식으로 리소스에 액세스하여 동일한 스크립트에서 전역 상수 스레드 _number를 수정하여 스레드의 수를 변경할 수 있습니다.
크롤링은 UIC CS 하위 도메인 : https://www.cs.uic.edu/에서 시작됩니다.
크롤링은 넓은 첫 번째 전략으로 발생하며, 모든 페이지는 HTMLPARSER 라이브러리를 사용하여 탈취, 다운로드 및 구문 분석되며 링크가 추출되어 UIC 도메인에 속한 다음 적절한 형식 인 경우 FIFO 대기열에 추가됩니다. 모든 나쁜 형식의 블랙리스트는 내가 크롤링에 들어간 결과를 보면서 나에게 도출 되었으며이 18 개의 형식으로 구성되어 있습니다 : ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png", ".pdf", ",", ",". " ".tgz", ".zip", ".exe", ".js", ".css", ".ppt". 10 초의 시간 초과는 연결을 닫고 다음 페이지로 전달하기 전에 페이지를 다운로드하는 최대 시간으로 지정됩니다.
URL은 또한 추출 된 후에도 수정되고, 모든 초기 HTTP가 HTTP가되고, 끝에있는 모든 슬래시가 제거되고, 쿼리 문자열이 제거되고, 해시 기호 (#)로 표현 된 페이지 내 링크도 Crawler가 다른 인 잉크를 가진 더 많은 페이지가 다른 페이지가 다른 페이지라고 생각하지 않기 위해 제거됩니다. 또한, <a> 태그가 열리고 다른 태그가 열린 링크의 처리는 문자열에서 다른 태그 "<"의 개구부에서 링크를 분할하여 href를 닫기 전에 내부에 다른 태그가 열립니다.
크롤링 중에 두 개의 사전, 코드의 URL 및 URL 코드의 URL이 나중에 사용할 수 있도록 지속적으로 디스크에 저장되며, 웹 페이지의 코드는 다운로드 된 페이지의 수는 시간순으로 다운로드됩니다.
크롤링 된 페이지의 전처리는 run_preprocessing.py 스크립트에서 실행될 수 있습니다. 또한 고려해야 할 페이지 수와 해당 상수 를 변경하여 페이지 순위의 최대 반복 수를 지정할 수도 있습니다 .
전처리 중에 Preprocess.py 스크립트의 CustomTokenizer 객체가 사용됩니다. <cript> 및 <style>을 제외한 모든 태그에서 먼저 일반 텍스트를 얻음으로써 각 페이지는 전처리됩니다. 이 단계에서는 매우 빠른 라이브러리를 사용하기로 결정했습니다. Selectolax 는 C에 쓰여진 겸손한 엔진을 사용하는 Python API 인 SelectOlax를 사용하기로 결정했습니다. CPYTHON은 물론 순수한 Python으로 작성된 모든 HTML 파싱과 관련하여 계산 시간에서 적어도 하나의 크기의 크기를 제공합니다. 그런 다음 페이지가 토큰 화되고, 토큰은 NLTK 의 PorterStemmer를 사용하여 줄기를 줄이고, stopwords.txt 에서 제공된 스톱워드 목록을 사용하여 스톱워드가 제거되며, 숫자는 제거되고 3 글자보다 짧은 단어는 고려되지 않습니다.
전처리에서 역 지수가 구축되고 각 Word-DOC 쌍의 TF-IDF가 계산되고 역 지수에 저장됩니다. 지시 된 웹 그래프 ( Graph.py )도 생성되어 Page_Rank.py 에서 Page Rank의 구현으로 공급됩니다. 쿼리에 응답하는 데 나중에 필요한 모든 파일은 이진 파일로 저장됩니다.
10000 페이지에 대한 전처리 및 Page_Rank 수렴에 걸리는 총 시간은 약 236 초였으며 페이지 순위 실행 시간은 약 11 초에 불과했습니다.
main.py 스크립트에는 검색 엔진의 액세스 포인트가 포함되어 있습니다. 프로그램이 시작되면 CustomTokenizer 객체가 쿼리를 토큰 화하기 위해 작성됩니다. 대신 쿼리를 기반으로 문서를 순위하기 위해 TFIDFRANKER 객체가 인스턴스화됩니다.
문서가 사용자 쿼리를 기반으로 순위가 매겨지면 최대 100 개의 문서가 고려되면이 상수는 main.py : max_results_to_consider에서 변경 될 수 있으며 다른 사용자 정의 가능한 매개 변수는 시간에 표시 할 결과 수입니다.
사용자 인터페이스는 그래픽이며 Python 패키지 인 EasyGui를 사용하여 구현됩니다. GUI는 프로그램의 기본 기능에 대한 기본 API를 포함하는 확장 가능한 모듈 인 CustomGui.py 입니다.
프로그램이 시작되면 사용자에게 기본 설정을 요청받습니다. 그 후 메인 메뉴가 나타납니다. 메인 메뉴는 검색 엔진의 현재 설정과 수행 할 수있는 주요 작업에 대한 일부 버튼을 보여줍니다. 기본 메뉴에서 적절한 버튼을 선택하여 런타임시 설정을 동적으로 변경할 수 있습니다. 다른 두 가지 선택은 다음과 같습니다. 프로그램을 종료하고 쿼리 실행. 사용자가 버튼을 눌러 새 쿼리를 만들면 새 창이 나타나고 사용자에게 새 쿼리를 삽입하라는 메시지가 표시됩니다. 그가 클릭하면 쿼리가 전처리되고 문서가 순위가 매겨지고 첫 번째 10 개 (프로그램의 변수) 문서는 사전 처리 된 쿼리의 정보와 함께, 유사 관련 피드백이 켜져있는 경우 확장 된 토큰을 함께 표시합니다. 이제 사용자는 결과를 두 번 클릭하여 시스템의 기본 브라우저에서 새 탭에서 페이지를 열거나 목록 끝에서 "더 많은 결과 표시"를 재귀 적으로 눌러 10 개의 결과를 더 표시 할 수 있습니다. 또한 의사 관련 피드백이 꺼진 경우 사용자에게 확장과 동일한 쿼리를 다시 실행할 수 있습니다.
쿼리를 실행하고 결과를 취소하거나 열기로 결정한 후, 사용자는 메인 메뉴로 돌아와서 설정을 변경하고/또는 새 쿼리를 다른 설정으로 동일한 쿼리 또는 동일한 쿼리를 실행하여 결과를 이전에 얻은 것과 비교할 수 있습니다.
이 프로젝트를 개발하는 동안 경험 한 주요 과제는 다음과 같습니다.
처음에는 어떤 종류의 스마트 구성 요소를 디자인 해야하는지 선택하기가 정말 어려웠습니다. 나는이 유형의 응용 프로그램에 대한 경험이 없으며 테스트 할 데모가없는 개선에 대한 생각은 너무 어렵습니다.
구현 부분에서, 나는 스레드와 같이 아직 알지 못했던 Python 라이브러리 및 구성을 배우는 데 많은 시간을 보냈습니다. 스레드와 같이 HTML 페이지에서 링크를 얻기 위해 웹 스크래핑을 구현하거나 수행하는 방법. 처음부터 배워야 할 또 다른 것은 파이썬에서 GUI를 만드는 방법이었습니다.
성가신 일은 다양한 형식과 잘못된 형식을 발견했기 때문에 10000 페이지를 두 번 이상 크롤링해야한다는 사실이었습니다. 결국 블랙리스트에 대한 형식의 전체 목록은 18이고 ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png", ".pdf", ".gz".rar ",", ",", "." ".exe", ".js", ".css", ".ppt".
매우 도전적인 것은 하이퍼 파라미터 튜닝과 페이지 순위의 통합으로 문서를 순위에 올랐습니다. 매개 변수 " e "는 확장 쿼리의 토큰에 얼마나 중요한지를 결정하는 매개 변수는 데이터 (각 쿼리의 관련 문서)가 표시되지 않은 경우 검색 엔진의 평균 성능을 알 수 없기 때문에 조정하기가 가장 어렵습니다. 또한 쿼리 관련성은 주관적이며 사람이 검색하고자하는 것을 알지 못하며 쿼리를 기반으로 만 추측 할 수 있습니다. 나는 e가 최대 0.5 여야한다고 결정했고 결국 0.1-0.2 정도를 설정했습니다. 사용자가 입력하지 않은 단어에 많은 중요성을 부여함으로써 쿼리를 많이 바이어스하고 싶지 않습니다.
내가 사용한 가중 체계는 웹 검색 엔진과 관련하여 가장 효과적인 것으로 판명되었으며 각 문서에서 단어의 중요성을 올바른 방식으로 설명하기 때문에 문서에서 단어의 간단한 TF-IDF 였습니다. 나는 그것이이 프로젝트의 목적이 아니기 때문에 다른 법안을 시도하는 것에 대해 생각조차하지 않았으며 이것은 단지 잘 작동하는 것처럼 보였습니다.
문서 순위를 매기는 데 사용되는 유사성 측정은 코사인 유사성 이었습니다. 내부 제품 유사성에서 시작하여 한 줄의 코드를 변경하는 문제 일 것입니다. 코사인 유사성은 문서 길이와 쿼리 길이를 고려하기 때문에 사용하는 것이 좋습니다. 그것은 더 복잡하고 일반적으로 이러한 유형의 응용 프로그램에서 실제로 잘 작동하므로 유사성 측정을 선택하는 것은 실제로 문제가되지 않았으며, 코사인 유사성이 올바른 것이라는 것을 알았습니다.
나는 내가 생각해 낸 임의적이고 다양한 쿼리에 대해 10에서 정밀도를 평가했습니다 (처음 10 개의 결과를 검색 한 결과). 결과는 다음과 같습니다.
쿼리 : "어드바이저 논문", 첫 번째 결과는 https://grad.uic.edu/electronic-thesisdistation-faqs이며 모든 결과 는 논문 및 상관 관계와 관련이 있다고 생각합니다.
쿼리 : “커리어 박람회”, 첫 번째 결과는 https://ecc.uic.edu/career-fairs이며 모든 결과가 커리어 페어, 커리어 서비스, 이벤트 및 고용과 다소 관련이 있다고 생각합니다. 저는이 질문에 정밀도를 줄 것입니다. p = 1.0.
쿼리 : “연구 보조”, 첫 번째 결과는 http://grad.uic.edu/assistantships였으며, 마지막 것은 Asistantships와 관련이 있다고 생각합니다. UIC 도메인에는 RA에 대한 특정 페이지가 없기 때문에이 쿼리에 P = 0.9 를 제공 할 것입니다.
쿼리 : “인턴쉽과 직업”, 첫 번째 결과는 https://careerservices.uic.edu/students/internships 였지만 이번에는 6 개의 웹 페이지 만 관련이 있었지만 여전히 경력 및 고용과 관련이 없었습니다. 이 쿼리에 P = 0.6을 정밀하게 줄 것입니다.
쿼리 : “학생 센터 이스트 주소”, 첫 번째 결과는 https://fimweb.fim.uic.edu/buildingsdata.aspx입니다.이 쿼리는 더 구체적이고 복잡하며 실제로 4 가지 결과에서만 건물의 주소를 추출 할 수는 있지만 다른 모든 결과는 여전히 나쁘지 않았습니다. 이 쿼리에 P = 0.4를 정밀하게 줄 것입니다.
평균 정밀도가 0.78 이고 모든 쿼리가 적어도 하나의 관련 결과를 반환했다는 사실은 결과가 이산적이라고 생각합니다.
내가 실험 한 최초의 지능은 평범하고 단순한 페이지 순위였습니다. 페이지의 전처리 중에 링크가 추출되고 링크 연결을 기반으로 월드 그래프가 생성됩니다. Page Rank의 구현은 전체 그래프와 강하게 연결된 성분을 생성하는 것이 었으며, 이는 모든 노드에서 널 확률이 아닌 그래프의 다른 노드로 얻을 수 있음을 의미합니다. 이 해석으로 임의의 워커가 한 페이지에 갇힐 가능성은 없습니다.
페이지 순위는 문서의 점수에 맞게 통합하기가 약간 어려웠습니다. 처음에, 나는 코사인 유사성과 페이지 순위의 선형 조합을 시도하고 그것이 어떻게 작동하는지 확인하려고 노력했으며 페이지 순위의 무게가 홈페이지보다 너무 많고 다른 권위있는 페이지가 항상 결과에 나타나기 때문에 꽤 나빴습니다. 대신 무게가 코사인 유사성에 더 많이 기울어지면 페이지 순위는 전혀 영향을 미치지 않을 것입니다.
두 번째 시도는 꽤 좋은 결과를 얻었습니다. 나는 기본적으로 처음 100 개의 결과를 사용하여 다른 사람들을 모두 사용하고 폐기했으며 관련이없는 것으로 간주했습니다. 그런 다음 페이지 순위와 선형 조합을 수행했습니다. 이번에는 이미 관련된 문서의 다른 순열 일 뿐이 므로이 시점에서 홈페이지 및 기타 권위있는 문서가 이미 버려 졌기 때문에 작동했습니다.
이 유형의 애플리케이션에서 Page Rank의 목적이 달성되었다고 생각합니다. 더 관련성이 높은 페이지를 고려하여 사용자가 자신의 쿼리에 입력 한 것과 매우 유사한 결과 외에도 우수하고 신뢰할 수있는 정보 소스를 찾을 수 있도록 정상적인 검색을 편향시킬 수있었습니다.
CPRF (Context Pseudo Relevance 피드백) 나는 실제 구현에서 거의 한 달 동안 내 원칙과 맞춤형 스마트 구성 요소에 대한이 아이디어를 생각해 냈습니다. 내가 구현할 때, 나는 그것이 예상대로 작동했을 것이라고 확신하지 못했고 나는 아무것도하지 않는 것을 두려워했다.
웹 검색 엔진이 어떤 종류의 스마트 구성 요소를 가질 수 있는지 생각할 때, 사용자 쿼리의 컨텍스트를 추측하고 그가 구체적으로 요구하는 것 외에도 그가 검색 한 것과 매우 관련이있는 결과와 더불어 그를 줄 수 있다면 좋을 것이라고 생각했습니다. 동의어를 기반으로 한 간단한 정적 쿼리 확장은 너무 단순했고 관련이 있지만 의미가 다른 내용을 캡처 할 수 없었을 것입니다.
그러나 처음에는 다른 것이 없기 때문에 시작점은 항상 사용자의 쿼리 여야합니다. 의사 관련 피드백이 어떻게 자율적으로 쿼리를 재구성 할 수 있었는지에 대한 아이디어를 정말 좋아했습니다. 물론 사용자가 자신의 쿼리에 어떤 다른 단어를 포함시키고 싶은지 물었을 때 명백한 관련성 피드백은 아마도 더 나을 것입니다. 그러나 동시에 검색하는 동안 몇 가지 질문에 응답해야한다는 것이 성가신 일 수 있습니다. 의사 관련 피드백은 사용자가 알지 못하는 더 복잡한 쿼리를 배경으로 더 적절하고 쉬운 방법으로 보입니다.
공식화 된 쿼리의 컨텍스트를 표현할 수있는 단어를 추출하기 위해 나는 처음에 검색된 문서가 가지고있는 몇 가지 본질적인 정보를 사용하기로 결정했습니다. 특히, 문서에서 TF-IDF가 가장 높은 단어는 해당 문서의 주제와 다른 문서와 차별화 될 수 있다고 생각합니다. 왜냐하면 단어가 많은 문서에 포함되어 있지 않을 때 TF-IDF가 높기 때문에 해당 문서에서 재발합니다.
컨텍스트 단어를 추출하는 프로세스는 다음과 같습니다. 순위가 매겨진 문서에서 숫자 _docs_expansion 문서를 취합니다 . , 각 문서에 대해 나는 가장 높은 tf-idf (constant numb 결국 나는 토큰을 평가하고 맨 위 순위는 쿼리의 컨텍스트를 나타내는 각각의 검색된 문서의 일반적인 단어입니다. 그런 다음 n 확장 된 단어 (constant numb
확장 된 토큰은 쿼리의 원래 단어보다 적은 차이 가중치가 주어 지므로이 E_Const는 Statistics.py Script에서 변경할 수 있습니다.
지능형 구성 요소가 실제로 어떤 경우에는 약간의 개선을 제공한다고 생각한 쿼리를 기반으로합니다.
항상 작동하는 첫 번째 큰 결과는 검색된 문서 세트를 확장 할 수있는 기능입니다. 실제로 몇 문서에 쿼리에 단어가 포함 된 경우 일반 검색 엔진은 소수의 문서 만 검색합니다. 대신, CPRF 스마트 구성 요소를 사용하면 결과 세트가 훨씬 더 크며 크기가 100 개 이상인 검색 세트로 이어질 수 있습니다.
일부 쿼리에서 알아 차린 또 다른 긍정적 인 결과는 실제로 첫 번째 결과로 찾고 있던 것을 찾는 반면 간단한 검색 엔진은 상위 10 개 결과에서도 찾지 못한다는 것입니다. 이에 대한 예는 “컴퓨터 과학 과정”을 검색하여 볼 수 있습니다. 내가 찾고 싶은 것은 UIC의 컴퓨터 과학 부서에서 제공하는 모든 주요 과정의 목록입니다. 이것은 지능형 구성 요소가 활성화 될 때 엔진에 의해 검색된 첫 번째 결과입니다. 대신, 활성화하지 않고 해당 페이지는 첫 번째 결과가 아닙니다.
마지막으로, 나는 "정보 검색" 을 검색하려고 시도했는데, CPRF가 없는 검색 엔진은 매우 나빴습니다. 첫 번째 결과는 UIC 부서의 검색 페이지입니다. 아마도 UIC 도메인에 정보 검색을위한 페이지가 없거나 도메인에 포함되지 않았기 때문일 수도 있습니다. 그러나 스마트 구성 요소가 켜져 있고, 이와 관련된 많은 웹 페이지가 발견되었고, 확장 된 단어 중 2 개는이 과정을 가르치는 교수 인 “Cornelia Caragea” 였으므로 많은 페이지가 그녀의 출판물과 정보 검색과 관련된 작업과 관련하여 검색 엔진의 매우 좋은 속성이기도합니다. 매우 관련성이 높은 결과를 찾을 수없는 경우 관련 사항에 대한 최상의 결과를 찾을 수 있습니다.
평범한 검색 엔진과 스마트 구성 요소를 사용하는 비교를 할 때 5.3에서 설명한 바와 같이, 생성 된 결과는 꽤 좋았으며 이것에 대해 생각할 때 기대했던 것을 얻었습니다. 내가 테스트하여 알아 차린 좋은 것들은 다음과 같습니다.
원래 쿼리가 많은 웹 사이트 만 출력하는 경우에도 더 많은 결과를 찾을 수 있습니다.
제가 실제로 찾고 있던 것을 첫 번째 결과로 찾는 능력, 예를 들어 5.3 항에서 설명한 것처럼 "컴퓨터 과학 과정" 에서 쿼리에서 "컴퓨터 과학 과정".
코퍼스에 쿼리와 매우 관련이있는 페이지가 포함되어 있고 사용자가 검색하는 내용이 포함되어 있지 않은 경우에도 불명예 컨텐츠를 검색하는 매우 멋진 속성은 5.3 항에 설명 된대로 쿼리 "정보 검색" 에 대해 알았습니다.
이것이 올바른 결과를 낳고 있음을 보여주는 한 가지 방법은 컨텍스트를 나타내는 상위 10 개의 확장 단어에서 사용자 쿼리에 속하는 단어가 존재한다는 사실이었습니다. 이것은 메소드가 주제를 효과적으로 캡처 할 수있는 방법을 보여 주며 해당 세트의 다른 단어를 원래 쿼리의 컨텍스트와 동일한 컨텍스트에 속하지 않는 경우 다른 단어를 설명하는 다른 방법이 없습니다.
대신 페이지 순위에 대해 이야기합니다. 나는 그것이 그 일을한다고 생각하지만, 내가 구현 한 방식에서 순위를 너무 많이 바꾸지는 않지만, 그 결과가 더 권위있는 페이지를 선호하는 결과를 편향시키는 방법 일뿐입니다.
확실히 여기에서 해결해야 할 사항 중 하나는 하이퍼 파라미터 튜닝입니다. 라벨이 붙은 데이터가 부족하기 때문에 주로 수행하기가 가장 어려운 일입니다. 쿼리의 정밀도를 평가할 수없는 경우 매개 변수의 값이 더 잘 작동하는지 알 수 없으며 자동으로 조정하려면 이미 레이블이 지정된 데이터가 많이 있어야합니다.
