第 1 页
Information Retrieval and Map-Reduce Implementations Adopted from Jimmy Lin’s slides, which is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States
第 2 页
Roadmap Introduction to information retrieval Basics of indexing and retrieval Inverted indexing in MapReduce Retrieval at scale
第 3 页
First, nomenclature… Information retrieval (IR) ⚫ Focus on textual information (= text/document retrieval) ⚫ Other possibilities include image, video, music, … What do we search? ⚫ Generically, “collections” ⚫ Less-frequently used, “corpora” What do we find? ⚫ Generically, “documents” ⚫ Even though we may be referring to web pages, PDFs, PowerPoint slides, paragraphs, etc.
第 4 页
Information Retrieval Cycle Source Selection Resource Query Formulation Query Search Results Selection Documents System discovery Vocabulary discovery Concept discovery Document discovery Examination Information source reselection Delivery
第 5 页
The Central Problem in Search Author Searcher Concepts Concepts Query Terms Document Terms “tragic love story” “fateful star-crossed romance” Do these represent the same concepts?
第 6 页
Abstract IR Architecture Query Documents online offline Representation Representation Function Function Query Representation Document Representation Comparison Index Function Hits
第 7 页
How do we represent text? Remember: computers don’t “understand” anything! “Bag of words” ⚫ Treat all the words in a document as index terms ⚫ Assign a “weight” to each term based on “importance” (or, in simplest case, presence/absence of word) ⚫ Disregard order, structure, meaning, etc. of the words ⚫ Simple, yet effective! Assumptions ⚫ Term occurrence is independent ⚫ Document relevance is independent ⚫ “Words” are well-defined
第 8 页
What’s a word? 天主教教宗若望保祿二世因感冒再度住進醫院。 這是他今年第二度因同樣的病因住院。 الناطق باسم - وقال مارك ريجيف إن شارون قبل - الخارجية اإلسرائيلية الدعوة وسيقوم للمرة األولى بزيارة تونس، التي كانت لفترة طويلة المقر 1982 الرسمي لمنظمة التحرير الفلسطينية بعد خروجها من لبنان عام. Выступая в Мещанском суде Москвы экс-глава ЮКОСа заявил не совершал ничего противозаконного, в чем обвиняет его генпрокуратура России. भारत सरकार ने आर्थिक सर्वेक्ष ण में वर्वत्तीय र्वर्ि 2005-06 में सात फ़ीसदी वर्वकास दर हाससल करने का आकलन ककया है और कर सुधार पर ज़ो र ददया है 日米連合で台頭中国に対処…アーミテージ前副長官提言 조재영 기자= 서울시는 25일 이명박 시장이 `행정중심복합도시'' 건설안 에 대해 `군대라도 동원해 막고싶은 심정''이라고 말했다는 일부 언론의 보도를 부인했다.
第 9 页
Sample Document McDonald's slims down spuds “Bag of Words” Fast-food chain to reduce certain types of fat in its french fries with new cooking oil. NEW YORK (CNN/Money) - McDonald's Corp. is 14 × McDonalds cutting the amount of "bad" fat in its french fries nearly in half, the fast-food chain said Tuesday as 12 × fat it moves to make all its fried menu items healthier. But does that mean the popular shoestring fries 11 × fries won't taste the same? The company says no. "It's a win-win for our customers because they are 8 × new getting the same great french-fry taste along with an even healthier nutrition profile," said Mike Roberts, president of McDonald's USA. 7 × french But others are not so sure. McDonald's will not specifically discuss the kind of oil it plans to use, 6 × company, said, nutrition but at least one nutrition expert says playing with the formula could mean a different taste. Shares of Oak Brook, Ill.-based McDonald's 5 × food, oil, percent, (MCD: down $0.54 to $23.22, Research, reduce, taste, Tuesday Estimates) were lower Tuesday afternoon. It was unclear Tuesday whether competitors Burger King and Wendy's International (WEN: down … $0.80 to $34.91, Research, Estimates) would follow suit. Neither company could immediately be reached for comment. …
第 10 页
Information retrieval models An IR model governs how a document and a query are represented and how the relevance of a document to a user query is defined. Main models: ⚫ Boolean model ⚫ Vector space model ⚫ Statistical language model ⚫ etc 10
第 11 页
Boolean model Each document or query is treated as a “bag” of words or terms. Word sequence is not considered. Given a collection of documents D, let V = {t1, t2, ..., t|V|} be the set of distinctive words/terms in the collection. V is called the vocabulary. A weight wij > 0 is associated with each term ti of a document dj ∈ D. For a term that does not appear in document dj, wij = 0. dj = (w1j, w2j, ..., w|V|j), 11
第 12 页
Boolean model (contd) Query terms are combined logically using the Boolean operators AND, OR, and NOT. ⚫ E.g., ((data AND mining) AND (NOT text)) Retrieval ⚫ Given a Boolean query, the system retrieves every document that makes the query logically true. ⚫ Called exact match. The retrieval results are usually quite poor because term frequency is not considered. 12
第 13 页
Sec. 1.3 Boolean queries: Exact match • The Boolean retrieval model is being able to ask a query that is a Boolean expression: – Boolean Queries are queries using AND, OR and NOT to join query terms • Views each document as a set of words • Is precise: document matches condition or not. – Perhaps the simplest model to build an IR system on • Primary commercial retrieval tool for 3 decades. • Many search systems you still use are Boolean: – Email, library catalog, Mac OS X Spotlight 13
第 14 页
Strengths and Weaknesses Strengths ⚫ Precise, if you know the right strategies ⚫ Precise, if you have an idea of what you’re looking for ⚫ Implementations are fast and efficient Weaknesses ⚫ Users must learn Boolean logic ⚫ Boolean logic insufficient to capture the richness of language ⚫ No control over size of result set: either too many hits or none ⚫ When do you stop reading? All documents in the result set are considered “equally good” ⚫ What about partial matches? Documents that “don’t quite match” the query may be useful also
第 15 页
Vector Space Model t3 d2 d3 d1 θ φ t1 d5 t2 d4 Assumption: Documents that are “close together” in vector space “talk about” the same things Therefore, retrieve documents based on how close the document is to the query (i.e., similarity ~ “closeness”)
第 16 页
Similarity Metric Use “angle” between the vectors: d d cos() = j k d d j k d d n w w sim(d ,d ) = j k = i=1 i, j i,k j k d d n n w2 w2 j k i, j i,k i=1 i=1 Or, more generally, inner products: sim(d ,d ) = d d = n w w j k j k i=1 i, j i,k
第 17 页
Vector space model Documents are also treated as a “bag” of words or terms. Each document is represented as a vector. However, the term weights are no longer 0 or 1. Each term weight is computed based on some variations of TF or TF-IDF scheme. 17
第 18 页
Term Weighting Term weights consist of two components ⚫ Local: how important is the term in this document? ⚫ Global: how important is the term in the collection? Here’s the intuition: ⚫ Terms that appear often in a document should get high weights ⚫ Terms that appear in many documents should get low weights How do we capture this mathematically? ⚫ Term frequency (local) ⚫ Inverse document frequency (global)
第 19 页
TF.IDF Term Weighting N w = tf log i, j i, j n i w weight assigned to term i in document j i, j tf number of occurrence of term i in document j i, j N number of documents in entire collection n number of documents with term i i
第 20 页
Retrieval in vector space model Query q is represented in the same way or slightly differently. Relevance of di to q: Compare the similarity of query q and document di. Cosine similarity (the cosine of the angle between the two vectors) Cosine is also commonly used in text clustering 20
评论 (0)
暂无评论。快来抢沙发吧！