K-nearest neighbor for text classification, Computer Engineering

Assignment Help:

Assignment 2: K-nearest neighbor for text classification.

The goal of text classification is to identify the topic for a piece of text (news article, web-blog, etc.). Text classification has obvious utility in the age of information overload, and it has become a popular turf for applying machine learning algorithms. In this project, you will have the opportunity to implement k-nearest neighbor and apply it to text classification on the well known Reuter news collection.

1.       Download the dataset from my website, which is created from the original collection and contains a training file, a test file, the topics, and the format for train/test.

2.       Implement the k-nearest neighbor algorithm for text classification. Your goal is to predict the topic for each news article in the test set. Try the following distance or similarity measures with their corresponding representations.

a.        Hamming distance: each document is represented as a boolean vector, where each bit represents whether the corresponding word appears in the document.

b.       Euclidean distance: each document is represented as a numeric vector, where each number represents how many times the corresponding word appears in the document (it could be zero).

c.         Cosine similarity with TF-IDF weights (a popular metric in information retrieval): each document is represented by a numeric vector as in (b). However, now each number is the TF-IDF weight for the corresponding word (as defined below). The similarity between two documents is the dot product of their corresponding vectors, divided by the product of their norms.

3.        Let w be a word, d be a document, and N(d,w) be the number of occurrences of w in d (i.e., the number in the vector in (b)). TF stands for term frequency, and TF(d,w)=N(d,w)/W(d), where W(d) is the total number of words in d. IDF stands for inverted document frequency, and IDF(d,w)=log(D/C(w)), where D is the total number of documents, and C(w) is the total number of documents that contains the word w; the base for the logarithm is irrelevant, you can use e or 2. The TF-IDF weight for w in d is TF(d,w)*IDF(d,w); this is the number you should put in the vector in (c). TF-IDF is a clever heuristic to take into account of the "information content" that each word conveys, so that frequent words like "the" is discounted and document-specific ones are amplified. You can find more details about it online or in standard IR text.

4.       You should try k = 1, k = 3 and k = 5 with each of the representations above. Notice that with a distance measure, the k-nearest neighborhoods are the ones with the smallest distance from the test point, whereas with a similarity measure, they are the ones with the highest similarity scores.

Mips simulator: testing, Your code will be tested using a command script. T...

Your code will be tested using a command script. The script is available on Blackboard in the archive MIPSimTest.zip. It contains a ReadMe file that explains how to run the script

Bounded rationality in decision making, Q.What do you mean by the term 'bou...

Q.What do you mean by the term 'bounded rationality in decision making'? Maximizing the outcomes of a decision is an ideal stage. Habitually it is an impossible thing. The caus

History of parallel computers, History Of Parallel Computers The test ...

History Of Parallel Computers The test with and implementations of the utilize of parallelism started year back in the 1950s by the IBM.  The IBM enlarges computers also calle

What is the use of status command, What is the use of status command, data ...

What is the use of status command, data output command, and data input command. A status command is used to test a variety of status conditions in the interface and the periphe

What is message passing libraries, Q. What is Message Passing Libraries? ...

Q. What is Message Passing Libraries? In this part we will consider about message passing libraries. Traditionally a range of message passing libraries have been available ever

What is file allocation table, Q. What is File allocation table? FAT ma...

Q. What is File allocation table? FAT maps the usage of data space of disk. It comprises information about space used by every individual file and unused disk space as well as

What is a cgi bin directory, A CGI bin directory is a special directory on ...

A CGI bin directory is a special directory on the server where CGI scripts are allowed to be implemented. Most servers are configured to only permit CGI scripts to be implemented f

Explain user datagram protocol, Explain User Datagram Protocol. UDP(Use...

Explain User Datagram Protocol. UDP(User Datagram Protocol) : User Datagram Protocol uses a connectionless communication paradigm. It is an application using UDP does not re

Segment combinations, Segment Combinations In 8086 assembler provides a...

Segment Combinations In 8086 assembler provides a means for combining segments declared in various modules. Some typical combine types are: 1.   PUBLIC: This combine directi

Predicates - first-order logic, Predicates - first-order logic: First ...

Predicates - first-order logic: First and foremost in first-order logic sentences, because predicates. Hence the indications of that some things are related in some way. So af