"""A data set for a machine learning problem. It has the following fields:

def __init__(self, examples=None, attrs=None, attrnames=None, target=-1,

inputs=None, values=None, distance=mean_boolean_error,

name='', source='', exclude=()):

"""Accepts any of DataSet's fields. Examples can also be a

self.name = name

self.source = source

self.values = values

self.distance = distance

self.got_values_flag = bool(values)

# Initialize .examples from string or list or data directory

if isinstance(examples, str):

self.examples = parse_csv(examples)

else:

self.examples = examples or parse_csv(open_data(name + '.csv').read())

# Attrs are the indices of examples, unless otherwise stated.

if self.examples and not attrs:

attrs = list(range(len(self.examples[0])))

self.attrs = attrs

# Initialize .attrnames from string, list, or by default

if isinstance(attrnames, str):

self.attrnames = attrnames.split()

else:

self.attrnames = attrnames or attrs

self.setproblem(target, inputs=inputs, exclude=exclude)

def setproblem(self, target, inputs=None, exclude=()):

"""Set (or change) the target and/or inputs.

self.target = self.attrnum(target)

exclude = list(map(self.attrnum, exclude))

if inputs:

self.inputs = removeall(self.target, inputs)

else:

self.inputs = [a for a in self.attrs

if a != self.target and a not in exclude]

if not self.values:

self.update_values()

self.check_me()

def check_me(self):

"""Check that my fields make sense."""

assert len(self.attrnames) == len(self.attrs)

assert self.target in self.attrs

assert self.target not in self.inputs

assert set(self.inputs).issubset(set(self.attrs))

if self.got_values_flag:

# only check if values are provided while initializing DataSet

list(map(self.check_example, self.examples))

def add_example(self, example):

"""Add an example to the list of examples, checking it first."""

self.check_example(example)

self.examples.append(example)

def check_example(self, example):

"""Raise ValueError if example has any invalid values."""

if self.values:

for a in self.attrs:

if example[a] not in self.values[a]:

raise ValueError('Bad value {} for attribute {} in {}'

.format(example[a], self.attrnames[a], example))

def attrnum(self, attr):

"""Returns the number used for attr, which can be a name, or -n .. n-1."""

if isinstance(attr, str):

return self.attrnames.index(attr)

elif attr < 0:

return len(self.attrs) + attr

else:

return attr

def update_values(self):

self.values = list(map(unique, zip(*self.examples)))

def sanitize(self, example):

"""Return a copy of example, with non-input attributes replaced by None."""

return [attr_i if i in self.inputs else None

for i, attr_i in enumerate(example)]

def classes_to_numbers(self, classes=None):

"""Converts class names to numbers."""

if not classes:

# If classes were not given, extract them from values

classes = sorted(self.values[self.target])

for item in self.examples:

item[self.target] = classes.index(item[self.target])

def remove_examples(self, value=""):

"""Remove examples that contain given value."""

self.examples = [x for x in self.examples if value not in x]

self.update_values()

def split_values_by_classes(self):

"""Split values into buckets according to their class."""

buckets = defaultdict(lambda: [])

target_names = self.values[self.target]

for v in self.examples:

item = [a for a in v if a not in target_names] # Remove target from item

buckets[v[self.target]].append(item) # Add item to bucket of its class

return buckets

def find_means_and_deviations(self):

"""Finds the means and standard deviations of self.dataset.

target_names = self.values[self.target]

feature_numbers = len(self.inputs)

item_buckets = self.split_values_by_classes()

means = defaultdict(lambda: [0] * feature_numbers)

deviations = defaultdict(lambda: [0] * feature_numbers)

for t in target_names:

# Find all the item feature values for item in class t

features = [[] for i in range(feature_numbers)]

for item in item_buckets[t]:

for i in range(feature_numbers):

features[i].append(item[i])

# Calculate means and deviations fo the class

for i in range(feature_numbers):

means[t][i] = mean(features[i])

deviations[t][i] = stdev(features[i])

return means, deviations

def __repr__(self):

