"""

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

values=None, distance=mean_boolean_error, name='', source='', exclude=()):

"""

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)

elif examples is None:

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

else:

self.examples = examples

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

if self.examples is not None and attrs is None:

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

self.attrs = attrs

# initialize .attr_names from string, list, or by default

if isinstance(attr_names, str):

self.attr_names = attr_names.split()

else:

self.attr_names = attr_names or attrs

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

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

"""

self.target = self.attr_num(target)

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

if inputs:

self.inputs = remove_all(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.attr_names) == 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.attr_names[a], example))

def attr_num(self, attr):

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

if isinstance(attr, str):

return self.attr_names.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):

"""

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 _ 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):

r"""

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

"""

examples = examples or dataset.examples

if len(examples) == 0:

return 0.0

right = 0

for example in examples:

desired = example[dataset.target]

output = predict(dataset.sanitize(example))

if output == desired:

right += 1

if verbose >= 2:

print(' OK: got {} for {}'.format(desired, example))

elif verbose:

print('WRONG: got {}, expected {} for {}'.format(output, desired, example))

"""

"""

examples = dataset.examples

if test_split is None:

train = examples[:start] + examples[end:]

val = examples[start:end]

else:

total_size = len(examples)

val_size = int(total_size * test_split)

train_size = total_size - val_size

train = examples[:train_size]

val = examples[train_size:total_size]

"""

errs = []

size = 1

while True:

err = cross_validation(learner, dataset, size, k, trials)

# check for convergence provided err_val is not empty

if err and not isclose(err[-1], err, rel_tol=1e-6):

best_size = 0

min_val = inf

i = 0

while i < size:

if errs[i] < min_val:

min_val = errs[i]

best_size = i

i += 1

return learner(dataset, best_size)

errs.append(err)

"""

k = k or len(dataset.examples)

if trials > 1:

trial_errs = 0

for t in range(trials):

errs = cross_validation(learner, dataset, size, k, trials)

trial_errs += errs

return trial_errs / trials

else:

fold_errs = 0

n = len(dataset.examples)

examples = dataset.examples

random.shuffle(dataset.examples)

for fold in range(k):

train_data, val_data = train_test_split(dataset, fold * (n // k), (fold + 1) * (n // k))

dataset.examples = train_data

h = learner(dataset, size)

fold_errs += err_ratio(h, dataset, train_data)

# reverting back to original once test is completed

dataset.examples = examples

if sizes is None:

sizes = list(range(2, len(dataset.examples) - trials, 2))

def score(learner, size):

random.shuffle(dataset.examples)

return cross_validation(learner, dataset, size, trials)

"""

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

"""

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

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

self.attr = attr

self.attr_name = attr_name 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."""

attr_val = example[self.attr]

if attr_val in self.branches:

return self.branches[attr_val](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.attr_name

print('Test', name)

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

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

subtree.display(indent + 1)

def __repr__(self):

"""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):

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)

if all_same_class(examples):

return DecisionLeaf(examples[0][target])

if len(attrs) == 0:

return plurality_value(examples)

A = choose_attribute(attrs, examples)

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

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

subtree = decision_tree_learning(exs, remove_all(A, attrs), examples)

tree.add(v_k, subtree)

return tree

def plurality_value(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]]

"""

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):

"""

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))

"""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)

"""

idx_i = dataset.inputs

idx_t = dataset.target

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 weights

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 = dot_product(w, x)

t = example[idx_t]

err.append(t - y)

# update weights

for i in range(len(w)):

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

def predict(example):

x = [1] + example

return dot_product(w, x)

"""

idx_i = dataset.inputs

idx_t = dataset.target

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 weights

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 = []

h = []

# pass over all examples

for example in examples:

x = [1] + example

y = sigmoid(dot_product(w, x))

h.append(sigmoid_derivative(y))

t = example[idx_t]

err.append(t - y)

# update weights

for i in range(len(w)):

buffer = [x * y for x, y in zip(err, h)]

w[i] = w[i] + learning_rate * (dot_product(buffer, X_col[i]) / num_examples)

def predict(example):

x = [1] + example

return sigmoid(dot_product(w, x))

def __init__(self, kernel=linear_kernel, C=1.0):

self.kernel = kernel

self.C = C # hyper-parameter

self.eps = 1e-6

self.n_sv = -1

self.sv_x, self.sv_y, = np.zeros(0), np.zeros(0)

self.alphas = np.zeros(0)

self.w = None

self.b = 0.0 # intercept

def fit(self, X, y):

"""

# In QP formulation (dual): m variables, 2m+1 constraints (1 equation, 2m inequations)

self.QP(X, y)

sv_indices = list(filter(lambda i: self.alphas[i] > self.eps, range(len(y))))

self.sv_x, self.sv_y, self.alphas = X[sv_indices], y[sv_indices], self.alphas[sv_indices]

self.n_sv = len(sv_indices)

if self.kernel == linear_kernel:

self.w = np.dot(self.alphas * self.sv_y, self.sv_x)

# calculate b: average over all support vectors

sv_boundary = self.alphas < self.C - self.eps

self.b = np.mean(self.sv_y[sv_boundary] - np.dot(self.alphas * self.sv_y,

self.kernel(self.sv_x, self.sv_x[sv_boundary])))

