Category: Data Science

01
Июл
2020

Онлайн: факультет Data Engineering

Получите современную профессию и год опыта, а ещё добавьте несколько проектов в резюме. Для обучения достаточно школьных знаний.
— Читать дальше «Факультет Data Engineering»

21
Май
2020

Онлайн: хакатон Speaker Identification by Deep Learning

Конкурс по разработке модели глубокого обучения на Python для распознавания отдельных голосов в датасетах большого размера.
— Читать дальше «Хакатон Speaker Identification by Deep Learning»

05
Май
2020

Старт 21 мая, онлайн: курс «Машинное обучение»

Получите прикладной опыт разработки ML-проектов: от сбора и простого анализа данных до построения масштабных моделей и их оптимизации.
— Читать дальше «Курс «Машинное обучение»»

24
Апр
2020

Как пандемия влияет на финансовые рынки: анализ данных

Какое влияние оказывает COVID-19 на финансовые рынки: анализируем текущую ситуацию и сравниваем с тем, как реагировал глобальный рынок на минувшие пандемии.

Если вы живёте в городе, где введён режим самоизоляции, то наверняка знаете о проблемах бизнеса, замечаете, как начали закрываться кафе, рестораны, магазины. Нет производства – нет зарплат, растёт безработица, снижается оборот денег, рынок падает. Подобная ситуация наблюдается сейчас во всём мире. В статье приведён краткий анализ ситуации, основанный на рассмотрении четырёх макроэкономических индексов:

Влияние на финансовые
рынки

Начнём с оценки
текущего влияния распространения коронавируса на финансовые рынки. Для создания диаграмм использовался Python (код целиком доступен в репозитории на GitHub). Например, для построения ежедневного процентного изменения для S&P500 использовался следующий скрипт:

            # Читаем данные
import pandas_datareader as pdr

# Для построения графиков
import matplotlib.pyplot as plt
plt.style.use('seaborn-darkgrid')

# Для операций над данными
import pandas as pd
import numpy as np

# get_data_yahoo(inst_ticker, start_date, end_date)
data_sp = pdr.get_data_yahoo('^GSPC', '17-Nov-19')

# Рассчитываем процентное изменение
data_pc = data_sp.Close.pct_change()

# Строим
data_pc.plot(figsize=(10, 7), grid=True)
plt.axvline('30-Jan-20')
plt.show()
        
 Ежедневного процентное изменение для индекса S&P500
Ежедневного процентное изменение для индекса S&P500

Для получения индекса S&P500 использовал
метод pandas_datareaders
get_data_yahoo
. Он принимает два аргумента: первый – тикер “^GPSC" для S&P500 в Yahoo Finance, а второй – дата, начиная с которой мы хотим получить данные. При запуске мы получаем набор данных с шестью столбцами. Ежедневное
процентное изменение рассчитывается с помощью метода pct_change().

Ежедневное процентное
изменение

Помимо S&P500,
построим графики для остальных индексов.

            # Читаем таймлайны из файла CSV
timelines = pd.read_csv('pandemics_timelines.csv').dropna()
for col in timelines.columns[1:]:
    timelines[col] = pd.to_datetime(timelines[col])
    
# Читаем данные из yahoo fianance
def get_data(tl):    
    inst_list = ['^GSPC', 'CL=F','GC=F', 'TLT']
    data = pd.DataFrame()
    for inst in inst_list:
        try:
            data[inst] = pdr.get_data_yahoo(inst, tl.first_case.iloc[0]-timedelta(days=30), 
                                        tl.last_date.iloc[0]+timedelta(days=365))['Adj Close']    
        except Exception as e:
            print('No data available for ',inst, e)

    return data
    
# Получаем данные во время covid19
covid_timelines = timelines.loc[timelines.pandemic_name=='covid19']
data= get_data(covid_timelines)

# Строим график ежедневного процентного изменения
def plot_daily_pc(data, tl):
    data_pc = data.pct_change().dropna()
    fig = plt.figure(figsize=(12, 8))
    i = 0
    for col in data_pc.columns:
        # Добавляем доп.график
        sub = fig.add_subplot(2, 2, i+1)
        i = i+1
        # Заголовок
        sub.set_title(col, fontsize=20)
        # График
        r = random.random()
        b = random.random()
        g = random.random()
        data_pc[col].plot(color=(r, g, b))
        sub.set_ylabel('Returns')
        sub.grid(which="major", color='k', linestyle='-.', linewidth=0.2)
        sub.axvline(x=tl.first_case.iloc[0], color='RoyalBlue',
                    linestyle='dashdot', linewidth=3)
        sub.axvline(x=tl.who_emergency.iloc[0], color='Red',
                    linestyle='dashdot', linewidth=3)

    plt.tight_layout()
    plt.show()
    
plot_daily_pc(data, covid_timelines)
        