return '<DataSet({}): {:d} examples, {:d} attributes>'.format(

r"""Input is a string consisting of lines, each line has comma-delimited

lines = [line for line in input.splitlines() if line.strip()]

"""A probability distribution formed by observing and counting examples.

def __init__(self, observations=None, default=0):

"""Create a distribution, and optionally add in some observations.

if observations is None:

observations = []

self.dictionary = {}

self.n_obs = 0

self.default = default

self.sampler = None

for o in observations:

self.add(o)

def add(self, o):

"""Add an observation o to the distribution."""

self.smooth_for(o)

self.dictionary[o] += 1

self.n_obs += 1

self.sampler = None

def smooth_for(self, o):

"""Include o among the possible observations, whether or not

if o not in self.dictionary:

self.dictionary[o] = self.default

self.n_obs += self.default

self.sampler = None

def __getitem__(self, item):

"""Return an estimate of the probability of item."""

self.smooth_for(item)

return self.dictionary[item] / self.n_obs

# (top() and sample() are not used in this module, but elsewhere.)

def top(self, n):

"""Return (count, obs) tuples for the n most frequent observations."""

return heapq.nlargest(n, [(v, k) for (k, v) in self.dictionary.items()])

def sample(self):

"""Return a random sample from the distribution."""

if self.sampler is None:

self.sampler = weighted_sampler(list(self.dictionary.keys()),

list(self.dictionary.values()))

"""A very dumb algorithm: always pick the result that was most popular

most_popular = mode([e[dataset.target] for e in dataset.examples])

def predict(example):

"""Always return same result: the most popular from the training set."""

return most_popular

if simple:

return NaiveBayesSimple(dataset)

if continuous:

return NaiveBayesContinuous(dataset)

else:

"""A simple naive bayes classifier that takes as input a dictionary of

target_dist = {c_name: prob for c_name, prob in distribution.keys()}

attr_dists = {c_name: count_prob for (c_name, _), count_prob in distribution.items()}

def predict(example):

"""Predict the target value for example. Calculate probabilities for each

def class_probability(targetval):

attr_dist = attr_dists[targetval]

return target_dist[targetval] * product(attr_dist[a] for a in example)

return argmax(target_dist.keys(), key=class_probability)

"""Just count how many times each value of each input attribute

target_vals = dataset.values[dataset.target]

target_dist = CountingProbDist(target_vals)

attr_dists = {(gv, attr): CountingProbDist(dataset.values[attr])

for gv in target_vals

for attr in dataset.inputs}

for example in dataset.examples:

targetval = example[dataset.target]

target_dist.add(targetval)

for attr in dataset.inputs:

attr_dists[targetval, attr].add(example[attr])

def predict(example):

"""Predict the target value for example. Consider each possible value,

def class_probability(targetval):

return (target_dist[targetval] *

product(attr_dists[targetval, attr][example[attr]]

for attr in dataset.inputs))

return argmax(target_vals, key=class_probability)

"""Count how many times each target value occurs.

means, deviations = dataset.find_means_and_deviations()

target_vals = dataset.values[dataset.target]

target_dist = CountingProbDist(target_vals)

def predict(example):

"""Predict the target value for example. Consider each possible value,

def class_probability(targetval):

prob = target_dist[targetval]

for attr in dataset.inputs:

prob *= gaussian(means[targetval][attr], deviations[targetval][attr], example[attr])

return prob

return argmax(target_vals, key=class_probability)

"""k-NearestNeighbor: the k nearest neighbors vote."""

def predict(example):

"""Find the k closest items, and have them vote for the best."""

best = heapq.nsmallest(k, ((dataset.distance(e, example), e)

for e in dataset.examples))

return mode(e[dataset.target] for (d, e) in best)

"""Compute the first component of SVD."""

def normalize_vec(X, n=2):

"""Normalize two parts (:m and m:) of the vector."""

X_m = X[:m]

X_n = X[m:]

norm_X_m = norm(X_m, n)

Y_m = [x/norm_X_m for x in X_m]

norm_X_n = norm(X_n, n)

Y_n = [x/norm_X_n for x in X_n]

return Y_m + Y_n

def remove_component(X):

"""Remove components of already obtained eigen vectors from X."""

X_m = X[:m]

X_n = X[m:]

for eivec in eivec_m:

coeff = dotproduct(X_m, eivec)

X_m = [x1 - coeff*x2 for x1, x2 in zip(X_m, eivec)]

for eivec in eivec_n:

coeff = dotproduct(X_n, eivec)

X_n = [x1 - coeff*x2 for x1, x2 in zip(X_n, eivec)]

return X_m + X_n

m, n = len(X), len(X[0])

A = [[0]*(n+m) for _ in range(n+m)]

for i in range(m):

for j in range(n):

A[i][m+j] = A[m+j][i] = X[i][j]

eivec_m = []

eivec_n = []

eivals = []

for _ in range(num_val):

X = [random.random() for _ in range(m+n)]

X = remove_component(X)

X = normalize_vec(X)

for i in range(max_iter):

old_X = X

X = matrix_multiplication(A, [[x] for x in X])

X = [x[0] for x in X]

X = remove_component(X)

X = normalize_vec(X)

# check for convergence

if norm([x1 - x2 for x1, x2 in zip(old_X, X)]) <= 1e-10:

break

projected_X = matrix_multiplication(A, [[x] for x in X])

projected_X = [x[0] for x in projected_X]

eivals.append(norm(projected_X, 1)/norm(X, 1))

eivec_m.append(X[:m])

eivec_n.append(X[m:])

"""A fork of a decision tree holds an attribute to test, and a dict

def __init__(self, attr, attrname=None, default_child=None, branches=None):

"""Initialize by saying what attribute this node tests."""

self.attr = attr

self.attrname = attrname or attr

self.default_child = default_child

self.branches = branches or {}

def __call__(self, example):

"""Given an example, classify it using the attribute and the branches."""

attrvalue = example[self.attr]

if attrvalue in self.branches:

return self.branches[attrvalue](example)

else:

# return default class when attribute is unknown

return self.default_child(example)

def add(self, val, subtree):

"""Add a branch. If self.attr = val, go to the given subtree."""

self.branches[val] = subtree

def display(self, indent=0):

name = self.attrname

print('Test', name)

for (val, subtree) in self.branches.items():

print(' ' * 4 * indent, name, '=', val, '==>', end=' ')

subtree.display(indent + 1)

print() # newline

def __repr__(self):

return ('DecisionFork({0!r}, {1!r}, {2!r})'

"""A leaf of a decision tree holds just a result."""

def __init__(self, result):

self.result = result

def __call__(self, example):

return self.result

def display(self, indent=0):

print('RESULT =', self.result)

def __repr__(self):

"""[Figure 18.5]"""

target, values = dataset.target, dataset.values

def decision_tree_learning(examples, attrs, parent_examples=()):

if len(examples) == 0:

return plurality_value(parent_examples)

elif all_same_class(examples):

return DecisionLeaf(examples[0][target])

elif len(attrs) == 0:

return plurality_value(examples)

else:

A = choose_attribute(attrs, examples)

tree = DecisionFork(A, dataset.attrnames[A], plurality_value(examples))

for (v_k, exs) in split_by(A, examples):

subtree = decision_tree_learning(

exs, removeall(A, attrs), examples)

tree.add(v_k, subtree)

return tree

def plurality_value(examples):

"""Return the most popular target value for this set of examples.

popular = argmax_random_tie(values[target],

key=lambda v: count(target, v, examples))

return DecisionLeaf(popular)

def count(attr, val, examples):

"""Count the number of examples that have example[attr] = val."""

return sum(e[attr] == val for e in examples)

def all_same_class(examples):

"""Are all these examples in the same target class?"""

class0 = examples[0][target]

return all(e[target] == class0 for e in examples)

def choose_attribute(attrs, examples):

"""Choose the attribute with the highest information gain."""

return argmax_random_tie(attrs,

key=lambda a: information_gain(a, examples))

def information_gain(attr, examples):

"""Return the expected reduction in entropy from splitting by attr."""

def I(examples):

return information_content([count(target, v, examples)

for v in values[target]])

N = len(examples)

remainder = sum((len(examples_i)/N) * I(examples_i)

for (v, examples_i) in split_by(attr, examples))

return I(examples) - remainder

def split_by(attr, examples):

"""Return a list of (val, examples) pairs for each val of attr."""

return [(v, [e for e in examples if e[attr] == v])

for v in values[attr]]

"""An ensemble of Decision Trees trained using bagging and feature bagging."""

def data_bagging(dataset, m=0):

"""Sample m examples with replacement"""

n = len(dataset.examples)

return weighted_sample_with_replacement(m or n, dataset.examples, [1]*n)

def feature_bagging(dataset, p=0.7):

"""Feature bagging with probability p to retain an attribute"""

inputs = [i for i in dataset.inputs if probability(p)]

return inputs or dataset.inputs

def predict(example):

print([predictor(example) for predictor in predictors])

return mode(predictor(example) for predictor in predictors)

predictors = [DecisionTreeLearner(DataSet(examples=data_bagging(dataset),

attrs=dataset.attrs,

attrnames=dataset.attrnames,

target=dataset.target,

inputs=feature_bagging(dataset))) for _ in range(n)]

"""[Figure 18.11]"""

def decision_list_learning(examples):

if not examples:

return [(True, False)]

t, o, examples_t = find_examples(examples)

if not t:

raise Exception

return [(t, o)] + decision_list_learning(examples - examples_t)

def find_examples(examples):

"""Find a set of examples that all have the same outcome under

raise NotImplementedError

def passes(example, test):

"""Does the example pass the test?"""

raise NotImplementedError

def predict(example):

"""Predict the outcome for the first passing test."""

for test, outcome in predict.decision_list:

if passes(example, test):

return outcome

predict.decision_list = decision_list_learning(set(dataset.examples))

learning_rate=0.01, epochs=100):

"""Layered feed-forward network.

hidden_layer_sizes = hidden_layer_sizes or [3] # default value

i_units = len(dataset.inputs)

o_units = len(dataset.values[dataset.target])

# construct a network

raw_net = network(i_units, hidden_layer_sizes, o_units)

learned_net = BackPropagationLearner(dataset, raw_net,

learning_rate, epochs)

def predict(example):

# Input nodes

i_nodes = learned_net[0]

# Activate input layer

for v, n in zip(example, i_nodes):

n.value = v

# Forward pass

for layer in learned_net[1:]:

for node in layer:

inc = [n.value for n in node.inputs]

in_val = dotproduct(inc, node.weights)

node.value = node.activation(in_val)

# Hypothesis

o_nodes = learned_net[-1]

prediction = find_max_node(o_nodes)

return prediction

"""[Figure 18.23] The back-propagation algorithm for multilayer networks"""

# Initialise weights

for layer in net:

for node in layer:

node.weights = random_weights(min_value=-0.5, max_value=0.5,

num_weights=len(node.weights))

examples = dataset.examples

'''

o_nodes = net[-1]

i_nodes = net[0]

o_units = len(o_nodes)

idx_t = dataset.target

idx_i = dataset.inputs

n_layers = len(net)

inputs, targets = init_examples(examples, idx_i, idx_t, o_units)

for epoch in range(epochs):

# Iterate over each example

for e in range(len(examples)):

i_val = inputs[e]

t_val = targets[e]

# Activate input layer

for v, n in zip(i_val, i_nodes):

n.value = v

# Forward pass

for layer in net[1:]:

for node in layer:

inc = [n.value for n in node.inputs]

in_val = dotproduct(inc, node.weights)

node.value = node.activation(in_val)

# Initialize delta

delta = [[] for _ in range(n_layers)]

# Compute outer layer delta

# Error for the MSE cost function

err = [t_val[i] - o_nodes[i].value for i in range(o_units)]

# The activation function used is the sigmoid function

delta[-1] = [sigmoid_derivative(o_nodes[i].value) * err[i] for i in range(o_units)]

# Backward pass

h_layers = n_layers - 2

for i in range(h_layers, 0, -1):

layer = net[i]

h_units = len(layer)

nx_layer = net[i+1]

# weights from each ith layer node to each i + 1th layer node

w = [[node.weights[k] for node in nx_layer] for k in range(h_units)]

delta[i] = [sigmoid_derivative(layer[j].value) * dotproduct(w[j], delta[i+1])

for j in range(h_units)]

# Update weights

for i in range(1, n_layers):

layer = net[i]

inc = [node.value for node in net[i-1]]

units = len(layer)

for j in range(units):

layer[j].weights = vector_add(layer[j].weights,

scalar_vector_product(

learning_rate * delta[i][j], inc))

"""Logistic Regression, NO hidden layer"""

i_units = len(dataset.inputs)

o_units = len(dataset.values[dataset.target])

hidden_layer_sizes = []

raw_net = network(i_units, hidden_layer_sizes, o_units)

learned_net = BackPropagationLearner(dataset, raw_net, learning_rate, epochs)

def predict(example):

o_nodes = learned_net[1]

# Forward pass

for node in o_nodes:

in_val = dotproduct(example, node.weights)

node.value = node.activation(in_val)

# Hypothesis

return find_max_node(o_nodes)

"""Single Unit of Multiple Layer Neural Network

def __init__(self, weights=None, inputs=None):

self.weights = weights or []

self.inputs = inputs or []

self.value = None

"""Create Directed Acyclic Network of given number layers.

# Check for PerceptronLearner

if hidden_layer_sizes:

layers_sizes = [input_units] + hidden_layer_sizes + [output_units]

else:

layers_sizes = [input_units] + [output_units]

net = [[NNUnit() for n in range(size)]

for size in layers_sizes]

n_layers = len(net)

# Make Connection

for i in range(1, n_layers):

for n in net[i]:

for k in net[i-1]:

n.inputs.append(k)

n.weights.append(0)

inputs = {}

targets = {}

for i in range(len(examples)):

e = examples[i]

# Input values of e

inputs[i] = [e[i] for i in idx_i]

if o_units > 1:

# One-Hot representation of e's target

t = [0 for i in range(o_units)]

t[e[idx_t]] = 1

targets[i] = t

else:

# Target value of e

targets[i] = [e[idx_t]]

"""Define with learner = LinearLearner(data); infer with learner(x)."""

idx_i = dataset.inputs

idx_t = dataset.target # As of now, dataset.target gives only one index.

examples = dataset.examples

num_examples = len(examples)

# X transpose

X_col = [dataset.values[i] for i in idx_i] # vertical columns of X

# Add dummy

ones = [1 for _ in range(len(examples))]

X_col = [ones] + X_col

# Initialize random weigts

num_weights = len(idx_i) + 1

w = random_weights(min_value=-0.5, max_value=0.5, num_weights=num_weights)

for epoch in range(epochs):

err = []

# Pass over all examples

for example in examples:

x = [1] + example

y = dotproduct(w, x)

t = example[idx_t]

err.append(t - y)

# update weights

for i in range(len(w)):

w[i] = w[i] + learning_rate * (dotproduct(err, X_col[i]) / num_examples)

def predict(example):

x = [1] + example

return dotproduct(w, x)

"""Given a list of learning algorithms, have them vote."""

def train(dataset):

predictors = [learner(dataset) for learner in learners]

def predict(example):

return mode(predictor(example) for predictor in predictors)

return predict

"""[Figure 18.34]"""

def train(dataset):

examples, target = dataset.examples, dataset.target

N = len(examples)

epsilon = 1/(2*N)

w = [1/N]*N

h, z = [], []

for k in range(K):

h_k = L(dataset, w)

h.append(h_k)

error = sum(weight for example, weight in zip(examples, w)

if example[target] != h_k(example))

# Avoid divide-by-0 from either 0% or 100% error rates:

error = clip(error, epsilon, 1 - epsilon)

for j, example in enumerate(examples):

if example[target] == h_k(example):

w[j] *= error/(1 - error)

w = normalize(w)

z.append(math.log((1 - error)/error))

return WeightedMajority(h, z)

"""Return a predictor that takes a weighted vote."""

def predict(example):

return weighted_mode((predictor(example) for predictor in predictors),

weights)

"""Return the value with the greatest total weight.

totals = defaultdict(int)

for v, w in zip(values, weights):

totals[v] += w

"""Given a learner that takes just an unweighted dataset, return

def train(dataset, weights):

return unweighted_learner(replicated_dataset(dataset, weights))

"""Copy dataset, replicating each example in proportion to its weight."""

n = n or len(dataset.examples)

result = copy.copy(dataset)

result.examples = weighted_replicate(dataset.examples, weights, n)

"""Return n selections from seq, with the count of each element of

assert len(seq) == len(weights)

weights = normalize(weights)

wholes = [int(w*n) for w in weights]

fractions = [(w*n) % 1 for w in weights]

return (flatten([x]*nx for x, nx in zip(seq, wholes)) +

"""Return the proportion of the examples that are NOT correctly predicted.