代写INT304编程、代写python程序设计

日期：2022-03-26 08:32

INT304: Pattern Recognition In Computer Vision S2 2021-2022

Assignment/Lab 1: Feature Selection

Lecturer: Xi Yang Unit: INT Dept. of Intelligent Science

Disclaimer:

1. Lab reports deadlines are strict. University late submission policy will be applied.

2. Collusion and plagiarism are absolutely forbidden (University policy will be

applied).

3. Report is due 21 days from the date of running this lab. (March 29th, 2022)

1.1 Objectives

• Master the concepts and knowledge on feature selection.

• Be familiar with the text processing

1.2 Introduction

Text categorization is the task on classifying a set of documents into categories from a set of predefined

labels. Texts cannot be directly handled by our model. The indexing procedure is the first step that maps

a text dj into a numeric representation during the training and validation. The standard tfidf function

is used to represent the text. The unique words from English vocabulary are represented as a dimension of

the dataset. The high dimensionality of the word space may be problematic for our classification methods.

In this case, we will choose a subset by the feature selection methods to reduce the dimensionality of the

feature space.

1.3 Tasks

1.3.1 Data Preprocessing

• ( 10 marks ) Download the text dataset and read the documents: http://qwone.com/ jason/20Newsgroups/.

The training examples of the version 20news-bydate.tar.gz are used for our experiments, where

the duplicates are removed.

• ( 10 marks ) Remove the stopwords (Stopword.txt), which are frequent words that carry no information.

Convert all word into their lower case form. Delete all non-alphabet characters from the text. Hint: using

python set, regex and dict

• ( 10 marks ) Perform word stemming, which means the remove the word suffix.

– install the library: nltk (python language)

– usage: see the following code on how to use Porter stemmer (https://www.nltk.org/howto/stem.html).

1-1

1-2 Lecture 1: Feature Selection

from nltk . stem . porter import *

stemmer = PorterStemmer ()

plurals = [’caresses ’, ’flies ’, ’dies ’, ’mules ’, ’denied ’,

’died ’, ’agreed ’, ’owned ’, ’humbled ’, ’sized ’,

’meeting ’, ’stating ’, ’siezing ’, ’itemization ’,

’sensational ’, ’traditional ’, ’reference ’, ’colonizer ’,

’plotted ’]

singles = [ stemmer . stem ( plural ) for plural in plurals ]

1.3.2 Indexing

The documents are represented as the vector space model. In the vector space model, each document is

represented as a vector of words. A collection of documents are represented by a document-by-word matrix

A

A = (aik) (1.1)

where aik is the weight of word k in document i.

1.3.3 Feature Selection

Feature selection try to remove non-informative words from the document in order to improve categorization

effectiveness and reduce the computational complexity.

• ( 10 marks ) Remove the low-frequency words

The document frequency for a word is the number of documents in which the words occurs. You should

compute the document frequency for each word in the training dataset and removes those words whose

document frequency is less than some predefined threshold (the setting df < 5).

• ( 40 marks ) Choose features with information gain

Information gain measures the number of bits of information by knowing the presence or absence of a

word in a document.

( 10 marks ) Let c1, c2, · · · , cK denote the set of possible categories. The information gain of a word

w is defined to be

IG(w) = H(C) − H(C|w)

= −

X

K

j=1

P(cj ) log(P(cj )) + P(w)

X

K

j=1

P(cj |w) log P(cj |w) + P( ¯w)

X

K

j=1

P(cj |w¯) log P(cj |w¯)

– 5 marks P(cj ): the fraction of documents in the total collection that belongs to class cj

– 5 marks P(w): the fraction of documents in which the word w occurs

– 10 marks P(cj |w): the fraction of documents from class cj that have at least one occurrence of

word w

– 10 marks P(cj |w¯): the fraction of documents from class cj that does not contain the word w

In the end, we choose 1000 word with maximum IG values by sorting all words.

Lecture 1: Feature Selection 1-3

1.3.4 ( 20 marks ) TFIDF Representation

TFIDF representation assigns the weight to word i in document k in proportion to the number of occurrences

of the word in the document, and inverse proportion to the number of documents in the collection for which

the word occurs at least once.

aik = fik ∗ log(N/nk) (1.2)

• fik: the frequency of word k in document i

• N: the number of documents in the training dataset

• nk: the total number of times word k occurs in the training dataset called the document frequency.

Taking int account the length of different documents, we normalize the representation of the document as

Aik = q

aik

P1000

j=1 a

2

ij

(1.3)

The training set can be represent as a matrix AN×1000. Once the features are chosen, the test set can be

converted into another matrix BM×1000, where M is the size of the test dataset.

1.4 Lab Report

• Write a short report which should contain a concise description of your results and observations.

• Please insert the clipped running image into your report for each step.

• Submit the report and the source code to electronically into LearningMall.

• Python is strongly suggested.

• The report is strongly suggested to be written with the latex typesetting language.

• The report in pdf format and python source code of your implementation should be zipped into a single

file. The naming of report is as follows:

e.g. StudentID LastName FirstName LabNumber.zip (123456789 Einstein Albert 1.zip)

1.5 Hints

Please refer to the paper for more details: K Aas and L. Eikvil, Text Categorisation: A Survey, 1999.

• Latex IDE: texstudio

• Python IDE: pycharm

• Use the python set, dict and list collections flexibly.