Elective-I D3 Implement Decision trees on Digital Library Data to mirror more titles (PDF) in the library application ,compare it with Naive Bayes algorithm using python

PROGRAM

filename: b12.py

from __future__ import division
import math,os
from multiprocessing import Process,Queue
#probability for categorical attribute



def info(title):
    print title
    print 'module name:', __name__
    if hasattr(os, 'getppid'):  # only available on Unix
        print 'parent process:', os.getppid()
    print 'process id:', os.getpid()

#print gaussian_dis(30,18,6)
#print categorical_prob(20,[12,10,10,13,14,32,43],len([12,20,10,13,14,32,43]))

def readfile(filename):
 f = open(filename,"r")
 dictionary = {}
 dictionary['age']=[]
 dictionary['income']=[]
 dictionary['student']=[]
 dictionary['credit_rating'] = []
 dictionary['buys_computer'] = []
 for line in f:
  x = line.split(" ")
  dictionary['age'].append(x[0])
  dictionary['income'].append(x[1])
  dictionary['student'].append(x[2])
  dictionary['credit_rating'].append(x[3])
  dictionary['buys_computer'].append(x[4].rstrip())
 return dictionary



def getIncome(q):
    #income
    info('function getIncome')
    income_high_yes = 0
    income_high_no = 0
    income_low_no = 0
    income_low_yes = 0
    income_medium_yes = 0
    income_medium_no = 0
    len_yes=0
    len_no=0
    for x in xrange(tnor):
        if dicti['income'][x]=='high':
            if dicti['buys_computer'][x]=='yes':
                income_high_yes+=1
                len_yes+=1
            else:
                income_high_no+=1
                len_no+=1
        elif dicti['income'][x]=='low':
            if dicti['buys_computer'][x]=='yes':
                income_low_yes+=1
                len_yes+=1
            else:
                income_low_no+=1
                len_no+=1
        else:
            if dicti['buys_computer'][x]=='yes':
                income_medium_yes+=1
                len_yes+=1
            else:
                income_medium_no+=1
                len_no+=1
                
    income_high_yes_prob=income_high_yes/len_yes
    income_high_no_prob=income_high_no/len_no

    income_low_yes_prob=income_low_yes/len_yes
    income_low_no_prob=income_low_no/len_no

    income_medium_yes_prob = income_medium_yes/len_yes
    income_medium_no_prob = income_medium_no/len_no
    q.put([income_high_yes_prob,income_high_no_prob,income_low_yes_prob,income_low_no_prob,income_medium_yes_prob,income_medium_no_prob])


def getCreditRating(q):
    credit_fair_yes = 0
    credit_fair_no = 0
    credit_exc_yes = 0
    credit_exc_no = 0
    len_yes=0
    len_no=0
    for x in xrange(tnor):
        if dicti['credit_rating'][x]=='excellent':
            if dicti['buys_computer'][x]=='yes':
                    credit_exc_yes+=1
                    len_yes+=1
            else:
                    credit_exc_no+=1
                    len_no+=1    
        else:
            if dicti['buys_computer'][x]=='yes':
                    credit_fair_yes+=1
                    len_yes+=1
            else:
                    credit_fair_no+=1
                    len_no+=1    
    credit_fair_yes_prob = credit_fair_yes/len_yes
    credit_exec_yes_prob = credit_exc_yes/len_yes
    credit_fair_no_prob = credit_fair_no/len_no
    credit_exec_no_prob = credit_exc_no/len_no
    q.put([credit_fair_yes_prob,credit_fair_no_prob,credit_exec_yes_prob,credit_exec_no_prob])


def getStudentStatus(q):
    #student
    info('function getStudentStatus')
    studno_yes = 0
    studyes_yes = 0
    studno_no = 0
    studyes_no = 0
    len_yes=0
    len_no=0
    for x in xrange(tnor):
        if dicti['student'][x]=='no':
            if dicti['buys_computer'][x]=='yes':
                    studno_yes+=1
                    len_yes+=1
            else:
                    studno_no+=1
                    len_no+=1    
        else:
            if dicti['buys_computer'][x]=='yes':
                    studyes_yes+=1
                    len_yes+=1
            else:
                    studyes_no+=1
                    len_no+=1    
    studyes_yes_prob = studyes_yes/len_yes
    studyes_no_prob = studyes_no/len_no
    studno_yes_prob = studno_yes/len_yes
    studno_no_prob = studno_no/len_no
    q.put([studyes_yes_prob,studyes_no_prob,studno_yes_prob,studno_no_prob])