Процентное изменения четырёх рассматриваемых показателей с ноября 2019 г. по апрель 2020 г.
Процентное изменения четырёх рассматриваемых показателей с ноября 2019 г. по апрель 2020 г.

Синяя штрихпунктирная вертикаль – дата, когда был выявлен первый случай заболевания. Колебания индексов были незначительны до тех пор, пока Всемирная организация здравоохранения (ВОЗ) не объявила чрезвычайное положение, приведшее к резкой потере стабильности – вспышка COVID-19 оказала сильное влияние на финансовые рынки.

Совокупная доходность

Построим кривые совокупной доходности акций для перечисленных индексов. Дата начала – за несколько дней до первого случая, последний рассматриваемый день – 30 марта.

            def plot_cumulative_returns(data,tl):
    data_cum_ret = (data.pct_change()+1).cumprod()
    data_cum_ret.plot(figsize=(10,7),grid=True)
    plt.legend(loc='best')
    plt.ylabel('Cumulative Returns')
    plt.axvline(x=tl.first_case.iloc[0],color='RoyalBlue',linestyle='dashdot',linewidth=3)
    plt.axvline(x=tl.who_emergency.iloc[0],color='Red',linestyle='dashdot',linewidth=3)
    plt.axvline(x=tl.pandemic_declaration.iloc[0],color='LightSeaGreen',linestyle='dashdot',linewidth=3)
    plt.axvspan(tl.last_date.iloc[0], tl.last_date.iloc[0]+timedelta(days=365),color='dodgerblue', alpha=0.2)
    plt.show()
    
plot_cumulative_returns(data, covid_timelines)
        
Кривые совокупной доходности с ноября 2019 г. по конец марта 2020 г.
Кривые совокупной доходности с ноября 2019 г. по конец марта 2020 г.

Доходность от нефти после объявления упала сильнее всего – в течение указанного периода почти
на 60%. Резкое снижение показала и рентабельность индекса S&P500.

Секторальные показатели

До сих
пор мы говорили о S&P500 в целом, но что происходит с секторами экономики, входящими в
индекс? Построим график, который учитывает основные секторы рынка.

            def plot_sector(tl):
    sector_list = ['IHE', 'IYW', 'IYF', 'IYK', 'IYZ','ITM', 'IYE']

    columns = ['Pharma', 'Technology', 'Financials', 'Consumer Goods',
               'Telecom', 'Basic Materials', 'Energy']

    sector_data = pd.DataFrame()
    for inst in sector_list:
        try:
            sector_data[inst] = pdr.get_data_yahoo(inst, tl.first_case.iloc[0]-timedelta(days=30), 
                                        tl.last_date.iloc[0]+timedelta(days=365))['Adj Close']    
        except:
            pass

    sector_data.columns = columns
    plot_cumulative_returns(sector_data, tl)
plot_sector(covid_timelines)
        
Кривые совокупной доходности для отдельных секторов глобальной экономики
Кривые совокупной доходности для отдельных секторов глобальной экономики

Два сектора, которые
оказались наименее подвержены влиянию – это фармацевтика и технологии. Однако в целом, все секторы находятся в «одной
поре», пусть относительная величина и отличается. Наибольшие трудности испытывает энергетический сектор – это логично, учитывая, как пострадал показатель Crude Oil.

Далее мы предлагаем рассмотреть
варианты развития ситуации с вирусом, опираясь на прежний опыт. В истории уже
случались вспышки пандемии, нанёсшие колоссальный вред рынкам – полезно
разобраться, как справлялось человечество в былые времена.

Сценарий применения строгих
мер

Атипичная пневмония

В 2002 г. вспышка
пандемии захватила юг Китая, были инфицированы 8500 человек. Распространение болезни взяли под контроль теми же способами, что сегодня: изоляцией, карантином и отслеживанием контактов. Социальное дистанцирование позволило сдержать распространение, однако идентифицировать пневмонию было намного проще,
чем COVID-19.

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

Временные зависимости распространения атипичной пневмонии (SARS) в 2003 г.
Временные зависимости распространения атипичной пневмонии (SARS) в 2003 г.

Взглянем, что происходило с финансовыми рынками во время вспышки атипичной пневмонии.

Ежедневное процентное изменение четырёх индексов в случае вспышки атипичной пневмонии 2002-2003 г.
Ежедневное процентное изменение четырёх индексов в случае вспышки атипичной пневмонии 2002-2003 г.

Поскольку эпидемия преимущественно проходила в Китае, мы видим меньшее влияние на финансовые рынки. Можно наблюдать некоторые резкие движения в обоих направлениях, указывающие на увеличение волатильности. Наиболее резкое снижение совокупной доходности также наблюдалось для индекса Crude oil, остальные индексы оказались менее подвержены влиянию.

Кривые совокупной доходности с ноября 2002 г. по июль 2003 г. во время распространения SARS
Кривые совокупной доходности с ноября 2002 г. по июль 2003 г. во время распространения SARS

