Что такое датамайнинг в играх

Датамайн

Датамайн (иначе датамине, от data mine — раскопки данных) — название, обозначающее процесс извлечения информации из определенного сайта или же программы, причем информация не является официально публичной. Например, при помощи датамайна сайтов можно обнаружить будущие страницы, которые еще не опубликованы официально, если их адреса устроены регулярно по датам, аналогично в файлах компьютерных игр возможно найти параметры и числовые данные, не показываемые в актуальной игре (те же шансы получения некоторых предметов). Официально датамайн считается полулегальным, но очень тяжело определить, что он был сделан, кроме того при датамайне приложений всегда можно отключать Интернет или использовать виртуальную машину и тогда в принципе невозможно отследить, что он был произведен.

Описание [ править ]

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

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

В игре Path of Exile датамайн производится автоматически на сайте poedb.tw и обновляется после каждого патча, можно посмотреть все предметы, их свойства, все микротранзакции, в том числе и те, что ещё не были официально выпущены (так как разработчики их помещают в клиент заблаговременно). Был таким образом найден и некоторый не релизованный контент. При этом большое количество информации недоступно, например, вся информация по шансам выпадения определенных предметов, так как эта информация хранится только на сервере и не подается на клиент. Официально правилами сказано, что датамайнить клиент запрещено, но технически невозможно отследить факт проведения датамайна, если сделать копию файла Content.ggpk и работать над ней в отдельной папке.

В Fate/Grand Order долгое время клиент шифровался и делать датамайны было сложно, потом шифрование оказалось отключено после перехода на другую платформу и некоторое время китайские исследователи изымали из кода игры информацию о готовящихся героях и событиях. Впоследствии команда разработчиков перестала помещать контент заблаговременно, однако в день выхода патча всё равно стало возможно получить отдельный контент намного раньше, чем до него можно добраться в игре (на несколько часов раньше, чем сервера вообще будут включены). Были также и фейковые датамайны, где публиковались заведомо ложные сведения с целью вызвать обсуждение или потроллить сообщество.

Источник

Data Mining: что внутри

Уровни информации

Я не думаю, что открою Америку, если скажу, что не вся информация одинаково полезна. Иногда для объяснения какого-то понятия необходимо написать много текста, а иногда для объяснения сложнейших вопросов достаточно посмотреть на простую диаграмму. Для сокращения избыточности информации были придуманы математические формулы, чертежи, условные обозначения, программный код и т.д. Кроме того, важным является не только сама информация, но и ее представление. Понятно, что котировки акций более наглядно можно продемонстрировать с помощью графика, а математические формулы опишут законы Ньютона в более компактном виде.

В процессе развития информационных технологий, а также систем сбора и хранения данных — баз данных (databases), хранилищ данных (data warehousing), и с недавних пор, облачных репозиториев, возникла проблема анализа больших объемов данных, когда аналитик или управленец не в состоянии вручную обработать большие массивы данных и принять решение. Понятно, что аналитику необходимо каким-то образом представить исходную информацию в более компактном виде, с которой может справится человеческий мозг за приемлемое время.

Между уровнями нет четких граней, но такая классификация позволит нам в дальнейшем не запутаться с терминологией.

Data Mining

Осмелюсь ввести еще один термин для первого пункта — Data Extracting, который буду использовать в дальнейшем.

Information retrieval

Information retrieval используется для получения структурированных данных или репрезентативной выборки меньшего размера. По нашей классификации information retrieval оперирует данными первого уровня, а в результате выдает информацию второго уровня.

Самым простым примером information retrieval является поисковая система, которая на основании неких алгоритмов выводит часть информации из полного набора документов. Кроме того, любая система, которая работает с тестовыми данными, метаинформаций или базами данных тем или иным способом использует инструменты information retrieval. Инструментами могут выступать методы индексации, фильтрации, сортировки данных, парсеры и т.д.

Text Mining

Другие названия: text data mining, text analysis, очень близкое понятие – concern mining.

Text mining может работать как с сырыми данными, так и с частично обработанными, но в отличие от information retrieval, text mining анализирует текстовую информацию с помощью математических методов, что позволяет получать результат с элементами знания.

