Sabtu, 24 April 2010
di
21.51
|
tugas individu STBI part2
Resume
buku Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze teks 4 dan teks 6
Konstruksi Index
Dalam bab ini, kita melihat bagaimana membangun sebuah indeks terbalik. Kami akan memanggil proses konstruksi indeks atau pengindeksan dan proses atau mesin yang melaksanakan pengindeksan. Rancangan algoritma pengindeksan diatur oleh batasan hardware. Oleh karena itu kita akan memulai bab ini dengan tinjauan dasar-dasar perangkat keras komputer yang relevan untuk pengindeksan. Kami kemudian memperkenalkan semacam berbasis pengindeksan yang diblokir, sebuah mesin tunggal algoritma yang efisien yang dirancang untuk statis koleksi yang dapat dilihat sebagai yang lebih scalable. Untuk koleksi yang sangat besar seperti web, pengindeksan harus didistribusikan melalui kelompok komputer dengan ratusan atau ribuan mesin. Akhirnya, kita akan membahas beberapa komplikasi yang dapat timbul dalam pengindeksan. Seperti keamanan dan indeks untuk pengambilan peringkat. Dalam pencarian web, dokumen tidak pada sistem file lokal, tapi harus spider atau merangkak. Di pencarian perusahaan, sebagian besar dokumen yang terangkum dalam manajemen konten bervariasi sistem, aplikasi email dan database. Sementara sebagian besar aplikasi ini dapat diakses melalui http, API biasanya lebih efisien. Pembaca harus menyadari bahwa bangunan sub-sistem yang berupa teks mentah untuk proses pengindeksan dapat dengan sendirinya menjadi masalah yang menantang.
Dasar Hardware
Banyak keputusan ketika membangun sebuah sistem pencarian informasi yang didasarkan pada karakteristik dari sistem perangkat keras komputer. Karena itu kita memulai bab ini dengan tinjauan singkat perangkat keras komputer. Sebuah dasar daftar hardware yang akan kita butuhkan dalam pembahasan ini untuk memotivasi sistem IR desain berikut.
• Akses ke data dalam memori jauh lebih cepat daripada akses data pada disk. Ini mengambil beberapa clock cycle (mungkin 5 × 10-9 detik) untuk mengakses byte memori, tetapi lebih lama untuk transfer dari disk (sekitar 2 × 10-8 detik). Akibatnya, kita ingin menyimpan data sebanyak mungkin dalam memori, terutama data yang sering kita butuhkan untuk mengakses. Kita sebut teknik yang sering digunakan menyimpan data disk caching dalam cache memori utama.
• Ketika melakukan sebuah disk membaca atau menulis, butuh beberapa saat untuk disk head untuk pindah ke bagian disk tempat data berada. Kali ini disebut mencari waktu dan ini adalah tentang 5ms pada umumnya rata-rata untuk disk. Tidak ada data sedang ditransfer selama mencari. Dalam rangka untuk memaksimalkan transfer data bunga, potongan data yang akan dibaca harus disimpan pada disk. Sebagai contoh, menggunakan angka-angka pada Tabel 4.1 hal itu mungkin memakan waktu sedikitnya 0,2 detik untuk mentransfer 10 MB dari disk ke memori jika disimpan sebagai salah satu bongkahan, tetapi sampai 0.2 + 100 × (5 × 10-3) = 0,7 detik jika disimpan dalam 100 non-contiguous bongkahan karena kita perlu memindahkan disk kepala sampai dengan 100 kali.
• Sistem operasi umumnya membaca dan menulis seluruh blok. Dengan demikian, membaca
satu byte dari disk dapat mengambil waktu sebanyak membaca seluruh blok. Ukuran blok dari 8 KB, 16 KB, 32 KB dan 64 KB yang umum.
• Data transfer dari disk ke memory akan ditangani oleh systembus, bukan oleh prosesor. Ini berarti bahwa prosesor yang tersedia untuk memproses data saat disk I / O. Kita dapat memanfaatkan fakta ini untuk mempercepat transfer data dengan dikompresi menyimpan data pada disk. Dengan asumsi yang efisien dekompresi algoritma, total waktu membaca dan kemudia dikompresi data biasanya kurang daripada membaca data yang tidak dikompresi.
• Server yang digunakan dalam sistem IR biasanya memiliki beberapa GB memori utama, kadang-kadang puluhan GB. Ruang disk yang tersedia adalah beberapa kali lipat lebih besar.
Blocked sort-based indexing
Pertama-tama membuat perakitan koleksi semua docID istilah-pasangan. Kemudian menyortir pasangan dengan istilah sebagai kunci dominan dan docID sebagai kunci sekunder. Akhirnya, kami mengatur untuk setiap docIDs istilah ke daftar posting dan menghitung statistik seperti frekuensi term dan dokumen. Untuk koleksi yang kecil, semua ini dapat dilakukan di memori. Kami akan menjelaskan metode untuk koleksi besar yang memerlukan penggunaan sekunder penyimpanan. Untuk membuat pembangunan index lebih efisien, kami mewakili istilah termIDs, di mana masing-masing adalah unik termID nomor seri. Kita dapat membangun pemetaan dari istilah ke termIDs on the fly sementara kami memproses koleksi, dalam dua pendekatan lulus, kami menyusun kosakata pertama dan membangun indeks terbalik. Algoritma konstruksi indeks yang dijelaskan dalam bab ini melewati satu data. Jika ukuran file antara selama indeks konstruksi dalam faktor kecil memori yang tersedia, maka teknik kompresi dapat membantu; tetapi banyak koleksi file posting yang besar tidak bisa masuk ke dalam memori bahkan setelah kompresi. Dengan memori utama tidak mencukupi, kita perlu menggunakan algoritma sorting eksternal. Untuk dapat diterima kecepatan, persyaratan pusat algoritma semacam itu adalah bahwa hal itu meminimalkan jumlah random disk yang mencari selama sequential pemilahan disk dibaca jauh lebih cepat daripada mencari seperti yang kita jelaskan sebelumnya. Salah satu solusinya adalah blocked sort-berbasis algoritma pengindeksan atau BSBI pada Gambar 4.2. BSBI (i) segmen koleksi menjadi beberapa bagian dengan ukuran yang sama, (ii) memilah termID pasang docID setiap bagian dalam memori, (iii) toko intermediate diurutkan hasilnya pada disk dan (iv) gabungan semua hasil menengah ke dalam akhir indeks.
Algoritma memparsing dokumen ke termID-docID dan mengakumulasi pasangan
pasangan dalam memory sampai blok ukuran tetap penuh pada Gambar 4.2. Kami memilih ukuran blok untuk menyesuaikan dengan nyaman ke dalam memori untuk
izin yang cepat dalam-memori semacam itu. Blok ini kemudian dibalik dan ditulis ke disk.
Inversi melibatkan dua langkah. Pertama kita menyortir pasangan termID-inversi docID. Berikutnya kami kumpulkan semua termID-docID berpasangan dengan termID yang sama ke dalam daftar posting, dimana posting hanyalah sebuah docID. Hasilnya, indeks terbalik untuk blok baru saja kita baca, kemudian ditulis ke disk.
Single-pass di memori pengindeksan
Blocked sort berbasis skala pengindeksan memiliki sifat yang sangat baik. Untuk koleksi yang sangat besar, struktur data ini tidak muat ke dalam memori. Alternatif yang lebih scalable adalah
single-pass di memori atau SPIMI pengindeksan. SPIMI dapat mengindeks koleksi dari berbagai ukuran asalkan ada cukupruang disk yang tersedia. SPIMI-invert disebut berulang pada token sungai sampai seluruh koleksi telah diproses. Token diproses satu per satu. Ketika sebuah istilah terjadi untuk pertama kali, itu akan ditambahkan ke kamus, dan daftar posting baru diciptakan. Perbedaan antara BSBI dan SPIMI adalah bahwa SPIMI menambahkan posting langsung
ke daftar posting. Daripada pertama mengumpulkan semua pasangan termID-docID
kemudian menyortir mereka (seperti yang kita lakukan di BSBI), masing-masing daftar posting adalah dinamis dan akan segera tersedia untuk mengumpulkan posting. Ini memiliki dua keuntungan. Hal ini akan menghemat memori karena kita melacak istilah milik sebuah daftar posting, sehingga termIDs dari posting tidak perlu disimpan. Sebagai hasilnya, indeks proses pembangunan secara keseluruhan lebih efisien.
Distributed pengindeksan
Koleksi sering begitu besar sehingga kita tidak dapat melakukan konstruksi indeks yang efisien
pada satu mesin. Hal ini terutama berlaku dari World Wide Web dimana kita membutuhkan komputer yang besar untuk membangun apapun. Oleh karena itu mesin pencari web didistribusikan menggunakan algoritma pengindeksan untuk indeks konstruksi. Hasil dari proses pembangunan adalah indeks yang didistribusikan terbagi di beberapa mesin, baik menurut istilah atau sesuai dengan dokumen. Inti dari sebuah cluster adalah memecahkan masalah komputasi besar komoditas murah mesin atau node yang dibangun dari standar bagian (prosesor, memori, disk) sebagai lawan pada sebuah super komputer dengan perangkat keras khusus. Sementara ratusan atau ribuan dari mesin tersedia dalam kelompok-kelompok seperti itu, mesin bisa gagal setiap waktu. Satu persyaratan untuk mengindeks terdistribusi kuat karena itu yang kita
membagi pekerjaan ke dalam potongan-potongan yang kita dapat dengan mudah menetapkan dan - dalam kasus failure - menugaskan kembali.
Pengindeksan dynamic
Istilah-istilah baru perlu ditambahkan ke dalam kamus, dan daftar posting perlu diperbarui untuk istilah-istilah yang ada. Cara paling mudah untuk mencapai ini adalah dengan merekonstruksi secara berkala indeks dari nol. Ini adalah solusi yang baik jika sejumlah perubahan dari waktu ke waktu adalahkecil dan penundaan dalam membuat dokumen baru dicari dapat diterima, dan
jika cukup banyak sumber daya yang tersedia untuk membangun indeks baru sementara yang lama masih tersedia untuk query. Sebuah indeks dan largemain indeks tambahan kecil
yang menyimpan dokumen baru. Indeks auxiliary disimpan di dalam memori. Pencarian
dijalankan di kedua indeks dan hasil penggabungan. Penghapusan disimpan dalam sebuah penghapusan bit vektor. Kita dapat menyaring dokumen dihapus sebelum kembali
hasil pencarian. Dokumen diperbarui dengan menghapus dan memasukkan kembali dokumen tersebut.
.
Jenis indeks
Algoritma yang dibahas di sini semua bisa diterapkan untuk posisi indeks. Dalam indeks kita telah mempertimbangkan sejauh ini, daftar posting diperintahkan dengan terhadap docID. Hal ini menguntungkan untuk kompresi - docIDs bukannya lebih kecil kita dapat menekan kesenjangan antara ID, sehingga mengurangi kebutuhan ruang untuk indeks. Namun, struktur ini
untuk indeks tidak optimal ketika kita membangun peringkat peringkat Retrieval, dibandingkan dengan sistem pengambilan Boolean. Dalam peringkat pencarian, posting sering disusun berdasarkan berat badan atau dampak, dengan bobot tertinggi posting pertama terjadi. Dengan susunan ini, scanning postingan daftar selama pemrosesan query biasanya dapat dihentikan lebih awal ketika beban telah menjadi begitu kecil sehingga dokumen lebih lanjut dapat diperkirakan dari rendah kesamaan dengan query.
Skor, Istilah Bobot dan Model Ruang Vector
Sejauh ini kita telah berurusan dengan indeks yang mendukung Boolean queries. Dalam kasus koleksi dokumen besar, jumlah hasil dokumen yang sesuai dapat jauh melebihi jumlah pengguna manusia yang bisa menyaring. Oleh karena itu, penting untuk sebuah mesin pencari untuk menentukan peringkat-memesan pencocokan dokumen permintaan. Bab ini terdiri dari tiga ide pokok :
1. Kami memperkenalkan parametrik dan zona indeks, yang berfungsi
dua tujuan. Pertama, mereka memungkinkan kita untuk mengindeks dan mengambil dokumen oleh metadata seperti bahasa di mana sebuah dokumen yang tertulis. Kedua,
mereka memberi kita sarana untuk penilaian sederhana (dan dengan demikian peringkat) dokumen sebagai tanggapan atas permintaan.
2. Selanjutnya, kita mengembangkan gagasan bobot pentingnya istilah dalam dokumen, berdasarkan statistik terjadinya istilah.
3. Setelah itu kami menunjukkan bahwa dengan melihat setiap dokumen sebagai vektor seperti berat, kita dapat menghitung skor antara permintaan dan setiap dokumen.
Pandangan ini dikenal sebagai ruang vektor mencetak gol.
Parametric dan zona indeks
Sebagian besar dokumen memiliki struktur tambahan. Umumnya dokumen digital menyandi,
mesin dikenali dalam bentuk, metadata tertentu yang terkait MET dengan setiap dokumen.
Dengan metadata, kita berarti bentuk-bentuk khusus data tentang dokumen, seperti
sebagai penulis (s), judul dan tanggal publikasi. Metadata ini akan umumnya meliputi bidang-bidang seperti tanggal penciptaan dan format dokumen, baik penulis dan mungkin judul dokumen.
Pertimbangkan pertanyaan dari form "menemukan dokumen yang ditulis oleh WilliamShakespeare pada tahun 1601, yang berisi frase sayangnya Yorick miskin ". Pemrosesan query kemudian seperti biasa terdiri dari posting persimpangan, kecuali bahwa kita dapat menggabungkan posting dari standar terbalik serta indeks parametrik. Ada satu parametric indeks untuk masing-masing bidang; hal itu memungkinkan kita untuk memilih hanya
pencocokan dokumen tanggal yang ditentukan dalam pencarian.
Zona mirip dengan bidang, kecuali isi zona dapat berupa teks bebas. Sedangkan lapangan mungkin diperlukan waktu yang relatif kecil pada seperangkat nilai, zona dapat dianggap sebagai sewenang-wenang, jumlah teks terbatas. Misalnya, judul dan abstrak dokumen umumnya diperlakukan sebagai zona. Kita mungkin membangun sebuah indeks terbalik terpisah untuk setiap zona dari sebuah dokumen, untuk mendukung permintaan tersebut sebagai "menemukan dokumen dengan pedagang di judul dan william dalam daftar penulis dan ungkapan hujan lembut di dalam tubuh ". Hal ini memiliki efek membangun indeks. Sedangkan dalam kamus untuk indeks parametric berasal dari kosakata yang tetap (himpunan bahasa, atau set tanggal), yang kamus untuk indeks zona struktur harus kosa kata apa pun yang berasal dari
teks zona itu.
Berat zona scoring
Kita telah berfokus pada pengambilan dokumen berdasarkan Boolean query di ladang dan zona. Kita sekarang beralih ke aplikasi kedua zona dan ladang. Boolean query diberi q dan sebuah dokumen d zona tertimbang menetapkan skor ke pasangan (q, d) suatu nilai dalam interval [0, 1], dengan menghitung kombinasi linear zona nilai, di mana setiap zona dokumen menyumbangkan Boolean nilai. Lebih khusus lagi, pertimbangkan satu set dokumen masing-masing memiliki ℓ
zona. Biarkan g1,. . . , G ℓ ∈ [0, 1] sehingga ℓ å i = 1 gi = 1. Untuk 1 ≤ i ≤ ℓ, biarkan si menjadi
Nilai boolean yang menunjukkan pertandingan (atau ketiadaan daripadanya) antara q dan engan
zona. Misalnya, nilai Boolean dari zona bisa 1 jika semua permintaan istilah (s) yang terjadi di zona itu, dan nol sebaliknya; memang, itu bisa setiap Boolean fungsi yang memetakan kehadiran istilah permintaan dalam zona ke 0, 1. Kemudian, zona skor tertimbang didefinisikan sebagai
ZONESCORE (Q1, q2)
1 float nilai [N] = [0]
2 konstan g [ℓ]
3 p1 ← postingan lama (Q1)
4 p2 ← postingan lama (q2)
5 / / nilai [] adalah sebuah array dengan skor entri untuk setiap dokumen, diinisialisasi ke nol.
6 / / p1 dan p2 adalah diinisialisasi agar menunjuk ke awal masing-masing posting.
7 / / Asumsikan g [] adalah untuk melakukan masing-masing zona bobot.
8 sementara p1 6 = NIL dan p2 6 = NIL
9 lakukan jika docID (p1) = docID (p2)
10 maka skor [docID (p1)] ← WEIGHTEDZONE (p1, p2, g)
11 p1 ← berikutnya (p1)
12 p2 ← berikutnya (p2)
13 else if docID (p1) Belajar beban
Bagaimana kita menentukan bobot tertimbang gi untuk zona scoring? Bobot ini dapat ditentukan oleh seorang ahli (atau, pada prinsipnya, user); namun semakin, bobot ini adalah "belajar" dengan menggunakan contoh-contoh pelatihan yang telah dinilai editorial. Metodologi yang terakhir ini berada di bawah kelas umum pendekatan untuk penilaian dan peringkat dalam pencarian informasi, yang dikenal sebagai mesin-belajar relevansi. Kami menyediakan pengenalan singkat dengan topik ini di sini karena zona tertimbang mencetak menyajikan pengaturan yang bersih untuk memperkenalkan itu; sebuah lengkap tuntutan perkembangan pemahaman pembelajaran mesin.
Sejauh ini, skor telah bergantung pada apakah atau tidak istilah query hadir dalam
zona dalam dokumen. Kami mengambil langkah logis berikutnya: sebuah dokumen atau
zona yang menyebutkan istilah query lebih sering lebih berkaitan dengan permintaan
dan karenanya harus menerima skor yang lebih tinggi. Untuk memotivasi ini, kita mengingat
pengertian tentang permintaan teks bebas diperkenalkan sebelumnya: query di mana
persyaratan query diketik ke dalam bentuk yang unik antarmuka pencarian, tanpa
menghubungkan operator pencarian (seperti Boolean operator). Query ini gaya, yang sangat populer di Web, pandangan query hanya sebagai kumpulan kata-kata. Sebuah mekanisme penilaian yang masuk akal maka adalah untuk menghitung skor. Singkatnya, di atas istilah permintaan, skor pertandingan antara setiap query dan jangka dokumen. Menjelang akhir ini, kami tetapkan untuk setiap istilah dalam dokumen yang berat untuk istilah, yang tergantung pada jumlah kemunculan istilah dalam dokumen.
Dokumen Inverse Frekuensi
Istilah mentah frekuensi seperti di atas menderita masalah yang kritis: semua persyaratan yang
dianggap sama pentingnya ketika datang untuk menilai relevansi pada permintaan. Bahkan istilah tertentu memiliki sedikit atau tidak ada diskriminasi dalam menentukan kekuatan
relevansi.
Sebaliknya, adalah lebih umum digunakan untuk tujuan ini dokumen frekuensi quency DFT, didefinisikan sebagai jumlah dokumen dalam koleksi yang berisi istilah t. Hal ini karena dalam usaha untuk membedakan antara dokumen untuk tujuan penilaian lebih baik menggunakan tingkat dokumen statistik (seperti sebagai jumlah dokumen yang berisi istilah) daripada menggunakan koleksi-lebar statistik untuk istilah. Secara khusus, nilai cf baik mencoba dan asuransi yang kurang lebih sama, tetapi nilai-nilai df mereka berbeda secara signifikan.
Model ruang vektor untuk penilaian
Dalam Bagian ini kami mengembangkan pengertian tentang vektor dokumen yang menangkap kepentingan relatif dari istilah dalam dokumen. Representasi dari serangkaian dokumen sebagai vektor dalam ruang vektor yang umum dikenal sebagai space model vektor dan merupakan dasar informasi host operasi pengambilan dari scoring berkisar pada permintaan dokumen, dokumen klasifikasi dan dokumen clustering. Pertama-tama kita mengembangkan ide-ide dasar yang mendasari vector ruang mencetak; sebuah langkah penting dalam perkembangan ini adalah pandangan pertanyaan sebagai vektor dalam ruang vektor yang sama sebagai koleksi dokumen.
Titik Produk
Himpunan dokumen dalam koleksi kemudian dapat dipandang sebagai satu set vektor dalam sebuah ruang vektor, di mana terdapat satu sumbu untuk setiap istilah.
Bagaimana kita mengukur kesamaan antara dua dokumen dalam vector ruang? Upaya pertama mungkin mempertimbangkan besarnya perbedaan vector antara dua vektor dokumen. Ukuran ini menderita kekurangan: dua dokumen dengan isi yang sangat mirip dapat memiliki perbedaan yang signifikan vector hanya karena satu jauh lebih lama daripada yang lain. Jadi distribusi relative istilah mungkin identik dalam dua dokumen, tetapi istilah absolute frekuensi satu mungkin jauh lebih besar. Untuk mengimbangi efek dokumen panjang, cara standar
mengukur kesamaan antara dua dokumen (d1) dan d2 adalah untuk menghitung
kosinus kesamaan vektor mereka representasi ~ V (d1) dan ~ V kosinus kesamaan (d2) rumus (6.10)
Di mana pembilang mewakili perkalian titik dari vektor ~ V (d1) dan ~ V (d2), sedangkan penyebutnya adalah produk Euklidean lengths. Perkalian titik ~ x • Euclidean LENGTH ~ y dari dua vektor didefinisikan sebagai AM i = 1 Xiyi. Biarkan ~ V (d) menyatakan vektor dokumen untuk d, dengan M komponen ~ V 1 (d). . . ~ VM (d). The Euclidean panjang d didefinisikan sebagai q i = 1 ~ V 2 i (d). Efek dari penyebut Persamaan (6.10) dengan demikian untuk panjang-menormalkan. Normalisasi vektor ~ V ((d1)) dan ~ V (d2) ke unit vektor ~ v ((d1)) = ~ V ((d1)) / | ~ V ((d1)) |.
Komputasi nilai vector
Dalam pengaturan khas kami memiliki koleksi dokumen masing-masing diwakili oleh seorang
vektor, teks bebas query diwakili oleh vektor, dan bilangan bulat positif K. Kami mencari koleksi dokumen-dokumen K dengan skor tertinggi ruang vektor query yang diberikan. Kita sekarang memulai studi penentuan dokumen K dengan ruang vektor skor tertinggi untuk query tertentu. Biasanya, kita mencari ini K atas dokumen dalam diperintahkan oleh penurunan nilai; misalnya banyak pencarian mesin menggunakan K = 10 untuk mengambil dan peringkat-urutan halaman pertama sepuluh hasil terbaik. Di sini kami memberikan algoritma dasar perhitungan ini, kami mengembangkan perawatan lebih lengkap teknik dan pendekatan yang efisien.
COSINESCORE (q)
1 float Skor [N] = 0
2 Initialize Panjang [N]
3 untuk setiap query t jangka
4 lakukan menghitung wt, q dan mengambil daftar posting untuk t
5 untuk setiap pasangan (d, tft, d) dalam daftar posting
6 lakukan Skor [d] + = wft, d × wt, q
7 Baca array Length [d]
8 untuk masing-masing d
9 melakukan Skor [d] = Skor [d] / Length [d]
10 kembali ke K komponen Top Skor []
Gambar 6.14 ◮ algoritma dasar untuk menghitung skor ruang vektor.
Gambar 6.14 memberikan algoritma dasar untuk menghitung skor ruang vektor. Panjang array memegang panjang (faktor normalisasi) untuk masing-masing dari N dokumen, sedangkan memegang Skor array nilai untuk masing-masing dokumen. Ketika skor akhirnya dihitung pada Langkah 9, semua itu tetap dalam Langkah 10 adalah untuk memilih dari dokumen K dengan skor tertinggi.
Resume
buku Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze teks 4 dan teks 6
Konstruksi Index
Dalam bab ini, kita melihat bagaimana membangun sebuah indeks terbalik. Kami akan memanggil proses konstruksi indeks atau pengindeksan dan proses atau mesin yang melaksanakan pengindeksan. Rancangan algoritma pengindeksan diatur oleh batasan hardware. Oleh karena itu kita akan memulai bab ini dengan tinjauan dasar-dasar perangkat keras komputer yang relevan untuk pengindeksan. Kami kemudian memperkenalkan semacam berbasis pengindeksan yang diblokir, sebuah mesin tunggal algoritma yang efisien yang dirancang untuk statis koleksi yang dapat dilihat sebagai yang lebih scalable. Untuk koleksi yang sangat besar seperti web, pengindeksan harus didistribusikan melalui kelompok komputer dengan ratusan atau ribuan mesin. Akhirnya, kita akan membahas beberapa komplikasi yang dapat timbul dalam pengindeksan. Seperti keamanan dan indeks untuk pengambilan peringkat. Dalam pencarian web, dokumen tidak pada sistem file lokal, tapi harus spider atau merangkak. Di pencarian perusahaan, sebagian besar dokumen yang terangkum dalam manajemen konten bervariasi sistem, aplikasi email dan database. Sementara sebagian besar aplikasi ini dapat diakses melalui http, API biasanya lebih efisien. Pembaca harus menyadari bahwa bangunan sub-sistem yang berupa teks mentah untuk proses pengindeksan dapat dengan sendirinya menjadi masalah yang menantang.
Dasar Hardware
Banyak keputusan ketika membangun sebuah sistem pencarian informasi yang didasarkan pada karakteristik dari sistem perangkat keras komputer. Karena itu kita memulai bab ini dengan tinjauan singkat perangkat keras komputer. Sebuah dasar daftar hardware yang akan kita butuhkan dalam pembahasan ini untuk memotivasi sistem IR desain berikut.
• Akses ke data dalam memori jauh lebih cepat daripada akses data pada disk. Ini mengambil beberapa clock cycle (mungkin 5 × 10-9 detik) untuk mengakses byte memori, tetapi lebih lama untuk transfer dari disk (sekitar 2 × 10-8 detik). Akibatnya, kita ingin menyimpan data sebanyak mungkin dalam memori, terutama data yang sering kita butuhkan untuk mengakses. Kita sebut teknik yang sering digunakan menyimpan data disk caching dalam cache memori utama.
• Ketika melakukan sebuah disk membaca atau menulis, butuh beberapa saat untuk disk head untuk pindah ke bagian disk tempat data berada. Kali ini disebut mencari waktu dan ini adalah tentang 5ms pada umumnya rata-rata untuk disk. Tidak ada data sedang ditransfer selama mencari. Dalam rangka untuk memaksimalkan transfer data bunga, potongan data yang akan dibaca harus disimpan pada disk. Sebagai contoh, menggunakan angka-angka pada Tabel 4.1 hal itu mungkin memakan waktu sedikitnya 0,2 detik untuk mentransfer 10 MB dari disk ke memori jika disimpan sebagai salah satu bongkahan, tetapi sampai 0.2 + 100 × (5 × 10-3) = 0,7 detik jika disimpan dalam 100 non-contiguous bongkahan karena kita perlu memindahkan disk kepala sampai dengan 100 kali.
• Sistem operasi umumnya membaca dan menulis seluruh blok. Dengan demikian, membaca
satu byte dari disk dapat mengambil waktu sebanyak membaca seluruh blok. Ukuran blok dari 8 KB, 16 KB, 32 KB dan 64 KB yang umum.
• Data transfer dari disk ke memory akan ditangani oleh systembus, bukan oleh prosesor. Ini berarti bahwa prosesor yang tersedia untuk memproses data saat disk I / O. Kita dapat memanfaatkan fakta ini untuk mempercepat transfer data dengan dikompresi menyimpan data pada disk. Dengan asumsi yang efisien dekompresi algoritma, total waktu membaca dan kemudia dikompresi data biasanya kurang daripada membaca data yang tidak dikompresi.
• Server yang digunakan dalam sistem IR biasanya memiliki beberapa GB memori utama, kadang-kadang puluhan GB. Ruang disk yang tersedia adalah beberapa kali lipat lebih besar.
Blocked sort-based indexing
Pertama-tama membuat perakitan koleksi semua docID istilah-pasangan. Kemudian menyortir pasangan dengan istilah sebagai kunci dominan dan docID sebagai kunci sekunder. Akhirnya, kami mengatur untuk setiap docIDs istilah ke daftar posting dan menghitung statistik seperti frekuensi term dan dokumen. Untuk koleksi yang kecil, semua ini dapat dilakukan di memori. Kami akan menjelaskan metode untuk koleksi besar yang memerlukan penggunaan sekunder penyimpanan. Untuk membuat pembangunan index lebih efisien, kami mewakili istilah termIDs, di mana masing-masing adalah unik termID nomor seri. Kita dapat membangun pemetaan dari istilah ke termIDs on the fly sementara kami memproses koleksi, dalam dua pendekatan lulus, kami menyusun kosakata pertama dan membangun indeks terbalik. Algoritma konstruksi indeks yang dijelaskan dalam bab ini melewati satu data. Jika ukuran file antara selama indeks konstruksi dalam faktor kecil memori yang tersedia, maka teknik kompresi dapat membantu; tetapi banyak koleksi file posting yang besar tidak bisa masuk ke dalam memori bahkan setelah kompresi. Dengan memori utama tidak mencukupi, kita perlu menggunakan algoritma sorting eksternal. Untuk dapat diterima kecepatan, persyaratan pusat algoritma semacam itu adalah bahwa hal itu meminimalkan jumlah random disk yang mencari selama sequential pemilahan disk dibaca jauh lebih cepat daripada mencari seperti yang kita jelaskan sebelumnya. Salah satu solusinya adalah blocked sort-berbasis algoritma pengindeksan atau BSBI pada Gambar 4.2. BSBI (i) segmen koleksi menjadi beberapa bagian dengan ukuran yang sama, (ii) memilah termID pasang docID setiap bagian dalam memori, (iii) toko intermediate diurutkan hasilnya pada disk dan (iv) gabungan semua hasil menengah ke dalam akhir indeks.
Algoritma memparsing dokumen ke termID-docID dan mengakumulasi pasangan
pasangan dalam memory sampai blok ukuran tetap penuh pada Gambar 4.2. Kami memilih ukuran blok untuk menyesuaikan dengan nyaman ke dalam memori untuk
izin yang cepat dalam-memori semacam itu. Blok ini kemudian dibalik dan ditulis ke disk.
Inversi melibatkan dua langkah. Pertama kita menyortir pasangan termID-inversi docID. Berikutnya kami kumpulkan semua termID-docID berpasangan dengan termID yang sama ke dalam daftar posting, dimana posting hanyalah sebuah docID. Hasilnya, indeks terbalik untuk blok baru saja kita baca, kemudian ditulis ke disk.
Single-pass di memori pengindeksan
Blocked sort berbasis skala pengindeksan memiliki sifat yang sangat baik. Untuk koleksi yang sangat besar, struktur data ini tidak muat ke dalam memori. Alternatif yang lebih scalable adalah
single-pass di memori atau SPIMI pengindeksan. SPIMI dapat mengindeks koleksi dari berbagai ukuran asalkan ada cukupruang disk yang tersedia. SPIMI-invert disebut berulang pada token sungai sampai seluruh koleksi telah diproses. Token diproses satu per satu. Ketika sebuah istilah terjadi untuk pertama kali, itu akan ditambahkan ke kamus, dan daftar posting baru diciptakan. Perbedaan antara BSBI dan SPIMI adalah bahwa SPIMI menambahkan posting langsung
ke daftar posting. Daripada pertama mengumpulkan semua pasangan termID-docID
kemudian menyortir mereka (seperti yang kita lakukan di BSBI), masing-masing daftar posting adalah dinamis dan akan segera tersedia untuk mengumpulkan posting. Ini memiliki dua keuntungan. Hal ini akan menghemat memori karena kita melacak istilah milik sebuah daftar posting, sehingga termIDs dari posting tidak perlu disimpan. Sebagai hasilnya, indeks proses pembangunan secara keseluruhan lebih efisien.
Distributed pengindeksan
Koleksi sering begitu besar sehingga kita tidak dapat melakukan konstruksi indeks yang efisien
pada satu mesin. Hal ini terutama berlaku dari World Wide Web dimana kita membutuhkan komputer yang besar untuk membangun apapun. Oleh karena itu mesin pencari web didistribusikan menggunakan algoritma pengindeksan untuk indeks konstruksi. Hasil dari proses pembangunan adalah indeks yang didistribusikan terbagi di beberapa mesin, baik menurut istilah atau sesuai dengan dokumen. Inti dari sebuah cluster adalah memecahkan masalah komputasi besar komoditas murah mesin atau node yang dibangun dari standar bagian (prosesor, memori, disk) sebagai lawan pada sebuah super komputer dengan perangkat keras khusus. Sementara ratusan atau ribuan dari mesin tersedia dalam kelompok-kelompok seperti itu, mesin bisa gagal setiap waktu. Satu persyaratan untuk mengindeks terdistribusi kuat karena itu yang kita
membagi pekerjaan ke dalam potongan-potongan yang kita dapat dengan mudah menetapkan dan - dalam kasus failure - menugaskan kembali.
Pengindeksan dynamic
Istilah-istilah baru perlu ditambahkan ke dalam kamus, dan daftar posting perlu diperbarui untuk istilah-istilah yang ada. Cara paling mudah untuk mencapai ini adalah dengan merekonstruksi secara berkala indeks dari nol. Ini adalah solusi yang baik jika sejumlah perubahan dari waktu ke waktu adalahkecil dan penundaan dalam membuat dokumen baru dicari dapat diterima, dan
jika cukup banyak sumber daya yang tersedia untuk membangun indeks baru sementara yang lama masih tersedia untuk query. Sebuah indeks dan largemain indeks tambahan kecil
yang menyimpan dokumen baru. Indeks auxiliary disimpan di dalam memori. Pencarian
dijalankan di kedua indeks dan hasil penggabungan. Penghapusan disimpan dalam sebuah penghapusan bit vektor. Kita dapat menyaring dokumen dihapus sebelum kembali
hasil pencarian. Dokumen diperbarui dengan menghapus dan memasukkan kembali dokumen tersebut.
.
Jenis indeks
Algoritma yang dibahas di sini semua bisa diterapkan untuk posisi indeks. Dalam indeks kita telah mempertimbangkan sejauh ini, daftar posting diperintahkan dengan terhadap docID. Hal ini menguntungkan untuk kompresi - docIDs bukannya lebih kecil kita dapat menekan kesenjangan antara ID, sehingga mengurangi kebutuhan ruang untuk indeks. Namun, struktur ini
untuk indeks tidak optimal ketika kita membangun peringkat peringkat Retrieval, dibandingkan dengan sistem pengambilan Boolean. Dalam peringkat pencarian, posting sering disusun berdasarkan berat badan atau dampak, dengan bobot tertinggi posting pertama terjadi. Dengan susunan ini, scanning postingan daftar selama pemrosesan query biasanya dapat dihentikan lebih awal ketika beban telah menjadi begitu kecil sehingga dokumen lebih lanjut dapat diperkirakan dari rendah kesamaan dengan query.
Skor, Istilah Bobot dan Model Ruang Vector
Sejauh ini kita telah berurusan dengan indeks yang mendukung Boolean queries. Dalam kasus koleksi dokumen besar, jumlah hasil dokumen yang sesuai dapat jauh melebihi jumlah pengguna manusia yang bisa menyaring. Oleh karena itu, penting untuk sebuah mesin pencari untuk menentukan peringkat-memesan pencocokan dokumen permintaan. Bab ini terdiri dari tiga ide pokok :
1. Kami memperkenalkan parametrik dan zona indeks, yang berfungsi
dua tujuan. Pertama, mereka memungkinkan kita untuk mengindeks dan mengambil dokumen oleh metadata seperti bahasa di mana sebuah dokumen yang tertulis. Kedua,
mereka memberi kita sarana untuk penilaian sederhana (dan dengan demikian peringkat) dokumen sebagai tanggapan atas permintaan.
2. Selanjutnya, kita mengembangkan gagasan bobot pentingnya istilah dalam dokumen, berdasarkan statistik terjadinya istilah.
3. Setelah itu kami menunjukkan bahwa dengan melihat setiap dokumen sebagai vektor seperti berat, kita dapat menghitung skor antara permintaan dan setiap dokumen.
Pandangan ini dikenal sebagai ruang vektor mencetak gol.
Parametric dan zona indeks
Sebagian besar dokumen memiliki struktur tambahan. Umumnya dokumen digital menyandi,
mesin dikenali dalam bentuk, metadata tertentu yang terkait MET dengan setiap dokumen.
Dengan metadata, kita berarti bentuk-bentuk khusus data tentang dokumen, seperti
sebagai penulis (s), judul dan tanggal publikasi. Metadata ini akan umumnya meliputi bidang-bidang seperti tanggal penciptaan dan format dokumen, baik penulis dan mungkin judul dokumen.
Pertimbangkan pertanyaan dari form "menemukan dokumen yang ditulis oleh WilliamShakespeare pada tahun 1601, yang berisi frase sayangnya Yorick miskin ". Pemrosesan query kemudian seperti biasa terdiri dari posting persimpangan, kecuali bahwa kita dapat menggabungkan posting dari standar terbalik serta indeks parametrik. Ada satu parametric indeks untuk masing-masing bidang; hal itu memungkinkan kita untuk memilih hanya
pencocokan dokumen tanggal yang ditentukan dalam pencarian.
Zona mirip dengan bidang, kecuali isi zona dapat berupa teks bebas. Sedangkan lapangan mungkin diperlukan waktu yang relatif kecil pada seperangkat nilai, zona dapat dianggap sebagai sewenang-wenang, jumlah teks terbatas. Misalnya, judul dan abstrak dokumen umumnya diperlakukan sebagai zona. Kita mungkin membangun sebuah indeks terbalik terpisah untuk setiap zona dari sebuah dokumen, untuk mendukung permintaan tersebut sebagai "menemukan dokumen dengan pedagang di judul dan william dalam daftar penulis dan ungkapan hujan lembut di dalam tubuh ". Hal ini memiliki efek membangun indeks. Sedangkan dalam kamus untuk indeks parametric berasal dari kosakata yang tetap (himpunan bahasa, atau set tanggal), yang kamus untuk indeks zona struktur harus kosa kata apa pun yang berasal dari
teks zona itu.
Berat zona scoring
Kita telah berfokus pada pengambilan dokumen berdasarkan Boolean query di ladang dan zona. Kita sekarang beralih ke aplikasi kedua zona dan ladang. Boolean query diberi q dan sebuah dokumen d zona tertimbang menetapkan skor ke pasangan (q, d) suatu nilai dalam interval [0, 1], dengan menghitung kombinasi linear zona nilai, di mana setiap zona dokumen menyumbangkan Boolean nilai. Lebih khusus lagi, pertimbangkan satu set dokumen masing-masing memiliki ℓ
zona. Biarkan g1,. . . , G ℓ ∈ [0, 1] sehingga ℓ å i = 1 gi = 1. Untuk 1 ≤ i ≤ ℓ, biarkan si menjadi
Nilai boolean yang menunjukkan pertandingan (atau ketiadaan daripadanya) antara q dan engan
zona. Misalnya, nilai Boolean dari zona bisa 1 jika semua permintaan istilah (s) yang terjadi di zona itu, dan nol sebaliknya; memang, itu bisa setiap Boolean fungsi yang memetakan kehadiran istilah permintaan dalam zona ke 0, 1. Kemudian, zona skor tertimbang didefinisikan sebagai
ZONESCORE (Q1, q2)
1 float nilai [N] = [0]
2 konstan g [ℓ]
3 p1 ← postingan lama (Q1)
4 p2 ← postingan lama (q2)
5 / / nilai [] adalah sebuah array dengan skor entri untuk setiap dokumen, diinisialisasi ke nol.
6 / / p1 dan p2 adalah diinisialisasi agar menunjuk ke awal masing-masing posting.
7 / / Asumsikan g [] adalah untuk melakukan masing-masing zona bobot.
8 sementara p1 6 = NIL dan p2 6 = NIL
9 lakukan jika docID (p1) = docID (p2)
10 maka skor [docID (p1)] ← WEIGHTEDZONE (p1, p2, g)
11 p1 ← berikutnya (p1)
12 p2 ← berikutnya (p2)
13 else if docID (p1) Belajar beban
Bagaimana kita menentukan bobot tertimbang gi untuk zona scoring? Bobot ini dapat ditentukan oleh seorang ahli (atau, pada prinsipnya, user); namun semakin, bobot ini adalah "belajar" dengan menggunakan contoh-contoh pelatihan yang telah dinilai editorial. Metodologi yang terakhir ini berada di bawah kelas umum pendekatan untuk penilaian dan peringkat dalam pencarian informasi, yang dikenal sebagai mesin-belajar relevansi. Kami menyediakan pengenalan singkat dengan topik ini di sini karena zona tertimbang mencetak menyajikan pengaturan yang bersih untuk memperkenalkan itu; sebuah lengkap tuntutan perkembangan pemahaman pembelajaran mesin.
Sejauh ini, skor telah bergantung pada apakah atau tidak istilah query hadir dalam
zona dalam dokumen. Kami mengambil langkah logis berikutnya: sebuah dokumen atau
zona yang menyebutkan istilah query lebih sering lebih berkaitan dengan permintaan
dan karenanya harus menerima skor yang lebih tinggi. Untuk memotivasi ini, kita mengingat
pengertian tentang permintaan teks bebas diperkenalkan sebelumnya: query di mana
persyaratan query diketik ke dalam bentuk yang unik antarmuka pencarian, tanpa
menghubungkan operator pencarian (seperti Boolean operator). Query ini gaya, yang sangat populer di Web, pandangan query hanya sebagai kumpulan kata-kata. Sebuah mekanisme penilaian yang masuk akal maka adalah untuk menghitung skor. Singkatnya, di atas istilah permintaan, skor pertandingan antara setiap query dan jangka dokumen. Menjelang akhir ini, kami tetapkan untuk setiap istilah dalam dokumen yang berat untuk istilah, yang tergantung pada jumlah kemunculan istilah dalam dokumen.
Dokumen Inverse Frekuensi
Istilah mentah frekuensi seperti di atas menderita masalah yang kritis: semua persyaratan yang
dianggap sama pentingnya ketika datang untuk menilai relevansi pada permintaan. Bahkan istilah tertentu memiliki sedikit atau tidak ada diskriminasi dalam menentukan kekuatan
relevansi.
Sebaliknya, adalah lebih umum digunakan untuk tujuan ini dokumen frekuensi quency DFT, didefinisikan sebagai jumlah dokumen dalam koleksi yang berisi istilah t. Hal ini karena dalam usaha untuk membedakan antara dokumen untuk tujuan penilaian lebih baik menggunakan tingkat dokumen statistik (seperti sebagai jumlah dokumen yang berisi istilah) daripada menggunakan koleksi-lebar statistik untuk istilah. Secara khusus, nilai cf baik mencoba dan asuransi yang kurang lebih sama, tetapi nilai-nilai df mereka berbeda secara signifikan.
Model ruang vektor untuk penilaian
Dalam Bagian ini kami mengembangkan pengertian tentang vektor dokumen yang menangkap kepentingan relatif dari istilah dalam dokumen. Representasi dari serangkaian dokumen sebagai vektor dalam ruang vektor yang umum dikenal sebagai space model vektor dan merupakan dasar informasi host operasi pengambilan dari scoring berkisar pada permintaan dokumen, dokumen klasifikasi dan dokumen clustering. Pertama-tama kita mengembangkan ide-ide dasar yang mendasari vector ruang mencetak; sebuah langkah penting dalam perkembangan ini adalah pandangan pertanyaan sebagai vektor dalam ruang vektor yang sama sebagai koleksi dokumen.
Titik Produk
Himpunan dokumen dalam koleksi kemudian dapat dipandang sebagai satu set vektor dalam sebuah ruang vektor, di mana terdapat satu sumbu untuk setiap istilah.
Bagaimana kita mengukur kesamaan antara dua dokumen dalam vector ruang? Upaya pertama mungkin mempertimbangkan besarnya perbedaan vector antara dua vektor dokumen. Ukuran ini menderita kekurangan: dua dokumen dengan isi yang sangat mirip dapat memiliki perbedaan yang signifikan vector hanya karena satu jauh lebih lama daripada yang lain. Jadi distribusi relative istilah mungkin identik dalam dua dokumen, tetapi istilah absolute frekuensi satu mungkin jauh lebih besar. Untuk mengimbangi efek dokumen panjang, cara standar
mengukur kesamaan antara dua dokumen (d1) dan d2 adalah untuk menghitung
kosinus kesamaan vektor mereka representasi ~ V (d1) dan ~ V kosinus kesamaan (d2) rumus (6.10)
Di mana pembilang mewakili perkalian titik dari vektor ~ V (d1) dan ~ V (d2), sedangkan penyebutnya adalah produk Euklidean lengths. Perkalian titik ~ x • Euclidean LENGTH ~ y dari dua vektor didefinisikan sebagai AM i = 1 Xiyi. Biarkan ~ V (d) menyatakan vektor dokumen untuk d, dengan M komponen ~ V 1 (d). . . ~ VM (d). The Euclidean panjang d didefinisikan sebagai q i = 1 ~ V 2 i (d). Efek dari penyebut Persamaan (6.10) dengan demikian untuk panjang-menormalkan. Normalisasi vektor ~ V ((d1)) dan ~ V (d2) ke unit vektor ~ v ((d1)) = ~ V ((d1)) / | ~ V ((d1)) |.
Komputasi nilai vector
Dalam pengaturan khas kami memiliki koleksi dokumen masing-masing diwakili oleh seorang
vektor, teks bebas query diwakili oleh vektor, dan bilangan bulat positif K. Kami mencari koleksi dokumen-dokumen K dengan skor tertinggi ruang vektor query yang diberikan. Kita sekarang memulai studi penentuan dokumen K dengan ruang vektor skor tertinggi untuk query tertentu. Biasanya, kita mencari ini K atas dokumen dalam diperintahkan oleh penurunan nilai; misalnya banyak pencarian mesin menggunakan K = 10 untuk mengambil dan peringkat-urutan halaman pertama sepuluh hasil terbaik. Di sini kami memberikan algoritma dasar perhitungan ini, kami mengembangkan perawatan lebih lengkap teknik dan pendekatan yang efisien.
COSINESCORE (q)
1 float Skor [N] = 0
2 Initialize Panjang [N]
3 untuk setiap query t jangka
4 lakukan menghitung wt, q dan mengambil daftar posting untuk t
5 untuk setiap pasangan (d, tft, d) dalam daftar posting
6 lakukan Skor [d] + = wft, d × wt, q
7 Baca array Length [d]
8 untuk masing-masing d
9 melakukan Skor [d] = Skor [d] / Length [d]
10 kembali ke K komponen Top Skor []
Gambar 6.14 ◮ algoritma dasar untuk menghitung skor ruang vektor.
Gambar 6.14 memberikan algoritma dasar untuk menghitung skor ruang vektor. Panjang array memegang panjang (faktor normalisasi) untuk masing-masing dari N dokumen, sedangkan memegang Skor array nilai untuk masing-masing dokumen. Ketika skor akhirnya dihitung pada Langkah 9, semua itu tetap dalam Langkah 10 adalah untuk memilih dari dokumen K dengan skor tertinggi.
Diposting oleh
Zaoldyek Hunter Modunk
Label:
sistem temu balik informasi
0 komentar:
Posting Komentar