Посмотрим,
как пошли дела после того, как кризис закончился. Голубая область соответствует времени, когда ВОЗ объявила, что кризис болезни преодолён.

Кривые совокупной доходности с ноября 2002 г. по июль 2004 г. (более широкий интервал)
Кривые совокупной доходности с ноября 2002 г. по июль 2004 г. (более широкий интервал)

После объявления ВОЗ наблюдалось быстрое восстановление показателей.

Сценарий широкого распространения заражения

В случае второго сценария речь пойдёт об Испанском гриппе («испанке»),
который во время Первой мировой войны затронул почти 30% населения
планеты, а также о так называемых Азиатском (H2N2) и Гонконгском (H3N2) гриппах, от которых пострадало
около полумиллиона человек.

«Испанка»

Испанский грипп развивался тремя волнами: июнь-июль 1918 года, октябрь-декабрь 1918 года, январь-март 1919 года. На нижеприведённом графике использовался индекс
Доу-Джонса
(индекс S&P500 был предложен лишь в 1927 году):

Изменение индекса Доу-Джонса в 1918-1919 г. (<a href="https://www.macrotrends.net/1319/dow-jones-100-year-historical-chart" target="_blank" rel="noopener noreferrer nofollow">источник данных</a>)
Изменение индекса Доу-Джонса в 1918-1919 г. (источник данных)

С удивлением можно обнаружить, что рынок во время распространения «испанки» шёл вверх. Причина заключается в крупном предшествовавшем событии – Первой мировой войне. На рынке наблюдался восходящий тренд, связанный с восстановлением после войны.

Штаммы гриппа H2N2 и H3N2

Ниже приведены
показатели совокупной доходности для S&P500 во время распространения соответственно Азиатского гриппа (1957-1959 гг.) и Гонконгского гриппа (1968-1971 гг.).

Совокупная доходность для S&amp;P500 во время распространения азиатского гриппа (H2N2)
Совокупная доходность для S&P500 во время распространения азиатского гриппа (H2N2)
Совокупная доходность для S&amp;P500 во время распространения гонконгского гриппа (H3N2)
Совокупная доходность для S&P500 во время распространения гонконгского гриппа (H3N2)

Красная вертикаль указывает
на период, когда ВОЗ объявила чрезвычайную ситуацию. Голубая область соответствует периоду завершения
пандемии. Можно видеть, что показатели в обоих случаях начали расти ещё до объявления о преодолении пандемии.

Заключение

Рынок не любит неопределённости. Когда объявляется чрезвычайное положение, он резко падает. Но как только предпринимаются необходимые шаги для сдерживания ситуации и ВОЗ объявляет её безопасной, рынок реагирует подъёмом на докризисный уровень, а в некоторых случаях даже превосходит его.

Расскажите в нашем обсуждении, как на работу вашей компании и лично на вас повлияло распространение коронавируса.

23
Апр
2020

Tesseract.js: извлекаем текст из картинок с помощью JavaScript

Инструкция по извлечению текста из картинок с помощью OCR-библиотеки Tesseract.js. В конце статьи можно поиграть с получившимся интерактивным демо-приложением.

Вы пропустили лекцию и попросили тетрадку у однокурсника, чтобы наверстать материал. Но переписывать длинный конспект нет ни времени, ни желания – что же делать?

Понадобится приложение, распознающее текст в нетекстовых документах. К счастью, такая технология существует и называется OCR (Optical Character Recognition). Более того, она доступна даже на JavaScript!

Извлечение текста из изображения с помощью библиотеки Tesseract.js
Извлечение текста из изображения с помощью библиотеки Tesseract.js

Встречайте Tesseract.js – мощную библиотеку, умеющую распознавать символы на любом изображении. Сегодня мы разберёмся, как с ней работать.

1. Подключаем Tesseract.js

