Науки о данных

И. В. Щуров, НИУ ВШЭ

На странице курса находятся дополнительные материалы.

Домашнее задание №6

За разные задачи можно получить разное число баллов. Если не указано обратное, задача весит 1 балл. Максимум за ДЗ можно набрать 23 балла.

Чтобы сдать ДЗ, его надо загрузить в nbgr-x в виде ipynb-файла. Получить ipynb-файл можно, выбрав в Jupyter пункт меню File → Download as... → IPython Notebook (.ipynb).

Часть I. Ещё немножко про классы

Задача 1 (2 балла)

Рассмотрим следующий класс, описывающий абстрактное устройство.

In [ ]:
class Device(object):
    def __init__(self, name):
        self.name = name
        self.is_on = False
        
    def __repr__(self):
        return f"Device({self.name!r})"
       
    def turn_on(self):
        self.is_on = True
        
    def turn_off(self):
        self.is_on = False
        
    def toggle(self):
        self.is_on = not self.is_on

Написать класс TVSet, наследующий от Device (то есть являющийся подклассом класса Device).

  1. Добавить в класс TVSet атрибут channel. Конструктор TVSet по-прежнему должен принимать на вход только name. При создании экземпляра класса TVSet, атрибут channel должен быть установлен в 1. Конструктор (__init__) класса TVSet должен вызывать материнский конструктор с помощью super().__init__(…).
  2. repr и str должны теперь возвращать строчку вида "TVSet('{name}')".
  3. Добавить метод switch_channel(), принимающий на вход канал (число) и меняющий атрибут channel соответствующим образом. При попытке поменять канал на не включенном телевизоре канал не должен меняться (ничего не должно происходить).
In [ ]:
"# YOUR CODE HERE"
In [ ]:
# Constructor
def test_constructor(cl):
    tvset = cl("TV")
    assert tvset.is_on is False
    xbox = cl("Xbox")
    assert xbox.is_on is False
    assert xbox is not tvset

# turning on and off
def test_turn_on_off(cl):
    tvset = cl("TV")
    xbox = cl("Xbox")
    tvset.turn_on()
    assert tvset.is_on is True
    assert xbox.is_on is False
    tvset.turn_on()
    assert tvset.is_on is True
    assert xbox.is_on is False
    tvset.turn_off()
    assert tvset.is_on is False
    assert xbox.is_on is False
    tvset.turn_off()
    assert tvset.is_on is False
    assert xbox.is_on is False

# toggling
def test_toggling(cl):
    tvset = cl("TV")
    assert tvset.is_on is False
    tvset.toggle()
    assert tvset.is_on is True
    tvset.toggle()
    assert tvset.is_on is False

# Subclassing tests
assert issubclass(TVSet, Device)
test_constructor(TVSet)
test_turn_on_off(TVSet)
test_toggling(TVSet)

tvset = TVSet("tv1")
assert str(tvset) == "TVSet('tv1')"
assert repr(tvset) == "TVSet('tv1')"
assert tvset.channel == 1
In [ ]:
tvset = TVSet("tv1")
# New method tests
assert tvset.is_on is False
tvset.channel = 42
tvset.switch_channel(2)
assert tvset.channel == 42
tvset.turn_on()
tvset.switch_channel(3)
assert tvset.channel == 3, "Switch doesn't work"

Часть II: Numpy

Во всех задачах словом «массив» обозначается объект типа np.array. Везде, где не оговорено обратное, запрещается пользоваться циклами и list comprehensions!

_Некоторые задачи разработаны Ф. Тюриным. Часть задач взята из ДЗ№2 этого курса, составленного Евгением Ковалёвым по материалам задач Факультета компьютерных наук._

In [ ]:
import numpy as np

Задача 2 (1 балл)

Написать функцию double_this(arr), принимающую на вход массив arr, состоящий из чисел, и возвращающую массив, полученный удвоением каждого элемента arr.

Подсказка: Операции с массивами действуют поэлементно.

Ещё подсказка: Нужно считать, что arr уже является np.array, преобразовывать его к этому типу не нужно. Например, для проверки вашей функции нужно запускать что-то вроде

dobule_this(np.array([1, 2, 3]))
In [ ]:
"# YOUR CODE HERE"
In [ ]:
from timeit import timeit
import numpy as np

def testme(f, inp, outp):
    q = f(np.array(inp))
    assert isinstance(q, np.ndarray), "Функция должна возвращать массив numpy (np.array)"
    assert np.array_equal(q, np.array(outp)), "Ошибка для входного списка "+str(np.array(inp))
def test(inp, outp):
    testme(double_this, inp, outp)