Задачи, которые решает text mining: нахождение шаблонов данных, получение структурированной информации, построение иерархий объектов, классификация и кластеризация данных, определение тематики или области знаний, автоматическое реферирование документов, задачи автоматической фильтрации контента, определение семантических связей и другие.

Для решения задач text mining используют статистические методы, методы интерполяции, аппроксимации и экстраполяции, нечеткие методы, методы контент-анализа.

Web Mining

Ну и наконец мы добрались к web mining – наборе подходов и техник для извлечения данных из веб-ресурсов.
Так как веб-источники, ка правило, не являются текстовыми данными, то и подходы к процессу извлечения данных отличаются в этом случае. В первую очередь необходимо помнить, что информация в вебе хранится в виде специального языка разметки HTML (хотя есть и другие форматы – RSS, Atom, SOAP, но об этом поговорим позже), веб-страницы могут иметь дополнительную метаинформацию, а также информацию о структуре (семантике) документа, каждый веб-документ находится внутри некого домена и к нему могут применяться правила поисковой оптимизации (SEO).

Это первая статья из цикла, посвященного data mining / extracting / web mining. Пожелания и аргументированная критика принимаются.

Источник

Как стать датамайнером

Подробнее о профессии датамайнера и о том, как им стать, будет рассказано в представленной статье.

Особенности профессии датамайнера

Профессия датамайнера ориентирована не просто на обработку информационных массивов, но и на поиск в них скрытых данных и взаимосвязей между ними. Иными словами, суть работы датамайнера состоит в обнаружении полезных знаний, которые невозможно выявить при помощи простого анализа.

Датамайнеры наиболее востребованы в компаниях, чья деятельность связана с IT, e-commerce и финтехом. Перечень обязанностей этих специалистов по интеллектуальной обработке данных представлен:

Кроме того, датамайнеры в своей работе занимаются:

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

Как стать датамайнером

К датамайнерам предъявляются серьезные требования по знанию иностранного языка и языков программирования R, Python, SQL. Кроме того, датамайнер должен иметь грамотную и речь и хорошие коммуникативные навыки, обладать пунктуальностью, аналитическими способностями, быть контактным, инициативным и эрудированным.

Пройти обучение на датамайнера, получить и развить все необходимые для этой работы навыки можно, записавшись на курс профессиональной переподготовки по программе«Инструментальные средства бизнес-аналитики», которую проводит ВШБИ НИУ ВШЭ. Подать заявку на обучение можно на нашем сайте.

Источник

Data Mining в онлайн играх

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

Мы захотели узнать, почему уходят игроки и можно ли предсказать их уход. Предмет исследования – ММОРПГ Аион, однако наши результаты оказались применимы к широкому кругу игр и онлайн сервисов.

Чуть ли не британскими учеными установлено, что у пользователя очень короткая память. Сегодня он ушел из игры, а завтра уже не вспомнит, что он вообще ее устанавливал. Если игрок ушел, то действовать надо немедленно. Но как нам определить, действительно ли ушел человек, или просто сегодня вечером пьет пиво с друзьями и в игре не появится? Идеальным случаем было бы предсказание потенциального ухода еще до того, как пользователь нас покинул. И даже до того, как в его сознании зародилась мысль, что Аион не похож на торт. Наверное, такая задача тоже решаема, однако мы ставили более реалистичную цель – оперативно предсказывать уход в день последнего логина в игру. Уходом назовем неактивность человека в течение недели – и мы как раз не хотим ждать эти 7 дней, а желаем знать как можно скорее, что игрок больше не вернется. Мы желаем знать будущее!

Техническая сторона

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

На проект выделили часть ресурсов нашей системы аналитики – два блейд сервера Dual Xeon E5630 32Gb RAM, 10 Tb холодного хранилища для исходных и промежуточных данных, 3 Tb горячего хранилища в RAID10 SAS массиве для рабочих данных. Оба сервера под MS SQL 2008R2 – один под БД и один под Analysis Services. Программная часть решения – стандартный пакет Business Intelligence от Microsoft, входящий в SQL Server.

Фаза 1 – я все знаю!