if __name__ == '__main__':
    dicti = readfile("data_nb.txt")
    print dicti

    #Total number of rows in the record
    tnor = len(dicti['buys_computer'])

    aprior_num_yes = 0
    for x in dicti['buys_computer']:
     if x=='yes':
      aprior_num_yes+=1

    print len(dicti['buys_computer'])
    aprior_yes = aprior_num_yes/len(dicti['buys_computer'])
    #print aprior_yes
    aprior_no = (len(dicti['buys_computer'])-aprior_yes)/len(dicti['buys_computer'])

    yes_total_prob = 1
    no_total_prob = 1

    info('main line')
    q = Queue()
    p = []
    p1 = Process(target=getIncome, args=(q,))
    p2 = Process(target=getStudentStatus,args=(q,))
    p3 = Process(target=getCreditRating,args=(q,))
    p.append(p1)
    p.append(p2)
    p.append(p3)
    process_output = []
    for x in p:
        x.start()
        process_output.append(q.get())
    for x in p:
        x.join()
    income_high_yes_prob = process_output[0][0]
    income_high_no_prob = process_output[0][1]
    income_medium_yes_prob = process_output[0][2]
    income_medium_no_prob = process_output[0][3]
    income_low_yes_prob = process_output[0][4]
    income_low_no_prob = process_output[0][5]

    studyes_yes_prob = process_output[1][0]
    studyes_no_prob = process_output[1][1]
    studno_yes_prob = process_output[1][2]
    studno_no_prob = process_output[1][3]

    credit_fair_yes_prob = process_output[2][0] 
    credit_fair_no_prob = process_output[2][1]
    credit_exec_yes_prob = process_output[2][2]
    credit_exec_no_prob = process_output[2][3]


    income_x = raw_input("Enter the income:\n>")
    credit_x = raw_input("Enter the credit rating:\n>")
    stud_x = raw_input("Enter the student status:\n>")

    if income_x=='high':
        yes_total_prob*=income_high_yes_prob
        no_total_prob*=income_high_no_prob
    elif income_x=='medium':
        yes_total_prob*=income_medium_yes_prob
        no_total_prob*=income_medium_no_prob
    else:
        yes_total_prob*=income_low_yes_prob
        no_total_prob*=income_low_no_prob

    if credit_x=='fair':
        yes_total_prob*=credit_fair_yes_prob
        no_total_prob*=credit_fair_no_prob
    else:
        yes_total_prob*=credit_exec_yes_prob
        no_total_prob*=credit_exec_no_prob    

    if stud_x=='yes':
        yes_total_prob*=studyes_yes_prob
        no_total_prob*=studyes_no_prob
    else:
        yes_total_prob*=studno_yes_prob
        no_total_prob*=studno_no_prob



    print "No Probablility: "+str(no_total_prob)
    print "Yes Probability: "+str(yes_total_prob)
    if no_total_prob>yes_total_prob:
        print "NO"
    else:
        print "YES"    
        

filename: data_nb.txt

10 high no fair no
12 high no excellent no
32 high no fair yes
64 medium no fair yes
65 low yes fair yes
60 low yes excellent no
37 low yes excellent yes
18 medium no fair no
16 low yes fair yes
69 medium yes fair yes
15 medium yes excellent yes
36 medium no excellent yes
31 high yes fair yes
70 medium no excellent no

OUTPUT

ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$python b12.py
{'credit_rating': ['fair', 'excellent', 'fair', 'fair', 'fair', 'excellent', 'excellent', 'fair', 'fair', 'fair', 'excellent', 'excellent', 'fair', 'excellent'], 'buys_computer': ['no', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'no'], 'age': ['10', '12', '32', '64', '65', '60', '37', '18', '16', '69', '15', '36', '31', '70'], 'student': ['no', 'no', 'no', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'no'], 'income': ['high', 'high', 'high', 'medium', 'low', 'low', 'low', 'medium', 'low', 'medium', 'medium', 'medium', 'high', 'medium']}
14
main line
module name: __main__
parent process: 4406
process id: 4594
function getIncome
module name: __main__
parent process: 4594
process id: 4595
function getStudentStatus
module name: __main__
parent process: 4594
process id: 4596
Enter the income:
>high
Enter the credit rating:
>fair
Enter the student status:
>no
No Probablility: 0.128
Yes Probability: 0.0493827160494
NO

