IFN647 Text, Web and Media Analytics
Assignment 1 Specification
Question 1. Parsing of Documents & Queries
The motivation for Question 1 is to design your own document and query parsers. So please don't use python packages that we didn't use in the workshop.
Task 1.1: Define a document parsing function parse_rcv1v2(stop_words, inputpath) to parse a data collection (e.g., RCV1v2 dataset), where parameterstop_words is a list of common English words (you may use the file 'common-english-words.txt' to find all stop words), and parameter inputpath is the folder that stores a set of XML files.
The following are the major steps in the document parsing function:
Step 1) The function reads XML files from inputpath (e.g., RCV1v2). For each file, it finds the docID (document ID) and index terms, and then represents it in a Rcv1Doc Object.
You need to define a Rcv1Doc class by using Bag-of-Words to represent a document:
. Rcv1Doc needs a docID variable (attribute) which is simply assigned by the value of ‘itemid’ in <newsitem …>.
. In this task, Rcv1Doc can be initialized with three attributes: docID attribute, an empty dictionary (the attribute name is terms) of key-value pair of (String term: int frequency); and doc_len (the document length) attribute.
. You may define your own methods, e.g., getDocId() to get the document ID, get_term_list() to get a sorted list of all terms occurring in the document, etc.
Step 2) It then builds up a collection of Rcv1Doc objects for the given dataset, this collection can be a dictionary structure (as we used in the workshop), a linked list, or a class Rcv1Coll for storing a collection of Rcv1Doc objects. Please note the rest descriptions are based on the dictionary structure with docID as key andRcv1Doc object as value.
Step 3) At last, it returns the collection of Rcv1Doc objects.
You also need to follow the following specification to define this parsing function:
Please use the basic text pre-processing steps, such as tokenizing, stopping words removal and stemming of terms.
Tokenizing –
. You are required to provide definitions of words and terms and describe them as comments in your Python solution
. You need to tokenize at least the ‘<text>…</text>’ part of document, exclude all tags, and discard punctuations and/or numbers based on your definition of terms.
. Define method add_term() for class Rcv1Doc to add new term or increase term frequency when the term occur again.
Stopping words removal and stemming of terms –
. Use the given stopping words list (“common-english-words.txt”) to ignore/remove all stopping words. Open and read the given file of stop-words and store them into a list stopwordList. When adding a term, please check whether the term exists in the stopwordList, and ignore it if it is in the stopwordList.
. Please use porter2 stemming algorithm to updateRcv1Doc’s terms.
Task 1.2: Define a query parsing function parse_query(query0, stop_words), where we assume the original query is a simple sentence or a title in a String format (query0), and stop_words is a list of stop words that you can get from 'common-english-words.txt'.
For example, let query0 =
'CANADA: Sherritt to buy Dynatec, spin off unit, canada.'
the function will return a dictionary:
{'canada': 2, 'sherritt': 1, 'buy': 1, 'dynatec': 1, 'spin': 1, 'unit': 1}
Please note you should use the same text transformation technique as the document, i.e., tokenizing steps for queries must be identical to steps for documents.
Task 1.3: Define a main function to test function parse_rcv1v2( ) and parse_query( ). The main function uses the provided dataset, calls function parse_rcv1v2() to get a collection of Rcv1Doc objects. For each document in the collection, firstly print out its docID, the number of terms and the total number of words in the document (doc_len). It then sorts terms (by frequency) and prints out a term:freq list. At last, it saves the output into a text file (file name is “your full name_Q1.txt”).
Output Example for file “807606news.xml”
Document 807606 contains 60 terms and have total 187 words
bid : 7
bank : 6
insur : 5
great : 5
west : 5
royal : 5
london : 4
quot : 4
trilon : 3
tender : 3
stake : 3
offer : 3
tuesday : 2
percent : 2
billion : 2
canada : 2
match : 2
myhal : 2
june : 2
sharehold : 2
per : 2
share : 2
financi : 1
corp : 1
group : 1
lifeco : 1
inc : 1
doe : 1
posit : 1
wait : 1
see : 1
fail : 1
spokesman : 1
georg : 1
…
Query: CANADA: Sherritt to buy Dynatec, spin off unit, canada
The parsed query:
{'canada': 2, 'sherritt': 1, 'buy': 1, 'dynatec': 1, 'spin': 1, 'unit': 1}
Question 2. TF*IDF-based IR Model
TF*IDF is a popular term weighting method, which uses the following Eq. (1) to calculate a weight for term k in a document i, where the base of log is e. You may review lecture notes to get the meaning of each variable in the equation.
Task 2.1: Define a function my_df(coll) to calculate document-frequency (df) for a given Rcv1Doc collection coll and return a {term:df, …} dictionary.
Task 2.1 outputs example:
There are 16 documents in this data set and contains 1131 terms.
The following are the terms’ document-frequency:
bank : 9
day : 9
over : 9
three : 9
open : 8
percent : 8
quot : 8
isra : 7
kill : 7
palestinian : 7
state : 7
two : 7
west : 7
armi : 6
clash : 6
dead : 6
death : 6
five : 6
forc : 6
gaza : 6
israel : 6
jerusalem : 6
near : 6
now : 6
offici : 6
one : 6
power : 6
settlement : 6
share : 6
shot : 6
sourc : 6
strip : 6
thursday : 6
wednesday : 6
…
Task 2.2: Use Eq. (1) to define a function my_ idf(doc, df, ndocs) to calculate TF*IDF value (weight) of every term in a Rcv1Doc object, where doc is a Rcv1Doc object or a dictionary of {term:freq,…}, df is a {term:df, …} dictionary, and ndocs is the number of documents in a given Rcv1Doc collection. The function returns a {term:tfidf_weight , …} dictionary for the given document doc.
Task 2.3: Define a main function to call my_tfidf() and print out top 20 terms (with its value of tf*idf weight) for each document in RCV1v2 if it has more than 20 terms and save the output
into a text file (file name is “your full name_Q2.txt”).
. You also need to implement a TF*IDF based IR model.
. You can assume titles of XML documents (the <title>…</title> part) are the original queries, and test at least three titles.
. You need to use function parse_query() that you defined for Question 1 to parse original queries.
. For each query Q, please use the abstract model of ranking (Eq. (2)) to calculate a ranking score for each document D.
At last, append the output (in descending order) into the text file (“your full name_Q2.txt”).
Task outputs example:
Document 783803 contains 200 terms
news : 0.17035607692216304
amp : 0.1592306252146964
pari : 0.1511453922729016
europ : 0.14561417279056282
franc : 0.1409330529548014
internet : 0.12805951243965727
brand : 0.12805951243965727
canal : 0.12805951243965727
plus : 0.12805951243965727
publish : 0.12805951243965727
amauri : 0.12805951243965727
tribun : 0.12805951243965727
conserv : 0.12805951243965727
advertis : 0.12776705769162228
product : 0.11942296891102228
french : 0.11345286925789884
media : 0.10921062959292212
made : 0.10921062959292212
purchas : 0.10331760830805707
newspap : 0.10331760830805707
…
The Ranking Result for query: Reuters French Advertising & Media Digest
783803 : 0.4902835325897291
79565 : 0.11543335906065105
783802 : 0.10147652909458862
807606 : 0.056210308354032956
780723 : 0.053218812101198436
809481 : 0.052111427395384456
80283 : 0.045884305679098916
807600 : 0.0315682718089489
79552 : 0
809495 : 0
780718 : 0
80282 : 0
…
Question 3. BM25-based IR Model
BM25 is a popular IR model with an effective ranking algorithm, which uses the following Eq. (3) to calculate a document score or ranking for a given query Q and a document D, where the base of log is 2. You may review lecture notes to get the meaning of each variable in the equation.
You can use the Rcv1Doc collection to calculate these variables, such as N and ni (you may assume R = ri = 0).
Task 3.1: Define a Python function avg_length(coll) to calculate and return the average
document length of all documents in the collection coll.
. In the Rcv1Doc class, for the variable (attribute) doc_len (the document length), add accessor (get) and mutator (set) methods for it.
. You may modify your code defined in Question 1 by calling the mutator method of doc_len to save the document length in a Rcv1Doc object when creating the Rcv1Doc object. At the same time, sum up every Rcv1Doc’s doc_len as totalDocLength, then at the end, calculate the average document length and return it.
Task 3.2: Use Eq. (3) to define a python function my_bm25(coll, q, df) to calculate documents ’ BM25 score for a given original query q, where df is a {term:df, …} dictionary. Please note you should parse query using the same method as parsing documents (you can call function parse_query() that you defined for Question 1). For the given query q, the function returns a dictionary of {docID: bm25_score, … } for all documents in collection coll.
Task 3.3: Define a main function to implement a BM25-based IR model to rank documents in
the given document collection RCV1v2 using your functions.
. You are required to test all the following queries:
o The British-Fashion Awards
o Rocket attacks
o Broadcast Fashion Awards
o stock market
. The BM25-based IR model needs to print out the ranking result (sort them by using each document's ranking score in descending order) of top-6 possible relevant documents for a given query and append outputs into the text file (“your full name_Q3.txt”).
PS: you may get negative BM25 scores because N is not large enough and ni can be close to N.
You can fix this by increasing N.
Task outputs example:
Average document length for this collection is: ...
The query is: Broadcast Fashion Awards
The following are the BM25 score for each document:
Document ID: 79565, Doc Length: 861 -- BM25 Score: 0.0
Document ID: 79552, Doc Length: 60 -- BM25 Score: 0.0
Document ID: 783803, Doc Length: 490 -- BM25 Score: 4.794590009994427
Document ID: 809495, Doc Length: 703 -- BM25 Score: 0.0
Document ID: 780718, Doc Length: 107 -- BM25 Score: 0.0
Document ID: 741309, Doc Length: 104 -- BM25 Score: 0.0
Document ID: 807600, Doc Length: 538 -- BM25 Score: 0.0
Document ID: 79548, Doc Length: 374 -- BM25 Score: 0.0
Document ID: 783802, Doc Length: 120 -- BM25 Score: 14.105767524697614
Document ID: 809481, Doc Length: 151 -- BM25 Score: 0.0
Document ID: 80280, Doc Length: 646 -- BM25 Score: 0.0
…
For query "Broadcast Fashion Awards", the top-6 possible relevant documents are:
783802 14.105767524697614
783803 4.794590009994427
80283 1.2997432366627848
79565 0.0
79552 0.0
809495 0.0
…
Assignment 1 Requirements
. Your Python solution should be a few .py files and be able to be tested in Pycharm (lab version).
. You can add more methods, variables or functions. For any new one, you should provide comments to understand its definition and usage.
. Your output does not need to match the example output exactly.
. Your programs should be well laid out, easy to read and well commented.
. All items submitted should be clearly labelled with your name or student number.
. Marks will be awarded for programs (correctness, programming style, elegance, commenting) and outputs, according to the marking guide.
. You will lose marks for inaccurate outputs, code problems or errors, missing required files or comments, or not following the specification and requirements.