Поскольку я много лет был геймдизайнером и провел под сотню плейтестов, то был уверен, что и сейчас экспертное мнение даст 90% ответов почему уходят игроки. Не научился пользоваться телепортацией, надоело бегать ногами – ушел. Умер от первого же монстра в игре – ушел. Не выполнил вторую миссию, застрял и не знает что делать – ушел. Аион, при всем его качестве и технологичности, не самая дружелюбная к новичку игра. Это черта всех корейских игр, рассчитанных на хардкорную и гиперсоциальную среду корейских игроков, а не одиноких скучающих российских казуальных пользователей.

Как читать lift chart: нижняя наклонная прямая линия — это результат генератора случайных чисел, предсказывающего нашу булеву переменную научным методом бросания монетки. Верхняя линия, быстро доходящая до 100% — это оракул, идеальный предсказатель будущего. Между ними находится неровная, трепещущая ниточка – это наша модель. Чем ближе график к идеальной линии – тем выше предсказательная точность модели. График приведен для 7-го уровня, но картина похожая от первого до девятого.

Fatality! Наша первая модель предсказывает уходящих игроков чуть-чуть лучше метода орла и решки. Отправляем в модели оставшиеся гипотезы, чистим данные, процессим:

Уже лучше, но все равно точность чуть выше 50%. А если посмотреть детальнее recall (ошибки второго рода), то картина грустная:

Эта же таблица русским языком – из каждых 100 предсказанных моделью уходов 49 будут ложные (игрок никуда уходить не собирался), точность модели составит 1008/(1008+982)=51%. При этом еще часть реальных уходов модель вообще пропустит – примерно 28% из истинно ушедших [391/(391+1008)=28%]. Внимание, это не каноническое определение recall, но такая формула нагляднее.

Итог фазы 1: все изначальные идеи провалились, предсказание не работает. Шеф, все пропало!

Фаза 2 – мы ничего не знаем

Полный разгром и бегство с поля боя, и вечный вопрос «Что делать?». На помощь приходит наивный алгоритм Байеса – максимально человеко-читаемый и понятный из всех data mining классификаторов. Анализ Байесом показал, что выбранные гипотезы довольно слабо характеризуют ушедших и остающихся игроков, то есть я ошибся с выбором изначальных предпосылок. Но, поиграв с глубиной и чувствительностью другого алгоритма, дерева принятия решений, стало понятно – есть правильные гипотезы, дерево ветвится по ним, но факторов решительно недостаточно – рост дерева прерывается на 2-3 ветке.

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

Я собрал брейншторм с командой проекта, где мы фонтанировали идеями – кто же наши новички, как они играют, чем они отличаются друг от друга. Вспоминали истории как наши подруги и жены знакомились с Аионом, и что из этого вышло. Итогом брейншторма стал дополненный список индивидуальных гипотез (пользовался ли игрок телепортацией, расширил ли себе инвентарь, привязал ли точку воскрешения и т.д.) и новая идея – хорошо бы посмотреть насколько вообще отличается активность уходящих от остающихся в игре.

Загрузили, обучили, верифицировали, проанализировали. Не буду грузить вас морем lift chart’ов по каждому уровню и каждой модели, приведу сразу обработанные и проанализированные данные:

Пик точности на 9 уровне был связан с внутренней особенностью игры на момент исследования.

В целом картина улучшилась в области 2-4 уровней, но 6-8 ниже плинтуса, с такой точностью данные нам просто бесполезны.

Дерево принятия решений бодро показывает – факторы активности являются самыми важными для предсказания ухода. По сути, три величины – время на уровне, убитые монстры и сделанные задания – определяют львиную долю уходов. Остальные факторы добавляют не более 5% точности. Также дерево по-прежнему остается голым, крона обрывается на третьей ветке – то есть модель жаждет больше релевантных метрик. Что еще непонятно – точность трех алгоритмов сильно меняется от уровня к уровню.

Итог фазы 2: успех идеи об измерении средней активности, а не индивидуальных факторов. Но точность предсказания все еще неудовлетворительна. Путь по граблям вывел к правильной последовательности анализа результатов – сначала факторы и корреляции (Байес), потом их влияние на итог (дерево решений).

Фаза 3 – мы знаем куда копать

Воодушевленный прогрессом, я наметил три вектора развития проекта – больше метрик общей активности, больше специфических метрик индивидуальной эффективности, и более глубокое изучение инструментов Microsoft BI.

Пришлось повозиться с новыми индивидуальными метриками, связанными с глубиной геймплея и эффективностью игры, например процентом автоатаки. Мы сегментировали персонажей по классам (воины направо, целители налево) и для каждого класса рассчитали 25, 50 и 75-й перцентили распределения по %% автоатаки, и разбили всех на 4 категории. Теперь данные нормализованы, и игровые классы можно сравнивать между собой – на вход data mining моделей уходит номер категории.

Индивидуальные метрики закрепились на глубине седьмого-девятого узла дерева, т.е. они прибавили пару процентов к точности предсказания, но не улучшили ситуацию кардинально. Следующим шагом было штудирование книги Data Mining with Microsoft SQL Server 2008 на предмет тонкостей работы с Analysis Services. Сама по себе книга помогла только с настройкой чувствительности дерева (от силы плюс один-два процента прироста точности), но натолкнула на мысль о правильной дискретизации.

В примере выше с автоатакой мы сделали ручную дискретизацию данных – разбиение на категории по каким-то признакам. SQL сервер автоматически делает дискретизацию несколькими способами. Экспериментальным путем я быстро понял, что алгоритм разбиения и число сегментов очень сильно влияют на предсказательную силу модели. Ручное изменение числа сегментов сильно влияет на форму и точность дерева. На ручную подгонку я потратил неделю, скрупулезно для каждой структуры каждого уровня (а это 9 уровней по 30+ метрик) экспериментируя с числом сегментов. Для каких-то метрик оптимальным было 7 сегментов (например, время на текущем уровне), для каких-то 12 (суммарное время в игре), для каких-то больше 20 (число убитых монстров).

Ручная настройка дала сильный прирост предсказанных значений – точность при этом не сильно повысилась, но модели стали делать заметно меньше пропусков, а результаты дерева сравнялись с нейронной сетью:

Итог фазы 3: мы вышли на приемлемые показатели точности и аккуратности и узнали много интересного про нашу игру и наших игроков.

Фаза 4 – только победа

Я, честно говоря, думал, что потолок достигнут – дерево ветвится глубиной до 9-12 узлов, аккуратность сильно улучшена. Новые гипотезы точность никак не повышают, новые факторы никакой информации не дают. В принципе, общая точность в 78% и recall 16% — это удовлетворительно для начала работы с игроками. Я бы, наверное, не стал при таких цифрах давать бесплатную подписку для удержания в игре, но сообщать игроку релевантную информацию уже можно без особых ошибок.

Помощь пришла неожиданно – поскольку data mining проект длился уже третий месяц, у нас несколько устарели логи – игра же изменилась за это время. Подгрузив немного свежих данных, а заодно в очередной раз доработав ETL процедуры, мы заметили изменения в моделях. На новых данных они вели себя иначе – при, в общем-то, прежней точности и аккуратности, разбиения дерева были другими. На этом этапе все три алгоритма обучались очень быстро – минуту на каждый уровень из 9, и накормить их дополнительным набором данных просто.

Сказано – сделано, выгружаем вообще все накопленные за 3 месяца данные и одним махом направляем модели обучаться (процесс стал занимать не минуту, а целых пять на каждый уровень – не критично). Очередной раунд ручной подгонки, и вот итог:

Увеличив объем обучающих данных, мы сделали процесс обработки дольше, но зато какой отличный результат!

С первым уровнем, к сожалению, немного можно сделать – около половины уходов, как сказал бы Авинаш Кошик, “I came, I puked, I left”. У нас есть данные о буквально паре действий игрока – и дальше он закрывает клиент игры и никогда не возвращается обратно.

Напоминаю, что все исследования выше – это обучение на накопленных исторических данных. Теперь я хочу проверки боем! Проверяем на живых данных – берем свежих, сегодняшних пользователей, прогоняем через модель и сохраняем результат предсказания. Через неделю сравниваем предсказания модели с объективной реальностью – кто из недельной давности новичков действительно ушел, а кто в игре остался:

Самое интересное

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

Победа!