test([1, 2, 3], [2, 4, 6])
test([1.1, 2.2, 3.3], [2.2, 4.4, 6.6])
test([1]*10, [2]*10)
test([1]*10+[2]*15, [2]*10+[4]*15)

N = 1000000

benchmark = timeit("[x*x for x in np.array([1]*N)]", "from __main__ import N, np", number=1)
otherbenchmark = timeit("double_this(np.array([1]*N))", 
                        "from __main__ import N, np, double_this", number=1)
assert benchmark > otherbenchmark*2, "Код работает слишком медленно — вы точно не пользовались циклами?"

Задача 3 (1 балл)

Написать функцию select_even(arr), принимающую на вход массив целых чисел arr и возвращающую новый массив, который состоит из всех чётных элементов arr.

Подсказка: напомним, что все арифметические операции, а также операции сравнения, действуют на массивы поэлементно.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
from timeit import timeit
import numpy as np

def testme(f, inp, outp):
    q = f(np.array(inp))
    assert isinstance(q, np.ndarray), "Функция должна возвращать массив numpy (np.array)"
    assert np.array_equal(q, np.array(outp)), "Ошибка для входного списка "+str(np.array(inp))
def test(inp, outp):
    testme(select_even, inp, outp)

test([1, 2, 3, 4, 5], [2, 4])
test([], [])
test([1, 3, 5], [])
test([5, 4, 3, 2, 0], [4, 2, 0])
test([100, 200, 300, 199, 299, 150], [100, 200, 300, 150])

N = 100000
benchmark = timeit("[x for x in np.array([1]*N) if x*2]", "from __main__ import N, np", number=1)
otherbenchmark = timeit("select_even(np.array([1]*N))", 
                        "from __main__ import N, select_even, np", number=1)
assert benchmark > otherbenchmark*2, "Код работает слишком медленно — вы точно не пользовались циклами?"
# should be at least two times faster than list comprehensions

Задача 4 (2 балла)

Напишите функцию closest_value(array, value), вычисляющую самое близкое и самое дальнее числа к данному в рассматриваемом массиве чисел. Например, если на вход поступают массив array([0, 1, 2, 3, 4]) и число 1.33, то ответом будет (1, 4).

Подсказка. Вам пригодится функция np.argmin() или метод .argmin(), а также функция np.abs(), позволяющая быстро поэлементно взять модуль.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert closest_value(np.array([0, 1, 2, 3, 4]), 1.33) == (1, 4)
assert closest_value(np.array([0]), 0) == (0, 0)
assert closest_value(np.array([1, 1.1, 1.11, 1.111, 1.1111]), 100) == (1.1111, 1)
assert closest_value(np.array([-100, 400, 100500]), 0) == (-100, 100500)

Задача 5 (2 балла)

Написать функцию wipe_even(arr, target_value, in_place), принимающую на вход массив целых чисел arr, и возвращающую массив, полученный из arr путём замены всех чётных элементов на target_value. Если target_value не указано, то оно должно считаться равным числу 0. Если указан параметр in_place и он равен True, то функция должна менять исходный массив, а если не указан или указан в False, то сохранять его неизменным (но возвращать изменённую согласно условию версию).

Подсказка. Чтобы получить копию исходного массива можно использовать метод .copy(). Выбор по условию, который вы использовали в select_even, можно использовать не только для того, чтобы получить какие-то элементы массива, но и чтобы изменить их — то есть выражения с выбором по условию могут стоять слева от знака =.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
from timeit import timeit
import numpy as np

def test(inp, outp, target=0, in_place=False):
    inp = np.array(inp)
    inp_backup = np.array(inp)

    q = wipe_even(inp, target, in_place)
    assert isinstance(q, np.ndarray), "Функция должна возвращать массив numpy (np.array)"
    assert np.array_equal(q, np.array(outp)), "Ошибка для входного списка "+str(np.array(inp))
    if in_place:
        assert np.array_equal(inp, np.array(outp)), "Функция должна менять исходный список"
    else:
        assert np.array_equal(inp, inp_backup), "Исходный список должен остаться неизменным"

test([1, 2, 3, 4, 5], [1, 0, 3, 0, 5], in_place=True)
test([], [], in_place=True)
test([1, 3, 5], [1, 3, 5], in_place=True)
test([5, 4, 3, 2, 0], [5, 0, 3, 0, 0], in_place=True)
test([100, 200, 300, 199, 299, 150], [0, 0, 0,  199, 299, 0], in_place=True)

test([1, 2, 3, 4, 5], [1, 99, 3, 99, 5], target = 99, in_place=True)

