Generators in Python

I was trying to construct a two dimensional code and encountered the following problem:

>>> l = list()
>>> l.append([] for i in range(5))
>>> l[0].append(1)
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: 'generator' object has no attribute 'append'

Hmm, I thought I was creating an empty list and append another 5 empty lists. However:

>>> l
[<generator genexpr="" object=""> at 0x102077fc0>]

Recall my conversation with my friend the day before about generators, I decide to dig a little bit deeper.

It turns out I am using the generator expression, and thus instead of creating a list of lists, I created a generator object.

So what is a generator function?
In Python, generator functions allow for more efficient memory use. Consider we need to get the range from 0 to a very large integer (I just realize in Python 3 there is no maximum integer), and we need operate on this range of number (e.g., print them out). We can either construct a list and operate this list, which will consume all of our memory or, we can simply generate the number and operate it at the same time. For example, we can generate the number, print it out, and only remember the current number so that we can do the next operation. Take a look at the following class:

class firstn(object):
    def __init__(self, n):
        self.n = n
        self.num, self.nums = 0, []

    def __iter__(self):
        return self

    # Python 3 compatibility
    def __next__(self):
        return self.next()

    def next(self):
        if self.num < self.n:
            cur, self.num = self.num, self.num+1
            return cur
        else:
            raise StopIteration()

The class constructs an iterator, but it does not store the each element in the memory. In fact, it only stores the current element and the element prior to it. When operating on this iterator, all we need to do is to operate, store the current result and generate the next element. This saves a lot of memory.

However, writing in this way is somehow cumbersome. Python provides an easier way to do it --yield:

>>> def firstn(n):
...     num = 0
...     while num < n:
...         yield num
...         num += 1
... 
>>> firstn(100)
<generator object firstn at 0x10207e0d8>

The firstn(n) function is written in the generator function manner.

We can even skip writing a function by using a generator expression:

>>> (n for n in range(5))
<generator genexpr="" object=""> at 0x10207e048>
>>> [n for n in range(5)]
[0, 1, 2, 3, 4]

As you can see, the only difference between a generator and a list constructor is () versus []. And this is the reason I encountered the problem I mentioned at the beginning of the post.

However, even though there are lots of perks by using generators, do remember such iterator (remember a generator is still an iterator) can only be iterate once. Because the elements are not saved in the memory, after the operation, the elements are gone. You have to create a generator (or call the function if you write a generator function) if you want to perform the operations again.

Last thing, how to solve the above-mentioned problem?

Not this way if you are thinking of it:

>>> l.append([[] for i in range(5)])
>>> l
[[[], [], [], [], []]]

append() appends the item (which is a list of lists you have just constructed) to l, which results a list that has an element of a list of lists...

either extend() or += should work:

>>> l.extend([[] for i in range(5)])
>>> l
[[], [], [], [], []]
>>> l += [[] for i in range(5)]
>>> l
[[], [], [], [], [], [], [], [], [], []]

References:
[1] https://wiki.python.org/moin/Generators
[2] http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python
[3] http://stackoverflow.com/questions/5164642/python-print-a-generator-expression

Regular Expression 101

A small task in my new job requires me to match a file name. there are lots of ways to do it, and regex is among one of them. More important, it gives me a reason to finally go through the basics of regex.
This blog contains the basic concepts of regex. If you only want to get your feet wet, this is enough, otherwise please refer to the reference. :)


Twelve special characters
backslash \
caret ^
dollar sign $
dot .
vertical bar |
question mark ?
asterisk *
plus +
opening parenthesis (
closing parenthesis )
opening square bracket [
opening curly brace {

In order to match these special characters, an extra backslash is needed. e.g., 1 \+ 1 = 2 matches 1 + 1 = 2, a\\b matches a\b.

Character classes
Matches only one out of several characters. For example: "gr[ae]y" matches "gray" or "grey" but not "graey" or "greey".

A hyphen can be used to specify a range of characters:
[0-9a-fA-F] matches a single hexadecimal digit.
[0-0a-fxA-FX] matches the letter X or a hexadecimal digit.

A caret indicates does not match.
"q[^x]" matches any character after "q" except "x". For example, "qu". However, it does not match single character "q".


Shorthand character classes
\d matches a single character that is a digit.
\w matches a "word character", which is defined as all alphanumeric characters(0-9 + a-z + A-Z) plus underscore.
\s matches a white space character ([\r\n\t\f], \r: carriage return, \f: form feed, \n: new line).
Capital indicates negated versions.
\D = [^\d]
\W = [^\w]
\S = [^\s]

Non-printable characters
Special characters like \r \n \t can also be used in regex. If the application supports Unicode, use \uFFFF or \x{FFFF} to insert a Unicode character. For example, \u20AC or \x{20AC} matches the euro currency sign.
If the application does not support Unicode, use \xFF to match a specific character by its hexadecimal index in the character set. \xA9 matches the copyright symbol in the Latin-1 character set.

The dot matches any single character
except line break characters. equals[^\n] in Unix or [^\r\n] in Windows.
For example, gr.y matches gray, grey, gr&y, etc.

Anchors
^ matches the position before the first character in the string while $ matches the position after the last character. \b indicates word boundary. It allows you to perform a "whole word only" search. More specific, \b matches before and after an alphanumeric sequence. \B is the negated version of \b.
^a indicates a string starts with "a", e.g.,  "abc".
c$ indicates a string ends with "c", e.g., "abc".
^\s+ matches leading whitespace and \s+$ matches trailing whitespace.
\b4\b matches "4" but not "44" or "a4".

When there are multiple lines in one string, e.g., lineone\nlinetwo, ^ and $ can be used to match each line, rather than the entire string. e.g., $ can match the position before \n and after "e" as well as end of the string. Likewise, ^ can match the start of the string and the position after \n and before "l" in the second line.
In Java, Python PHP as well as Perl, $ matches the position before line break as well as the very end of the string, regardless of whether the character is a line break. For example, "^\d$" matches "1" or "1\n".

\A and \Z are permanent start of string and end of string anchors, they cannot match line breaks. However, JavaScript, XML POSIX or XPath does not support these two tokens. In Python, \Z matches at the very end of the string("^\d$" matches "1\n" or "1"). In other languages such as Java and PHP, \Z matches positions before the final line break ("^\d$" matches "1\n" or "1"), use \z (lower case) to match the absolute end of string ("\A\d\z" only matches "1" but not "1\n" because the end of string is a line-breaking token not a digit).

Alternation
"cat|dog" matches "cat" in "cats and dogs". If the regex is applied again, it matches "dog".

Repetition
? makes the preceding token in the regex optional.
"colou?r" matches "color" or "colour".
* tells the engine to attempt to match the proceeding token zero or more times.
+ matches the proceeding token one or more times.
"<[A-Za-z][A-Za-z0-9]*>" matches an HTML tag without any attributes.
"<[A-Za-z0-9]+>" also matches an HTML tag, but may also match an invalid one such as "<1>".
Curly braces are used to specify an amount of repetition.
"\b[1-9][0-9]{3}\b" matches a number between 1000 and 9999.
"\b[1-9][0-9]{2,4}\b" matches a number between 100 and 99999.

Greedy and Lazy Repetition
The repetition operators are greedy. They expand the match as far as they can, and only give if they have to satisfy the remainder of the regex.
For example, the regex "<.+>" matches "<EM>first</EM>" in "This is a <EM> first</EM> test". Why? Let's say s = "<.+>" and p = "This is a <EM> first</EM> test". Regex engine finds the first "<", which is "<" before "E". Now since "+" repeats the "." one or more times, the engine tries to match "." as much as possible, until the end of p ("<EM> first</EM> test"). Then it tries to match">" in s, which is not a match. Note for now ".+" matches "EM> first</EM> test" in p.
The engine then backtracks by reducing the repetition of "." by one, which matches ".+" to "EM> first</EM> tes", and it is still not a match. The engine then repeatedly reduces "." until it can match ">", which is ""<EM> first</EM>".

So what if we want to match a "<EM>"?
We can make the repetition lazy by adding "?", i.e., "<.+?>". This tells the engine to repeat "." as few times as possible. The minimum is one. Using the above example. After the engine matches "<", it tries to proceed to match ">" with "E", which is not a match, then it repeat "." by one, and matches ">" with "M", still not a match. It continuously repeats "." until it matches ">", which now matches"<.+?>" to "<EM>".

Alternatively, in this case, we can use "<[^>]+>" to match an HTML tag. This regex matches anything but ">" one ore more times after the "<" is matches. The perk of this is to avoid backtracking, which increases the speed of the regex engine.

\Q...\E Escape sequence
\Q...\E sequence can be used to escape a string of characters, matching them as literal characters. The escaped characters are treated as individual literal characters.
For example, "\Q*\d+*\E" matches "*\d+*" since all characters between "\Q" and "\E" are not treated as special characters.
When applying repeating characters such as "+" or "{3}", it will only be applied to the last character. e.g., "\Q*\d+*\E+" matches "*\d+**" in "*\d+**\d+*".


Grouping and Capturing
Place parentheses around multiple tokens to group them together. A quantifier can also be applied. Parentheses create a capturing group. Use special syntax (?:string) to group tokens without creating a capturing group. This is more efficient if you don't plan to use the group's contents. For example[1], considering pattern:
p = "http://stackoverflow.com/questions/tagged/regex".

If we apply regex:
"(http|ftp)://([^/\r\n]+)(/[^\r\n]*)?"

We will have the result:
Match "http://stackoverflow.com/questions/tagged/regex"
Group 1: "http"
Group 2: "stackoverflow.com"
Group 3: "/questions/tagged/regex"

However, if we don't need the protocol, we can use "(?:)" to create a non-capturing group:
regex: "(?:http|ftp)://([^/\r\n]+)(/[^\r\n]*)?"

Match "http://stackoverflow.com/questions/tagged/regex"
Group 1: "stackoverflow.com"
Group 2: "/questions/tagged/regex"


Using backreferences to match the same text again
Backreferences  match the same text as previously matched by a capturing group. For example, "<([A-Z][A-Z0-9]*)\b[^>]*>.*?</\1> matches a pair of opening and closing HTML tags, and the text (if there is any) in between. If "<([A-Z][A-Z0-9]*)\b[^>]*>" matches "<b>" (bold text) then "</\1>" matches "</b>".

Backreferences are represented by "\" plus number. The first group starts backreference number one, i.e., "\1", the second group "\2". Non-capturing groups are skipped. Most regex engines support up to 99 capturing groups and double-digit backreferencs. So "\99" is valid if there are 99 capturing groups.

However, if the regex has many groups, it can be cumbersome to track their numbers. Alternatively, we can name our groups. In Python,  (?P<mygroup>[abc]) = (?P=mygroup) is the same as ([abc]) =\1
The HTML tag example above can now be written as "<(?P<tag>[A-Z][A-Z0-9]*)\b[^>]*>.*?</?P=tag>

The same backreference can be reused more than once. "([a-c])x\1x\1" matches "axaxa" or "bxbxb" or "cxcxc".

Unicode properties
"\p{L}" matches a single character that is in the given Unicode category. "L" stands for letter. "\P{L}" matches a single character that is not in the given Unicode category. See details.

Lookaround
The tokens inside the group are matched but not kept, it tends to match the syntax outside the group.
Look ahead:
"c(?=a)" matches any "c" that follows by an "a". Thus it matches "c" in "cat" but not "c" in "click".
"c(?!a)" matches any "c" that does not follow by an "a". Thus it matches "c" in "click" but not "c" in "cat".
Look behind:
"(?<=a)b" matches any "b" that has a proceeding "a", e.g., "b" in "abc".
"(?<!a)b" matches any "b" that has a proceeding character that is not "a", e.g., "cbc" but not "abc".


References
[1] https://stackoverflow.com/questions/3512471/non-capturing-group/3513858#3513858
[2] http://www.regular-expressions.info/

Natural Language Processing: the IMDB movie reviews

Natural language processing (NLP) relates to problems dealing with text problems, usually based on machine learning algorithms. Many machine learning models require features to be quantified, which leads to a great challenge to NLP: how to transfer the large amount of text contents to a language that the computer can understand.

In this blog I apply the IMDB movie reviews and use three different ways to classify if a review is a positive one or negative one. The first one, which creates features according to the occurrence of the words, and the second one, which uses Google's word2vec to transfer a word to a vector, are based on Kaggle's Bag of Words Meet Bag of Popcorn tutorial. The third one, which uses doc2vec, is an optimized version from word2vec by Le and Mikolov[1].

All the src can be found on my Github.

Data cleaning and text processing

A paragraph of text content, or corpus,  may contain HTML tags, punctuations numbers and symbols (e.g., emojis) that affect the result of prediction. Moreover, it needs to be broken down to single words before it can be applied to any feature creating methods.

* Please refer to my First touch in data science (Titanic project on Kaggle) Part I: a simple model 

HTML tags

Some corpus contains HTML tags such as <br/> ,<pre> etc. In this blog, I use a Python library Beautiful Soup to do that.

review_text = BeautifulSoup(raw_review).get_text()

Break down to words

A long paragraph of text contents is hard for the computer to process it. Thus, we need to break the paragraph to single words. It is true that the order of the words may affect the meaning of the content, thus affect the prediction. As we may see later, doc2vec takes into account word order and has been shown to be the best method for IMDB movie review classifications. Moreover, punctuations such as ":)" (smileys) and numbers may also affect the classification. The original tutorial from Kaggle does not include the smileys and numbers option, for better performance, I added these two in my code.

The code uses regular expression to find patterns (numbers or punctuations) and replace them with white space for split up later.

Python provides re library for regular expression operations.

smileys = """:-) :) :o) :] :3 :c) :> =] 8) =) :} :^)

:D 8-D 8D x-D xD X-D XD =-D =D =-3 =3 B^D :( :/ :-( :'( :D :P""".split()
smiley_pattern = "|".join(map(re.escape, smileys))


# re.sub() replace the pattern by the desired character/string
# [^] matches a single character that is not contained within the brackets
    if remove_numbers and remove_smileys:

elif remove_smileys:
# any character that is not in a to z and A to Z (non text)
        review_text = re.sub("[^a-zA-Z]", " ", review_text)
         # numbers are also included

review_text = re.sub("[^a-zA-Z0-9" + smiley_pattern + "]", " ", review_text)
review_text = re.sub("[^a-zA-Z0-9]", " ", review_text)
    elif remove_numbers:
        review_text = re.sub("[^a-zA-Z" + smiley_pattern + "]", " ", review_text)

else:

After we remove the unnecessary symbols, we split the paragraph to single words.

# split in to a list of words

words = review_text.lower().split()

This operation gives a list of single words.

Remove stop words

Stop words are those high frequent words that do not carry much meaning. Examples include "I", "you", "this", "is"...etc. Including such stop words may affect the model prediction. Here, I use Natural Language Toolkit to get all the common stop words. It's not included in Python's default library, thus we need to install it and its dictionary first. Please do not use IDE to install it, it will not work. Please check the NLTK documentation for installation and downloading the data. A separate window will pop up when you type the nltk.download() command in the interactive model and ask you to select the desired dictionary. I selected all, you may select specific library (e.g., stopwords).

After installation and got the desired data, import stopwords library. Now all we need to do is to remove the stop words that are in the stopwords library from the list of words we have created from the review.

from nltk.corpus import stopwords
if remove_stopwords:

# create a set of all stop words
stops = set(stopwords.words("english"))

words = [w for w in words if w not in stops]

# remove stop words from the list

The final list of words should look like this:

>>> words = processData.review_to_words(train["review"][0], True, False, False)
>>> words

['stuff', 'going', 'moment', 'mj', "i've", 'started', 'listening', 'music', 'watching', 'odd', 'documentary', 'watched', 'wiz', 'watched', 'moonwalker', 'maybe', 'want', 'get', 'certain', 'insight', 'guy', 'thought', 'really', 'cool', 'eighties', 'maybe', 'make', 'mind', 'whether', 'guilty', 'innocent', 'moonwalker', 'part', 'biography', 'part', 'feature', 'film', 'remember', 'going', 'see', 'cinema', 'originally', 'released', 'subtle', 'messages', "mj's", 'feeling', 'towards', 'press', 'also', 'obvious', 'message', 'drugs', 'bad', "m'kay", 'visually', 'impressive', 'course', 'michael', 'jackson', 'unless', 'remotely', 'like', 'mj', 'anyway', 'going', 'hate', 'find', 'boring', 'may', 'call', 'mj', 'egotist', 'consenting', 'making', 'movie', 'mj', 'fans', 'would', 'say', 'made', 'fans', 'true', 'really', 'nice', 'actual', 'feature', 'film', 'bit', 'finally', 'starts', '20', 'minutes', 'excluding', 'smooth', 'criminal', 'sequence', 'joe', 'pesci', 'convincing', 'psychopathic', 'powerful', 'drug', 'lord', 'wants', 'mj', 'dead', 'bad', 'beyond', 'mj', 'overheard', 'plans', 'nah', 'joe', "pesci's", 'character', 'ranted', 'wanted', 'people', 'know', 'supplying', 'drugs', 'etc', 'dunno', 'maybe', 'hates', "mj's", 'music', 'lots', 'cool', 'things', 'like', 'mj', 'turning', 'car', 'robot', 'whole', 'speed', 'demon', 'sequence', 'also', 'director', 'must', 'patience', 'saint', 'came', 'filming', 'kiddy', 'bad', 'sequence', 'usually', 'directors', 'hate', 'working', 'one', 'kid', 'let', 'alone', 'whole', 'bunch', 'performing', 'complex', 'dance', 'scene', 'bottom', 'line', 'movie', 'people', 'like', 'mj', 'one', 'level', 'another', '(which', 'think', 'people)', 'stay', 'away', 'try', 'give', 'wholesome', 'message', 'ironically', "mj's", 'bestest', 'buddy', 'movie', 'girl', 'michael', 'jackson', 'truly', 'one', 'talented', 'people', 'ever', 'grace', 'planet', 'guilty', 'well', 'attention', "i've", 'gave', 'subject', 'hmmm', 'well', "don't", 'know', 'people', 'different', 'behind', 'closed', 'doors', 'know', 'fact', 'either', 'extremely', 'nice', 'stupid', 'guy', 'one', 'sickest', 'liars', 'hope', 'latter']

Processing all the reviews:

clean_train_reviews = []
print("Cleaning and parsing training data", end="\n")
for i in range(0, num_reviews):
    # if (i+1) % 1000 == 0:
    # print("Review %d of %d\n" % (i+1, num_reviews))
    clean_train_reviews.append(" ".join(processData.review_to_words(train["review"][i], True,False,False)))

The review_to_words() function contains all operations to process a review.

def review_to_words(raw_review, remove_stopwords=False, remove_numbers=False, remove_smileys=False):
    # use BeautifulSoup library to remove the HTML/XML tags (e.g., 
)
    review_text = BeautifulSoup(raw_review).get_text()

    # emotional symbols may affect the meaning of the review
    smileys = """:-) :) :o) :] :3 :c) :> =] 8) =) :} :^)
                :D 8-D 8D x-D xD X-D XD =-D =D =-3 =3 B^D :( :/ :-( :'( :D :P""".split()
    smiley_pattern = "|".join(map(re.escape, smileys))

    # [^] matches a single character that is not contained within the brackets
    # re.sub() replace the pattern by the desired character/string
    if remove_numbers and remove_smileys:
        # any character that is not in a to z and A to Z (non text)
        review_text = re.sub("[^a-zA-Z]", " ", review_text)
    elif remove_smileys:
         # numbers are also included
        review_text = re.sub("[^a-zA-Z0-9]", " ", review_text)
    elif remove_numbers:
        review_text = re.sub("[^a-zA-Z" + smiley_pattern + "]", " ", review_text)
    else:
        review_text = re.sub("[^a-zA-Z0-9" + smiley_pattern + "]", " ", review_text)


    # split in to a list of words
    words = review_text.lower().split()

    if remove_stopwords:
        # create a set of all stop words
        stops = set(stopwords.words("english"))
        # remove stop words from the list
        words = [w for w in words if w not in stops]

    # for bag of words, return a string that is the concatenation of all the meaningful words
    # for word2Vector, return list of words
    # return " ".join(words)
    return words

Note:
The Kaggle tutorial mentioned that:

If you are appending a list of lists to another list of lists, "append" will only append the first list; you need to use "+=" in order to join all of the lists at once.

This is not the case for Python 3. In Python 3, += join all the lists together and flatten them, while append appends each list to the list. See this post.

This part of the code is included the processData.py in the review to 

Bag of words model

Now we have a list of words. The next thing we need to do is to create features for the model we are going to train based on all reviews (list of words) we have. The simplest way is to learn a vocabulary(bag-of-words model) from all the reviews we have, then use this vocabulary as the features and count the occurrence of each word in the vocabulary in each list of words. The result will be a vector, with each element the occurrence of a word in the vocabulary. And this vector will be used as the feature vector for training.

For example,

dictionary {the, cat, sat, on, hat, dog, likes, and}

sentence1: the cat sat on the hat {2, 1, 1, 1, 1, 0, 0, 0}

sentence2: the dog likes the cat and the hat {3, 1, 0, 0, 1, 1, 1, 1} 

I use the feature_extraction module from scikit-learn to create a bag-of-words features. CountVectorizer converts a collection of text documents to a matrix of token counts.  Here, we will convert the list of the list of words (each review is a list) to a matrix. Each row will be a frequency vector, each column is the frequency of the word. Note that CountVectorizer has the option of preprocessing, and it is definitely worth trying. :)

