web search engine UIC
1.0.0
イリノイ大学シカゴのイリノイ大学でのCS 582情報検索コースの最終プロジェクト
ターミナルからプログラムを実行するには、コマンドを使用するだけです。
python main.py
検索エンジンの機能とUIをよりよく説明するためにレポートが提供されています。
Report.pdf
このドキュメントは、イリノイ大学シカゴ校でのCS 582情報検索の最終プロジェクトのレポートです。このプロジェクトは、UICドメインのWeb検索エンジンをゼロから構築することで構成されていました。このソフトウェアは、Webクロールから始まり、ページの前処理、インデックス作成、最後にグラフィカルユーザーインターフェイスを追加して、モジュール式に構築されました。さらに、私たちによって発明されたカスタマイズされた「スマート」コンポーネントは必要でした。
ユーザーのクエリから幅広いコンテキストを取得しようとする疑似リバンスフィードバックアプローチに基づいてクエリ拡張を使用して、検索エンジンの最適化を実験することにしました。これにより、主に検索エンジンに2種類の改善が追加されるはずです。
すべての結果をクエリの単語のみに焦点を合わせるのではなく、取得したページのセットに多様で関連するコンテンツを含めてください。
クエリに存在する単語のいずれも含まれていないが、同じトピックを扱うため、ユーザーにとって興味深い可能性があるWebページを含む、結果の総数を拡大します。
ページランクの実装も統合されており、アプリケーションUIからオンまたはオフにすることができます。両方のスマートコンポーネントの詳細については、このドキュメントの後半でご覧いただけます。
ソフトウェアを含むリポジトリには、githubを介してアクセスできます。
https://github.com/mirkomantovani/web-search-engine-uic
このソフトウェアは、Python3でオブジェクト指向のプログラミングファッションで記述されており、将来のために簡単に拡張できるようにします。広範かつ時間のかかるクロールとページの前処理を実行せずにコードを簡単にダウンロードしてテストできるようにするために、UICドメインから10000ページを含むデータセット：https：//www.uic.edu/、およびpreprocessedページと必要なファイルが生成されたページング、ページ '、ページ、ページ、ページ、ページ、ページ、ページ、ページURL）はリポジトリに含まれています。このようにして、リポジトリをクローニングすることにより、 main.pyを実行でき、1秒未満で検索エンジンが入力のクエリを取得する準備ができています。ただし、クロールと前処理を実行するスクリプトも含まれており、他のすべてのコンポーネントを使用して以下のサブセクションで説明します。
Webクローリングは、スクリプトMultiThreaded_Crawling.pyを実行することで実行できます。クローリングは、キューモジュールを使用して同期した方法でリソースにアクセスすることで並行して発生します。
クロールは、UIC CSサブドメインから始まります：https：//www.cs.uic.edu/ multiThreaded_crawling.pyスクリプトで指定されています。
クロールは、幅広い戦略で起こり、すべてのページはhtmlparserライブラリを使用してデキュー、ダウンロード、および解析され、そのリンクは抽出され、UICドメインに属するようにチェックされ、適切な形式の場合はFIFOキューに追加されます。すべての悪い形式のブラックリストは、私がrawいをしていた結果を見ている間に私によって導き出されました：「.docx "、" .doc "、" .avi "、" .mp4 "、" .jpg "、" .jpeg "、" .png "、" .gif ".pdf"、 ".tar" ".trar ".tgz"、 ".zip"、 ".exe"、 ".js"、 ".css"、 ".ppt"。 10秒のタイムアウトは、接続を閉じて次のページに渡す前に、ページをダウンロードする最大時間として指定されています。
URLは抽出された後にも変更され、初期のHTTPごとにすべてのHTTPになり、最後にスラッシュされたすべてが排除され、クエリ文字列が削除され、ハッシュシンボル（＃）で表されるページ内リンクも削除されます。さらに、<a>タグが開かれ、別のタグが内部に開かれたリンクの処理は、文字列内の別のタグ「<」の開く際にリンクを分割することにより行われます。
クロール中に、2つの辞書、URLからのURLとURLのコードが常にディスクに保存され、後で使用されます。Webページのコードは、ダウンロードされたページの番号です。
クロールされたページの前処理は、 run_preprocessing.pyスクリプトから実行できます。また、対応する定数page_rank_max_iterとn_pagesを変更することにより、考慮すべきページ数とページランクの最大反復数を指定することもできます。
プリプロセシング中に、 Preprocess.pyスクリプトからのカスタムトケニザオブジェクトが使用されます。各ページは、最初に<script>および<style>を除くすべてのタグでプレーンテキストを取得することにより前処理されます。このステップでは、非常に高速なライブラリであるselectolaxを使用することにしました。これは、Cpythonで書かれた控えめなエンジンを使用するPython APIであり、もちろん、純粋なPythonで記述されたHTML区画に関して、少なくとも1桁の計算時間が少なくなります。その後、ページはトークン化され、トークンはNLTKによってポーターステムマーを使用して抑制され、ストップワードはファイルstopwords.txtで提供されるストップワードのリストを使用して排除され、数字は削除され、3文字より短い単語は考慮されません。
前処理では、反転インデックスが構築され、各ワードドックペアのTF-IDFが計算され、反転インデックスに保存されます。また、指示されたWebグラフ（ Graph.py ）も作成され、 page_rank.pyのページランクの実装にフィードが表示されます。後でクエリに答えるのに必要なすべてのファイルは、バイナリファイルとして保存されます。
10000ページの前処理とpage_rankコンバージェンスにかかる合計時間は約236秒で、ページランクの実行時間は約11秒でした。
Main.pyスクリプトには、検索エンジンへのアクセスポイントが含まれています。プログラムが開始されると、クエリをトークン化するためにCustomTokenizerオブジェクトが作成されると、クエリに基づいてドキュメントをランク付けするために、TFIDFrankerオブジェクトがインスタンス化されます。
ドキュメントがユーザーのクエリに基づいてランク付けされている場合、最大100のドキュメントが考慮されます。この定数はmain.py：max_results_to_considerで変更される可能性があります。
ユーザーインターフェイスはグラフィカルであり、PythonパッケージであるEasyGuiを使用して実装されています。 GUIは、プログラムの基本機能のメインAPIを含む拡張可能なモジュールであるCustomGui.pyです。
プログラムが起動すると、ユーザーには、ページランクとコンテキストの擬似リバンスフィードバックを使用するかどうかにかかわらず、ユーザーに基本的な設定が求められます。その後、メインメニューが表示されます。メインメニューには、検索エンジンの現在の設定と、実行できるメインアクションのボタンが表示されます。メインメニューから適切なボタンを選択することにより、実行時に設定を動的に変更できます。他の2つの選択肢は、プログラムを終了してクエリを実行することです。ユーザーがボタンを押して新しいクエリを作成すると、新しいウィンドウが表示され、ユーザーは新しいクエリを挿入するように求められます。彼が大丈夫にクリックすると、クエリが前処理され、ドキュメントがランク付けされ、最初の10（プログラムの変数）ドキュメントは、プリドレバンスのクエリに関する情報と、おそらく擬似リレクトフィードバックが発生している場合は拡張トークンの情報とともに表示されます。ユーザーは、結果をダブルクリックして、システムのデフォルトブラウザの新しいタブでページを開くか、リストの最後にある「より多くの結果を表示」を再帰的に押して、さらに10の結果を表示できます。さらに、擬似リバンスフィードバックがオフになっている場合、ユーザーには拡張と同じクエリを再実行する可能性も与えられます。
クエリを実行して結果をキャンセルまたは開くことにした後、ユーザーはメインメニューに戻って、設定を変更したり、異なる設定で新しいクエリまたは同じクエリを実行して、結果を以前に取得したものと比較できます。
このプロジェクトの開発中に私が経験した主な課題は次のとおりです。
当初、どのようなスマートコンポーネントを設計するかを選択することは本当に困難でした。私はこのタイプのアプリケーションの経験はまったくありません。テストするデモを持たずに改善について考えるのは非常に困難です。
実装の部分では、スレッド、HTMLページからリンクを取得するためにWebスクレイピングを実装または実行する方法など、まだ知らなかったPythonライブラリや構成について多くの時間を費やしました。私がゼロから学ばなければならなかったもう一つのことは、PythonでGUIを作成する方法でした。
迷惑なことは、さまざまな間違った形式をページで見つけたので、私は10000ページ以上を複数回crabっていなければならなかったという事実でした。最終的に、私がブラックリストしなければならなかったフォーマットのリスト全体のサイズは18で、それは「.docx」、 ".doc"、 ".avi"、 ".mp4"、 ".jpg"、 ".jpeg"、 ".png"、 ".gif"、 ".pdf"、 ".gz"、 "。 ".exe"、 ".js"、 ".css"、 ".ppt"。
非常に挑戦的なことは、ハイパーパラメータのチューニングと、ドキュメントをランク付けするためのページランクの統合でした。拡張クエリのトークンにどれだけ重要なことを与えるかを決定するパラメーター「 E 」は、データをラベル付けしていない場合、検索エンジンの平均パフォーマンスを知ることができないため、チューニングが最も困難です（各クエリの関連ドキュメント）。また、クエリの関連性は主観的であり、人が何を取得したいかわからず、クエリに基づいてのみ推測することができます。 Eは最大で0.5であることを決め、最後に0.1-0.2頃に設定しました。ユーザーが入力されていない単語を非常に重要にすることで、クエリをあまりバイアスしたくありません。
私が使用した重み制度は、Web検索エンジンに関して最も効果的なものの1つであり、各ドキュメントの単語の重要性を正しい方法で説明しているため、ドキュメントの単語の単純なTF-IDFでした。このプロジェクトの目的ではなかったからといって、別の尺度を試すことさえ考えていませんでした。
ドキュメントのランク付けに使用される類似性尺度は、コサインの類似性でした。内部製品の類似性から開始し、それに切り替えることは、1行のコードを変更するだけの問題になりました。 Cosineの類似性は、ドキュメントの長さとクエリの長さを考慮するため、使用する方が良いと思います。それはより複雑であり、通常、このタイプのアプリケーションで実際にはかなりうまく機能するため、類似性の尺度を選択することは実際には問題ではありませんでした。コサインの類似性が正しいことを知っていました。
私は、私が思いついたランダムで多様なクエリについて、10時（最初の10の結果を取得した結果のみを考慮する）で精度の評価を行いました。結果は次のとおりです。
クエリ： 「アドバイザー論文」、最初の結果はhttps://grad.uic.edu/electronic-thesisdissertation-faqsでした。すべての結果は論文と相関関係に関連していたと思います。
クエリ： 「キャリアフェア」、最初の結果はhttps://ecc.uic.edu/career-fairsでした。すべての結果は、キャリアフェア、キャリアサービス、イベント、雇用に多少関連していたと思います。
クエリ： 「研究アシスタントシップ」、最初の結果はhttp://grad.uic.edu/assistantshipsであり、最後のものを除くすべてがアシスタントシップに関連していたと思います。これは、ra、ta、またはgaであるためです。
クエリ： 「インターンシップと雇用」、最初の結果はhttps://careerservices.uic.edu/students/internshipsでした。今回は6つのWebページのみが関連していましたが、まだキャリアと雇用に関連していないものでした。このクエリに精度： p = 0.6を示します。
クエリ： 「学生センターイーストアドレス」、最初の結果はhttps://fimweb.fim.uic.edu/buildingsdata.aspxでした。このクエリはより具体的かつ複雑であり、実際には4つの結果からのみ実際に建物のアドレスを抽出できますが、他のすべての結果は、学生センターについては、学生センターについて話していません。このクエリに精度： p = 0.4を与えます。
平均精度は0.78で、すべてのクエリが少なくとも1つの関連する結果を返したという事実で、結果は個別だと思います。
私が実験した最初のインテリジェントは、単純でシンプルなページランクでした。ページの前処理中に、リンクが抽出され、リンク接続に基づいて世界グラフが作成されます。 Pageランクの実装は、グラフ全体で強く接続されたコンポーネントを作成したようなものでした。つまり、すべてのノードから、非ヌル確率でグラフの別のノードに到達することが可能です。この解釈により、ランダムな歩行者がページに詰まってしまう可能性はありません。
ページのランクは、ドキュメントのスコアリングに統合してランク付けするのが少し困難でした。最初は、コサインの類似性とページランクの線形組み合わせを実行して、どのように機能したかを確認しようとしましたが、ページランクの重みがホームページや他の権威あるページが常に結果に表示されるよりも多すぎる場合、それはかなり悪かったです。代わりに、重量がコサインの類似性に向かってさらに傾いている場合、ページランクはまったく効果がありません。
2番目の試みはかなり良い結果をもたらしました。私は基本的に、最初の100の結果を他のすべてのもののみを使用して廃棄しただけで、それらは関連性がないと考えました。次に、ページランクと線形の組み合わせを行いました。今回は、すでに関連する文書の別の順列であり、たとえばホームページやその他の権威ある文書がこの時点ですでに破棄されているため、機能しました。
このタイプのアプリケーションでのページランクの目的が達成されたと思います。通常の検索にバイアスをかけて、より関連性の高いより権威あるページを検討することができたため、ユーザーは彼がクエリのタイプに非常に似た結果に加えて、優れた信頼できる情報源を見つける可能性が高くなりました。
コンテキスト擬似リバンスフィードバック（ CPRF ）私は、実際の実装からほぼ1か月間、私の原則とカスタマイズされたスマートコンポーネントのこのアイデアを思いつきました。私が実装していたとき、それが期待どおりに機能していたかどうかはわかりませんでした。
Web検索エンジンがどのようなスマートコンポーネントを持つことができるかを考えていたとき、ユーザーのクエリのコンテキストを推測し、彼が具体的に求めているものに加えて、彼が検索したものに非常に関連するいくつかの結果に加えて彼を与えることができればいいと思いました。同義語に基づく単純な静的クエリ拡張は、単純すぎて、関連するが異なるセマンティックを持っているコンテンツをキャプチャすることができなかったでしょう。
ただし、最初は他に何もないため、開始点は常にユーザーのクエリでなければなりません。私は、擬似関係のフィードバックがあなたが自律的な方法であなたのクエリを再定式化できる方法のアイデアが本当に気に入っていました。もちろん、ユーザーがクエリにどの他の言葉を含めたいかを尋ねられたときに明示的な関連性フィードバックがおそらくより良いでしょうが、同時に、検索中にいくつかの質問に応答しなければならないことは迷惑になる可能性があります。擬似リバンスフィードバックは、ユーザーが認識していないより複雑なクエリをバックグラウンドで実行するためのより適切で簡単な方法のようです。
定式化されたクエリのコンテキストを表現できるいくつかの単語を抽出するために、最初に取得したドキュメントが持っている本質的な情報を使用することにしました。特に、ドキュメント内の最高のTF-IDFを持つ単語は、そのドキュメントのトピックと、他のドキュメントと区別するものを表すことができると思います。なぜなら、TF-IDFは多くのドキュメントに含まれていないが、そのドキュメントでは再発している場合に高いからです。
コンテキスト単語を抽出するプロセスは次のとおりです。ランク付けされたドキュメントから、number_docs_expansionドキュメントを取得します。 、各ドキュメントについて、最高のTF-IDF（constant number_top_tokens）のトークンを撮影し、それらの個々のトークンごとに、単語が存在する場合、各ドキュメントのこの単語のすべてのTF-IDFを要約します。最後に、トークンをランク付けし、上位の単語は、クエリのコンテキストを表す各取得ドキュメントの一般的な単語です。次に、n拡張単語（constant number_expansion_tokens）セットを返します。このセットには、オリジナルのクエリトークンが繰り返されず、それらの単語をあまりにも重視するために差し引かれます。
拡張されたトークンには、クエリの元の単語よりも少ない差が与えられます。このE_CONSTはstatistics.pyスクリプトで変更できます。
インテリジェントなコンポーネントが実際にいくつかの改善をもたらすと思うクエリに基づいています。
常に機能する最初の大きな結果は、常に取得されたドキュメントのセットを拡張する機能です。実際、クエリに単語のいずれかが含まれている場合、プレーン検索エンジンはこれらの少数のドキュメントのみを取得するだけです。代わりに、 CPRFスマートコンポーネントを使用すると、結果のセットが大きくなり、サイズが100を超えるドキュメントである検索セットにつながる可能性があります。
いくつかのクエリで気づいたもう1つの肯定的な結果は、実際に私が探していたものを最初の結果として見つけたのに対し、単純な検索エンジンは上位10の結果でさえ見つけられないことです。この例は、 「コンピューターサイエンスコース」を検索することで観察できます。私が見つけたいのは、UICのコンピューターサイエンス部門が提供するすべてのメインコースのリストです。これは、インテリジェントコンポーネントがアクティブなときにエンジンによって取得された最初の結果です。代わりに、それをアクティブにせずに、そのページは最初の結果ではありません。
最後に、 「情報検索」を検索しようとしましたが、 CPRFのない検索エンジンは非常に悪かったです。最初の結果はUICの部門の検索ページです。これは、おそらくUICドメインに情報検索のページがないか、ドメインに含まれていないためです。ただし、スマートコンポーネントがオンになっていると、これに関連する多くのWebページが見つかりました。拡張された単語の2つは「Cornelia caragea」、このコースを教えている教授であるため、多くのページが実際に彼女の出版物と情報の検索に関連していました。これは検索エンジンの非常に良いプロパティでもあります。非常に関連性のある結果が見つからない場合でも、関連することについて可能な限り最良の結果を見つけることができます。
5.3で説明されているように、プレーン検索エンジンとスマートコンポーネントを使用したときの比較を行ったように、作成された結果はかなり良かったと思います。私がそれをテストすることで私が気づいた良いことを要約したのは：
元のクエリがWebサイトの束のみを出力する場合でも、さらに多くの結果を見つける機能。
パラグラフ5.3で説明したように、たとえば「コンピューターサイエンスコース」のクエリなど、私が実際に探していたものを最初の結果として見つける能力。
コーパスにクエリに非常に関連するページとユーザーが検索しているページが含まれていない場合でも、個別のコンテンツを取得するという非常に優れたプロパティは、パラグラフ5.3で説明されているように、クエリ「情報検索」についてこれに気付きました。
これが正しい結果を生み出していることを私に示した1つの方法は、コンテキストを表す上位10の拡張単語で、ユーザーのクエリに属するいくつかの単語が存在するという事実でした。これは、この方法がトピックを効果的にキャプチャできる方法を示しており、元のクエリのコンテキストと同じコンテキストに属する単語としてではないにしても、そのセットの他の単語を説明する他の方法はありません。
代わりにページランクについて話します。私はそれがその仕事をすると思いますが、それは私が実装した方法でランキングをあまり変えません。それは、もしあればより権威あるページを好むために結果をバイアスする方法です。
確かに、ここから対処しなければならないことの1つは、ハイパーパラメーターのチューニングです。主にラベル付きデータがないために行うことは最も難しいことです。クエリの精度を評価できない場合、パラメーターのどの値がうまく機能するかはわかりません。自動的にチューニングするために、すでにラベル付けされたデータがたくさんあるはずです。