N = 100000
benchmark = timeit("[0 if x*2 else x for x in np.array([1]*N)]", 
                   "from __main__ import np, N", number=1)
otherbenchmark = timeit("wipe_even(np.array([1]*N), in_place=True)", 
                        "from __main__ import np, N, wipe_even", number=1)
assert benchmark > otherbenchmark*1.5, "Код работает слишком медленно — вы точно не пользовались циклами?"

Задача 6 (1 балл)

Напишите функцию is_increasing_np(arr), проверяющую, что массив arr являются строго возрастающим. Сортировкой пользоваться нельзя.

Подсказка. Вам пригодятся функции np.diff() и np.all().

In [ ]:
"# YOUR CODE HERE"
In [ ]:
def _is_increasing(arr):
    return is_increasing_np(np.array(arr))

assert _is_increasing([1, 2, 3, 4, 5]) == True
assert _is_increasing([1, 10, 15, 16, 17]) == True
assert _is_increasing([5]) == True
assert _is_increasing([5, 5]) == False
assert _is_increasing([5, 6, 7, 7]) == False
assert _is_increasing([5, 6, 7, 8, 7]) == False
assert _is_increasing([2, 1, 5, 6]) == False

assert _is_increasing([1, 1]) == False

assert _is_increasing([1, 2, 3, 3]) == False
assert _is_increasing(list(range(10000))) == True
assert _is_increasing([3, 2, 3]) == False

Задача 7 (2 балла)

Написать функцию weighted_sum(weights, grades, normalize), возвращающую взвешенную сумму оценок, записанных в массив grades, в соответствии с весами, записанными в массив weights. Например, для weights = np.array([0.3, 0.3, 0.4]) и grades = np.array([7, 9, 8]) функция должна вернуть число $0.3\times 7+0.3\times 9+0.4\times 8=8.0$.

Если параметр normalize установлен в True, а сумма всех весов отличается от 1, то следует умножить все веса на одно и то же число таким образом, чтобы их сумма была равна 1, в противном случае следует использовать веса «как есть», даже если их сумма отличается от 1. Если функция запущена без указания параметра normalize, следует считать, что normalize = False.

Подсказка: Встроенная функция sum() также работает с массивами numpy, но гораздо быстрее использовать метод .sum() или функцию np.sum() (проверьте с помощью %timeit!)

In [ ]:
"# YOUR CODE HERE"
In [ ]:
from timeit import timeit
import numpy as np

def test(w, g, out, normalize = False):
    q = weighted_sum(np.array(w), np.array(g), normalize)
    assert np.isclose(q, out)

test([0.3, 0.3, 0.4], [7, 9, 8], 8)
test([0.1, 0.2, 0.3, 0.4], [1, 5, 3, 2], 2.8)
test([1, 2, 3, 4], [1, 5, 3, 2], 28)
test([1, 2, 3, 4], [1, 5, 3, 2], 2.8, normalize=True)
In [ ]:
N = 1000000

test([1, 2, 3, 4], [1, 5, 3, 2], 28)

benchmark = timeit("sum([x/x for x in np.array([1]*N)])", "from __main__ import N, np", number=1)
otherbenchmark = timeit("weighted_sum(np.array([1.1]*N), np.array([1]*N), True)", 
                        "from __main__ import N, weighted_sum, np", number=1)
assert benchmark > otherbenchmark*1.4, "Код работает слишком медленно — вы точно использовали методы numpy?"

Задача 8 (1 балл)

Написать функцию find_max(matrix), принимающую на вход матрицу matrix и возвращающую массив, элементами которого являются максимальные значения столбцов matrix. (Подсказка: поищите что-нибудь вроде columnwise maximum numpy в ближайшей поисковой системе. Таким образом решаются 99% проблем с numpy.)

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert (find_max(np.array([[9, 9, 4], [8, 8, 1], [5, 3, 6], [3, 3, 3], [2, 1, 9]])) == np.array([9, 9, 9])).all()
assert (find_max(np.array([[0, 1, 2], [3, 4, 5], [6, 7, 8]])) == np.array([6, 7, 8])).all()
assert (find_max(np.array([[0, 1, 2], [3, 0, 5], [6, 7, 1]])) == np.array([6, 7, 5])).all()
assert (find_max(np.array([[-10, 1, 2, 5], [3, 30, 5, 17], [-100, -100, -100, 100], [1, 1, 2, -80]])) == 
        np.array([3, 30, 5, 100])).all()
assert (find_max(np.array([[1]])) == np.array([1])).all()

Задача 9 (2 балла)