# max_features determine the maximum words that is taken into account, 5000 here
# e.g. dictionary {the, cat, sat, on, hat, dog, likes, and}
# sentence1: the cat sat on the hat {2, 1, 1, 1, 1, 0, 0, 0}
# sentence2: the dog likes the cat and the hat {3, 1, 0, 0, 1, 1, 1, 1}
vectorizer = CountVectorizer(analyzer="word",
                             tokenizer=None,
                             preprocessor=None,
                             stop_words=None,
                             max_features=5000)

This part of the code is included in the nlp.py.

Word2Vec

Word2Vec is a project developed by Google using neural network implementation that learns distributed representations for words[2]. There are quite a few resources explaining the details of Word2Vec. I selected a few here.

Modern Methods for Sentiment Analysis

Deep Learning, NLP, and Representations

Word2Vec doc

Quora question

Stack overflow

Stanford sentimental analysis

In short, given a dictionary (e.g., wikitionary), Word2Vec map each word to a vector so that words can be compared or operated. For example, "king" -"man" = "queen" - "woman".

The original Word2Vec is implemented in C. In Python, the Gensim package provides excellent implementation of the project. 

Word2Vec expects single sentences, each one as a list of words. That means a review will be broken down to a list of lists, with each list a list of words. So the question is, how to determine what is a sentence? There are several different ways to define the end of a sentence ("?",  ".", "!", " ", etc), moreover, sometimes capitalization at the beginning of a sentence may also indicate the previous word is the end of a sentence. Thus, it is hard to do it manually. Python's NLTK package provides punkt module for sentence splitting. If you have downloaded all packages when you install NLTK, you can directly import punkt, otherwise download the module first. 

Processing each review is the same as the way shown previously. However, Kaggle's tutorial have mentioned that it is better not to remove stop words because the algorithm relies on the broader context of the sentence in order to produce high-quality word vectors. It may also be helpful not remove numbers and smileys. The review_to_word() can be used directly with default options.

I wrote the function review_to_sentences() to process each review.

def review_to_sentences(review, tokenizer, remove_stopwords=False, remove_numbers=False, remove_smileys=False):
    """
    This function splits a review into parsed sentences
    :param review:
    :param tokenizer:
    :param remove_stopwords:
    :return: sentences, list of lists
    """
    # review.strip()remove the white spaces in the review
    # use tokenizer to separate review to sentences
    raw_sentences = tokenizer.tokenize(review.strip())

    #cleaned_review = [review_to_words(sentence, remove_stopwords, remove_numbers, remove_smileys) for sentence
    #                  in raw_sentences if len(sentence) > 0]
    # generic form equals append
    cleaned_review = []
    for sentence in raw_sentences:
        if len(sentence) > 0:
            cleaned_review += review_to_words(sentence, remove_stopwords, remove_numbers, remove_smileys)

    return cleaned_review

Before you start training the model, it is better to install Cython for better performance:

**Make sure you have a C compiler before installing gensim, to use optimized (compiled) word2vec training**
(70x speedup compared to plain NumPy implementation [3]_). 

The source code of Word2Vec in Gensim can be found here. They also provide tutorials in the doc string, so it's worth taking a look. :)

The model is trained using skip-gram algorithm (See reference[1]) in default. You can also train the model using continuous bag of words (CBOW) by setting sg=0. Refer to this and this for detailed explanations on skip-gram and CBOW. According to Mikolov (the guy who developed word2vec), skip-gram works well with small amount of the training data, represents well even rare words or phrases. CBOW is several times faster to train than the skip-gram, slightly better accuracy for the frequent words. Based on Kaggle tutorial, skip-gram produces better results on this data set.

num_features = 500  # word vector dimensionality
# minimum word count: any word that does not occur at least this many times
# across all documents is ignored
min_word_count = 40
num_workers = 4  # Number of threads to run in parallel
context = 10  # Context window size
downsampling = 1e-3  # Downsample setting for frequent words

print("Training model...")
model = word2vec.Word2Vec(bag_sentences, workers=num_workers,
                          size=num_features, min_count=min_word_count,
                          window=context, sample=downsampling)

# If you don't plan to train the model any further, calling
# init_sims will make the model much more memory-efficient
model.init_sims(replace=True)
# save the model for future use
model.save("Word2VectforNLPTraining")

This part of the code can be found in word2vecNLP.py

Explore the model
Since we have saved the model, we can load the model directly.

>>> from gensim.models import Word2Vec
>>> model = Word2Vec.load("Word2VectforNLPTraining") 

The model consists a feature vector for each word in the vocabulary, stored in a numpy array called "syn0".

>>> print(type(model.syn0))
#number of words, number of features
>>> model.syn0.shape
(17978, 500)
>>> model["man"]
array([-0.0173709 , -0.05453965, -0.01378504, -0.02687   , -0.0247492 ,
       -0.02725732, -0.08029163, -0.01303324, -0.01790693,  0.02459037,
       -0.0451758 ,  0.06946673,  0.00119434, -0.01014592,  0.00334688,
       ...
       -0.01781173, -0.05186122, -0.04420475,  0.00410226, -0.05667625,
        0.06580704, -0.00364238, -0.14961284,  0.02291572, -0.04049427,
       -0.0516507 ,  0.03579128,  0.00122541,  0.02547096,  0.03301932], dtype=float32)

doesnt_match() function tries to deduce which word in a set is most dissimilar from the others.

>>> model.doesnt_match("man woman child kitchen".split())
'kitchen'
>>> model.doesnt_match("paris berlin london austria".split())
'paris'

most_similar(): returns the score of the most similar words based on the criteria. The topn option determines the top N most similar words. Positive words contribute positively towards the similarity, negative words negatively.

>>> model.most_similar(positive=['woman', 'king'], negative=['man'], topn=10)
[('princess', 0.4017685651779175), ('queen', 0.3796828091144562), ('prince', 0.36173444986343384), ('mistress', 0.3507348895072937), ('rudolf', 0.3303285539150238), ('maid', 0.32905253767967224), ('astor', 0.32380762696266174), ('throne', 0.31540173292160034), ('stepmother', 0.3121083974838257), ('antoinette', 0.31201446056365967)]

This part of the code is included in exploreWord2VecModel.py

Doc2Vec
Doc2Vec takes into account the word order. Details about Doc2Vec can be found in this blog and reference [1]. In gensim, Doc2Vec is implemented as a derived class from Word2Vec. A tutorial about Doc2Vec can be found here.

Instead of skip-gram and CBOW, Doc2Vec implements distributed memory and distributed bag of words (DBOW). Default algorithm is distributed memory (dm=1), by setting dm=0, you can use DBOW.

Doc2Vec requires each sentence to be a LabeledSentence object, which is different from Word2Vec. The easiest way is to create the LabeledSentence object for each sentence.

def labelizeReviews(reviewSet, labelType):
    """
    add label to each review
    :param reviewSet:
    :param label: the label to be put on the review
    :return:
    """
    labelized = []
    for index, review in enumerate(reviewSet):

        labelized.append(doc2vec.LabeledSentence(words=review, labels=['%s_%s'%(labelType, index)]))
    return labelized
# the input to doc2vec is an iterator of LabeledSentence objects
# each consists a list of words and alist of labels
labeled = labelizeReviews(labeled, 'LABELED')
unlabeled = labelizeReviews(unlabeled, 'UNLABELED')

Training part is similar to Word2Vec.

num_features = 500
# minimum word count: any word that does not occur at least this many times
# across all documents is ignored
min_word_count = 40
# the paper (http://arxiv.org/pdf/1405.4053v2.pdf) suggests 10 is the optimal
context = 10
#  threshold for configuring which higher-frequency words are randomly downsampled;
# default is 0 (off), useful value is 1e-5
# set the same as word2vec
downsampling = 1e-3
um_workers = 4  # Number of threads to run in parallel

# if sentence is not supplied, the model is left uninitialized
# otherwise the model is trained automatically
# https://www.codatlas.com/github.com/piskvorky/gensim/develop/gensim/models/doc2vec.py?line=192
model = doc2vec.Doc2Vec(size=num_features,
                        window=context, min_count=min_word_count,
                        sample=downsampling, workers=4)

model.build_vocab(bag_labeled_sentence)
# gensim documentation suggests training over data set for multiple times
# by either randomizing the order of the data set or adjusting learning rate
# see here for adjusting learn rate: http://rare-technologies.com/doc2vec-tutorial/
# iterate 10 times
for it in range(10):
    # perm = np.random.permutation(bag_labeled_sentence.shape[0])
    model.train(np.random.permutation(bag_labeled_sentence))

This part of the code can be found in doc2vecNLP.py

IMDB review classification

Word2Vec or Doc2Vec only allows us to project text words to vectors. In order to classify a paragraph of text contents, we still need to determine the features of each review.

Vector Averaging
The easiest method is averaging the word vectors in each review. Each word is a vector of num_features (500 in my case), if we add all words in the review and take the average, in the end the review becomes a vector of num_features dimension.

For example,
review: "shirley is awesome"
"shirley" = "0.3 0.6 0.8"
"is" = "1.2 3.5 4.6"
"awesome" = "0.9 1.2 8.7"

then the vector of the review = "(0.3 + 1.2 + 0.9)/3 (0.6 + 3.5 + 1.2)/3 (0.8 + 4.6 + 8.7)/3" = “0.8 1.77 4.7”

def makeFeatureVec(review, model, num_features):
    """
    given a review, define the feature vector by averaging the feature vectors
    of all words that exist in the model vocabulary in the review
    :param review:
    :param model:
    :param num_features:
    :return:
    """

    featureVec = np.zeros(num_features, dtype=np.float32)
    nwords = 0

    # index2word is the list of the names of the words in the model's vocabulary.
    # convert it to set for speed
    vocabulary_set = set(model.index2word)

    # loop over each word in the review and add its feature vector to the total
    # if the word is in the model's vocabulary
    for word in review:
        if word in vocabulary_set:
            nwords = nwords + 1
            # add arguments element-wise
            # if x1.shape != x2.shape, they must be able to be casted
            # to a common shape
            featureVec = np.add(featureVec, model[word])
    featureVec = np.divide(featureVec,nwords)
    return featureVec

def getAvgFeatureVecs (reviewSet, model):

    # initialize variables
    counter = 0
    num_features = model.syn0.shape[1]
    reviewsetFV = np.zeros((len(reviewSet),num_features), dtype=np.float32)

    for review in reviewSet:
        reviewsetFV[counter] = makeFeatureVec(review, model, num_features)
        counter += 1
    return reviewsetFV

This part of the code can be found on w2vPredictVectorAveraging.py

Clustering
The second one is a fancier one, which uses the clustering algorithm, in specific, the K-means algorithm, to cluster each word to a centroid, and use the vector of the centroid as the feature vector of the review.

I use scikit-learn to perform K-means algorithm.

from sklearn.cluster import KMeans
def kmeans(num_clusters, dataSet):
    # n_clusters: number of centroids
    # n_jobs: number of jobs running in parallel
    kmeans_clustering = KMeans(n_clusters=num_clusters)
    # Compute cluster centers and predict cluster index for each sample
    centroidIndx = kmeans_clustering.fit_predict(dataSet)

    return centroidIndx

After training, each word in the vocabulary is assigned to a centroid.

Now we need to create the feature vector for each review. We can do this by creating a vector of dimension the number of clusters, and add the centroid of each word in the review to the vector. For example,

vocabulary:
   word         centroid
"Shirley"            0
"Dora"               1
"is"                    2
"awesome"        1
"fun"                 0

Number of centroids: 3
So review
"Shirley is awesome" = {1, 1, 1}
"Shirley is fun" = {2, 0, 1}
"Dora is awesome" = {0, 2, 1}

The function create_bag_of_centroids() implements this method.

def create_bag_of_centroids(reviewData):
        """
        assign each word in the review to a centroid
        this returns a numpy array with the dimension as num_clusters
        each will be served as one feature for classification
        :param reviewData:
        :return:
        """
        featureVector = np.zeros(num_clusters, dtype=np.float)
        for word in reviewData:
            if word in index_word_map:
                index = index_word_map[word]
                featureVector[index] += 1
        return featureVector

This part of the code can be found in the w2vPredictClustering.py.

Classification
After you create feature vectors using either of the above method. There are several models you supervised learning methods you can use to classify the review. Reference [1] uses a logistic regression and claims they got 94% test accuracy. I use random forest and got on average 0.84 score for all methods mentioned above except using Doc2Vec and clustering (only 0.73).

def rfClassifer(n_estimators, trainingSet, label, testSet):

    forest = RandomForestClassifier(n_estimators)
    forest = forest.fit(trainingSet, label)
    result = forest.predict(testSet)

    return result

Discussion

Overall, this is a pretty fun object. The above three methods are quite different and take different time for training, but they are similar in certain way: all of them try to project text contents to a feature vector of desired dimension and use that feature vector for classification.

There are quite a few approaches to improve the results: taking into account punctuations, symbols (smileys), use different classification models and so on.



References

[1] Le, Q. V., & Mikolov, T. (2014). Distributed representations of sentences and documents. arXiv preprint arXiv:1405.4053

[2]Goldberg, Yoav, and Omer Levy. "word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method." arXiv preprint arXiv:1402.3722
[3] Optimizing word2vec in gensim, http://radimrehurek.com/2013/09/word2vec-in-python-part-two-optimizing/

Acknowledgement
Kaggle
Codatlas

First touch in data science (Titanic project on Kaggle) Part II: Random Forest

In this post, I will use the Pandas and Scikit learn packages to make the predictions.

Reading the data
Instead of using csv reader provided by Python itself, here we use Pandas.

import pandas as pd
import numpy as np
from sklearn.ensemble import RandomForestClassifier
import csv
# always use header =  0 when row 0 is the header row
df = pd.read_csv('/path/train.csv', header = 0)
test_df = pd.read_csv('/path/test.csv', header = 0)

Pandas store the data into an object called DataFrame. It also provides functions for basic statistics of the data.

df.head(n) returns the first n rows of the data.
df.tail(n) returns the last n rows of the data.

>>> df.head(3)
   PassengerId  Survived  Pclass  \
0            1         0       3   
1            2         1       1   
2            3         1       3   

                                                Name     Sex  Age  SibSp  \