За два месяца, с нуля – никто из нас никогда даже близко с data mining не сталкивался, — с помощью двух книг и желания попробовать что-то новое, на основе созданной нами мощной, но пассивной системы аналитики в Иннове, мы сделали инструмент, активно смотрящий в будущее. В отличие от обычной отчетности и аналитики трендов на исторических данных, мы в 6 утра уже знаем почти наверняка о наших вчерашних новичках в Аионе – увидим ли мы их сегодня в игре или нет. И можем действовать, пока еще не поздно.

Анализ проведен для онлайн-игры, но как вы могли заметить, основной вклад в точность предсказания был от обобщенных метрик активности – и я уверен, что подход будет работать для любого вашего продукта или сервиса, с которым активно работают пользователи, если конечно у вас есть желание выйти на качественно новый уровень.

PS. Если тема хабравчанам интересна, то можно продолжить – про предсказание уходов старичков, сегментацию и кластеризацию, миграцию между кластерами и другие data mining проекты, которые мы сделали в уходящем году.

PS2. Вторая книга, рекомендую абсолютно всем — Программируем коллективный разум

Источник

Data Mining – интеллектуальный анализ данных

1. Что такое Data Mining?

Data Mining переводится как “добыча” или “раскопка данных”. Нередко рядом с Data Mining встречаются слова “обнаружение знаний в базах данных” (knowledge discovery in databases) и “интеллектуальный анализ данных”. Их можно считать синонимами Data Mining. Возникновение всех указанных терминов связано с новым витком в развитии средств и методов обработки данных.

До начала 90-х годов, казалось, не было особой нужды переосмысливать ситуацию в этой области. Все шло своим чередом в рамках направления, называемого прикладной статистикой (см. например, [1]). Теоретики проводили конференции и семинары, писали внушительные статьи и монографии, изобиловавшие аналитическими выкладками.

Вместе с тем, практики всегда знали, что попытки применить теоретические экзерсисы для решения реальных задач в большинстве случаев оказываются бесплодными. Но на озабоченность практиков до поры до времени можно было не обращать особого внимания – они решали главным образом свои частные проблемы обработки небольших локальных баз данных.

И вот прозвенел звонок. В связи с совершенствованием технологий записи и хранения данных на людей обрушились колоссальные потоки информационной руды в самых различных областях. Деятельность любого предприятия (коммерческого, производственного, медицинского, научного и т.д.) теперь сопровождается регистрацией и записью всех подробностей его деятельности. Что делать с этой информацией” Стало ясно, что без продуктивной переработки потоки сырых данных образуют никому не нужную свалку.

Специфика современных требований к такой переработке следующие:

Традиционная математическая статистика, долгое время претендовавшая на роль основного инструмента анализа данных, откровенно спасовала перед лицом возникших проблем. Главная причина – концепция усреднения по выборке, приводящая к операциям над фиктивными величинами (типа средней температуры пациентов по больнице, средней высоты дома на улице, состоящей из дворцов и лачуг и т.п.). Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для “грубого” разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP).

В основу современной технологии Data Mining (discovery-driven data mining) положена концепция шаблонов (паттернов), отражающих фрагменты многоаспектных взаимоотношений в данных. Эти шаблоны представляют собой закономерности, свойственные подвыборкам данных, которые могут быть компактно выражены в понятной человеку форме. Поиск шаблонов производится методами, не ограниченными рамками априорных предположений о структуре выборке и виде распределений значений анализируемых показателей. Примеры заданий на такой поиск при использовании Data Mining приведены в табл. 1.

Таблица 1. Примеры формулировок задач при использовании методов OLAP и Data Mining [2]

Важное положение Data Mining – нетривиальность разыскиваемых шаблонов. Это означает, что найденные шаблоны должны отражать неочевидные, неожиданные (unexpected) регулярности в данных, составляющие так называемые скрытые знания (hidden knowledge). К обществу пришло понимание, что сырые данные (raw data) содержат глубинный пласт знаний, при грамотной раскопке которого могут быть обнаружены настоящие самородки (рис.1).

Рисунок 1. Уровни знаний, извлекаемых из данных

В целом технологию Data Mining достаточно точно определяет Григорий Пиатецкий-Шапиро – один из основателей этого направления:

Data Mining – это процесс обнаружения в сырых данных

G. Piatetsky-Shapiro, Knowledge Stream Partners

2. Кому это нужно”

Сфера применения Data Mining ничем не ограничена – она везде, где имеются какие-либо данные. Но в первую очередь методы Data Mining сегодня, мягко говоря, заинтриговали коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing). Опыт многих таких предприятий показывает, что отдача от использования Data Mining может достигать 1000%. Например, известны сообщения об экономическом эффекте, в 10-70 раз превысившем первоначальные затраты от 350 до 750 тыс. дол. [3]. Известны сведения о проекте в 20 млн. дол., который окупился всего за 4 месяца. Другой пример – годовая экономия 700 тыс. дол. за счет внедрения Data Mining в сети универсамов в Великобритании.

Data Mining представляют большую ценность для руководителей и аналитиков в их повседневной деятельности. Деловые люди осознали, что с помощью методов Data Mining они могут получить ощутимые преимущества в конкурентной борьбе. Кратко охарактеризуем некоторые возможные бизнес-приложения Data Mining [2].

2.1. Некоторые бизнес-приложения Data Mining

Розничная торговля

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

Банковское дело

Достижения технологии Data Mining используются в банковском деле для решения следующих распространенных задач:

Телекоммуникации

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

Страхование

Страховые компании в течение ряда лет накапливают большие объемы данных. Здесь обширное поле деятельности для методов Data Mining:

Другие приложения в бизнесе

Data Mining может применяться во множестве других областей:

2.2. Специальные приложения

Медицина

Известно много экспертных систем для постановки медицинских диагнозов. Они построены главным образом на основе правил, описывающих сочетания различных симптомов различных заболеваний. С помощью таких правил узнают не только, чем болен пациент, но и как нужно его лечить. Правила помогают выбирать средства медикаментозного воздействия, определять показания – противопоказания, ориентироваться в лечебных процедурах, создавать условия наиболее эффективного лечения, предсказывать исходы назначенного курса лечения и т. п. Технологии Data Mining позволяют обнаруживать в медицинских данных шаблоны, составляющие основу указанных правил.

Молекулярная генетика и генная инженерия

Пожалуй, наиболее остро и вместе с тем четко задача обнаружения закономерностей в экспериментальных данных стоит в молекулярной генетике и генной инженерии. Здесь она формулируется как определение так называемых маркеров, под которыми понимают генетические коды, контролирующие те или иные фенотипические признаки живого организма. Такие коды могут содержать сотни, тысячи и более связанных элементов.

На развитие генетических исследований выделяются большие средства. В последнее время в данной области возник особый интерес к применению методов Data Mining. Известно несколько крупных фирм, специализирующихся на применении этих методов для расшифровки генома человека и растений.

Прикладная химия

Методы Data Mining находят широкое применение в прикладной химии (органической и неорганической). Здесь нередко возникает вопрос о выяснении особенностей химического строения тех или иных соединений, определяющих их свойства. Особенно актуальна такая задача при анализе сложных химических соединений, описание которых включает сотни и тысячи структурных элементов и их связей.

Можно привести еще много примеров различных областей знания, где методы Data Mining играют ведущую роль. Особенность этих областей заключается в их сложной системной организации. Они относятся главным образом к надкибернетическому уровню организации систем [4], закономерности которого не могут быть достаточно точно описаны на языке статистических или иных аналитических математических моделей [5]. Данные в указанных областях неоднородны, гетерогенны, нестационарны и часто отличаются высокой размерностью.

3. Типы закономерностей

Выделяют пять стандартных типов закономерностей, которые позволяют выявлять методы Data Mining: ассоциация, последовательность, классификация, кластеризация и прогнозирование (рис. 2).

Рисунок 2. Типы закономерностей, выявляемых методами Data Mining

Ассоциация имеет место в том случае, если несколько событий связаны друг с другом. Например, исследование, проведенное в супермаркете, может показать, что 65% купивших кукурузные чипсы берут также и “кока-колу”, а при наличии скидки за такой комплект “колу” приобретают в 85% случаев. Располагая сведениями о подобной ассоциации, менеджерам легко оценить, насколько действенна предоставляемая скидка.