Implement Apriori approach for datamining to organize the data items on a shelf using the dataset.csv file of items purchased in a Mall by using Python

PROGRAM

filename: apriori.py

from collections import defaultdict

def readFile(fn):
 f = open(fn,"r")
 for line in f:
  line = line.strip().rstrip(",")
  record = frozenset(line.split(','))
  yield record

def returnItemSetTL(data_iter):
 _itemSet = set()
 TransactionList = []
 for record in data_iter:
  trans = frozenset(record)
  TransactionList.append(trans)
  for item in trans:
   _itemSet.add(frozenset([item]))
 return _itemSet,TransactionList 

def returnItemWithMinSupport(itemSet,TransactionList,ms,freqSet):
 localSet = defaultdict(int)
 _itemSet = set()
 for item in itemSet:
  for trans in TransactionList:
   if item.issubset(trans):
    localSet[item]+=1
    freqSet[item]+=1
 for item,count in localSet.items():
  support = float(count)/float(len(TransactionList))
  if support>=minSupport:
   _itemSet.add(item)
 return _itemSet    

def joinSet(itemSet,length):
 return set([i.union(j) for i in itemSet for j in itemSet if len(i.union(j))==length])

def getSupport(freqSet,item,TransactionList):
 return float(freqSet[item])/float(len(TransactionList))

def runApriori(data_iter,ms,mc):
 itemSet,TransactionList = returnItemSetTL(data_iter)

 freqSet = defaultdict(int)
 largeSet = {}
 oneCSet = returnItemWithMinSupport(itemSet,TransactionList,ms,freqSet)
 k=2
 currentLSet = oneCSet
 print "L1"
 print currentLSet
 while(currentLSet!=set([])):
  largeSet[k-1]=currentLSet
  currentLSet = joinSet(currentLSet,k)
  print "L",k
  print currentLSet
  currentCSet = returnItemWithMinSupport(currentLSet,TransactionList,ms,freqSet)
  currentLSet = currentCSet
  k+=1
 items = []
 for key,value in largeSet.items():
  items.extend([(tuple(item),getSupport(freqSet,item,TransactionList)) for item in value])
 print items
 max_value = 0
 for item,support in sorted(items,key=lambda(item,support):support):
  if max_value<len(item):
   max_value=len(item)
 for item,support in sorted(items,key=lambda(item,support):support):
  if max_value==len(item):
    print item


if __name__=='__main__':
 inFile = readFile("dataset.csv")
 minSupport = 0.6
 minConfidence = 1
 runApriori(inFile,minSupport,minConfidence)


filename: dataset.csv

Mango,Onion,Jar,Keychain,Eggs,Chocolate
Nuts,Onion,Jar,Keychain,Eggs,Chocolate
Mango,Apple,Keychain,Eggs
Mango,Toothbrush,Corn,Keychain,Chocolate
Corn,Onion,Onion,Keychain,Knife,Eggs

OUTPUT

Ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$python apriori.py
L1
set([frozenset(['Onion']), frozenset(['Chocolate']), frozenset(['Keychain']), frozenset(['Eggs']), frozenset(['Mango'])])
L 2
set([frozenset(['Mango', 'Keychain']), frozenset(['Eggs', 'Onion']), frozenset(['Onion', 'Chocolate']), frozenset(['Mango', 'Chocolate']), frozenset(['Keychain', 'Chocolate']), frozenset(['Eggs', 'Chocolate']), frozenset(['Keychain', 'Onion']), frozenset(['Mango', 'Onion']), frozenset(['Eggs', 'Keychain']), frozenset(['Eggs', 'Mango'])])
L 3
set([frozenset(['Eggs', 'Keychain', 'Onion']), frozenset(['Eggs', 'Keychain', 'Chocolate']), frozenset(['Mango', 'Keychain', 'Chocolate']), frozenset(['Mango', 'Keychain', 'Onion']), frozenset(['Eggs', 'Mango', 'Keychain']), frozenset(['Keychain', 'Onion', 'Chocolate'])])
L 4
set([])
[(('Onion',), 0.6), (('Chocolate',), 0.6), (('Keychain',), 1.0), (('Eggs',), 0.8), (('Mango',), 0.6), (('Eggs', 'Keychain'), 0.8), (('Mango', 'Keychain'), 0.6), (('Eggs', 'Onion'), 0.6), (('Keychain', 'Onion'), 0.6), (('Keychain', 'Chocolate'), 0.6), (('Eggs', 'Keychain', 'Onion'), 0.6)]
('Eggs', 'Keychain', 'Onion')

0-1 knapsack problem using branch and bound

How to find bound for every node for 0/1 Knapsack? 
The idea is to use the fact that the Greedy approach provides the best solution for Fractional Knapsack problem.
To check if a particular node can give us a better solution or not, we compute the optimal solution (through the node) using Greedy approach. If the solution computed by Greedy approach itself is more than the best so far, then we can’t get a better solution through the node.

Complete Algorithm:

1.      Sort all items in decreasing order of ratio of value per unit weight so that an upper bound can be computed using Greedy Approach.

2.      Initialize maximum profit, maxProfit = 0

3.      Create an empty queue, Q.

4.      Create a dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node are 0.

5.      Do following while Q is not empty.

§  Extract an item from Q. Let the extracted item be u.

§  Compute profit of next level node. If the profit is more than maxProfit, then update maxProfit.

§  Compute bound of next level node. If bound is more than maxProfit, then add next level node to Q.

§  Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes.

Following is C++ implementation of above idea.

// C++ program to solve knapsack problem using // branch and bound #include <bits/stdc++.h> using namespace std; // Structure for Item which store weight and corresponding // value of Item struct Item {     float weight;     int value; }; // Node structure to store information of decision // tree struct Node {     // level  --> Level of node in decision tree (or index     //             in arr[]     // profit --> Profit of nodes on path from root to this     //            node (including this node)     // bound ---> Upper bound of maximum profit in subtree     //            of this node/     int level, profit, bound;     float weight; }; // Comparison function to sort Item according to // val/weight ratio bool cmp(Item a, Item b) {     double r1 = (double)a.value / a.weight;     double r2 = (double)b.value / b.weight;     return r1 > r2; } // Returns bound of profit in subtree rooted with u. // This function mainly uses Greedy solution to find // an upper bound on maximum profit. int bound(Node u, int n, int W, Item arr[]) {     // if weight overcomes the knapsack capacity, return     // 0 as expected bound     if (u.weight >= W)         return 0;     // initialize bound on profit by current profit     int profit_bound = u.profit;     // start including items from index 1 more to current     // item index     int j = u.level + 1;     int totweight = u.weight;     // checking index condition and knapsack capacity     // condition     while ((j < n) && (totweight + arr[j].weight <= W))     {         totweight    += arr[j].weight;         profit_bound += arr[j].value;         j++;     }     // If k is not n, include last item partially for     // upper bound on profit     if (j < n)         profit_bound += (W - totweight) * arr[j].value /                                          arr[j].weight;     return profit_bound; } // Returns maximum profit we can get with capacity W int knapsack(int W, Item arr[], int n) {     // sorting Item on basis of value per unit     // weight.     sort(arr, arr + n, cmp);     // make a queue for traversing the node     queue<Node> Q;     Node u, v;     // dummy node at starting     u.level = -1;     u.profit = u.weight = 0;     Q.push(u);     // One by one extract an item from decision tree     // compute profit of all children of extracted item     // and keep saving maxProfit     int maxProfit = 0;     while (!Q.empty())     {         // Dequeue a node         u = Q.front();         Q.pop();         // If it is starting node, assign level 0         if (u.level == -1)             v.level = 0;         // If there is nothing on next level         if (u.level == n-1)             continue;         // Else if not last node, then increment level,         // and compute profit of children nodes.         v.level = u.level + 1;         // Taking current level's item add current         // level's weight and value to node u's         // weight and value         v.weight = u.weight + arr[v.level].weight;         v.profit = u.profit + arr[v.level].value;         // If cumulated weight is less than W and         // profit is greater than previous profit,         // update maxprofit         if (v.weight <= W && v.profit > maxProfit)             maxProfit = v.profit;         // Get the upper bound on profit to decide         // whether to add v to Q or not.         v.bound = bound(v, n, W, arr);         // If bound value is greater than profit,         // then only push into queue for further         // consideration         if (v.bound > maxProfit)             Q.push(v);         // Do the same thing,  but Without taking         // the item in knapsack         v.weight = u.weight;         v.profit = u.profit;         v.bound = bound(v, n, W, arr);         if (v.bound > maxProfit)             Q.push(v);     }     return maxProfit; } // driver program to test above function int main() {     int W = 10;   // Weight of knapsack     Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},                   {5, 95}, {3, 30}};     int n = sizeof(arr) / sizeof(arr[0]);     cout << "Maximum possible profit = "          << knapsack(W, arr, n);     return 0; }