def QP(self, X, y):

"""

#

m = len(y) # m = n_samples

K = self.kernel(X) # gram matrix

P = K * np.outer(y, y)

q = -np.ones(m)

G = np.vstack((-np.identity(m), np.identity(m)))

h = np.hstack((np.zeros(m), np.ones(m) * self.C))

A = y.reshape((1, -1))

b = np.zeros(1)

# make sure P is positive definite

P += np.eye(P.shape[0]).__mul__(1e-3)

self.alphas = solve_qp(P, q, G, h, A, b, sym_proj=True)

def predict_score(self, x):

"""

if self.w is None:

return np.dot(self.alphas * self.sv_y, self.kernel(self.sv_x, x)) + self.b

return np.dot(x, self.w) + self.b

def predict(self, x):

"""

def __init__(self, kernel=linear_kernel, decision_function='ovr', C=1.0):

self.kernel = kernel

self.decision_function = decision_function

self.C = C # hyper-parameter

self.n_class, self.classifiers = 0, []

def fit(self, X, y):

"""

labels = np.unique(y)

self.n_class = len(labels)

if self.decision_function == 'ovr': # one-vs-rest method

for label in labels:

y1 = np.array(y)

y1[y1 != label] = -1.0

y1[y1 == label] = 1.0

clf = BinarySVM(self.kernel, self.C)

clf.fit(X, y1)

self.classifiers.append(copy.deepcopy(clf))

elif self.decision_function == 'ovo': # use one-vs-one method

n_labels = len(labels)

for i in range(n_labels):

for j in range(i + 1, n_labels):

neg_id, pos_id = y == labels[i], y == labels[j]

x1, y1 = np.r_[X[neg_id], X[pos_id]], np.r_[y[neg_id], y[pos_id]]

y1[y1 == labels[i]] = -1.0

y1[y1 == labels[j]] = 1.0

clf = BinarySVM(self.kernel, self.C)

clf.fit(x1, y1)

self.classifiers.append(copy.deepcopy(clf))

else:

return ValueError("Decision function must be either 'ovr' or 'ovo'.")

def predict(self, x):

"""

n_samples = len(x)

if self.decision_function == 'ovr': # one-vs-rest method

assert len(self.classifiers) == self.n_class

score = np.zeros((n_samples, self.n_class))

for i in range(self.n_class):

clf = self.classifiers[i]

score[:, i] = clf.predict_score(x)

return np.argmax(score, axis=1)

elif self.decision_function == 'ovo': # use one-vs-one method

assert len(self.classifiers) == self.n_class * (self.n_class - 1) / 2

vote = np.zeros((n_samples, self.n_class))

clf_id = 0

for i in range(self.n_class):

for j in range(i + 1, self.n_class):

res = self.classifiers[clf_id].predict(x)

vote[res < 0, i] += 1.0 # negative sample: class i

vote[res > 0, j] += 1.0 # positive sample: class j

clf_id += 1

return np.argmax(vote, axis=1)

else:

"""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]"""

examples, target = dataset.examples, dataset.target

n = len(examples)

eps = 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, eps, 1 - eps)

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 a predictor that takes a weighted vote."""

def predict(example):

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

"""

totals = defaultdict(int)

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

totals[v] += w

"""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,

attr_names=dataset.attr_names, target=dataset.target,

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

"""

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)

"""

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 DataSet(name='restaurant', target='Wait', examples=examples,

{'None': 'No', 'Some': 'Yes',

'Full': T('WaitEstimate',

{'>60': 'No', '0-10': 'Yes',

'30-60': T('Alternate',

{'No': T('Reservation',

{'Yes': 'Yes',

'No': T('Bar', {'No': 'No',

'Yes': 'Yes'})}),

'Yes': T('Fri/Sat', {'No': 'No', 'Yes': 'Yes'})}),

'10-30': T('Hungry',

{'No': 'Yes',

'Yes': T('Alternate',

{'No': 'Yes',

'Yes': T('Raining',

{'No': 'No',

"""Generate a DataSet with n examples."""

def gen():

example = list(map(random.choice, restaurant.values))

example[restaurant.target] = waiting_decision_tree(example)

return example

"""

examples = []

for i in range(n):

bits = [random.choice([0, 1]) for _ in range(k)]

bits.append(int(sum(bits) > k / 2))

examples.append(bits)

"""

examples = []

for i in range(n):

bits = [random.choice([0, 1]) for _ in range(k)]

bits.append(sum(bits) % 2)

examples.append(bits)

"""2 inputs are chosen uniformly from (0.0 .. 2.0]; output is xor of ints."""

examples = []

for i in range(n):

x, y = [random.uniform(0.0, 2.0) for _ in '12']

examples.append([x, y, x != y])

"""

# default list of algorithms

algorithms = algorithms or [PluralityLearner, NaiveBayesLearner, NearestNeighborLearner, DecisionTreeLearner]

# default list of datasets

datasets = datasets or [iris, orings, zoo, restaurant, SyntheticRestaurant(20),

Majority(7, 100), Parity(7, 100), Xor(100)]

print_table([[a.__name__.replace('Learner', '')] + [cross_validation(a, d, k=k, trials=trials) for d in datasets]