Если существует цепочка связанных во времени событий, то говорят о последовательности. Так, например, после покупки дома в 45% случаев в течение месяца приобретается и новая кухонная плита, а в пределах двух недель 60% новоселов обзаводятся холодильником.

С помощью классификации выявляются признаки, характеризующие группу, к которой принадлежит тот или иной объект. Это делается посредством анализа уже классифицированных объектов и формулирования некоторого набора правил.

Кластеризация отличается от классификации тем, что сами группы заранее не заданы. С помощью кластеризации средства Data Mining самостоятельно выделяют различные однородные группы данных.

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

4. Классы систем Data Mining

Data Mining является мультидисциплинарной областью, возникшей и развивающейся на базе достижений прикладной статистики, распознавания образов, методов искусственного интеллекта, теории баз данных и др. (рис. 3). Отсюда обилие методов и алгоритмов, реализованных в различных действующих системах Data Mining. Многие из таких систем интегрируют в себе сразу несколько подходов. Тем не менее, как правило, в каждой системе имеется какая-то ключевая компонента, на которую делается главная ставка. Ниже приводится классификация указанных ключевых компонент на основе работы [6]. Выделенным классам дается краткая характеристика.

Рисунок 3. Data Mining – мультидисциплинарная область

Рисунок 4. Популярные продукты для Data Mining

4.1. Предметно-ориентированные аналитические системы

4.2. Статистические пакеты

Есть еще более серьезный принципиальный недостаток статистических пакетов, ограничивающий их применение в Data Mining. Большинство методов, входящих в состав пакетов опираются на статистическую парадигму, в которой главными фигурантами служат усредненные характеристики выборки. А эти характеристики, как указывалось выше, при исследовании реальных сложных жизненных феноменов часто являются фиктивными величинами.

В качестве примеров наиболее мощных и распространенных статистических пакетов можно назвать SAS (компания SAS Institute), SPSS (SPSS), STATGRAPICS (Manugistics), STATISTICA, STADIA и другие.

4.3. Нейронные сети

Это большой класс систем, архитектура которых имеет аналогию (как теперь известно, довольно слабую) с построением нервной ткани из нейронов. В одной из наиболее распространенных архитектур, многослойном перцептроне с обратным распространением ошибки, имитируется работа нейронов в составе иерархической сети, где каждый нейрон более высокого уровня соединен своими входами с выходами нейронов нижележащего слоя. На нейроны самого нижнего слоя подаются значения входных параметров, на основе которых нужно принимать какие-то решения, прогнозировать развитие ситуации и т. д. Эти значения рассматриваются как сигналы, передающиеся в следующий слой, ослабляясь или усиливаясь в зависимости от числовых значений (весов), приписываемых межнейронным связям. В результате на выходе нейрона самого верхнего слоя вырабатывается некоторое значение, которое рассматривается как ответ – реакция всей сети на введенные значения входных параметров. Для того чтобы сеть можно было применять в дальнейшем, ее прежде надо “натренировать” на полученных ранее данных, для которых известны и значения входных параметров, и правильные ответы на них. Тренировка состоит в подборе весов межнейронных связей, обеспечивающих наибольшую близость ответов сети к известным правильным ответам.

Основным недостатком нейросетевой парадигмы является необходимость иметь очень большой объем обучающей выборки. Другой существенный недостаток заключается в том, что даже натренированная нейронная сеть представляет собой черный ящик. Знания, зафиксированные как веса нескольких сотен межнейронных связей, совершенно не поддаются анализу и интерпретации человеком (известные попытки дать интерпретацию структуре настроенной нейросети выглядят неубедительными – система “KINOsuite-PR”).

Рисунок 5. Полиномиальная нейросеть

4.4. Системы рассуждений на основе аналогичных случаев

Идея систем case based reasoning – CBR – на первый взгляд крайне проста. Для того чтобы сделать прогноз на будущее или выбрать правильное решение, эти системы находят в прошлом близкие аналоги наличной ситуации и выбирают тот же ответ, который был для них правильным. Поэтому этот метод еще называют методом “ближайшего соседа” (nearest neighbour). В последнее время распространение получил также термин memory based reasoning, который акцентирует внимание, что решение принимается на основании всей информации, накопленной в памяти.

