Пользователь
0,0
рейтинг
9 января 2013 в 17:02

Разработка → Data Mining: Первичная обработка данных при помощи СУБД. Часть 1 tutorial

О чем статья

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

С этой точки зрения, очень интересным будет ресурс Kaggle[1], который превращает исследование данных в спорт. Там проводят соревнования по анализу данных. Некоторые соревнования — с обучающими материалами и предназначены для начинающих. Вот именно обучению анализу данных, на примере решения одной из обучающих задач, и будет посвящён цикл статей. Первая статья будет о подготовке данных и использованию СУБД для этой цели. Собственно, о том, как и с чего начать. Предполагается что читатель понимает SQL.

Задача: «Титаник: Машинное обучение на катастрофах.»

Одно из двух соревнований для начинающих — «Титаник»[2]. Перевод задания:
«Гибель Титаника это одно из наиболее бесславных кораблекрушений в истории. 15 апреля 1912 года, во время своего первого рейса, Титаник затонул после столкновения с айсбергом, погубив 1502 из 2224 человек пассажиров и команды. Эта сенсционная трагедия шокировала международное сообщество и привела к улучшению требований правил техники безопасности на судах. Одной из причин того, что кораблекрушение повлекло такие жертвы, стала нехватка спасательных шлюпок для пассажиров и команды. Также был элемент счастливой случайности, влияющий на спасение от утопления. Также, некоторые группы людей имели больше шансов выжить чем другие, такие как женщины, дети и высший класс. В этом соревновании мы предложим вам завершить анализ того, какие типы людей скорее всего спасутся. В частности, мы попросим вас применить средства машинного обучения для определения того, какие пассажиры спасутся в этой трагедии.»

Данные

Для соревнования дано два файла: train.csv и test.csv. Данные в текстовом виде разделенные запятыми. Одна строка — одна запись о пассажире. Некоторые даные для записи могут быть неизвестны и пропущены.
ОПИСАНИЕ ПЕРЕМЕННЫХ:
Имя переменной Что обозначает
survival Спасение (0 = Нет; 1 = Да)
pclass Класс пассажира(1 = 1st; 2 = 2nd; 3 = 3rd)
name Имя
sex Пол
age Возраст
sibsp Количество Братьев(Сестер)/Супругов на борту
parch Количество Родителей/Детей на борту
ticket Номер билета
fare Пассажирский тариф
cabin Каюта
embarked Порт посадки(C = Cherbourg; Q = Queenstown; S = Southampton)

Примечание:
Pclass является показателем социально-экономического статуса (SES)
1st ~ Upper; 2nd ~ Middle; 3rd ~ Lower
Возраст в годах; Дробный, если возраст меньше единицы(1)
Если возраст оценочный — то он в форме xx.5
Следующие определения используются для sibsp и parch.
Братья(Сестры): Брат, Сестра, Сводный брат, или Сводная сестра среди пассажиров Титаника
Супруги: Муж или Жена среди пассажиров Титаника (Любовницы и Женихи игнорируются)
Родители: Мать или Отец среди пассажиров Титаника.
Дети: Сын, Дочь, Пасынок или Падчерица среди пассажиров Титаника.
Другие члены семьи исключены, включая кузенов, кузин, дядь, тетушек, невесток, зятей
Дети, путешествующие с нянями имели parch=0.
Точно также путешествующие с близкими друзьями, соседями, не учитываются в родственных отношениях parch.


Эта задача, как видим, является хорошо структурированной и поля практически определены. Собственно, первый этап заключается в том, чтобы подать данные для машинного обучения. Вопросы выбора и переопределения полей, разбиения, слияния, классификации — зависят от подачи данных. По большому счету вопрос упирается в кодирование и нормализацию. Кодирование качественных признаков(существует несколько подходов) и предварительную обработку данных перед применением методов машинного обучения.Данная задача не sсодержит действительно большого объема данных. Но большинство задач(например Herritage Health Pr., Yandex интернет-математика ) не такие структурированные и приходиться оперировать миллионами записей. Делать это удобней с использованием СУБД. Я выбрал СУБД PostgreSQL. Весь SQL код писался под эту СУБД, но с небольшими изменениями подойдет и для MySQL, Oracle и MS SQL сервер.

Загружаем данные

Скачиваем два файла — train.csv и test.csv.
Создаем таблицы для хранения данных:
--Удаляем таблицу если она существует
DROP TABLE IF EXISTS titanik_train;
--Создаем таблицу
CREATE TABLE titanik_train
(
  survived int,
  pclass int,
  name varchar(255),
  sex varchar(255),
  age float,
  sibsp int,
  parch int,
  ticket varchar(255),
  fare float,
  cabin varchar(255),
  embarked varchar(255)
);
--Загружаем таблицу из CSV файла '/home/andrew/titanik/train.csv'.
-- HEADER значит что в CSV файле есть заголовок c именами полей.
COPY titanik_train FROM '/home/andrew/titanik/train.csv' CSV HEADER;

DROP TABLE IF EXISTS titanik_test;
CREATE TABLE titanik_test
(
  pclass int,
  name varchar(255),
  sex varchar(255),
  age float,
  sibsp int,
  parch int,
  ticket varchar(255),
  fare float,
  cabin varchar(255),
  embarked varchar(255)
);
COPY titanik_test FROM '/home/andrew/titanik/test.csv' CSV HEADER;

В результате получаем две таблицы: с тренировочными и тестовыми данными.
В этом случае не было ошибок загрузки данных. Т.е. все данные соответствовали тем типам, которые мы определили. Если же ошибки появляются — тогда есть два пути: сначала исправить и регулярными выражениями и редактором вроде sed(либо командой на основе perl -e) или сначала все загрузить в виде текстовых данных, и исправлять регулярными выражениямии запросами средствами СУБД.
Добавим первичный ключ:
--создаем последовательность
CREATE SEQUENCE titanik_train_seq;
--создаем таблицу с первичным ключем
select nextval('titanik_train_seq') as id, a.* 
into titanik_train_pk
from titanik_train a;


Исследование данных


Таблицы СУБД это всего-навсего средство. Средство помогающее удобнее изучать и преобразовывать данные. С самого начала удобно разделить поля записи про каждого пассажира на числовые и текстовые — по типу данных. Для применения машинных алгоритмов обучения, все равно прийдется все преобразовать к числовому представлению. И от того, насколько адекватно мы это сделаем, очень сильно зависит качество работы методов, которые мы выберем.

Числовые данные:
survived, pclass, age, sibsp, parch, fare
Текстовые данные:
name, sex, ticket, cabin, embarked

Начнем с данных, которые представлены в текстовом виде. Фактически, это проблема кодирования информации. И тут не обязательно самый простой подход будет самым правильным. Например, если отвлечься от этого примера, и представить, что у нас есть поле, которое определяет должность:
  • генеральный директор;
  • начальник отдела;
  • старший смены;
  • уборщик;
  • стажер;

Вполне логично кодировать их таким образом:
генеральный директор 5 1
начальник отдела 4 0.75
старший смены 3 0.5
уборщик 2 0.25
стажер 1 0

Т.е. мы таким образом попытались вписать такой вот элемент реальности как должности, в математическое представление. Это один(простейший) вариант подачи такой информации. Это при условии, что «расстояние» между должностями(что не соответствует реальности) считаем одинаковым. Т.е. тут возникает вопрос, а что такое «расстояние между должностями»? Важность? Объем полномочий? Объем ответствености? Распространенность? Место в иерархии? Или количество работников в такой должности на предприятии? Масса вопросов, на которые для задачи оторванной от реальности и не будет ответа. А в реальности ответы есть. И есть методы, которые помогают приблизить математическое представление к реальности. Но это тема для отдельной и сложной статьи, а пока, примем, что мы будем стараться кодировать данные в диапазоне от 0 до 1(Код 2).
Итак, для данных которые можно сравнить, есть хоть какое-то объяснение почему мы именно так, с определением меньшего и большего кодировали даные.
Ведь числа несут количественную информацию! Что-то больше, а что-то меньше!
А если у нас в качестве описательной информации «имя». Имеем ли мы право кодировать Данные например вот так:
Имя Код2
Николай 0
Петр 0.5
Павел 1

Вроде бы и можем мы так кодировать, но получается, что мы добавляем к данным составляющую, которой нет — сравнение имен(числа: больше-меньше) по неизвестному признаку. Логичней было бы подать данные несколько иначе(Ещё это называют bag-of-words):
№ записи Николай Петр Павел
15602 0 1 0
15603 0 0 1
15604 1 0 0

И вот сколько будет имен — столько будет и полей. И значения: 0 или 1. Недостаток налицо — а если у нас будет миллион разных имен? Что делать? В нашей простой задаче такой беды нет, но отвечу — это довольно динамично растущая отрасль компьютерных наук и математики — сжатие входных данных. Одно из ключевых слов — «sparse matrix». Ещё — «autoencoder», «Vowpal Wabbit»[3], «feature hashing». Опять таки — это тема для статьи. Кроме того, на хабре мелькали материалы по этой теме. Но для нашей задачи, мы пока отвлечемся от этой проблемы. И вернемся к вопросу:
А имеет ли первое представление право на жизнь?
Ответ сильно зависит от того, а можем ли мы пренебречь добавленной нами составляющей о ранжировании «неизвестного признака по которому мы сравнивали имена». Очень часто приходиться пренебрегать — когда другой возможности нет.

А если поставить вместо имен например число-буквенные номера билетов(что уже ближе к нашей задаче). С билетами проще — есть серия и есть номер. Номер можем оставить так как есть. Возможно он определяет место посадки, и соответственно дальность расположения от входа и т.п. А вот кодирование серии — уже сложнее. Прежде всего нужно ответить на вопрос: А может ли одно значение в реальности быть представлено в виде разных строк в даных? Ответ однозначный — может. Т.е. нужно это проверить. Самый простой вариант — опечатка. Лишняя точка, запятая, пробел или тире.
Наличие таких данных уже влечет искажения, и модель кторая построена на «испорченных» сведениях не покажет хорошего результата (только если это не делалось контролируемо для улучшения свойства обобщения модели).
Для начала отделим номер билета от серии(типа, марки и т.п.).
Для этого просмотрим данные, предварительно отсортировав по названию. Выделим группы данных:
  • билет без серии
  • билет с серией

Далее поступим таким образом: создадим таблицу, где серия выделена в отдельное поле. Там где нет серии — пока поставим пустое значение. Для этого воспользуемся запросом:
select id,survived,pclass,"name",sex,age,sibsp,parch,ticket,fare,cabin,embarked,
m[1] as ticket_type, m[2] as ticket_number
into titanik_train_1
from 
(select id,
  survived,pclass,"name",sex,age,sibsp,parch,ticket,fare,cabin,embarked,
  regexp_matches(ticket, '^\s*?(.*?)\s*?(\d*?)$') as m 
  from titanik_train_pk
) as a;

где '^\s*?(.*?)\s*?(\d*?)$' — регулярное выражение, позволяющее выделить части в поле билет — серию и номер в массив.
Номера оставим так как они есть, можно проверить регулярным выражением на наличие нецифровых символов. При помощи подобного регулярного выражения.
Проблема двойников


Если один и тот же объект реальности именуется по разному — получаем проблему двойников. Остановимся отлько лишь на одном аспекте обнаружения двойников: Опечатки в наименовании. Учитывая, что объем наших данных небольшой, и подлежит простому просматриванию, поступим таким образом — выведем все уникальные значения поля из таблицы.

Запрос:
select ticket_type, count(ticket_type) from titanik_train_1 group by 1 order by 2 desc;


А вот результат, где я отметил предположительно одинаковые значения, которые обозначены разными строками. 45 записей.

Довольно много совпадений. Если вникнуть в задачу глубже и узнать по какому принципу маркировались билеты — можно еще сократить количество наименований. Но, одним из условий задачи было не использовать дополнительных сведений по этой широкоизвестной трагедии. Потому остановимся только на этом.

Запросы для изменения данных выглядят так:
update  titanik_train_1 set ticket_type='A.5.' where ticket_type = 'A./5.';
update  titanik_train_1 set ticket_type='A.5.' where ticket_type = 'A/5';
update  titanik_train_1 set ticket_type='A.5.' where ticket_type = 'A/5.';
update  titanik_train_1 set ticket_type='A.5.' where ticket_type = 'A/S';
update  titanik_train_1 set ticket_type='A/4' where ticket_type = 'A/4.';
update  titanik_train_1 set ticket_type='A/4' where ticket_type = 'A4.';
update  titanik_train_1 set ticket_type='C.A.' where ticket_type = 'CA';
update  titanik_train_1 set ticket_type='C.A.' where ticket_type = 'CA.';
update  titanik_train_1 set ticket_type='SW/PP' where ticket_type = 'S.W./PP';
update  titanik_train_1 set ticket_type='SC/PARIS' where ticket_type = 'SC/Paris';
update  titanik_train_1 set ticket_type='SOTON/O.Q.' where ticket_type = 'SOTON/OQ';
update  titanik_train_1 set ticket_type='SOTON/O2' where ticket_type = 'STON/O 2.';
update  titanik_train_1 set ticket_type='SOTON/O2' where ticket_type = 'STON/O2.';
update  titanik_train_1 set ticket_type='W/C' where ticket_type = 'W./C.';
update  titanik_train_1 set ticket_type='W.E.P.' where ticket_type = 'WE/P';

Теперь записей 30.
В более сложных задачах, обработка существено отличается. Особенно, если просмотреть все не представляется возможным. Тогда можно воспользоваться функцией Левенштейна — это позволит найти близкие по написанию слова. Можна ее немного подправить и сделать слова которые отличаются только знаками препинания еще ближе. Опять-же возвращаемся к понятию меры и метрики — а что понимать под растоянием между словами? Символы которые более похожи по внешнему виду B и 8? Или те которые звучат похоже?
В принципе, таким нехитрым способом нужно пройтись по всем символьным полям в тренировочной и тестовой таблицах. Ещё, как улучшение можно отметить объединение данных по столбцам из этих таблиц перед поиском двойников.
О распределенности. На этом этапе работа по обработке данных не требует специальных знаний и может быть легко распаралеллена между некоторым числом исполнителей. Вот, например, на этом этапе, команда очень сильно обойдет соперника-одиночку.

Пост получился довольно объемным, потому продолжение — в следующей части.

Ссылки:

1. www.kaggle.com
2. www.kaggle.com/c/titanic-gettingStarted
3. http://hunch.net/~vw/

Обновление:
Часть вторая: habrahabr.ru/post/165281
Часть третья: habrahabr.ru/post/165283
Часть четвертая: habrahabr.ru/post/173819
Андрей Бабий @shadoof
карма
46,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (17)

  • +1
    как раз делаю последние дни тоже самое (я про титаник на кэггле), но с использованием глубоких сетей и машин Больцмана -)

    так какое место на момент публикации а вас там?
    • +1
      У меня места пока там нет — я тоже пытаюсь делать глубокими сетями и RBM, вдохновленный курсом НН на курсере www.coursera.org/course/neuralnets.
      • +1
        я по началу тупо загнал в двухслойную сеть, получил 800/1300, но это ниже чем gender benchmark -) щас вот обучается rbm
    • 0
      Тоже собираюсь заняться этой задачей, но пока засел на распознавании цифр.
      • +1
        Распознавание цифр — на хабре была статья про конволюционные сети, которые показывают хороший результат для этой задачи. Кстати, там же где взята база, на сайте Лекуна есть обзор методов для решения этой задачи. Про конволюционные сети(кстати, предложены Yann Lecun) habrahabr.ru/post/74326
        • 0
          Да, это знаю, в будущем планирую попробовать с конволюционными сетями. Но пока решил выжать максимум из SVM и из SVM в ансамблях с другими моделями.
  • 0
    кстати на счет кодирования перечислений, в МЛ удобно использовать так называемый dummy coding
    допустим переменная принимает значение из множества из n элементов, допустим k-ую категорию, то переменная заменяется набором 00..010..00 из n нулей, а на k-ом месте 1

    в табличном представлении, одна колонка заменится на n колонок
    • 0
      Да, есть такое. Но я пока не уверен, что так получиться хорошо. Подобную штуку — одна фича — 1 бит реализует vowpal_wabbit. C vowpal_wabbit.
  • +2
    Очень интересно. Надеюсь, что цикл не будет заброшен.
    • +1
      Цикл заброшен не будет — есть план дойти до финиша — пусть и с невысоким местом в таблице результатов
  • 0
    отличное начинание, будет интересно увидеть продолжение :)

    имхо, можно уделить еще внимание следующим вопросам:
    а) распространенным форматам входных данных (т.е. в каком вообще виде данные могут быть изначально);
    б) валидации данных (по крайней мере продолжить вашу базовую идею по типам данных и соответствующим способам их кодирования);
    в) работе с наборами данных с пропусками;
    г) предварительной консолидации/перегруппировке данных
    • 0
      На kaggle обычно в csv выкладывают. Валидация нужна согласен. Особенно ситуация с выбросами — все значения по 1 — а одно 1000 — скорее всего ошибка, про типы — да, регулярными выражениями их провеерить можно. пункт В — на потом, Г)скорее всего будет в следующей части.
  • +2
    Огромное спасибо, как раз то, что недавно искал! Прослушал лекции на Coursera «Computing for Data Analysing» и тут такой вот от вас подарок! Желаю довести цикл статей до какого то логического завершения а не забрасывать на первой же статье как часто делают, к сожалению…
    • 0
      Итак, вот логическое завершение цикла Data Mining: Первичная обработка данных при помощи СУБД Часть3. Дальше планирую описывать применение методов и их результативность.
  • 0
    Смущают следующие моменты:
    1. «Вроде бы и можем мы так кодировать, но получается, что мы добавляем к данным составляющую, которой нет — сравнение имен(числа: больше-меньше) по неизвестному признаку.»

    Это сравнение умозрительно. Можно формально сравнить имена по принципу «больше-меньше». Или, например, у вас имена будут: «1», «2», «3» — получается, что какое-то сравнение по неизвестному признаку уже есть? Так зачем плодить огромное количество лишних полей и потом заниматься сжатием данных?

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

    2. «Самый простой вариант — опечатка. Лишняя точка, запятая, пробел или тире.
    Наличие таких данных уже влечет искажения, и модель кторая построена на «испорченных» сведениях не покажет хорошего результата»

    На то он и статистический анализ, чтобы не зависеть существенно от ошибок. Опечатки могут и в буквах и при этом существенные. Да и просто набор данных может содержать очевидных аутлайеров. Это известная палка о двух концах: точность-устойчивость. Чем выше точность, тем ниже устойчивость как раз из-за наличия таких ошибок. Конечно, по возможности такие искажения стоит убирать, однако, делать это огульно опасно.

    3. «Довольно много совпадений. Если вникнуть в задачу глубже и узнать по какому принципу маркировались билеты — можно еще сократить количество наименований. Но, одним из условий задачи было не использовать дополнительных сведений по этой широкоизвестной трагедии. Потому остановимся только на этом.»

    Получается, что вы предположили, что в билетах были опечатки, но исправили их «как бог на душу положит», а значит намеренно внесли в данные искажения. Иногда приходится прибегать и к таким методам, но при этом хорошо бы оставить и исходный вариант и уже по итогам анализа данных решить, годятся ли ваши предположения.
    • 0
      Спасибо за комментарий!
      В целом — со всем согласен. По сути, все вращается вокруг «существенно» и «несущественно» и точность-устойчивость. Но с другой стороны — любой хрестоматийный подход говорит — постарайтесь собрать исходные данные как можно боле аккуратно. Или сделай это несколько раз.
      Огульное изменение — да, можно так сказать. Обоснованное только лишь гипотезой о том, что одно и тоже названо «немного» разными именами. И что такое «немного»? Но с другой стороны — это вариант который можно проверить. И зайти в тупик. Или наоборот.

      Исходный вариант — конечно остался, и в этом особеная прелесть хранения таблиц в базе данных. Закомментировал обновления — получил уже исходный вариант данных без правок. Либо убрал часть и т.д.

      Откуда растут ноги у первого пункта:
      1. «Вроде бы и можем мы так кодировать, но получается, что мы добавляем к данным составляющую, которой нет — сравнение имен(числа: больше-меньше) по неизвестному признаку.»
      Когда мы кодируем — мы так или иначе ранжируем. Если потом мы пытаемся строить модели — не важно регрессионные или нейросетевые или еще какие-либо, это ранжирование, и даже его крутизна и равномерность будет влиять на модель.Например, метод попарных сравнений Саати позволяет проранжировать, то, о чем можно спросить эксперта. А если спросить или проранжировать нельзя, тогда лучше, на мой взгляд, добавить лишнее поле. Хотя — согласен, момент спорный и нуждается в проверке.
      Проверю оба варианта уже в 3-4 части опуса.
      • 0
        Вы правы, а я поторопился с выводами. Даже простая регрессионная модель будет точнее с отдельными полями, если значений в перечислении больше двух. А если строить её правильно, то нужно добавлять измерения. Правда при большом количестве вариантов (как в случае с именами), если этот параметр значим, то скорее всего это следствие какого-то более простого правила.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.