Напишите функцию diag_prod(matrix), вычисляющую произведение всех ненулевых диагональных элементов на диагонали данной квадратной матрицы. Например, если на вход поступает матрица $$ \begin{pmatrix} 0 & 1 & 2\\ 3 & 4 & 5\\ 6 & 7 & 8\\ \end{pmatrix}, $$ то ответом будет 32. Гарантируется, что на лиагонали матрицы будет хотя бы один ненулевой элемент.

Подсказка. Функции, которые могут пригодиться при решении: np.diag(), np.prod()

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert diag_prod(np.array([[0, 1, 2], [3, 4, 5], [6, 7, 8]])) == 32
assert diag_prod(np.array([[0, 1, 2], [3, 0, 5], [6, 7, 1]])) == 1
assert diag_prod(np.array([[-10, 1, 2, 5], [3, 30, 5, 17], [-100, -100, -100, 100], [1, 1, 2, -80]])) == -2400000
assert diag_prod(np.array([[1]])) == 1

Задача 10 (2 балла)

Напишите функцию make_symmetric(matrix), делающую данную треугольную матрицу симметричной. Например, если на вход поступает матрица $$ \begin{pmatrix} 1 & 2 & 3 & 4\\ 0 & 5 & 6 & 7\\ 0 & 0 & 8 & 9\\ 0 & 0 & 0 & 10\\ \end{pmatrix}, $$ то на выходе должна быть матрица $$ \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 5 & 6 & 7\\ 3 & 6 & 8 & 9\\ 4 & 7 & 9 & 10\\ \end{pmatrix}. $$ Подсказка. np.diag может не только получить диагональ от существующей матрицы, но и сделать матрицу с данной диагональю.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert (make_symmetric(np.array([[1, 2, 3, 4], [0, 5, 6, 7], [0, 0, 8, 9], [0, 0, 0, 10]])) ==
        np.array([[1, 2, 3, 4], [2, 5, 6, 7], [3, 6, 8, 9], [4, 7, 9, 10]])).all()
assert (make_symmetric(np.array([[0, 0, 0, 0], [0, 9, 8, 0], [0, 0, -100, -1000], [0, 0, 0, 999]])) ==
        np.array([[0, 0, 0, 0], [0, 9, 8, 0], [0, 8, -100, -1000], [0, 0, -1000, 999]])).all()
assert (make_symmetric(np.array([[1]])) == np.array([[1]])).all()

Задача 11 (2 балла)

Написать функцию mean_by_gender(grades, genders), принимающую на вход два массива одинаковой длины: в массиве grades записаны оценки некоторых студентов, а в массиве genders — их пол в виде строк male или female. Требуется вернуть словарь, ключами которого будут строки male и female, а записями — среднее арифметическое оценок студентов соответствующего пола.

Например, если grades = np.array([5, 4, 3, 5, 2]) и genders = np.array(["female", "male", "male", "female", "male"]), функция должна вернуть словарь {'male': 3.0, 'female': 5.0}.

Подсказка. Для быстрого вычисления среднего есть функция np.mean() или соответствующий метод у объектов типа numpy.array.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
from timeit import timeit
import numpy as np

def test(grades, genders, outp):
    ret = mean_by_gender(np.array(grades), np.array(genders))
    assert np.isclose(ret['female'], outp['female'])
    assert np.isclose(ret['male'], outp['male'])

test([5, 4, 3, 5, 2], ["female", "male", "male", "female", "male"], {'male': 3.0, 'female': 5.0})
test([1, 0]*10, ['female', 'male']*10, {'female': 1, 'male': 0})
test(range(100), ['female', 'male']* 50, {'female': 49.0, 'male': 50.0})
test(list(range(100))+[100], ['male']*100+['female'], {'male':49.5, 'female': 100.0})
# mean_by_gender(np.array(range(100)), ['female', 'male']* 50)

def benchmark_test(a, b):
    xx = 0
    yy = 0
    im = 0
    fi = 0
    for x, y in zip(a, b):
        if x != y:
            xx += x
            yy += x
            im += 1
            fi += 1

    return xx+yy

N = int(1E5)
grades = np.array([1.1]*N + [2.2]*N)
genders = np.array(['male']*N + ['female']*N)

benchmark = timeit("assert np.isclose(mean_by_gender(grades, genders)['male'], 1.1)",
                   "from __main__ import np, mean_by_gender, grades, genders",
                   number=1)
reference_benchmark = timeit("benchmark_test(grades, genders)",
                             "from __main__ import benchmark_test, grades, genders",
                             number=1)