0                            Braund, Mr. Owen Harris    male   22      1   
1  Cumings, Mrs. John Bradley (Florence Briggs Th...  female   38      1   
2                             Heikkinen, Miss. Laina  female   26      0   

   Parch            Ticket     Fare Cabin Embarked  
0      0         A/5 21171   7.2500   NaN        S  
1      0          PC 17599  71.2833   C85        C  
2      0  STON/O2. 3101282   7.9250   NaN        S  
>>> df.tail(3)
     PassengerId  Survived  Pclass                                      Name  \
888          889         0       3  Johnston, Miss. Catherine Helen "Carrie"   
889          890         1       1                     Behr, Mr. Karl Howell   
890          891         0       3                       Dooley, Mr. Patrick   

        Sex  Age  SibSp  Parch      Ticket   Fare Cabin Embarked  
888  female  NaN      1      2  W./C. 6607  23.45   NaN        S  
889    male   26      0      0      111369  30.00  C148        C  
890    male   32      0      0      370376   7.75   NaN        Q  

df.dtypes returns the data type of all the columns. Remember that csv reads data defaults to string, import data using Pandas automatically converts data based on the actual type of the data.

>>> df.dtypes
PassengerId      int64
Survived         int64
Pclass           int64
Name            object
Sex             object
Age            float64
SibSp            int64
Parch            int64
Ticket          object
Fare           float64
Cabin           object
Embarked        object
dtype: object

Sometimes we want to know if there is missing data in the columns. df.info() can help on this.

>>> df.info()
class pandas.core.frame.dataframe=""
Int64Index: 891 entries, 0 to 890
Data columns (total 12 columns):
PassengerId    891 non-null int64
Survived       891 non-null int64
Pclass         891 non-null int64
Name           891 non-null object
Sex            891 non-null object
Age            714 non-null float64
SibSp          891 non-null int64
Parch          891 non-null int64
Ticket         891 non-null object
Fare           891 non-null float64
Cabin          204 non-null object
Embarked       889 non-null object
dtypes: float64(2), int64(5), object(5)
memory usage: 90.5 KB

There are total 891 rows but Age, Cabin and Embarked has fewer non-null rows, which indicates there is missing data.

Moreover, df.describe() provides basic statistics of the data.

>>> df.describe()
       PassengerId    Survived      Pclass         Age       SibSp  \
count   891.000000  891.000000  891.000000  714.000000  891.000000   
mean    446.000000    0.383838    2.308642   29.699118    0.523008   
std     257.353842    0.486592    0.836071   14.526497    1.102743   
min       1.000000    0.000000    1.000000    0.420000    0.000000   
25%     223.500000    0.000000    2.000000   20.125000    0.000000   
50%     446.000000    0.000000    3.000000   28.000000    0.000000   
75%     668.500000    1.000000    3.000000   38.000000    1.000000   
max     891.000000    1.000000    3.000000   80.000000    8.000000   

            Parch        Fare  
count  891.000000  891.000000  
mean     0.381594   32.204208  
std      0.806057   49.693429  
min      0.000000    0.000000  
25%      0.000000    7.910400  
50%      0.000000   14.454200  
75%      0.000000   31.000000  
max      6.000000  512.329200  

However, since there is missing values in some columns, we need to be careful when we quote the statistics using this method.

Pandas provides handy ways to select and filter data, see the following several examples:

df[list of column names][m:n]: selects n rows from row m with the desired columns.

>>> df[['Name','Pclass']][1:6]
                                                Name  Pclass
1  Cumings, Mrs. John Bradley (Florence Briggs Th...       1
2                             Heikkinen, Miss. Laina       3
3       Futrelle, Mrs. Jacques Heath (Lily May Peel)       1
4                           Allen, Mr. William Henry       3
5                                   Moran, Mr. James       3

df[criteria of df['column name']][list of column names]: filters the row based on the criteria and display the desired columns.

>>> df[df['Age']>60][['Name','Sex','Age']]
                                          Name     Sex   Age
33                       Wheadon, Mr. Edward H    male  66.0
54              Ostby, Mr. Engelhart Cornelius    male  65.0
96                   Goldschmidt, Mr. George B    male  71.0
116                       Connors, Mr. Patrick    male  70.5
170                  Van der hoef, Mr. Wyckoff    male  61.0
252                  Stead, Mr. William Thomas    male  62.0
275          Andrews, Miss. Kornelia Theodosia  female  63.0
280                           Duane, Mr. Frank    male  65.0
326                  Nysveen, Mr. Johan Hansen    male  61.0
438                          Fortune, Mr. Mark    male  64.0
456                  Millet, Mr. Francis Davis    male  65.0
483                     Turkula, Mrs. (Hedwig)  female  63.0
493                    Artagaveytia, Mr. Ramon    male  71.0
545               Nicholson, Mr. Arthur Ernest    male  64.0
555                         Wright, Mr. George    male  62.0
570                         Harris, Mr. George    male  62.0
625                      Sutton, Mr. Frederick    male  61.0
630       Barkworth, Mr. Algernon Henry Wilson    male  80.0
672                Mitchell, Mr. Henry Michael    male  70.0
745               Crosby, Capt. Edward Gifford    male  70.0
829  Stone, Mrs. George Nelson (Martha Evelyn)  female  62.0
851                        Svensson, Mr. Johan    male  74.0

Analyzing the data
Lots of machine learning models only allow for numerical imports. Thus for string type data such as Sex, we need to convert the data to numerical value.

# map female to 0 and male to 1
df['Gender'] = df['Sex'].map({'female': 0, 'male': 1}).astype(int)

the map() function maps all elements in an iterable ('female, 'male' in this example) to a given function (a discrete one here).

Filling the data becomes easier with Pandas because we can use the methods provided in the package. Here we will bin the passengers based on gender and passenger class and fill the missing age based on the median of each bin.

# fill in missing ages
# for each passenger without an age, fill the median age
# of his/her passenger class
median_ages = np.zeros((2,3))
for i in range(0, 2):
    for j in range(0, 3):
        median_ages[i, j] = df[(df['Gender'] == i) &
                               (df['Pclass'] == j + 1)]['Age'].dropna().median()

# create a new column to fill the missing age (for caution)
df['AgeFill'] = df['Age']
# since each column is a pandas data series object, the data cannot be accessed
# by df[2,3], we must provide the label (header) of the the column and use .loc()
# to locate the data e.g., df.loc[0, 'Age']
# or df[row]['header']
for i in range(2):
    for j in range(3):
        df.loc[(df.Age.isnull()) & (df.Gender == i) & (df.Pclass == j + 1),
               'AgeFill'] = median_ages[i, j]

We fill the Embarked based on the most common boarding place. In statistics, mode returns the most frequency element in the data set.

# fill the missing Embarked with the most common boarding place
# mode() returns the mode of the data set, which is the most frequent element in the data
# sometimes multiple values may be returned, thus in order to select the maximum
# use df.mode().iloc[0]
if len(df.Embarked[df.Embarked.isnull()]) > 0:
    df.Embarked[df.Embarked.isnull()] = df.Embarked.dropna().mode().iloc[0]

# returns an enumerate object
# e.g., [(0, 'S'), (1, 'C'),(2, 'Q')]
# Ports = list(enumerate(np.unique(df.Embarked)))
# Set up a dictionary that is an enumerate object of the ports
Ports_dict = {name : i for i, name in list(enumerate(np.unique(df.Embarked)))}
df['EmbarkFill'] = df.Embarked.map(lambda x: Ports_dict[x]).astype(int)

Drop the unwanted columns.

df = df.drop(['PassengerId', 'Name', 'Sex', 'Ticket', 'Cabin', 'Embarked', 'Age'], axis=1)

We need to do the same thing for test data. I will omit that part here, but you can find the full source code on my Github.

Training the model
The model we are going to build is called random forest.  Random forest is an ensemble learning method. It constructs a bag of decision trees at the training time and output the class that is the mode of the classes. The data set for each decision tree is produced(resampled from the original dataset) by bootstrap method.

We use scikit-learn to build the model and predict the data. Since scikit-learn only works with numpy arrays, after we clean the data with Pandas, we need to convert the data to numpy arrays.

# convert the data to numpy array
training_data = df.values
test_data = test_df.values

Then we build a random forest object and train the model.

# train the data using random forest
# n_estimators: number of trees in the forest, this number affects the prediction
forest = RandomForestClassifier(n_estimators=150)
# build the forest
# X: array-like or sparse matrix of shape = [n_samples, n_features]
# y: array-like, shape = [n_samples], target values/class labels
forest = forest.fit(training_data[0::, 1::], training_data[0::, 0])
output = forest.predict(test_data).astype(int)

Write the output to a csv file using Python's csv package.

# write the output to a new csv file
predictions_file = open("predictByRandomForest.csv", 'w')
open_file_object = csv.writer(predictions_file)
open_file_object.writerow(["PassengerId", "Survived"])
open_file_object.writerows(zip(ids, output))
predictions_file.close()

My score is 0.76555 on the leader board, on average, not too bad for the first try.

A few thoughts
Apparently choosing the right model is important, moreover, how to play around with the input parameters are also important(e.g., n_estimators).

For the data, I still need to learn what are the most relevant data for the "best" fit. Sometimes if we include more features, we may get more correct predictions, but it may also cause overfitting problem.

First touch in data science (Titanic project on Kaggle) Part I: a simple model

Right after I became Dr. Young, I decide to pick up the thing I always want to do yet didn't get enough time to work on: machine learning and data analytics.

Kaggle is a great source to start with. Besides the active competitions, they provide several entry-level projects that include tutorials. I start with the first one: Titanic.

The full description can be found here. In short, given the data of 891 passengers and if they have survived or not, predict what sorts of people were likely to survive.

I used Python to finish this project. There are good libraries in Python for data analysis and machine learning. Moreover, I personally think Python is a rather faster language, so it may be more efficient when dealing with large data set.


Understand the data
The first thing to do when start with data science is to read and understand the data. What we want to do is to use the determine which variable(s) is(are) strongly correlated with the ultimate survival. Part of the data is shown in the following figure.

In data science, features indicates the variables that are given in the data. In the Titanic dataset, Pclass, Name, Sex, Age, ..., are all features. labels are the outcome. In this dataset, the labels are survived (1) or not survived(0), and it's a binary class.

When a huge dataset with lots of features are given to you, some features are strongly correlated with the label, some are not. It would be better if more information is provided, however, without that, it is not bad to start with intuition. In the Titanic situation, it is possible that Sex, Age, Pclass are more related compare to say, Embarked (the place where the passenger was boarded).

Reading the data to Python
Python provides libraries to read csv file. Moreover, the numpy library, provides handy functions to analyze the data. The script provides here are in Python 3.4, for script in Python 2.x, see the Kaggle tutorial.

import csv
import numpy as np
training_object = csv.reader(open('/path/train.csv', 'r'))
training_header = training_object.__next__()
# create a numpy multidimensional array object
data = []
for row in training_object:
    data.append(row)
data = np.array(data)

Python has a very interesting way to deal with iterables. For example, data[:2] gives you the first two elements and data[-1] gives you the last element:

 >>> data = [1, 2, 3, 4, 5]  
 >>> data  
 [1, 2, 3, 4, 5]  
 >>> data[:2]  
 [1, 2]  
 >>> data[:-2]  
 [1, 2, 3]  
 >>> data[-1]  
 5  
 >>> data[-2:]  
 [4, 5]  

Analyzing the data
Here we try to build a simple model that assume Fare, Sex and Pclass (passenger class). To see the name of all the features, call training_header:

>>> training_header
['PassengerId', 'Survived', 'Pclass', 'Name', 'Sex', 'Age', 'SibSp', 'Parch', 'Ticket', 'Fare', 'Cabin', 'Embarked']

Since each person paid different fare to board, we need to bin up the fare price so that we can classify the passengers based on the fare bin.
csv reader in Python reads the data default to string, thus we need to convert it to float.

fare_ceiling = 40
# for ticket price higher than 39, it will be set to equal 39
# so that we can set 4 bins with equal size
# i.e., $0-9, $10-19, $20-29, $30-39
data[data[0::, 9].astype(np.float) >= fare_ceiling, 9] = fare_ceiling - 1.0

# basically make 4 equal bins
fare_bracket_size = 10
number_of_price_brackets = fare_ceiling / fare_bracket_size

# np.unique() return an array of unique elements in the object
# get the length of that array
number_of_classes = len(np.unique(data[0::, 2]))

data[0::, 9] indicates from the first row to the last and the 9th column. Numpy has a lovely way to select data. in the above code:

data[data[0::, 9].astype(np.float) >= fare_ceiling, 9]

selects all the rows with the fare (9th column) greater than fare_ceiling.

>>The Numpy.unique() function
This is a very interesting function. I looked at its src because I wanted to see if it uses the brutal iteration way. Apparently it is much smarter. The full source code can be found here. (referred to Codatlas). Here I simplify the implementation for the purpose of explanation.

Transfer the array to Numpy array and flatten the array to one-dimension array.

>>> ar = [1, 1, 2, 3, 3, 3, 2, 2, 2]
>>> ar = np.asanyarray(ar).flatten()
>>> ar
array([1, 1, 2, 3, 3, 3, 2, 2, 2])

Sort the array.

>>> ar.sort()
>>> ar
array([1, 1, 2, 2, 2, 2, 3, 3, 3])

Here comes the interesting part.

>>> aux = ar
>>> flag = np.concatenate(([True], aux[1:] != aux[:-1]))
>>> flag
array([ True, False,  True, False, False, False,  True, False, False], dtype=bool)

If we print aux[1:] and aux[:-1]:

>>> aux[1:]
array([1, 2, 2, 2, 2, 3, 3, 3])
>>> aux[:-1]
array([1, 1, 2, 2, 2, 2, 3, 3])

This operation is similar to shift the array right by one position, if there is no repeated element in the array, aux[1:] != aux[:-1] should return true at any position, otherwise, it will return false at the place with repeated elements.

Generate the return array based on the flag array.

>>> ret = aux[flag]
>>> ret
array([1, 2, 3])

<<Back to Analyzing the data

The next step is to calculate the statistics based on features we have chosen, i.e., for each sex, sum up all the survived people that are in a particular passenger class and fare bin.

# initialize the survival table with all zeros
survival_table = np.zeros((2, number_of_classes, number_of_price_brackets))

for i in range(number_of_classes):
    for j in range(int(number_of_price_brackets)):

        women_only_stats = data[(data[0::, 4] == "female")
                                & (data[0::, 2].astype(np.float) == i+1)  # i starts from 0,
                                # the ith class fare was greater than or equal to the least fare in current bin
                                & (data[0:, 9].astype(np.float) >= j*fare_bracket_size)
                                # fare was less than the least fare in next bin
                                & (data[0:, 9].astype(np.float) < (j+1)*fare_bracket_size), 1]

        men_only_stats = data[(data[0::, 4] != "female")
                              & (data[0::, 2].astype(np.float) == i + 1)
                              & (data[0:,9].astype(np.float) >= j * fare_bracket_size)
                              & (data[0:,9].astype(np.float) < (j + 1) * fare_bracket_size), 1]
        survival_table[0, i, j] = np.mean(women_only_stats.astype(np.float))
        survival_table[1, i, j] = np.mean(men_only_stats.astype(np.float))
# if nobody satisfies the criteria, the table will return a NaN
# since the divisor is zero
survival_table[survival_table != survival_table] = 0

Since Survived only contains 0 and 1, the probability of surviving at given passenger class is calculated by:

sum of survived passenger / total number of passenger

i.e., the mean.

Again, Survived only contains 0 and 1, thus we assume any probability greater than or equal to 0.5 should predict a survival.

# assume any probability >= 0.5 should result in predicting survival
# otherwise not
survival_table[survival_table < 0.5] = 0
survival_table[survival_table >= 0.5] = 1

Predicting the data
Now we need to use the table to predict the test data. We use csv reader to create a new file for writing file.

test_file  =open('/path/test.csv')
test_object = csv.reader(test_file)
test_header = test_object.__next__()
prediction_file = open("/path/genderClassModel.csv", 'w')
p = csv.writer(prediction_file)
p.writerow(["PassengerId", "Survived"])

The original tutorial provided by Kaggle uses a loop to determine if a passenger's fare falls in a certain bin. I personally don't like this way:  it's slow. Alternatively, we can calculate the bin by dividing the fare by fare_bracket_size (10 in this case).

for row in test_object:
    # for each passenger, find the price bin where the passenger
    # belongs to
    try:
        row[8] = float(row[8])
    # if data is missing, bin the fare according Pclass
    except:
        bin_fare = 3 - float(row[1])
        continue
    # assign the passenger to the last bin if the fare he/she paid
    # was greater than the fare ceiling
    if row[8] > fare_ceiling:
        bin_fare = number_of_price_brackets - 1
    else:
        bin_fare = int(row[8] / fare_bracket_size)

    if row[3] == 'female':
        p.writerow([row[0], "%d" %
            int(survival_table[0, float(row[1]) - 1, bin_fare])])
    else:
        p.writerow([row[0], "%d" %
                    int(survival_table[1, float(row[1]) - 1, bin_fare])])



test_file.close()
prediction_file.close()

In the next post, I will talk about using Pandas library to clean the data and use Scikit learn to train a machine learning model for the prediction.

The full src can be found on my Github.

K-means algorithm

K-means is a standard clustering method in machine learning. It aims to partition n observations in d dimension into k clusters in which each observation belongs to the cluster with the nearest mean.

The algorithm provided here uses standard Lloyd's algorithm. It is provided by (not me) Dpark as an example. Dpark is a Python clone of Spark written by a group of enthusiastic developers. Even though Spark now provides PySpark as a Python API for Spark, this project is still an impressive one. Enough credits should be given. :)

Note, this is not a tutorial about Spark or Dpark, for more information about Spark in Pyton, check PySpark doc or Dpark manual (in Chinese).

The original source code is from here.

The Llyord algorithm

• Input: 
• a set of n data points
• initialize randomly k centroids
• Repeat until convergence:
• set point i to the nearest centroid based on Euclidean distance
• update cluster centroid to be the mean of all the points assign to it

The main function

Here are some Spark methods used in the main function, the link on the name of the function directs to PySpark documentation, the second link directs to Dpark src.
textFile(): read file from file system. src
cache(): cache this RDD. src
map(): map the RDD to a new RDD based on the provided function. src
In the K-means implementation:

mappedPoints = points.map(lambda p: (closestCenter(p, centers), (p, 1)))

maps each point to the function closestCenter(p, centers), which assigns the point to the closest center, and return a key-value pair, where the key is the centroid index and the value is the tuple (point, 1), 1 is the count.

reduceByKey(): Merge the values for each key using the input function. src
In the K-means implementation:

mappedPoints.reduceByKey(
                lambda (s1,c1),(s2,c2): (s1+s2,c1+c2)
            )

aggregates the mappedPoints (key-value pair) based on the function (sum(points), sum(count)), and returns (centroid index, (sum of points, sum of counts))

collectAsMap(): return the key-value pair src

if __name__ == '__main__':
    # initialization
    D = 4  # d dimension
    K = 3  # number of clusters
    IT = 10  # number of iterations
    MIN_DIST = 0.01  # threshold for convergence
    # initialize k random centroids
    centers = [Vector([random.random() for j in range(D)]) for i in range(K)]
    # read the data points from file and parse them to vectors
    points = dpark.textFile('kmeans_data.txt').map(parseVector).cache()

    # iteration
    for it in range(IT):
        print 'iteration', it
        # assign each point to the closest centroid
        # return (centroid index, (point, count = 1))
        mappedPoints = points.map(lambda p: (closestCenter(p, centers), (p, 1)))
        # calculate the new center of the points within the cluster
        # reduceByKey() returns (centroid index, (sum of points, sum of counts)
        # then map the output to (centroid index, sum of points/sum of counts)
        # sum of points/sum of counts is the new center of the cluster
        ncenters = mappedPoints.reduceByKey(
                lambda (s1,c1),(s2,c2): (s1+s2,c1+c2)
            ).map(
                lambda (id, (sum, count)): (id, sum/count)
            ).collectAsMap()

        updated = False
        # update the new center
        for i in ncenters:
            # if the distance between the center and the new center is greater
            # than MIN_DIST, update the center to new center
            if centers[i].dist(ncenters[i]) > MIN_DIST:
                centers[i] = ncenters[i]
                updated = True
        # if there is no update, then all points are clustered
        # break the loop
        if not updated:
            break
        print centers

    print 'final', centers

parseVector()

The method first split the line (from the file) by white space then returns a Vector object.

def parseVector(line):
    return Vector(map(float, line.strip().split(' ')))

The Vector class can be found here.

Note: map(function, iterable) from Python
maps every item in an iterable based on the provided function and return a new iterator. In the above function, the splitted line is mapped to float number.



closestCenter()

assign the point to the closest centroid based on the Euclidean distance.

def closestCenter(p, centers):
    bestDist = p.squaredDist(centers[0])
    bestIndex = 0
    for i in range(1, len(centers)):
        d = p.squaredDist(centers[i])
        if d < bestDist:
            bestDist = d
            bestIndex = i
    return bestIndex

squaredDist() is in the Vector class.

Note: zip() from Python
Make an iterator that aggregates each element from each of the iterable. For example, in the squaredDist() method:

 return sum((a-b)*(a-b) for a,b in zip(self.data, o.data))

self.data and o.data are coordinates of points, say (1.0, 2.0, 3.0) and (4.0, 5.0, 6.0), zip function returns an object of ((1.0, 4.0), (2.0, 5.0), (3.0, 6.0))

Mysql note

Not all commands need to be in the same line. For example:

mysql> select 
    -> user();
+----------------+
| user()         |
+----------------+
| root@localhost |
+----------------+
1 row in set (0.00 sec)

If you decide not to execute the command in the process of entering it, type \c to cancel it:

mysql> select 
    -> user()
    -> ,now()
    -> \c
mysql> 

The table that summarizes the meaning of each prompt:

Prompt	Meaning
mysql>	Ready for new command.
->	Waiting for next line of multiple-line command.
'>	Waiting for next line, waiting for completion of a string that began with a single quote (“'”).
">	Waiting for next line, waiting for completion of a string that began with a double quote (“"”).
`>	Waiting for next line, waiting for completion of an identifier that began with a backtick (“`”).
/*>	Waiting for next line, waiting for completion of a comment that began with /*.

Create a table:

mysql> create table pet (name varchar(20), owner varchar(20),
    -> species varchar(20), sex char(1),birth DATE, death DATE);
Query OK, 0 rows affected (0.02 sec)

Use describe to see the information of the table:

describe pet;
+---------+-------------+------+-----+---------+-------+
| Field   | Type        | Null | Key | Default | Extra |
+---------+-------------+------+-----+---------+-------+
| name    | varchar(20) | YES  |     | NULL    |       |
| owner   | varchar(20) | YES  |     | NULL    |       |
| species | varchar(20) | YES  |     | NULL    |       |
| sex     | char(1)     | YES  |     | NULL    |       |
| birth   | date        | YES  |     | NULL    |       |
| death   | date        | YES  |     | NULL    |       |
+---------+-------------+------+-----+---------+-------+
6 rows in set (0.01 sec)

Load data to table:

mysql> load data local infile '/path/pet.txt' into table pet;
Query OK, 8 rows affected, 9 warnings (0.00 sec)
Records: 8  Deleted: 0  Skipped: 0  Warnings: 9

mysql> select * from pet;
+----------+--------+---------+------+------------+------------+
| name     | owner  | species | sex  | birth      | death      |
+----------+--------+---------+------+------------+------------+
| Fluffy   | Harold | cat     | f    | 1993-02-04 | NULL       |
| Claws    | Gwen   | cat     | m    | 1994-03-17 | 0000-00-00 |
| Buffy    | Harold | dog     | f    | 1989-05-13 | NULL       |
| Fang     | Benny  | dog     | m    | 1990-08-27 | NULL       |
| Bowser   | Diane  | dog     | m    | 1979-08-31 | 1995-07-29 |
| Chirpy   | Gwen   | bird    | f    | 1998-09-11 | 0000-00-00 |
| Whistler | Gwen   | bird    | N    | 1997-12-09 | 0000-00-00 |
| Slim     | Benny  | snake   | m    | 1996-04-29 | NULL       |
+----------+--------+---------+------+------------+------------+
8 rows in set (0.00 sec) 

Insert values:

mysql> insert into pet 
    -> values ('Jiemee', 'Shirley','cat','f', '2000-01-20', '2014-10-28');
Query OK, 1 row affected (0.01 sec)

mysql> select * from pet where name = 'Jiemee';
+--------+---------+---------+------+------------+------------+
| name   | owner   | species | sex  | birth      | death      |
+--------+---------+---------+------+------------+------------+
| Jiemee | Shirley | cat     | f    | 2000-01-20 | 2014-10-28 |
+--------+---------+---------+------+------------+------------+
1 row in set (0.00 sec)