Системы CBR показывают неплохие результаты в самых разнообразных задачах. Главным их минусом считают то, что они вообще не создают каких-либо моделей или правил, обобщающих предыдущий опыт, – в выборе решения они основываются на всем массиве доступных исторических данных, поэтому невозможно сказать, на основе каких конкретно факторов CBR системы строят свои ответы.

Другой минус заключается в произволе, который допускают системы CBR при выборе меры “близости”. От этой меры самым решительным образом зависит объем множества прецедентов, которые нужно хранить в памяти для достижения удовлетворительной классификации или прогноза [7].

Примеры систем, использующих CBR, – KATE tools (Acknosoft, Франция), Pattern Recognition Workbench (Unica, США).

4.5. Деревья решений (decision trees)

Деревья решения являются одним из наиболее популярных подходов к решению задач Data Mining. Они создают иерархическую структуру классифицирующих правил типа “ЕСЛИ… ТО…” (if-then), имеющую вид дерева. Для принятия решения, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид “значение параметра A больше x””. Если ответ положительный, осуществляется переход к правому узлу следующего уровня, если отрицательный – то к левому узлу; затем снова следует вопрос, связанный с соответствующим узлом.

Популярность подхода связана как бы с наглядностью и понятностью. Но деревья решений принципиально не способны находить “лучшие” (наиболее полные и точные) правила в данных. Они реализуют наивный принцип последовательного просмотра признаков и “цепляют” фактически осколки настоящих закономерностей, создавая лишь иллюзию логического вывода.

Вместе с тем, большинство систем используют именно этот метод. Самыми известными являются See5/С5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США), KnowledgeSeeker (ANGOSS, Канада). Стоимость этих систем варьируется от 1 до 10 тыс. долл.

Рисунок 6. Система KnowledgeSeeker обрабатывает банковскую информацию

4.6. Эволюционное программирование

Проиллюстрируем современное состояние данного подхода на примере системы PolyAnalyst – отечественной разработке, получившей сегодня общее признание на рынке Data Mining. В данной системе гипотезы о виде зависимости целевой переменной от других переменных формулируются в виде программ на некотором внутреннем языке программирования. Процесс построения программ строится как эволюция в мире программ (этим подход немного похож на генетические алгоритмы). Когда система находит программу, более или менее удовлетворительно выражающую искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных дочерних программ те, которые повышают точность. Таким образом система “выращивает” несколько генетических линий программ, которые конкурируют между собой в точности выражения искомой зависимости. Специальный модуль системы PolyAnalyst переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и пр.).

Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа – методе группового учета аргументов (МГУА) зависимость ищут в форме полиномов. В настоящее время из продающихся в России систем МГУА реализован в системе NeuroShell компании Ward Systems Group.

4.7. Генетические алгоритмы

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

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

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

Генетические алгоритмы имеют ряд недостатков. Критерий отбора хромосом и используемые процедуры являются эвристическими и далеко не гарантируют нахождения “лучшего” решения. Как и в реальной жизни, эволюцию может “заклинить” на какой-либо непродуктивной ветви. И, наоборот, можно привести примеры, как два неперспективных родителя, которые будут исключены из эволюции генетическим алгоритмом, оказываются способными произвести высокоэффективного потомка. Это особенно становится заметно при решении высокоразмерных задач со сложными внутренними связями.

4.8. Алгоритмы ограниченного перебора

Алгоритмы ограниченного перебора были предложены в середине 60-х годов М.М. Бонгардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множества задач из самых различных областей.

Эти алгоритмы вычисляют частоты комбинаций простых логических событий в подгруппах данных. Примеры простых логических событий: X = a; X 4.9. Системы для визуализации многомерных данных

В той или иной мере средства для графического отображения данных поддерживаются всеми системами Data Mining. Вместе с тем, весьма внушительную долю рынка занимают системы, специализирующиеся исключительно на этой функции. Примером здесь может служить программа DataMiner 3D словацкой фирмы Dimension5 (5-е измерение).

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

Рисунок 8. Визуализация данных системой DataMiner 3D

5. Резюме

Литература

Источник