Tesseract.js – это обычная JavaScript-библиотека. Чтобы использовать её возможности в проекте, необходимо подключить нужный файл. Сделать это можно любым удобным способом, например, используя CDN (https://unpkg.com/tesseract.js@v2.0.0-alpha.13/dist/tesseract.min.js) или в виде npm-пакета:

            // через npm
npm install tesseract.js
// через yarn
yarn add tesseract.js
        

2. Готовим разметку

Согласно официальному сайту Tesseract.js поддерживает более 100 языков, в том числе и русский – для демонстрации возможностей добавим в приложение выбор языка. Ещё нам потребуется input для загрузки самого изображения и поле для вывода результатов обработки.

Простейшая разметка выглядит так:

3. Запускаем Tesseract

3.1. Воркер

Всю работу выполняет воркер TesseractWorker, поэтому импортируем из пакета tesseract.js функцию createWorker. При создании воркеру можно передать функцию логирования, вызываемую при переходе между этапами обработки.

            import { createWorker } from 'tesseract.js';

const worker = createWorker({
  logger: (data) => console.log(data)
});
        

Приходящий в логгер объект данных содержит два поля: status и progress – их можно использовать для отображения прогресса обработки.

Логирование процесса обработки изображения
Логирование процесса обработки изображения

Инициализируем воркер с нужными настройками языка и запускаем процесс распознавания:

            async function recognize() {
  const file = document.getElementById('file').files[0];
  const lang = document.getElementById('langs').value;
  await worker.load();
  await worker.loadLanguage(lang);
  await worker.initialize(lang);
  const { data: { text } } = await worker.recognize(file);
  console.log(text);
  await worker.terminate();
  return text;
}
        

3.2. Метод recognize

То же самое можно сделать более декларативно – с помощью метода recognize объекта Tesseract:

            import Tesseract from 'tesseract.js';

function recognize() {
  const file = document.getElementById('file').files[0];
  const lang = document.getElementById('langs').value;

  return Tesseract.recognize(file, lang, {
      logger: data => console.log(data),
    })
   .then(({ data: {text }}) => {
     console.log(text);
     return text;
   })
}
        

Этот метод принимает файл, язык и объект настроек с логгером. Метод работает асинхронно и возвращает обычный Promise.

4. Отображение прогресса и результата

В результате выполнения метода recognize мы получаем много полезных данных:

Результат работы метода recognize
Результат работы метода recognize

Тут не только извлечённый текст, но и уровень уверенности (confidence), и даже расположение на изображении символов, слов, абзацев.

Осталось продемонстрировать полученные результаты пользователю.

            const log = document.getElementById('log');

// Отслеживание прогресса обработки
function updateProgress(status, progressValue) {
  log.innerHTML = '';
  const statusText = document.createTextNode(status);
  const progress = document.createElement('progress');
  progress.max = 1;
  progress.value = progressValue;
  log.appendChild(statusText);
  log.appendChild(progress);
}

// Вывод результата
function setResult(text) {
  log.innerHTML = '';
  text = text.replace(/\n\s*\n/g, '\n');
  const pre = document.createElement('pre');
  pre.innerHTML = text;
  log.appendChild(pre);
}
        

Наконец, добавим обработчик кликов на кнопку Начать обработку и соберём всё вместе:

            import Tesseract from 'tesseract.js';

// Распознавание изображения
function recognize(file, lang, logger) {
  return Tesseract.recognize(file, lang, {logger})
   .then(({ data: {text }}) => {
     return text;
   })
}

const log = document.getElementById('log');

// Отслеживание прогресса обработки
function updateProgress(data) {
  log.innerHTML = '';
  const statusText = document.createTextNode(data.status);
  const progress = document.createElement('progress');
  progress.max = 1;
  progress.value = data.progress;
  log.appendChild(statusText);
  log.appendChild(progress);
}

// Вывод результата
function setResult(text) {
  log.innerHTML = '';
  text = text.replace(/\n\s*\n/g, '\n');
  const pre = document.createElement('pre');
  pre.innerHTML = text;
  log.appendChild(pre);
}

document.getElementById('start').addEventListener('click', () => {
  const file = document.getElementById('file').files[0];
  if (!file) return;

  const lang = document.getElementById('langs').value;

  recognize(file, lang, updateProgress)
    .then(setResult);
});
        

Вот и вся программа! Поэкспериментируйте с разными изображениями и языками.

Наша демка сейчас обладает самым минимальным функционалом. Её можно существенно улучшить:

  • Оформить элементы с помощью CSS.
  • Добавить предпросмотр загруженного изображения.
  • Установить изображение по умолчанию.
  • Разрешить drag-n-drop-перетаскивание файлов.

Работающий демо-проект (с улучшениями) + его github-репозиторий.

***

Tesseract.js – отличная JS-библиотека для распознавания текста с изображений. Конечно, её возможности сильно ограничены. Зашумлённый фон и нестандартные шрифты существенно снижают точность обработки. Однако для множества проектов она может стать замечательным решением. В комментариях вы можете поделиться примерами того, как библиотека распознала (или не распознала) какой-либо текст – вместе мы сможем лучше понять ограничения библиотеки.

14
Апр
2020

Когда антивирус бессилен: распознавание вредоносных программ методами компьютерного зрения

Небольшая заметка про отображение бинарных файлов в виде картинок и применение средств computer vision для обнаружения троянов и вирусов.

Любой софт,
предназначенный специально д…

13
Апр
2020

Нейросети в помощь геймдев-художнику: машинное обучение для создания игрового пиксель-арта

О том, как генеративно-состязательные нейросети с Pix2Pix-архитектурой помогают художникам ускорить создание игрового дизайна.

Приведённые на заголовочной картинке спрайты взяты …

22
Мар
2020

11–12 апреля, Казань: хакатон «Интеллектуальные транспортные системы и элементы ситуационных центров»

Командам за 36 часов предстоит найти решения для задач управления «умной» транспортной инфраструктурой или развития информационно-аналитической платформы «Ситуационный центр».
— Читать дальше «Хакатон «Интеллектуальные транспортные системы и элементы с…

15
Мар
2020

Просто добавь нейросеть: 7 исторических фильмов в 4K и 60 FPS

Москва, Париж, Нью-Йорк и Англия времен Прекрасной эпохи, Луна и Марс начала космических путешествий – видео, качество которых улучшено с помощью нейросетей. Приятного просмотра!

04
Мар
2020

Хороший, плохой, злой: как Яндекс использует нейросети для борьбы со спамом и матом

Разработчики Яндекса автоматизировали борьбу со спамом и матом в своих сервисах. Рассказываем, какие инструменты они для этого использовали.

Любой сайт, где пользователи могут са…

03
Мар
2020

10 инструментов искусственного интеллекта Google, доступных каждому

Обзор десяти инструментов Google для ИИ, которые могут использовать разработчики, компании и аналитики. Где искать качественные наборы данных и как привязать к проекту готовую модель TensorFlow.

21
Фев
2020

Что умеют нейросети: 10 крутых примеров из недавних новостей

Десяток забавных и полезных применений нейронных сетей для обработки фотографий, видеороликов, управления беспилотными автомобилями, поиска новых лекарств и просто фана.

Мы погул…

16
Фев
2020

100+ лекций экспертов Постнауки об анализе данных, ИИ, роботах, математике и сетях

Более ста монологов российских (и не только) экспертов из 16 научных областей, связанных с информационными технологиями. Средняя длительность роликов составляет 15 мин.

Недавно …

07
Фев
2020

Как специалисту по Data Science написать классификатор, если часть данных неверно размечена

Данные важны для аналитики. Однако если они размечены неверно, от них может быть больше вреда, чем пользы. Разбираемся, как работать с такими данными.
— Читать дальше «Как специалисту по Data Science написать классификатор, если часть данных неверно ра…

04
Фев
2020

Python и динамическое программирование на примере задачи о рюкзаке

Как собрать ценные вещи в поездку так, чтобы хватило места? Без избыточной терминологии рассказываем о классической задаче, решаемой методом динамического программирования.

Момент настал – вы переезжаете в Сан-Франциско, чтобы стать известным дата сайентистом. Будете работать в крупной компании и скоро прославитесь. Но не всё сразу. Поначалу придётся ютиться в жилище, много меньшем, чем нынешний дом. Нужно решить, что взять с собой. Вы аналитик и намерены решить задачу эффективно. Обсудим алгоритм?

Описание проблемы

Представим, что на данный момент вы живёте в довольно большой квартире площадью 100 м2, а вещи занимают 50 м2. Вы знаете, что площадь нового жилья составит 40 м2 и хотите, чтобы вещи занимали не более 20 м2. Вы любите, когда на полу есть свободное место, да и не всё можно поставить впритык друг к другу. Нужно составить список вещей, определить площадь, занимаемую каждой вещью и составить рейтинг ценности предметов. Конечная цель – максимизировать материальную ценность того, что разместится на 20 квадратных метрах.

Перечисляем предметы

Вы составили список вещей и выразили занимаемую площадь в квадратных дециметрах (1 дм2 = 0.01 м2). Каждому предмету сопоставили ценность по шкале от 0 до 100. Получилась сводка данных о 29 предметах, которую можно оформить как словарь вида {'название предмета':(площадь, ценность) }:

            stuffdict = {'couch_s':(300,75), 
             'couch_b':(500,80), 
             'bed':(400,100), 
             'closet':(200,50), 
             'bed_s':(200,40), 
             'desk':(200,70), 
             'table':(300,80),
             'tv_table':(200,30),
             'armchair':(100,30),
             'bookshelf':(200,60), 
             'cabinet':(150,20),
             'game_table':(150,30),
             'hammock':(250,45),
             'diner_table_with_chairs':(250,70),
             'stools':(150,30),
             'mirror':(100,20),
             'instrument':(300,70),
             'plant_1':(25,10),
             'plant_2':(30,20),
             'plant_3':(45,25),
             'sideboard':(175,30),
             'chest_of_drawers':(25,40),
             'guest_bed':(250,40),
             'standing_lamp':(20,30), 
             'garbage_can':(30,35), 
             'bar_with_stools':(200,40), 
             'bike_stand':(100,80),
             'chest':(150,25),
             'heater':(100,25)
            }
        

Готово! Теперь видно, что кровать ('bed') занимает 400 дм2, а её ценность составляет 100, игровой стол ('game_table') занимает 150 дм2 квадратных метра и имеет ценность 30.

Максимазация ценности

Как максимизировать суммарную ценность объектов так, чтобы суммарная площадь не превышала 2000 дм2? Можно попробовать перебрать все возможные комбинации и рассчитать суммарную ценность для каждой из комбинаций. Решение получится, если выбрать максимальную суммарную ценность для 2000 дм2. Но вот незадача: и комбинаторика, и теория множеств утверждают, что 29 предметов дают 2²⁹ возможных комбинаций выбора предметов.

То есть более 536 миллионов. Похоже, такой перебор займёт некоторое время. Нельзя ли быстрее?

Стоит подумать о других вариантах. Что если начать с наиболее ценного предмета, затем следующего за ним по ценности, и так до тех пор, пока не заполнятся 20 квадратных метров? Такой алгоритм явно быстрее. Но даст ли он оптимальное решение? Есть сомнения. Как быстро решить задачу и найти лучшее решение?

Примечание: описанные выше случаи соответствуют полному перебору (метод «грубой силы», англ. brute force) и жадному (англ. greedy) алгоритму.

***

Динамическое программирование

Соответствующий класс проблем называют задача о рюкзаке. Своё название проблема получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

К счастью, знакомый слышал об этом классе задач и подсказал вам более разумный способ справиться с проблемой. Он объяснил, что можно рекурсивно разделить проблему на более мелкие подзадачи. Сохраняя результаты в ячейках таблицы мемоизации и используя их на следующих итерациях, вы быстро найдёте оптимальное решение. Вы как бы обменяете программную память на время. То есть воспользуетесь методом динамического программирования.

Этапы решения задачи с помощью динамического программирования

  1. Создаём словарь со списком элементов и их параметрами (площадь, ценность).
  2. Создаём списки значений площади и ценности.
  3. Используем списки для построения таблиц мемоизации.
  4. Получаем элементы из последней строки таблицы. Последняя строка таблицы мемоизации содержит оптимальное решение. Возможно, существует несколько оптимальных решений. Например, когда есть два предмета с одинаковой площадью и стоимостью или ряд предметов имеют суммарные площадь и ценность, как у другого предмета.

Рассмотрим, как реализовать этот план на практике. Первый шаг мы предусмотрительно выполнили ранее, перейдём ко второму.

Создаём списки значений площади и ценности

Разделяем списки значений исходного словаря, например, так:

            def get_area_and_value(stuffdict):
    area = [stuffdict[item][0] for item in stuffdict]
    value = [stuffdict[item][1] for item in stuffdict]        
    return area, value
        

Используем списки для мемоизации

Пусть n – общее число предметов, A – их максимально допустимая суммарная площадь в новом жилище (2000 дм2). Составим таблицу из n + 1 строк и A + 1 столбцов. Строки пронумеруем индексом i, столбцы – индексом a (чтобы помнить что в столбцах площадь, area). То есть в качестве номеров столбцов мы рассматриваем дискретные значения площади, отличающиеся друг от друга на 1.

            def get_memtable(stuffdict, A=2000):
      area, value = get_area_and_value(stuffdict)
      n = len(value) # находим размеры таблицы
      
      # создаём таблицу из нулевых значений
      V = [[0 for a in range(A+1)] for i in range(n+1)]

      for i in range(n+1):
            for a in range(A+1):
                  # базовый случай
                  if i == 0 or a == 0:
                        V[i][a] = 0

                  # если площадь предмета меньше площади столбца,
                  # максимизируем значение суммарной ценности
                  elif area[i-1] <= a:
                        V[i][a] = max(value[i-1] + V[i-1][a-area[i-1]], V[i-1][a])

                  # если площадь предмета больше площади столбца,
                  # забираем значение ячейки из предыдущей строки
                  else:
                        V[i][a] = V[i-1][a]       
      return V, area, value
        

Вначале создаётся и заполняется таблица в виде вложенных списков. Нулевую строку и нулевой столбец заполняем нулями. Это базовый случай: когда площадь или количество элементов равны нулю, значение ячейки равно нулю. Далее таблица значений V будет заполняться строка за строкой слева направо и сверху вниз:


Если площадь текущего элемента меньше или равна площади (номеру столбца) текущей ячейки, вычисляем значение ячейки следуя правилу:

            V[i][a] = max(value[i-1] + V[i-1][a-area[i-1], V[i-1][a])
        

То есть выбираем максимальное из двух значений:

  1. Сумма ценности текущего предмета value[i-1] и величины элемента из предыдущей строки i-1 с площадью, меньшей на величину площади текущего предмета area[i-1]. Обратите внимание: нужно помнить, что элементы в таблице отличаются по нумерации на единицу из-за нулевой строки.
  2. Значение элемента предыдущей строки с той же площадью, то есть из того же столбца, что текущая ячейка. То же значение устанавливается в случае, если площадь текущей ячейки меньше, чем площадь текущего элемента (см. блок else)

За счёт такого подхода при одной и той же суммарной площади элементов происходит максимизация суммарной ценности.

Забираем нужные элементы из последней строки таблицы

Найдём набор предметов с максимальной суммарной ценностью для указанной возможной площади. Начнём с нижнего правого угла таблицы с максимальным значением, и соберём предметы:

            def get_selected_items_list(stuffdict, A=2000):
      V, area, value = get_memtable(stuffdict)
      n = len(value)
      res = V[n][A]      # начинаем с последнего элемента таблицы
      a = A              # начальная площадь - максимальная
      items_list = []    # список площадей и ценностей
    
      for i in range(n, 0, -1):  # идём в обратном порядке
            if res <= 0:  # условие прерывания - собрали "рюкзак" 
                  break
            if res == V[i-1][a]:  # ничего не делаем, двигаемся дальше
                  continue
            else:
                  # "забираем" предмет
                  items_list.append((area[i-1], value[i-1]))
                  res -= value[i-1]   # отнимаем значение ценности от общей
                  a -= area[i-1]  # отнимаем площадь от общей
            
      selected_stuff = []

      # находим ключи исходного словаря - названия предметов
      for search in items_list:
            for key, value in stuffdict.items():
                  if value == search:
                        selected_stuff.append(key)
            
      return selected_stuff
        

Итак, мы нашли список:

            >>> stuff = get_selected_items_list(stuffdict)
>>> print(stuff)
['bike_stand', 'garbage_can', 'standing_lamp', 'chest_of_drawers',
'plant_3', 'plant_2', 'diner_table_with_chairs', 'bookshelf',
'armchair', 'table', 'desk', 'bed', 'couch_s']
        

Проверим суммарные площадь и ценность собранных предметов:

            >>> totarea = sum([stuffdict[item][0] for item in stuff])
>>> totvalue = sum([stuffdict[item][1] for item in stuff])
>>> print(totarea)
2000
>>> print(totvalue)
715
        

Получилось! Собираем вещи и отправляемся в путь (звучит песня Mamas & Paps – San Francisco).

***

Бонус: Тепловая карта таблицы

Тепловая карта ниже отображает рассмотренную выше таблицу. По оси абсцисс отложена доступная площадь, по оси ординат – список предметов. Цветовая шкала соответствует суммарной ценности. Можно видеть, как значения возрастают по мере продвижения по таблице снизу вверх.


Для построения использовалась библиотека matplotlib:

            def plot_memtable(V, stuffdict):
    plt.figure(figsize=(30,15))
    item_list = list(stuffdict.keys())
    item_list.insert(0, 'empty')
    sns.heatmap(V, yticklabels=item_list)
    plt.yticks(size=25)
    plt.xlabel('Area', size=25)
    plt.ylabel('Added item', size=25)
    plt.title('Value for Area with Set of Items', size=30)
    plt.show()
        

А тем, кто следит за нашим сериалом головоломок, динамическое программирование также поможет решить текущую задачу (головоломку о беглеце).

23
Янв
2020

Что нового в Pandas 1.0? ?

Pandas – популярная библиотека Python для работы с табличными данными, добавляющая к структуре массива NumPy именованные строки и столбцы, а также множество удобных методов. Pandas является одной из важных причин, почему Python стал доминирующим языком программирования в Data Science.

22
Янв
2020

21–22 февраля, Минск: конференция PyCon Belarus 2020

Ежегодная конференция для питонистов с обсуждением самых современных сфер применения языка и практикоориентированными воркшопами для спецов любого уровня.
— Читать дальше «Конференция PyCon Belarus 2020»

22
Янв
2020

8–9 февраля, Москва: хакатон Moscow Travel Hack

Хакатон, на котором от участников ждут решения, которые помогут создать новые проекты в области туризма и гостеприимства.
— Читать дальше «Хакатон Moscow Travel Hack»

22
Янв
2020

Обучение модели обнаружения объектов YOLO на пользовательском наборе данных

Рассматриваем подготовку собственного датасета и обучение YOLO на примере задачи распознавания шахматных фигур.

Нейросетевые модели обнаружения объектов делают много полезного. К…

17
Янв
2020

Наглядная шпаргалка по операциям с DataFrame в pandas для data wrangling и не только

Удобная и наглядная шпаргалка по основным операциям с DataFrame в pandas. Подходит для data wrangling и не только.
— Читать дальше «Наглядная шпаргалка по операциям с DataFrame в pandas для data wrangling и не только»

16
Янв
2020

Как повысить продуктивность при анализе данных? 25 неочевидных инструментов

Список бесплатных инструментов и библиотек для аналитиков данных. Заслуживающие внимания пакеты, программы и ресурсы, о которых не так часто упоминают, как о NumPy, Pandas или Jupyter.

Ниже представлен сжатый обзор 25 инструментов для самых разнообразных приложений науки о данных. Быстрый скрапинг веб-страниц и визуализация, анализ поведения клиентов и безопасное хранение ключей, работа в команде и развертывание моделей на облачных GPU.

В комментариях к публикации предлагаем поделиться своими любимыми библиотеками и инструментами.

Обзор DS инструментов:

  • Airtable: электронная таблица с мощью базы данных, альтернатива Google Sheets или Microsoft Excel. Отлично работает с Pandas, благодаря Python API. То что нужно для демонстрации результатов.
  • Orange: open source платформа, заточенная под машинное обучение и визуализацию данных, для которой не нужно уметь кодить. Качественная альтернатива Tableau или Power BI.
  • MarkDown: приложение для заметок на Node.js, полноценно работающее в офлайне с возможностью размещения на своём сервере.
  • Deepnote: приложение на базе Jupyter Notebook, созданное для совместной работы в реальном времени.

  • Dash by Plotly: JavaScript инструмент визуализации данных с открытым исходным кодом. Запустите готовую модель на Python или R, а Dash позаботится об остальном. Идеально подходит для создания мелких веб-приложений для показа клиенту.
  • KeeWeb: средство для безопасного хранения API-ключей и паролей.
  • MLxtend (сокр. от Machine Learning Extensions) – библиотека Python инструментов для повседневных задач обработки данных. Создатель – автор книги «Машинное обучение на Python» Себастьян Рашка.
            import numpy as np
import matplotlib.pyplot as plt
import matplotlib.gridspec as gridspec
import itertools
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
from sklearn.ensemble import RandomForestClassifier
from mlxtend.classifier import EnsembleVoteClassifier
from mlxtend.data import iris_data
from mlxtend.plotting import plot_decision_regions

# Initializing Classifiers
clf1 = LogisticRegression(random_state=0)
clf2 = RandomForestClassifier(random_state=0)
clf3 = SVC(random_state=0, probability=True)
eclf = EnsembleVoteClassifier(clfs=[clf1, clf2, clf3],
                              weights=[2, 1, 1], voting='soft')

# Loading some example data
X, y = iris_data()
X = X[:,[0, 2]]

# Plotting Decision Regions

gs = gridspec.GridSpec(2, 2)
fig = plt.figure(figsize=(10, 8))

labels = ['Logistic Regression', 'Random Forest', 
          'RBF kernel SVM', 'Ensemble']

for clf, lab, grd in zip([clf1, clf2, clf3, eclf],
                         labels,
                         itertools.product([0, 1],
                         repeat=2)):
    clf.fit(X, y)
    ax = plt.subplot(gs[grd[0], grd[1]])
    fig = plot_decision_regions(X=X, y=y,
                                clf=clf, legend=2)
    plt.title(lab)

plt.show() 
        

  • Lifetimes: библиотека для анализа поведения клиентов, прогнозирования прибыли и оттока
  • GitLab: альтернативное GitHub хранилище репозиториев с возможностью скрывать групповые репозитории. Удобно для закрытой командной работы и группового участия в ML-соревнованиях.
  • Draw.io: создания диаграмм для планирования проекта.
  • Spider: простой скраппер для веб-страниц в виде расширения Chrome. Можно скачивать страницы в CSV/JSON формате.
  • Simple Scraper: превратите любой сайт в API.
  • Airbnb Knowledge repo: ресурс для обмена знаниями между специалистами в области обработки данных и других технических профессий. Был создан для решения проблемы распространения знаний в рамках растущей команды.

  • Kyso: сервис помогает создать привлекательное и структурированное портфолио аналитика данных. Вы сможете просматривать чужие портфолио, увидите, как другие представляют себя и свои данные. Бесплатный период 14 дней.
  • LabelImg: графический инструмент для разметки объектов на картинках, добавление подписей и тегов изображений.

  • Reveal.js: фреймворк для создания HTML-презентаций. Многие аналитики используют его на своих выступлениях.
  • PythonAnywhere: простой способ развернуть онлайн лёгкий ML-проект на Python и сопутствующих библиотеках, если пока требуется лишь проверить гипотезу. В случае успеха легко перенести на AWS (руководство).
  • Sheety: превратите Google Sheet в API и моделируйте данные в реальном времени.
  • Jupyterthemes: устали от текущей темы Jupyter Notebook? Есть много других.
  • Light GBM: одна из популярных библиотек для односторонней выборки на основе градиента. В последние годы приобрела большую популярность, особенно на Kaggle.

  • Machine Learning A-Z: Practice Datasets and Codes: большое собрание данных и кода на Python и R, охватывающее популярные алгоритмы машинного обучения.
  • Gradient by Paperspace: запускайте блокноты Jupyter бесплатно на облачной машине, оснащённой графическими процессорами.
  • Glueviz: визуализируйте многомерные наборы данных. Бесплатный инструмент на основе Python (поставляется с Anaconda). Отлично подходит для поиска связей между наборами данных.

  • Hot dog or not hot dog?: мануал, не требующий знаний AI, машинного обучения и даже программирования. Руководство о том, как с IBM Watson написать программу для проверки, является ли объект хот-догом 🌭 или нет. Самый важный ресурс в подборке 😉
  • FloydHub Workspaces: облачная среда разработки для глубокого обучения. Можно запускать блокноты Jupyter, скрипты Python, использовать терминал и многое другое.

О чём-то не упомянули? Напишите, мы дополним статью вашими ссылками