ML-2018/lab4.py at master · paydaylight/ML-2018 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

# coding: utf-8

# # kNN Hash Example

# In[183]:


import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from functools import partial
from random import random
from sklearn.preprocessing import MinMaxScaler
from collections import defaultdict
from collections import Counter
import math


# ## Iris dataset

# In[184]:


df = load_iris()
df.data.shape


# In[185]:


def f_hash(w,r,b,x):
    return int((np.dot(w,x)+b)/r)


# * https://docs.python.org/2/library/functools.html Here you can read about "partial"
# * http://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.MinMaxScaler.html About mapping to [0,1]

# In[186]:


def euclidDist(x, y): #function to calculate Euclidean distance
    dist = 0
    for i in range(x.shape[0]):
        dist += math.pow(x[i] - y[0][i], 2)
    return math.sqrt(dist)


# In[190]:


class KNNHash(object):
    def __init__(self,m,L,nn):
        self.m = m
        self.L = L
        self.nn = nn

    def fit(self,X,y):
        self.t_hh = [] #hash table
        for j in range(self.L):
            f_hh = [] #compositional hash function
            for i in range(self.m):
                w = np.random.rand(1,X[0].shape[0]) #  weights of a hash function
                f_hh.append(partial(f_hash,w = w,r=random(),b=random())) # list of initialized hash function
            self.t_hh.append(
                (defaultdict(list),f_hh)
            )
        for n in range(X.shape[0]):
            for j in range(self.L):
                ind = 0
                for i in range(self.m):
                    ind = ind + self.t_hh[j][1][i](x=X[n]) #calculation of index in hash table, simply sum of all hash func
                self.t_hh[j][0][ind].append((X[n],y[n])) #saving sample into corresponding index

    def predict(self,u):
        for j in range(self.L):
            inds = []
            distArr = [] #array of distance
            clss = [] #array of classes
            for i in range(self.m):
                inds.append(self.t_hh[j][1][i](x=u))
            cntr = Counter([outp for inpt,outp in self.t_hh[j][0][sum(inds)]])
            print(cntr)
            for q in self.t_hh[j][0][sum(inds)]:
                distArr.append(euclidDist(u, q)) #appending distArr with distances
                clss.append(q[1]) #appending array of classes
            minInd = distArr.index(min(distArr)) #taking class of minimal distance
            print("min distance: " +  str(min(distArr)))
            print("class: " + str(clss[minInd]))
        print("\n")

            #Here you must put your code, extend the method with distance function and calculation with unknown sample "u"
            #Develop the rest part of kNN predict method that was discussed at the lecture


# In[191]:


scaler = MinMaxScaler()
scaler.fit(df.data)
x = scaler.transform(df.data)
y = df.target


# In[192]:


knnhash = KNNHash(4,4,4)
test1x = x[0]
test2x = x[75]
test3x = x[149]

test1y = y[0]
test2y = y[75]
test3y = y[149]
x = np.delete(x,[0,75,149],axis=0)
y = np.delete(y,[0,75,149],axis=0)

knnhash.fit(x,y)
print("test1y: " + str(test1y))
knnhash.predict(test1x)
print("-------------")
print("test2y: " + str(test2y))
knnhash.predict(test2x)
print("-------------")
print("test3y: " + str(test3y))
knnhash.predict(test3x)


# * Each string above corresponds to the particular hash table. And index in counter maps to the class. For example Counter({0: 13, 1: 1}) means that there are 13 samples close to "u" with "0" class labels and 1 sample with "1" class label.