Implemented Recommender System of Movie Rating

This blog is about an assignment of Machine Learning course on Coursera by Andrew NG. The assignment is to implement the collaborative filtering learning algorithm and apply it to a dataset of movie rating.
About Dataset
This dataset consists of ratings of 1 to 5. The dataset has 943 users, and 1682 movies.

There are two matrices in the dataset. One is matrix Y (a num_movies x num_users matrix) stores the rating y(i,j) (from 1 to 5). The matrices R is an binary-valued indicator matrix, where R(i,j)=1 if user j gave a rating to movie i, and R(i,j)=0 otherwise. The objective of collaborative filtering is to predict movie ratings for the movies that users have not yes rated, that is, the entries with R(i,j)=0.

The Collaborative filtering learning algorithm
Basic concepts:
1. By grouping similar users, we can perform recommendation based on collaborative filtering.
2. Does not require a lot of information about users & items itself.
3. Based on the history of user-item interactions.

Our objective function is collaborative filtering cost function

Then we need to solve the theta and x that minimize the J. The gradient of J is as below

We can either use gradient descent or other advanced optimization method to obtain the value of theta and x.

Once we get these parameters, we can predict the rating of movies which users do not actually rated.

        y_predict = theta*x

Part of results is as below:

Techniques and Ideas of Sentiment Analysis Based on Text

Sentiment analysis based on text is a multi-disciplinary research area, which involves natural language processing, database, information retrieval, data mining and artificial intellect, etc. The solution of a basic and classic sentiment analysis problem includes following steps:

1) Collect data
Currently, most of researches collect data from blogs, professional comment sites, news sites and some e-commercial sites. Among these products, users comments and blogs are preference for researchers.

2)Pre-processing
Research has been done in finding and telling subjective sentences in plain texts. But most work use existing sentences for classification. However, in order to reduce inference and increase accuracy, pre-processing is necessary.
According to features of different data and algorithms' requirements, pre-processing methods may vary from each other. For ex, stop-words, prefix (or suffix) trimming, part of speech, and necessary simplification and replacement.

3)Extract features
Feature is prerequisite for classification. According to need of classification, the most direct selection is sentimental word, like "Happy", "Good", "Angry" etc. Feature word can be extracted automatically, but sometimes sentiment vocabulary needs manual formulation.

4)Classification
Classification problem are often solved with standard classification algorithm, such as Support Vector Machines, Naive Bayes, etc.

MapReduce Framework to Implement PageRank Algorithm

Pagerank is the famous algorithm for early Google search engine. The best way to grasp the algorithm is getting one's hands dirty and implement the algorithm.

Simple PageRank Model

The simple network doesn't include any dead ends. Our goal is to get the page ranks for each node in the graph. There are two main assumptions of PageRank:

1. The surfer would randomly jump from one node to another node.

2. The page rank of a node is the sum of ranks of all its source nodes.

The second process involves repeating until the ranks converge. We can choose 3 types of stopping criterion.
1. Iterate mapper and reducer for N times. 
2. Repeat until the ranking of top-N nodes doesn't change.
3. Stop the iterative process when the page rank scores for all of the nodes converge (convergence tolerance=0.005)

In this implementation, I choose the 1st criterion as demo.

mapper.py


#!/usr/bin/env python

import sys

if __name__=="__main__":

    for line in sys.stdin:
        node, neighbour, rank = line.split()
        neighbour_list = neighbour.split(",")
        count = len(neighbour_list)
        print '%s\t[%s]' % (node, neighbour)
        for item in neighbour_list:
            print '%s\t%f' % (item,float(rank)/count)


reducer.py

#!/usr/bin/env python

import sys

if __name__=="__main__":
    alpha = 0.85
    cur_key = None
    cur_value = 0
    #count = 575712
    #count = 2
    neighbour = None
    for line in sys.stdin:
        node, value = line.split()
        if node == cur_key:
            if value.find('[')==-1:
                cur_value += float(value)
            else:
                neighbour = value.lstrip('[').rstrip(']')
        else:
            if cur_key:
                print '%s\t%s\t%s' % (cur_key,neighbour,(1-alpha)*cur_value+alpha)
                neighbour = None

            cur_key = node
            if value.find('[')==-1:
                cur_value = float(value)
            else:
                neighbour = value.lstrip('[').rstrip(']')
    print '%s\t%s\t%s' % (cur_key,neighbour,(1-alpha)*cur_value+alpha)

iterate.sh

#!/bin/bash
echo "the 0th job"
hadoop jar $HADOOP_PREFIX/contrib/streaming/hadoop-streaming-1.2.1.jar -D mapred.reduce.tasks=2 -mapper mapper.py -reducer reducer.py -file mapper.py -file reducer.py -input input/processed.graph5 -output output/output0

for i in $(seq 1 1 100)
do
        echo "the $i th job"
        hadoop jar $HADOOP_PREFIX/contrib/streaming/hadoop-streaming-1.2.1.jar -D mapred.reduce.tasks=2 -mapper mapper.py -reducer reducer.py -file mapper.py -file reducer.py -input output/output$(($i-1)) -output output/output$i
        if [ $i -gt 2 ]
        then
                hadoop dfs -rmr output/output$(($i-2))
                echo 'delete unused file to save disk'
        else
                echo 'do not delete'
        fi
done