web search engine UIC
1.0.0
Окончательный проект для курса поиска информации CS 582 в Университете Иллинойса в Чикаго
Для запуска программы из терминала просто используйте команду:
Python main.py
Представлен отчет, чтобы лучше объяснить функциональные возможности и пользовательский интерфейс поисковой системы, пожалуйста, см.
report.pdf
Этот документ является отчетом для окончательного проекта по поиску информации CS 582 в Университете Иллинойса в Чикаго. Проект состоял в создании веб -поисковой системы для домена UIC с нуля. Программное обеспечение было построено модульно, начиная с ползания в Интернете, проходившей страниц предварительной обработки, индексации и, наконец, добавления графического пользовательского интерфейса. Более того, индивидуальный «умный» компонент, изобретенный нами, был необходимым.
Я решил экспериментировать в поисковой оптимизации, используя расширение запросов на основе подхода обратной связи с псевдо-релеванкой, который пытается получить широкий контекст из запроса пользователя, я назвал это контекстом псевдо-релевантной обратной связи ( CPRF ). Это должно было добавить в основном два типа улучшений в поисковой системе:
Не сосредотачивайте все результаты только на словах в запросе, но включая разнообразный и связанный контент с полученным набором страниц.
Расширение общего количества результатов, включая веб -страницы, которые не содержат ни одного из слов, присутствующих в запросе, но все еще могут быть интересными для пользователя, поскольку рассматривают ту же тему.
Реализация ранга страницы также интегрирована и может быть включена или выключена из пользовательского интерфейса приложения. Более подробную информацию об обоих интеллектуальных компонентах можно найти позже в этом документе.
Репозиторий, содержащий программное обеспечение, можно получить через GitHub по адресу:
https://github.com/mirkomantovani/web-search-engine-uic
Программное обеспечение написано в Python3 объектно-ориентированным программным способом, чтобы сделать его легко расширяемым в будущем. Чтобы облегчить загрузку и тестирование кода без необходимости выполнять обширные и трудоемкие полки и предварительную обработку страниц, набор данных, содержащий 10000 страниц, заполненный доменом UIC: https://www.uic.ed URL) включены в репозиторий. Таким образом, клонируя репозиторий, main.py может быть запущен, и менее чем за секунду поисковая система готова получить запросы при вводе. Тем не менее, сценарии для запуска ползания и предварительной обработки также включены и объясняются в следующих подразделах со всеми другими компонентами.
Ползание в Интернете может быть выполнено, выполнив сценарий MultiThreaded_Crawling.py , ползание происходит параллельно, используя модуль очереди для доступа к ресурсам синхронизированным образом, количество тем может быть изменено, изменяя глобальную константу Trink_number в одном и том же сценарии, что по умолчанию, однако, по умолчанию, и все в другом месте, и не в чем -то в одном, и в этом времени, и в том же времени.
Ползание начинается с поддомена UIC CS: https://www.cs.uic.edu/, указанное в сценарии MultiThreaded_Crawling.py .
Ползание происходит со стратегией в ширине, каждая страница находится на грани, загружается и проанализирована с использованием библиотеки HTMLParser , ее ссылки извлекаются и проверяются, чтобы принадлежать к домену UIC, а затем добавляются в очередь FIFO, если он находится в соответствующем формате. Черный список всех плохих форматов был получен мной, когда я видел результаты, которые я получал в ползании, и он состоит в этом 18 форматах: «.docx», «.doc», «.avi», «.mp4», «.jpg»,. ".tgz", ".zip", ".exe", ".js", ".css", ".ppt". Тайм -аут 10 секунд указан как максимальное время для загрузки страницы перед закрытием подключения и передачи на следующую страницу.
URL-адреса также модифицируются после того, как они извлечены, каждый начальный HTTP становится HTTP, все срезанные в конце удаляются, строки запроса удаляются, а также внутригистральные связи, выраженные хеш-символом (#), также удаляются, чтобы не позволять липлеру верить, что больше страниц с разными инфинами-links различны и не являются различными PLLS. Более того, обработка ссылок, где открывается тег <a>, а в строке открывается другой тег, прежде чем закрытие Href была сделана, разделяя ссылку на открытии другого тега «<» в строке.
Во время ползания два словаря, URL -адрес из кода и код из URL постоянно сохраняются на диск, который будет использоваться позже, код веб -страницы - это число загруженной страницы в хронологическом порядке.
Предварительная обработка полных страниц может быть выполнена из сценария run_preprocessing.py , вы также можете указать количество страниц, которые необходимо рассмотреть и максимальное количество итераций ранга страницы, изменяя соответствующие константы Page_rank_max_iter и N_Pages.
Во время предварительной обработки используется объект CustomTokenizer из сценария preprocess.py . Каждая страница предварительно обрабатывается, сначала получая простой текст во всех тегах, кроме <script> и <style>. Для этого шага я решил использовать очень быструю библиотеку: SelectOlax , которая представляет собой API Python для использования скромного двигателя, написанного в C. CPYTHON, конечно, обеспечит, по крайней мере, на один порядок меньше в вычислительное время в отношении любых HTML -диапазонов, написанных в Pure Python. Страница затем токенов, токенов обходится с использованием портерштоммера от NLTK , остаточные слова устраняются с использованием списка остановок, указанных в остановке файла, цифры удаляются, а слова короче 3 буквы не рассматриваются.
В предварительной обработке строится инвертированный индекс, и TF-IDF каждой пары Word-DOC вычисляется и хранится в инвертированном индексе. Направленный веб -график ( graph.py ) также создается и подается для реализации ранга страницы в page_rank.py . Все файлы, необходимые позже, чтобы ответить на запрос, затем сохраняются как двоичные файлы.
Общее время, необходимое для предварительной обработки и конвергенции Page_rank для 10000 страниц, составило приблизительно 236 секунд, время выполнения ранга на странице составило всего около 11 секунд.
Сценарий Main.py содержит точку доступа к поисковой системе. Когда программа запускается, объект CustomTokenizer создается для токенизации запросов, вместо этого создается создание объекта TFIDFranker для ранжирования документов на основе запросов.
Когда документы ранжируются на основе запроса пользователя, учитывается максимум 100 документов, эта константа может быть изменена в main.py : max_results_to_consider, другие настраиваемые параметры - это количество результатов, которые можно отображать в результате времени на результатах_ПЕР_PAGE, количество страниц для использования: n_pages.
Пользовательский интерфейс графический и реализован с использованием пакета Python: EasyGui. GUI - это расширяемый модуль, CustomGui.py , который содержит основные API для основных функций программы.
Когда программа запускается, пользователю спрашивают основные настройки, хочет ли он использовать ранг страницы и контекст псевдо-релеванс-обратной связи или нет. После этого появляется главное меню. В главном меню показаны текущие настройки поисковой системы и некоторые кнопки для основных действий, которые можно выполнить. Настройки могут быть динамически изменены во время выполнения, выбрав соответствующую кнопку из основного меню. Два других варианта: покинуть программу и запуск запроса. Если пользователь нажимает кнопку, чтобы создать новый запрос, появится новое окно, и пользователю предложено вставить новый запрос. Когда он нажимает нормально, запрос предварительно обработан, и документы ранжируются, а первые 10 (переменные в программе) отображаются вместе с информацией о предварительно обработанном запросе и, возможно, расширенных токенах, если псевдо-релевантная обратная связь включен. Пользователь теперь может дважды щелкнуть результат, чтобы открыть страницу на новой вкладке в браузере по умолчанию своей системы или может рекурсивно нажать «Показать больше результатов» в конце списка, чтобы показать еще 10 результатов. Более того, если обратная связь с псевдо-релеванкой отключена, пользователю также предоставляется возможность повторно затронуть тот же запрос с расширением.
После запуска запроса и решил отменить или открыть результат, пользователь предлагается обратно в главное меню, где он может изменить настройку и/или запустить новый запрос или тот же с различными настройками, чтобы сравнить результаты с ранее полученными.
Основные проблемы, с которыми я столкнулся во время разработки этого проекта:
Первоначально было действительно трудно выбрать, какой разумный компонент для проектирования. У меня нет опыта в этом типе применения вообще, и я думаю о улучшениях без демонстрации для проверки, просто так сложно.
Во время части реализации я потратил много времени на изучение библиотек и конструкций Python, которые я еще не знал, например, тем, как реализовать или выполнять массовое соскоба, чтобы вытащить ссылки на HTML -странице. Еще одна вещь, которую я должен был учиться с нуля, - это как создать графический интерфейс в Python.
Настолько раздражающим было то, что мне пришлось ползти 10000 страниц более одного раза, потому что я обнаружил на страницах различных и неправильных форматов. В итоге весь список форматов, которые мне приходилось в черный список, имел размеры 18, и он включал «.docx», «.doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png". ".exe", ".js", ".css", ".ppt".
Очень сложной задачей была настройка Hyperparameters и интеграция ранга Page для ранжирования документов. Параметр « e » , чтобы решить, какую важность дать токенам расширенного запроса является наиболее сложным для настройки, потому что вы не можете знать средние результаты вашей поисковой системы, если у вас нет помеченных данных (соответствующие документы для каждого запроса). Кроме того, актуальность запроса субъективна, вы никогда не знаете, что человек хочет получить, и вы можете догадаться только на основе запроса. Я решил, что E должен быть не более 0,5, и в конце я установил его около 0,1-0,2, вы не хотите смещать запрос до большого количества, придавая большое значение словам, которые не напечатаны пользователем.
Схема взвешивания, которую я использовал, была простой TF-IDF слов в документах, поскольку она оказалась одной из наиболее эффективных, когда речь идет о веб-поисковых системах, и она учитывает важность слов в каждом документе правильным образом. Я даже не думал о том, чтобы попробовать другую меру только потому, что это не было целью этого проекта, и это, казалось, просто сработало.
Мера сходства, используемая для ранжирования документов, была сходством косинуса . Я реализовал, начиная с внутренней сходства продуктов, и переключение, это было бы просто вопросом изменения одной строки кода. Я думаю, что сходство косинуса лучше использовать, потому что оно учитывает длину документа и длину запроса. Это более сложно, и обычно это работает довольно хорошо на практике в этом типе приложений, поэтому выбор меры сходства не был на самом деле проблемой, я просто знал, что сходство косинуса было правильным.
Я провел оценку точности на 10 (только с учетом первых 10 результатов, полученных) для некоторых случайных и разнообразных запросов, которые я придумал. Вот результаты:
Запрос: «Тезис консультанта», первым результатом был https://grad.uic.edu/electronic-teestydissertation-faqs, и я думаю, что все результаты были связаны с тезисом и коррелированными вещами, я дам точность: P = 1,0 к этому запросу.
Запрос: «Ярмарка карьеры», первым результатом был https://ecc.uic.edu/career-fairs, и я думаю, что все результаты были несколько актуальны для ярмарок карьеры, карьерных услуг, мероприятий и занятости, я дам точность: P = 1,0 к этому запросу.
Запрос: «Помощник исследований», первым результатом был http://grad.uic.edu/assistanthips, и я думаю, что все, кроме последнего, были связаны с ассистентами, поскольку это RA, TA или GA, просто потому, что домен 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 результатов только с использованием и отбросил все, что они другие, и считал их нерелевантными. Затем я сделал линейную комбинацию с рангом. На этот раз это сработало, потому что это была лишь другая перестановка уже соответствующих документов, и, например, домашняя страница и другие авторитетные документы уже отброшены на данный момент.
Я думаю, что цель ранжирования страницы в этом типе приложения была достигнута, я смог сметить нормальный поиск, чтобы рассмотреть более актуальные более авторитетные страницы, чтобы пользователь с большей вероятностью обнаружил хорошие и надежные источники информации в дополнение к результатам, которые очень похожи на то, что он вводит в своем запросе.
Контекст обратной связи псевдо-релевантности ( CPRF ) я придумал эту идею своего принципа и индивидуального интеллектуального компонента почти через месяц после фактической реализации. Когда я реализовал, я не был уверен, что это сработало бы так же, как и ожидалось, и я очень боялся, что я делал все это ни за что.
Когда я думал о том, какую умную компонент может иметь веб -поисковая система, я подумал, что было бы неплохо, если бы мы могли догадаться о контексте пользовательского запроса и дать ему в дополнение к тому, что он конкретно просит, некоторые результаты, которые очень связаны с тем, что он искал. Простое расширение статического запроса, основанное на синонимах, было бы слишком простым и не смогло бы запечатлеть содержимое, которое связано, но имело бы другую семантику.
Тем не менее, отправной точкой всегда должна быть запрос пользователя, так как больше нет ничего, кроме как изначально. Мне очень понравилась идея о том, как псевдо-релевантная обратная связь смогла позволить вам переформулировать ваш запрос автономным образом. Конечно, отзывы о явной актуальности, когда пользователя спрашивают, какие другие слова он хотел бы включить в свой запрос, вероятно, будет лучше, но в то же время это может раздражать его, чтобы ответить на некоторые вопросы во время поиска. Псевдо-релевансная обратная связь кажется более подходящим и простым способом запуска на фоне более сложного запроса, о котором пользователь даже не знает.
Чтобы извлечь некоторые слова, которые могли бы выразить контекст сформулированного запроса, я решил использовать некоторую внутреннюю информацию, которую имеют первоначально извлеченные документы. В частности, я думаю, что слова с самым высоким TF-IDF в документе могут представлять тему этого документа и то, что он отличается от других, потому что TF-IDF высок, когда слово не содержится во многих документах, но оно рецидивирует в этом документе.
Процесс извлечения контекстных слов состоит из следующих: из ранговых документов я принимаю документы number_docs_expansion, которые я установил на 30, но может быть изменен в pseudo_relevance_feedback.py. , для каждого документа я беру жетоны с самым высоким TF-IDF (постоянный номер_TOP_TOKENS), и для каждого отличного токена в них я суммирую все TF-IDF этого слова каждого документа, если есть слово. В конце я ранжирует токены, а слова с верхним рангом - это общие слова каждого извлеченного документа, которые представляют контекст запроса. Затем я возвращаю N -расширенные слова (Constant Number_expansion_tokens), на что вычитаются токены запросов оригинала, чтобы не иметь повторений и придать слишком большое значение для этих слов.
Расширенные токены будут иметь разницу, меньше, чем исходные слова в запросе, этот e_const может быть изменен в сценарии Statistics.py .
Основываясь на запросах, которые я попробовал, думайте, что интеллектуальный компонент действительно дает некоторые улучшения в некоторых случаях.
Первые большие результаты, которые всегда работают, - это возможность расширить наборы извлеченных документов, на самом деле, если только несколько документов содержат какое -либо слово в запросе, простая поисковая система будет только извлекать эти несколько документов. Вместо этого, с интеллектуальным компонентом CPRF, наборы результатов будут намного больше и, возможно, всегда могут привести к извлеченному набору, размер которого составляет более 100 документов.
Еще один положительный результат, который я заметил в некоторых запросах, заключается в том, что он на самом деле находит то, что я искал в качестве первого результата, тогда как простая поисковая система даже не находит ее в десятке лучших результатов. Примером этого можно наблюдать путем поиска «курсов по информатике» , то, что я хотел найти, является списком всех основных курсов, предлагаемых Департаментом компьютерных наук в UIC. Это первый результат, извлеченный двигателем, когда интеллектуальный компонент активен. Вместо этого, без активации, эта страница не в первых результатах.
Наконец, я попытался искать «поиск информации» , поисковая система без CPRF была очень плохим, первый результат - это страница поиска для отделов UIC, это также, вероятно, потому, что нет страницы для поиска информации в домене UIC или просто не включена в домен. Тем не менее, с умным компонентом, было обнаружено много веб -страниц, связанных с этим, 2 из расширенных слов были «Корнелия Карагея», профессор, который преподает этот курс, так много страниц действительно были связаны с ее публикациями и ее работой в поисках информации, это также является очень хорошей собственностью поисковой системы. В случае, если очень релевантные результаты не могут быть найдены, он по -прежнему может найти наилучшие возможные результаты о родственных вещах.
Как объяснено в 5.3, когда я провел сравнение между обычной поисковой системой и использованием интеллектуального компонента, я думаю, что полученные результаты были довольно хорошими, и я понял, что ожидалось, когда думал об этом. Суммировали хорошие вещи, которые я заметил, тестируя это:
Возможность найти гораздо больше результатов, даже когда оригинальный запрос выводит только кучу сайтов.
Способность найти то, что я на самом деле искал в качестве первых результатов, например, в «Курсах информатики» , как я объяснил в пункте 5.3.
Очень хорошая собственность для получения дискретного контента даже там, где корпус не содержит страниц, которые очень актуальны для запроса, и, возможно, то, что пользователь ищет, я заметил это для запроса «поиск информации», как объяснено в пункте 5.3.
Одним из способов, который показал мне, что это дает правильные результаты, был тот факт, что в топ -10 расширяющихся слов, представляющих контекст, присутствовали некоторые слова, принадлежащие запросу пользователя. Это показывает, как метод эффективно способен запечатлеть тему, и нет другого способа описать другие слова в этом наборе, если не как слова, принадлежащие к тому же контексту, что и в исходном запросе.
Вместо этого говорить о ранге страницы. Я думаю, что он выполняет свою работу, но это не слишком сильно меняет рейтинг в том, как я реализовал, это просто способ смещения результатов, чтобы предпочесть более авторитетные страницы, если они есть.
Конечно, одна из вещей, которые должны быть рассмотрены отсюда, - это настройка гиперпараметров. Это самое сложное, что нужно делать в основном из -за отсутствия помеченных данных. Я не могу знать, какое значение параметра работает лучше, если я не могу оценить точность запросов, и для того, чтобы автоматически настроить его, должно быть много уже помеченных данных.