assert reference_benchmark > benchmark * 10, "Код работает слишком медленно — вы точно использовали методы numpy?"

Задача 12 (3 балла)

В некотором царстве, в некотором государстве, налог на доходы физических лиц вычисляется следующим образом. Базовая ставка налога составляет 13%. Если в каком-то месяце ваш заработок за год составит больше тысячи тугриков, то на оставшуюся часть года (не включая этот месяц) устанавливается ставка в 20%. Например, если вы зарабатываете каждый месяц 150 тугриков, то к июлю заработаете $150\times 7 = 1050$ тугриков и начиная с августа подоходный налог будет начисляться по ставке 20%. Написать функцию calculate_tax(income), принимающую на вход массив, содержащий доход за каждый месяц года, начиная с первого и возвращающую общую сумму налога, который предстоит заплатить за год. Год в некотором царстве может длиться более 12 месяцев, если по этому поводу будет принят соответствующий высочайший декрет.

Подсказка. Вам помогут функции np.cumsum() и np.where().

В этой задаче можно использовать if ровно один раз.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
from timeit import timeit
import numpy as np

assert np.isclose(calculate_tax(np.array([150]*12)), 286.5)
assert np.isclose(calculate_tax(np.array([100]*12)), 163)
assert np.isclose(calculate_tax(np.array([50]*12)), 78)
assert np.isclose(calculate_tax(np.array([1000]*12)), 2260)

assert np.isclose(calculate_tax(np.array(range(12))*100), 1215)
assert np.isclose(calculate_tax(np.array(range(11,-1,-1))*100), 1243)
In [ ]:
def dummy(x):
    z = 0
    for y in x:
        z += y
        z += y*0.12
        if z:
            z += y
    return z

assert np.isclose(calculate_tax(np.array(range(12))*100), 1215)

N = int(1E6)
arr = np.array([1]*N)
benchmark = timeit("calculate_tax(arr)", "from __main__ import calculate_tax, arr", number=1)
reference_benchmark = timeit("dummy(arr)", "from __main__ import dummy, arr", number=1)

assert reference_benchmark > benchmark*5, "Код работает слишком медленно — вы точно использовали методы numpy?"

Задача 13 (2 балла)

Создайте симметричную квадратную матрицу размера 1000 × 1000, заполненную случайными независимыми (кроме симметричных относительно диагонали, конечно) числами из стандартного нормального распределения. Найдите её собственные значения и постройте гистограмму, показывающую, как распределены эти собственные значения.

Подсказка. Сгенерировать матрицу можно с помощью np.random.normal, для этого в качестве параметра size нужно передать ей кортеж. Чтобы сделать матрицу верхнетреугольной, можно использовать специальную функцию numpy (найдите её), а как сделать верхнетреугольную матрицу симметричной вы, уже знаете, если решили задачу make_symmetric. Для нахождения собственных значений, как и для других операций линейной алгебры, есть подходящая функция в np.linalg — даже несколько функций — выберите нужную.

Замечание. Если всё сделано правильно, должен получиться полукруговой закон Вигнера. Кстати, можете попробовать заменить нормальное распределение на какое-нибудь другое с нулевым матожиданием. А что будет, если отказаться от требования симметричности? Собственные значения теперь могут быть комплексными, но можно нарисовать распределение их вещественных или мнимых частей.

Задача будет проверяться вручную.

In [ ]:
import matplotlib.pyplot as plt
%matplotlib inline
In [ ]:
"# YOUR CODE HERE"

Задача 14 (4 балла)

Напишите функцию circle_image(M), которая принимает на вход двумерный np.array размера 2×2 (матрицу) и рисует образ единичной окружности под действием оператора, заданного этой матрицей, а также собственные векторы оператора, заданного матрицей $MM^T$. Картинка должна быть нарисована таким образом, чтобы масштабы горизонтальной и вертикальной оси совпадали (в частности, прямые углы должны изображаться как прямые углы, а окружности как окружности).

Подсказки. Вам нужно найти координаты точек на единичной окружности и на каждую точку подействовать матрицей $M$. Чтобы обойтись без циклов, действие матрицы на набор точек нужно записать в виде одной матричной операции. Чтобы сделать одинаковый масштаб на осях, можно использовать plt.axis с подходящим аргументом.

Вопрос для размышления. Почему собственные векторы матрицы $MM^T$ связаны с осями получающегося эллипса? (Сдавать ответ не требуется.)

In [ ]:
"# YOUR CODE HERE"

Проверка: задача будет проверяться вручную. Для самопроверки: код

In [ ]:
circle_image(np.array([[2, 2], [1, 2]]))

должен рисовать такую картинку: