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

Anonymous Peers Help Making More Money

At the night of 9th September 2014, hundreds and thousands of people sit before their

computers,  waiting for a man and things that he would bring with.  These night owls formed an united group, with their enthusiasm ignited by the belief that their lives would rapidly improve following the live stream.  You may have guessed what I am talking about if you don't stray far from the Internet world. Actually, there is no way for you to escape from buzzes about the Apple Product Launch, no matter the source was your Facebook ,Twitter or other social network platforms.  News media also bombed people with their interpretation and views. 

On the other hand, Apple company are busy with their own issues. Supplying the new iPhones to meet the demands of booming customers is not easy. There are countries and areas who are on the list of first release. Hong Kong was included luckily. However, as Apple's largest market, supply to mainland China was delayed due to license issue. Since residents of China cannot buy iPhones directly through online order (via Hong Kong website), many mobile sale agents from China rushed to Hong Kong to purchase the product in short supply. Due to Hong Kong identity restrict, they can only buy the products from Hong Kong residents. Chinese who are eager to try the new phones must pay much higher price than official one. 

Such panic buying forms a large-scale and short-term market with high returns for people living in Hong Kong. The gap between the prices (one for official buying price and one for your selling price to sale agents) of an iPhone 6 plus can reached 5k ~ 7k HKD. As an individual seller, what I am concerned about is how to determine a price to make a good enough profit?

 This is actually a pricing problem :) 

However, it's not a normal pricing problem for a company to determine the proper price for a product.  There's indeed one product (maybe of limited types, but we'll assume only one). But sellers and buyers are totally isolated from each other in real life. 

As a seller, you want to determine the best price according to the market. In normal product marketing, sellers acquire detailed selling information from vendors,  so they can adjust the price accordingly. But in this iPhone case, one seller are not accessible to the selling information of another directly. Moreover, if the seller goes directly to ask the bid offered by a sale agent, he(she) would probably feel the bid is too low and is reluctant to sell. One can enumerate consulting as many agents as possible. The best outcome is picking the highest price from all bids. Before you make a final deal with the agent, you may reconsider your customer.

Is it a good idea to sell the iPhone to a sale agent? Actually, there are different channels for one to sell his(her) iPhone. The most beneficial way is to sell it to the end user. Taobao.com maybe a good place to sell one's goods,  but in this particular case, face-to-face transaction could be a more safe and convenient approach. Before that, the buyer and seller have to make an agreement on the price. There is actually a website for people to post iPhone's selling price in Hong Kong. http://www.itradephone.com

A seller can refer to others' bidding to determine his price for the iPhone. The virtual market, formed through an online platform, bridges one to other sellers, which in some sense resembles a real-world "single" amalgamate seller.  These anonymous sellers formed tied relationship with same goal.

One can browse through pages of bidding record to choose a price. This method is empirical, and suitable to sellers who want to make quick choice. But let's be a little verbose and technical. If  we assume 10% of bidding price is too high and 10% too low, we can avoid being too optimistic by plotting the distribution of the bidding price from the history records. 

The analytical process can be can be done as follows: 

1. Download the web pages and filter out the pricing data item.

2. Cleaning the data. Flush out the data that's below the Apple's official price, and unqualified input.

3. Process the data items to make a uniform integer type, e.g. 8000 (not 8,000 or 8000HKD)

4. Plot the histogram using python library.

5. Pick out a satisfying price according to the histogram.

The most challenging part is data preprocessing step. I will try to implement the coding in the next blog ;)