web search engine UIC
1.0.0
Proyek Akhir untuk Kursus Pengambilan Informasi CS 582 di University of Illinois di Chicago
Untuk menjalankan program dari terminal cukup gunakan perintah:
Python Main.py
Laporan disediakan untuk menjelaskan fungsionalitas dan UI mesin pencari dengan lebih baik, silakan merujuk ke:
Report.pdf
Dokumen ini adalah laporan untuk proyek akhir pengambilan informasi CS 582 di University of Illinois di Chicago. Proyek ini terdiri dari membangun mesin pencari web untuk domain UIC dari awal. Perangkat lunak ini dibangun secara modular, mulai dari perayapan web, melalui halaman preprocessing, pengindeksan dan akhirnya menambahkan antarmuka pengguna grafis. Selain itu, komponen "pintar" yang disesuaikan yang diciptakan oleh kami adalah sebuah syarat.
Saya memutuskan untuk bereksperimen dalam optimasi mesin pencari dengan menggunakan ekspansi kueri berdasarkan pendekatan umpan balik pseudo-relevansi yang mencoba untuk mendapatkan konteks luas dari kueri pengguna, saya menyebutnya konteks umpan balik pseudo-relevance ( CPRF ). Ini seharusnya ditambahkan terutama dua jenis perbaikan pada mesin pencari:
Jangan memfokuskan semua hasil hanya pada kata -kata dalam kueri tetapi termasuk konten yang beragam dan terkait dengan set halaman yang diambil.
Memperluas jumlah total hasil, termasuk halaman web yang tidak mengandung kata -kata yang ada dalam kueri tetapi masih bisa menarik bagi pengguna karena memperlakukan topik yang sama.
Implementasi peringkat halaman juga terintegrasi dan dapat dinyalakan atau dimatikan dari UI aplikasi. Rincian lebih lanjut tentang kedua komponen pintar dapat ditemukan nanti dalam dokumen ini.
Repositori yang berisi perangkat lunak dapat diakses melalui GitHub di:
https://github.com/mirkomantovani/web-search-engine-uic
Perangkat lunak ini ditulis dalam python3 dengan cara pemrograman yang berorientasi objek untuk membuatnya mudah diperluas untuk masa depan. Untuk memudahkan untuk mengunduh dan menguji kode tanpa harus melakukan perayapan dan preprocessing halaman yang luas dan memakan waktu, dataset yang berisi 10.000 halaman yang dirangkak dari domain UIC: https://www.uic.edu, dan halaman preproses dan file yang dibutuhkan (indeks terbalik, tf-tf-paer. URL) termasuk dalam repositori. Dengan cara ini dengan mengkloning repositori, Main.py dapat dijalankan dan dalam waktu kurang dari satu detik, mesin pencari siap untuk mendapatkan kueri dalam input. Namun, skrip untuk menjalankan merangkak dan preprocessing juga dimasukkan dan dijelaskan dalam subbagian berikut dengan semua komponen lainnya.
Perayapan web dapat dilakukan dengan mengeksekusi skrip multithreaded_crawling.py , merangkak terjadi secara paralel dengan menggunakan modul antrian untuk mengakses sumber daya dengan cara yang disinkronkan, jumlah utas dapat diubah dengan memodifikasi hal -hal lain yang ada di internet.
Merangkak dimulai dari subdomain CS UIC: https://www.cs.uic.edu/ ditentukan dalam skrip multithreaded_crawling.py .
Perayapan terjadi dengan strategi yang luas, setiap halaman didequeued, diunduh dan diuraikan menggunakan perpustakaan htmlparser , tautannya diekstraksi dan diperiksa untuk dimiliki oleh domain UIC, kemudian ditambahkan ke antrian FIFO jika berada dalam format yang sesuai. Daftar hitam dari semua format yang buruk diturunkan oleh saya saat melihat hasil yang saya dapatkan dalam merangkak dan terdiri dalam 18 format ini: ".docx", ".doc", ".avi", ".mp4", ".pd", ".jpeg", ".png", ".gif" "," .pdf "," .gz "," .png "," .gif ",". ".tgz", ".zip", ".exe", ".js", ".css", ".ppt". Waktu habis 10 detik ditentukan sebagai waktu maksimum untuk mengunduh halaman sebelum menutup koneksi dan lewat ke halaman berikutnya.
URL juga dimodifikasi setelah diekstraksi, setiap HTTP awal menjadi HTTPS, semua yang dipotong pada akhirnya dihilangkan, string kueri dihapus dan juga tautan intra-halaman yang diekspresikan oleh simbol hash yang berbeda (#) dihapus agar tidak membiarkan perayap percaya bahwa halaman-halaman yang berbeda di berbagai halaman yang berbeda di berbagai halaman di berbagai halaman yang berbeda. Selain itu, penanganan tautan di mana tag <a> dibuka dan tag lain dibuka di dalam sebelum menutup HREF dilakukan dengan membagi tautan pada pembukaan tag lain "<" di string.
Selama merangkak, dua kamus, URL dari kode dan kode dari URL secara konstan disimpan ke disk untuk digunakan nanti, kode halaman web adalah jumlah halaman yang diunduh dalam urutan kronologis.
Preprocessing dari halaman yang dirangkak dapat dieksekusi dari skrip run_preprocessing.py , di sana Anda juga dapat menentukan jumlah halaman yang perlu dipertimbangkan dan jumlah maksimum iterasi peringkat halaman dengan mengubah konstanta yang sesuai Page_Rank_MAX_ITER dan N_PAGES.
Selama preprocessing, objek CustomTokenizer dari preprocess.py Script digunakan. Setiap halaman diproses dengan terlebih dahulu mendapatkan teks biasa di semua tag kecuali <script> dan <tyle>. Untuk langkah ini saya memutuskan untuk menggunakan perpustakaan yang sangat cepat: selectolax , yang merupakan API Python untuk menggunakan mesin sederhana yang ditulis dalam C. cpython tentu saja akan memberikan setidaknya satu urutan besarnya lebih sedikit dalam waktu komputasi sehubungan dengan parsen HTML yang ditulis dalam ular surut murni. Halaman tersebut kemudian tokenized, token dibawa menggunakan Porterstemmer oleh NLTK , stopwords dihilangkan menggunakan daftar kata-kata stop yang disediakan dalam file stopwords.txt , digit dihapus dan kata-kata yang lebih pendek dari 3 huruf tidak dipertimbangkan.
Dalam preprocessing indeks terbalik dibangun dan TF-IDF dari setiap pasangan kata-doc dihitung dan disimpan dalam indeks terbalik. Grafik web terarah ( graph.py ) juga dibuat dan umpan ke implementasi peringkat halaman di page_rank.py . Semua file yang dibutuhkan nanti untuk menjawab kueri kemudian disimpan sebagai file biner.
Total waktu yang dibutuhkan untuk preprocessing dan Page_rank Convergence selama 10000 halaman adalah sekitar 236 detik, waktu berjalan peringkat halaman hanya sekitar 11 detik.
Script Main.py berisi titik akses ke mesin pencari. Ketika program dimulai, objek CustomTokenizer dibuat untuk tokenize kueri, objek TFIDFRANKER sebagai gantinya dipakai untuk memberi peringkat dokumen berdasarkan kueri.
Ketika dokumen diperingkat berdasarkan kueri pengguna, maksimum 100 dokumen dipertimbangkan, konstanta ini dapat berubah dalam main.py : max_results_to_consider, parameter lain yang dapat disesuaikan adalah jumlah hasil yang akan ditampilkan pada waktu result_per_page, jumlah halaman yang digunakan: n_page.
Antarmuka pengguna grafis dan diimplementasikan menggunakan paket Python: EasyGUI. GUI adalah modul yang dapat diperluas, customgui.py yang berisi API utama untuk fungsi dasar program.
Ketika program memulai pengguna ditanya pengaturan dasar, apakah dia ingin menggunakan peringkat halaman dan konteks umpan balik pseudo-relevansi atau tidak. Setelah itu menu utama muncul. Menu utama menunjukkan pengaturan saat ini dari mesin pencari dan beberapa tombol untuk tindakan utama yang dapat dilakukan. Pengaturan dapat diubah secara dinamis saat runtime dengan memilih tombol yang sesuai dari menu utama. Dua pilihan lainnya adalah: berhenti dari program dan menjalankan kueri. Jika pengguna menekan tombol untuk membuat kueri baru, jendela baru muncul, dan pengguna diminta untuk memasukkan kueri baru. Ketika dia mengklik oke, kueri diproses sebelumnya, dan dokumen-dokumen tersebut diberi peringkat dan 10 (variabel dalam program) dokumen ditampilkan bersama dengan informasi tentang kueri yang diproses dan mungkin token yang diperluas jika umpan balik pseudo-relevansi menyala. Pengguna sekarang dapat mengklik dua kali pada hasil untuk membuka halaman pada tab baru di browser default sistemnya atau dapat secara rekursif menekan "Tampilkan lebih banyak hasil" di akhir daftar untuk menunjukkan 10 hasil lainnya. Selain itu, jika umpan balik pseudo-relevance tidak aktif, pengguna juga diberikan kemungkinan untuk menjalankan kembali kueri yang sama dengan ekspansi.
Setelah menjalankan kueri dan memutuskan untuk membatalkan atau membuka hasilnya, pengguna diminta kembali ke menu utama di mana ia dapat mengubah pengaturan dan/atau menjalankan kueri baru atau yang sama dengan pengaturan yang berbeda untuk membandingkan hasil dengan yang diperoleh sebelumnya.
Tantangan utama yang saya alami selama pengembangan proyek ini adalah:
Awalnya sangat sulit untuk memilih komponen pintar seperti apa yang akan dirancang. Saya tidak memiliki pengalaman dalam jenis aplikasi ini dan berpikir tentang perbaikan tanpa memiliki demo untuk diuji sangat sulit.
Selama bagian implementasi, saya menghabiskan banyak waktu dalam belajar tentang perpustakaan Python dan konstruksi yang belum saya ketahui, seperti utas, cara menerapkan atau melakukan pengikisan web untuk mengeluarkan tautan dari halaman HTML. Hal lain yang harus saya pelajari dari awal adalah cara membuat GUI di Python.
Suatu hal yang menjengkelkan adalah fakta bahwa saya harus merangkak 100.000 halaman lebih dari sekali, karena saya menemukan di halaman yang beragam dan salah format. Pada akhirnya seluruh daftar format yang harus saya lakukan dengan blacklist memiliki ukuran 18 dan itu termasuk ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png", ".gif", ".pdf", ".gz,". ".Png". ".exe", ".js", ".css", ".ppt".
Suatu hal yang sangat menantang adalah penyetelan hiperparameter dan integrasi peringkat halaman untuk peringkat dokumen. Parameter " E " untuk memutuskan seberapa penting untuk diberikan kepada token kueri yang diperluas adalah yang paling sulit untuk disesuaikan karena Anda tidak dapat mengetahui kinerja rata -rata mesin pencari Anda jika Anda tidak memiliki data berlabel (dokumen yang relevan untuk setiap kueri). Juga, relevansi permintaan itu subyektif, Anda tidak pernah tahu apa yang ingin diambil seseorang, dan Anda hanya bisa menebak berdasarkan kueri. Saya memutuskan E harus paling banyak 0,5 dan pada akhirnya saya mengaturnya sekitar 0,1-0,2, Anda tidak ingin bias kueri menjadi banyak dengan memberikan banyak kepentingan pada kata-kata yang tidak diketik oleh pengguna.
Skema pembobotan yang saya gunakan adalah TF-IDF sederhana kata-kata dalam dokumen karena telah terbukti menjadi salah satu yang paling efektif dalam hal mesin pencari web dan memperhitungkan pentingnya kata-kata dalam setiap dokumen dengan cara yang benar. Saya bahkan tidak berpikir untuk mencoba tindakan lain hanya karena itu bukan tujuan dari proyek ini dan ini sepertinya berfungsi dengan baik.
Ukuran kesamaan yang digunakan untuk memberi peringkat dokumen adalah kesamaan kosinus . Saya menerapkan mulai dari kesamaan produk dalam dan beralih ke itu hanya akan menjadi masalah mengubah satu baris kode. Saya pikir kesamaan kosinus lebih baik untuk digunakan karena mempertimbangkan panjang dokumen dan panjang permintaan. Ini lebih kompleks, dan biasanya bekerja cukup baik dalam praktiknya dalam jenis aplikasi ini sehingga memilih ukuran kesamaan bukan masalah, saya hanya tahu bahwa kesamaan kosinus adalah yang tepat.
Saya melakukan evaluasi presisi pada 10 (hanya mempertimbangkan 10 hasil pertama diambil) untuk beberapa pertanyaan acak dan beragam yang saya buat. Inilah hasilnya:
Kueri: “Tesis Penasihat”, hasil pertama adalah https://grad.uic.edu/electronic-thesisdissertation-faqs dan saya pikir semua hasil terkait dengan tesis dan hal-hal yang berkorelasi, saya akan memberikan ketepatan: p = 1.0 untuk kueri ini.
Kueri: "Karier Fair", hasil pertama adalah https://ecc.uic.edu/career-fairs dan saya pikir semua hasilnya agak relevan dengan pameran karier, layanan karier, acara dan pekerjaan, saya akan memberikan presisi: p = 1.0 untuk pertanyaan ini.
Kueri: “Asisten Peneliti”, hasil pertama adalah http://grad.uic.edu/Assistantships dan saya pikir semua kecuali yang terakhir terkait dengan asisten, karena itu ra, ta atau ga, hanya karena domain UIC tidak memiliki halaman spesifik untuk RA, jadi saya akan memberikan presisi: P = 0,9 untuk query ini.
Kueri: “Magang dan Pekerjaan”, hasil pertama adalah https://careerservices.uic.edu/students/internships dan kali ini hanya 6 halaman web yang relevan, namun, yang belum terkait dengan karier dan pekerjaan. Saya akan memberikan presisi: p = 0,6 untuk kueri ini.
Permintaan: “Alamat East Pusat Mahasiswa”, hasil pertama adalah https://fimweb.fim.uic.edu/buildingsdata.aspx, permintaan ini lebih spesifik dan kompleks dan pada kenyataannya hanya dari 4 hasil kita sebenarnya dapat mengekstraksi alamat bangunan, semua hasil lainnya, bagaimanapun, berbicara tentang pusat siswa, yang masih belum buruk. Saya akan memberikan presisi: p = 0,4 untuk kueri ini.
Dengan presisi rata -rata 0,78 , dan fakta bahwa setiap kueri mengembalikan setidaknya satu hasil yang relevan, saya pikir hasilnya diskrit.
Cerdas pertama yang saya bereksperimen adalah peringkat halaman yang sederhana dan sederhana. Selama preprocessing halaman, tautan diekstraksi dan berdasarkan koneksi tautan, grafik dunia dibuat. Implementasi peringkat halaman sedemikian rupa sehingga menciptakan komponen yang sangat terhubung dengan seluruh grafik, yang berarti bahwa dari setiap node dimungkinkan untuk sampai ke simpul grafik lain dengan probabilitas non-nol. Dengan interpretasi ini tidak ada kemungkinan bahwa pejalan kaki acak akan terjebak di halaman.
Peringkat halaman agak sulit untuk diintegrasikan ke dalam penilaian dokumen untuk memberi peringkat. Pada awalnya, saya mencoba untuk hanya melakukan kombinasi linier dari kesamaan cosinus dan peringkat halaman dan melihat bagaimana kerjanya dan itu sangat buruk karena jika bobot peringkat halaman terlalu banyak daripada beranda dan halaman otoritatif lainnya akan selalu muncul dalam hasilnya. Sebaliknya jika berat lebih condong ke arah kemiripan cosinus maka peringkat halaman tidak akan berpengaruh sama sekali.
Upaya kedua menghasilkan hasil yang cukup bagus. Saya pada dasarnya hanya mengambil 100 hasil pertama hanya menggunakan dan membuang semua mereka yang lain dan menganggap mereka tidak relevan. Kemudian saya melakukan kombinasi linier dengan peringkat halaman. Kali ini berhasil karena itu hanya permutasi yang berbeda dari dokumen yang sudah relevan, dan misalnya beranda dan dokumen otoritatif lainnya sudah dibuang pada saat ini.
Saya pikir tujuan peringkat halaman dalam jenis aplikasi ini tercapai, saya dapat bias pencarian normal untuk mempertimbangkan lebih relevan halaman yang lebih otoritatif sehingga pengguna lebih cenderung menemukan sumber informasi yang baik dan andal di samping hasil yang sangat mirip dengan apa yang ia ketik dalam pertanyaannya.
Konteks umpan balik pseudo-relevance ( CPRF ) Saya datang dengan ide prinsip saya dan komponen pintar yang disesuaikan hampir sebulan dari implementasi aktual. Ketika saya sedang menerapkan, saya tidak yakin itu akan bekerja seperti yang diharapkan dan saya benar -benar takut bahwa saya melakukan semua itu tanpa hasil.
Ketika saya berpikir tentang komponen pintar seperti apa yang bisa dimiliki mesin pencari web, saya pikir akan lebih baik jika kita bisa menebak konteks permintaan pengguna dan memberikannya selain apa yang secara khusus dia minta, beberapa hasil yang sangat terkait dengan apa yang dia cari. Ekspansi kueri statis sederhana berdasarkan sinonim akan terlalu sederhana dan tidak akan dapat menangkap konten yang terkait tetapi memiliki semantik yang berbeda.
Namun, titik awal selalu harus menjadi kueri pengguna, karena tidak ada yang lain kecuali itu pada awalnya. Saya sangat menyukai gagasan tentang bagaimana umpan balik pseudo-revance dapat membiarkan Anda merumuskan kembali pertanyaan Anda dengan cara yang otonom. Tentu saja umpan balik relevansi yang eksplisit ketika pengguna ditanya kata -kata lain mana yang ingin ia sertakan dalam pertanyaannya mungkin akan lebih baik, tetapi pada saat yang sama bisa menjengkelkan baginya untuk harus menanggapi beberapa pertanyaan saat mencari. Umpan balik pseudo-relevansi tampaknya merupakan cara yang lebih tepat dan mudah untuk menjalankan di latar belakang beberapa permintaan yang lebih kompleks yang bahkan tidak disadari oleh pengguna.
Untuk mengekstrak beberapa kata yang dapat mengekspresikan konteks kueri yang dirumuskan, saya memutuskan untuk menggunakan beberapa informasi intrinsik yang dimiliki oleh dokumen yang awalnya diambil. Secara khusus, saya pikir kata-kata dengan TF-IDF tertinggi dalam sebuah dokumen dapat mewakili topik dokumen itu, dan apa yang dibedakan dari yang lain, karena TF-IDF tinggi ketika kata tersebut tidak terkandung dalam banyak dokumen tetapi berulang dalam dokumen itu.
Proses untuk mengekstrak kata -kata konteks adalah sebagai berikut: dari dokumen peringkat saya mengambil dokumen Number_Docs_Expansion, yang saya tetapkan ke 30 tetapi dapat diubah dalam pseudo_relevance_feedback.py. , untuk setiap dokumen saya mengambil token dengan TF-IDF tertinggi (konstanta number_top_tokens) dan untuk setiap token berbeda di dalamnya saya menjumlahkan semua TF-IDF dari kata ini dari setiap dokumen jika kata tersebut ada. Pada akhirnya saya memberi peringkat token dan kata -kata peringkat teratas adalah kata -kata umum dari setiap dokumen yang diambil yang mewakili konteks kueri. Saya kemudian mengembalikan kata -kata yang diperluas N (konstan number_expansion_tokens) set, yang dikurangi oleh token kueri aslinya agar tidak memiliki pengulangan dan memberikan terlalu banyak kepentingan pada kata -kata itu.
Token yang diperluas akan diberi bobot perbedaan, kurang dari kata -kata asli dalam kueri, E_CONST ini dapat diubah dalam skrip statistics.py .
Berdasarkan pertanyaan yang saya coba pikir komponen cerdas benar -benar memberikan beberapa peningkatan dalam beberapa kasus.
Hasil besar pertama yang bekerja selalu adalah kemampuan untuk memperluas set dokumen yang diambil, pada kenyataannya, jika hanya beberapa dokumen yang berisi kata apa pun dalam kueri, mesin pencari biasa hanya akan mengambil beberapa dokumen tersebut. Sebaliknya, dengan komponen pintar CPRF , hasil hasil akan jauh lebih besar dan mungkin selalu dapat mengarah pada set yang diambil yang ukurannya lebih dari 100 dokumen.
Hasil positif lain yang saya perhatikan dalam beberapa pertanyaan adalah bahwa ia benar -benar menemukan apa yang saya cari sebagai hasil pertama sedangkan mesin pencari sederhana bahkan tidak menemukannya dalam sepuluh hasil teratas. Contohnya dapat diamati dengan mencari "kursus ilmu komputer" , yang ingin saya temukan adalah daftar semua kursus utama yang ditawarkan oleh Departemen Ilmu Komputer di UIC. Ini adalah hasil pertama yang diambil oleh mesin ketika komponen cerdas aktif. Sebaliknya, tanpa mengaktifkannya, halaman itu tidak ada dalam hasil pertama.
Terakhir, saya mencoba mencari "pengambilan informasi" , mesin pencari tanpa CPRF sangat buruk, hasil pertama adalah halaman pencarian untuk departemen UIC, ini juga mungkin karena tidak ada halaman untuk pengambilan informasi dalam domain UIC atau tidak termasuk dalam domain. Namun, dengan komponen pintar menyala, banyak halaman web yang terkait dengan ini ditemukan, 2 dari kata -kata yang diperluas adalah "Cornelia caragea", profesor yang mengajar kursus ini, begitu banyak halaman yang memang terkait dengan publikasi dan pekerjaannya dalam pengambilan informasi, ini juga merupakan properti yang sangat baik dari mesin pencari. Dalam hal hasil yang sangat relevan tidak dapat ditemukan, masih dapat menemukan hasil terbaik tentang hal -hal terkait.
Seperti yang dijelaskan dalam 5.3 ketika saya melakukan perbandingan antara mesin pencari biasa dan menggunakan komponen pintar, saya pikir hasil yang diproduksi cukup bagus dan saya mendapatkan apa yang diharapkan ketika saya memikirkan hal ini. Hal -hal baik yang diringkas yang saya perhatikan dengan mengujinya adalah:
Kemampuan untuk menemukan lebih banyak hasil bahkan ketika kueri asli hanya menghasilkan banyak situs web.
Kemampuan menemukan apa yang sebenarnya saya cari sebagai hasil pertama, misalnya dalam pertanyaan "kursus ilmu komputer" , seperti yang saya jelaskan dalam paragraf 5.3.
Properti yang sangat bagus untuk mengambil konten diskrit bahkan di mana corpus tidak berisi halaman yang sangat relevan dengan kueri dan mungkin apa yang dicari pengguna, saya perhatikan ini untuk permintaan “pengambilan informasi” seperti yang dijelaskan dalam paragraf 5.3.
Salah satu cara yang menunjukkan kepada saya bahwa ini adalah menghasilkan hasil yang benar adalah fakta bahwa dalam 10 kata yang memperluas kata yang mewakili konteks, beberapa kata milik kueri pengguna hadir. Ini menunjukkan bagaimana metode ini secara efektif dapat menangkap topik dan tidak ada cara lain untuk menggambarkan kata -kata lain dalam set itu jika bukan sebagai kata yang termasuk dalam konteks yang sama dengan yang ada dalam kueri asli.
Berbicara tentang peringkat halaman sebagai gantinya. Saya pikir itu melakukan tugasnya, tetapi tidak mengubah peringkat terlalu banyak dalam cara saya menerapkan, itu hanya cara untuk bias hasil untuk lebih memilih halaman yang lebih otoritatif jika ada.
Yang pasti salah satu hal yang harus ditangani dari sini adalah penyetelan hiperparameter. Ini adalah hal yang paling sulit untuk dilakukan terutama karena kurangnya data berlabel. Saya tidak dapat mengetahui nilai parameter mana yang bekerja lebih baik jika saya tidak dapat mengevaluasi ketepatan kueri, dan untuk menyetelnya secara otomatis, harus ada banyak data yang sudah berlabel.
