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. Пожелания и аргументированная критика принимаются.
Разбираемся, в чем разница между Data Mining и Data Extraction
Что такое Data Mining?
Data mining, также называемый Обнаружение знаний в базе данных (KDD), представляет собой метод, часто используемый для анализа больших массивов данных с помощью статистических и математических методов для поиска скрытых закономерностей или тенденций и извлечения из них ценности.
Что можно сделать с помощью Data Mining?
Автоматизируя процесс, инструменты data mining могут просматривать базы данных и эффективно выявлять скрытые закономерности. Для предприятий data mining часто используется для выявления закономерностей и взаимосвязей в данных, помогающих принимать оптимальные решения в бизнесе.
Примеры применения
После того, как в 1990-х годах data mining получил широкое распространение, компании в широком спектре отраслей, включая розничную торговлю, финансы, здравоохранение, транспорт, телекоммуникации, электронную коммерцию и т.д., начали использовать методы data mining для получения информации на основе данных. Data mining может помочь сегментировать клиентов, выявить мошенничество, прогнозировать продажи и многое другое.
Этапы Data Mining
Data mining — это целостный процесс сбора, отбора, очистки, преобразования и извлечения данных для оценки закономерностей и, в конечном итоге, для извлечения ценности.
Как правило, весь процесс добычи данных можно обобщить до 7 этапов:
Недостатки Data Mining
Выше приведено краткое введение в data mining. Как я уже упоминала, data mining содержит процесс сбора и интеграции данных, который включает в себя процесс извлечения данных (data extraction). В этом случае можно с уверенностью сказать, что data extraction может быть частью длительного процесса data mining.
Что такое Data Extraction?
Также известное как «извлечение веб-данных» и «веб-скрепинг», этот процесс представляет собой акт извлечения данных из (обычно неструктурированных или плохо структурированных) источников данных в централизованные места и централизацию в одном месте для хранения или дальнейшей обработки. В частности, к неструктурированным источникам данных относятся веб-страницы, электронная почта, документы, файлы PDF, отсканированный текст, отчеты мейнфреймов, катушечные файлы, объявления и т.д. Централизованные хранилища могут быть локальными, облачными или гибридными. Важно помнить, что извлечение данных не включает в себя обработку или другой анализ, который может произойти позже.
Что можно сделать с помощью Data Extraction?
В основном цели извлечения данных делятся на 3 категории.
Некоторые примеры применения Data Extraction
Подобно data mining, извлечение данных широко используется в различных отраслях промышленности. Помимо мониторинга цен в электронной коммерции, извлечение данных может помочь в собственном исследовании, агрегировании новостей, маркетинге, в работе с недвижимостью, путешествиях и туризме, в консалтинге, финансах и во многом другом.
Шаги Data Extraction
Извлечение данных — первый этап ETL (аббревиатура Extract, Transform, Load: извлечение, преобразование, загрузка) и ELT (извлечение, загрузка и преобразование). ETL и ELT сами по себе являются частью завершенной стратегии интеграции данных. Другими словами, извлечение данных может быть частью их добычи.
Извлечение, преобразование, загрузка
В то время как data mining — это получение информации из больших массивов данных, data extraction — это гораздо более короткий и простой процесс. Его можно свести к трем этапам:
Недостатки Data Extraction
Ключевые различия между Data Mining и Data Extraction
Big Data vs Data Mining
В последнее время очень часто, как внутри команды, так и снаружи ее, я часто встречаю разное толкование понятий “Big Data” и “Data Mining”. Из-за этого растет непонимание между Исполнителем и Заказчиком относительно предлагаемых технологий и желаемого результата для обеих сторон.
Положение усугубляет отсутствие четких определений от какого-то общепринятого стандартизатора, а также разный порядок стоимости работ в глазах потенциального покупателя.
На рынке сложилось мнение, что “Data mining” — это когда Исполнителю отгрузили дамп, он там нашел пару трендов, сгенерил отчет и получил свой миллион рублей. С “Big Data” все гораздо интереснее. Люди думают, что это нечто из черной магии, а магия стоит дорого.
Целями данной статьи являются доказательство отсутствия существенных различий между толкованием данных понятий, а также разъяснение основных темных пятен в понимании предмета.
Что такое Big Data
Большие данные (англ. big data) в информационных технологиях — серия подходов, инструментов и методов обработки структурированных и неструктурированных данных огромных объёмов и значительного многообразия для получения воспринимаемых человеком результатов, эффективных в условиях непрерывного прироста, распределения по многочисленным узлам вычислительной сети, сформировавшихся в конце 2000-х годов, альтернативных традиционным системам управления базами данных и решениям класса Business Intelligence.
Что мы видим? Определение, которое должно определять по виду некий предмет (большой велосипед, маленькое дерево, самокат и т.д.), определяет на самом деле некое множество методов и целей, фактически определяя некий спектр процессов. Можно ли согласиться с таким определением, с допущением того, что бег трусцой (процесс) можно обозвать чайником (предмет)? Сложно сказать, попытаемся декомпозировать определение.
Неструктурированные данные
Unstructured Data (or unstructured information) refers to information that either does not have a pre-defined data model or is not organized in a pre-defined manner. Unstructured information is typically text-heavy, but may contain data such as dates, numbers, and facts as well.
Другими словами, нам пытаются сказать, что существуют данные без структуры… Причем приводят самый убийственный пример таких данных — текст. Интересно, что сказала бы моя учительница по русскому языку и литературе, если бы узнала, что русский язык\текст не имеет четкой структуры и как следствие — годы его изучения бессмысленны, так как мы учим правила, которых, как утверждают некоторые, не существует.
Для понимания моей точки зрения приведу пример — поле text в Postgres. Допустим я положу туда JSON. Для 8 версии — это будет просто text (неструктурированные данные), для 9 — это уже будет JSON (структурированные данные). То есть одни и те же данные одновременно являются и структурированными и неструктурированными? Опять невообразимый дуализм с лекций по физике? Ответ прост — неструктурированных данных не существует, просто для некоторых видов данных пока нет общепринятых и одновременно с этим широкораспространенных методов работы с этими данными.
Грамотный читатель, конечно же, воскликнет — а как же видеоданные? Любое видео — это набор кадров. Любой кадр — это изображение. Изображения бывают двух видов:
Итого — неструктурированных данных не существует.
Огромный размер
Здесь разночтений с общественным мнением у меня нет. Как только с объемом данных начинаются проблемы (сложно принимать, сложно хранить, сложно обрабатывать и т.д.) — у вас огромный размер (данных). Понятие довольно субъективное, для меня огромный размер измеряется в штуках. Для меня нижняя граница Big Data — миллион записей. Обоснование — запросы к СУБД со сложностью типа Θ( n2 ) на таком объеме выполняются несколько минут, что для меня долго.
Для других людей обоснование\критерий может быть другой, следовательно и нижняя граница огромного размера будет иной.
Что такое Data Mining
Data Mining (рус. добыча данных, интеллектуальный анализ данных, глубинный анализ данных) — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году.
Переведя на простой язык — у вас уже есть некий массив данных, который был уже ранее как-то обработан, а теперь вы этот массив данных обрабатываете снова, возможно как-то иначе чем прежде, и получаете некие полезные выводы, которые далее используете для получения профита.
Получается, что согласно определения википедии, декомпозиция “Data Mining” включает:
Выводы
Согласно проведенным выше декмопозициям определений — Data mining как бы “выигрывает” у Big Data за счет демократичного подхода к объему данных.
Согласно списку задач, решаемым при помощи методов Big Data и Data Mining, “выигрывает” уже Big Data, так как решает задачи сбора и хранения данных.
Таким образом, если учесть, что исследовать малые объемы данных в принципе не целесообразно, то значение понятия Data Mining полностью включено в значение понятия Big Data. Следовательно, те кто говорят, что эта задача является всего лишь “Data Mining”, а не волшебная “Big Data”, говорят примерно следующее — “Это не птица, это всего лишь голубь”, что является не верным с точки зрения формальной логики, которую мы все так уважаем.
Что касается цены, то в обоих областях знаний относительно пересекающихся задач используется идентичный стек технологий, инструментов и методов. Как следствие, цена на работы тоже должна быть одного порядка.
В заключение имеет смысл добавить, что многие пытаются сравнивать эти понятия между собой и другими понятиями (например, с задачей highload, как это сделал автор здесь: habrahabr.ru/company/beeline/blog/218669) по стеку программных средств. Например, если мы используем RDBMS, то это уже 100% не Big Data.
Не могу согласиться с такой точкой зрения, потому что современные RDBMS оперируют внушительными объемами данных и позволяют внутри себя хранить данные практически любых типов, которые при правильном индексировании довольно быстро агрегируются и выдаются на уровень приложения, причем есть возможность написать собственный механизм индексирования.
Вообще, неверно классифицировать класс задач по стеку програмно-технических средств, так как любая уникальная задача требует уникального подхода, который включает те инструменты, которые максимально эффективны для решения этой конкретной задачи.
Data mining что это такое
OLAP-системы предоставляют аналитику средства проверки гипотез при анализе данных, то есть основной задачей аналитика является генерация гипотез, которую он решает ее, основываясь на своих знаниях и опыте. Однако знания есть не только у человека, но и у накопленных данных, которые подвергаются анализу. Такие знания содержатся в огромной объеме информации, которую человек не в силах исследовать самостоятельно. В связи с этим существует вероятность пропустить гипотезы, которые могут принести значительную выгоду.
Для обнаружения «скрытых» знаний применяется специальные методы автоматического анализа, при помощи которых приходиться практически добывать знания из «завалов» информации. За этим направлением закрепился термин «добыча данных (DataMining)» или «интеллектуальный анализ данных».
DataMining – это процесс обнаружения в базах данных нетривиальных и практически полезных закономерностей. (BaseGroup)
DataMining – это процесс выделения, исследования и моделирования больших объемов данных для обнаружения неизвестных до этого структур(patters) с целью достижения преимуществ в бизнесе(SAS Institute)
DataMining – это процесс, цель которого – обнаружить новые значимые корреляции, образцы и тенденции в результате просеивания большого объема хранимых данных с использованием методик распознавания образцов плюс применение статистических и математических методов( GartnerGroup)
DataMining – это процесс обнаружения полезных знаний о бизнесе.(Н.М.Абдикеев «КБА»)
Свойства обнаруживаемых знаний
Рассмотрим свойства обнаруживаемых знаний.
В DataMining для представления полученных знаний служат модели. Виды моделей зависят от методов их создания. Наиболее распространенными являются: правила, деревья решений, кластеры и математические функции.
Задачи DataMining
Напомним, что в основу технологии DataMining положена концепция шаблонов, представляющих собой закономерности. В результате обнаружения этих, скрытых от невооруженного глаза закономерностей решаются задачи DataMining. Различным типам закономерностей, которые могут быть выражены в форме, понятной человеку, соответствуют определенные задачи DataMining.
Единого мнения относительно того, какие задачи следует относить к DataMining, нет. Большинство авторитетных источников перечисляют следующие: классификация,
кластеризация, прогнозирование, ассоциация, визуализация, анализ и обнаружение
отклонений, оценивание, анализ связей, подведение итогов.
Классификация (Classification)
Задача разбиения множества объектов или наблюдений на априорно заданные группы, называемые классами, внутри каждой из которых они предполагаются похожими друг на друга, имеющими примерно одинаковые свойства и признаки. При этом решение получается на основе анализа значений атрибутов (признаков).
Кластеризация (Clustering)
Краткое описание. Кластеризация является логическим продолжением идеи
классификации. Это задача более сложная, особенность кластеризации заключается в том, что классы объектов изначально не предопределены. Результатом кластеризации является разбиение объектов на группы.
Ассоциация (Associations)
Краткое описание. В ходе решения задачи поиска ассоциативных правил отыскиваются закономерности между связанными событиями в наборе данных.
Отличие ассоциации от двух предыдущих задач DataMining: поиск закономерностей осуществляется не на основе свойств анализируемого объекта, а между несколькими событиями, которые происходят одновременно. Наиболее известный алгоритм решения задачи поиска ассоциативных правил – алгоритм Apriori.
Последовательность (Sequence) или последовательная ассоциация (sequentialassociation)
Краткое описание. Последовательность позволяет найти временные закономерности между транзакциями. Задача последовательности подобна ассоциации, но ее целью является установление закономерностей не между одновременно наступающими событиями, а между событиями, связанными во времени (т.е. происходящими с некоторым определенным интервалом во времени). Другими словами, последовательность определяется высокой вероятностью цепочки связанных во времени событий. Фактически, ассоциация является частным случаем последовательности с временным лагом, равным нулю. Эту задачу DataMining также называют задачей нахождения последовательных шаблонов (sequentialpattern).
Правило последовательности: после события X через определенное время произойдет событие Y.
Пример. После покупки квартиры жильцы в 60% случаев в течение двух недель приобретают холодильник, а в течение двух месяцев в 50% случаев приобретается телевизор. Решение данной задачи широко применяется в маркетинге и менеджменте, например, при управлении циклом работы с клиентом (CustomerLifecycleManagement).
Регрессия, прогнозирование (Forecasting)
Краткое описание. В результате решения задачи прогнозирования на основе особенностей исторических данных оцениваются пропущенные или же будущие значения целевых численных показателей.
Дополнительные задачи
Задача оценивания сводится к предсказанию непрерывных значений признака.
Анализ связей (LinkAnalysis)
Задача нахождения зависимостей в наборе данных.
Визуализация (Visualization, GraphMining)
В результате визуализации создается графический образ анализируемых данных. Для решения задачи визуализации используются графические методы, показывающие наличие закономерностей в данных.
Подведение итогов (Summarization)
Достаточно близким к вышеупомянутой классификации является подразделение задач DataMining на следующие: исследования и открытия, прогнозирования и классификации, объяснения и описания.
Автоматическое исследование и открытие (свободный поиск)
Пример задачи: обнаружение новых сегментов рынка.
Для решения данного класса задач используются методы кластерного анализа.
Прогнозирование и классификация
Пример задачи: предсказание роста объемов продаж на основе текущих значений.
Методы: регрессия, нейронные сети, генетические алгоритмы, деревья решений.
Задачи классификации и прогнозирования составляют группу так называемого индуктивного моделирования, в результате которого обеспечивается изучение анализируемого объекта или системы. В процессе решения этих задач на основе набора данных разрабатывается общая модель или гипотеза.
Объяснение и описание
Пример задачи: характеристика клиентов по демографическим данным и историям покупок.
Методы: деревья решения, системы правил, правила ассоциации, анализ связей.
Сравнение кластеризации и классификации
Обучение с учителем
Обучение без учителя
Наличие метки класса
сопровождается меткой, указывающей
класс, к которому относится
Метки класса обучающего
Основание для классификации
Новые данные классифицируются на основании обучающего множества
Дано множество данных с целью
классов или кластеров данных
Сферы применения DataMining
Следует отметить, что на сегодняшний день наибольшее распространение технология DataMining получила при решении бизнес-задач. Возможно, причина в том, что именно в этом направлении отдача от использования инструментов DataMining может составлять, по некоторым источникам, до 1000% и затраты на ее внедрение могут достаточно быстро окупиться.
Применение DataMining для решения задач государственного уровня. Основныенаправления: поиск лиц, уклоняющихся от налогов; средства в борьбе с терроризмом.
Применение DataMining для научных исследований. Основные направления: медицина,биология, молекулярная генетика и генная инженерия, биоинформатика, астрономия,прикладная химия, исследования, касающиеся наркотической зависимости, и другие.
Применение DataMining для решения Web-задач. Основные направления: поисковыемашины (searchengines), счетчики и другие.
В сфере электронной коммерции DataMining применяется для формирования
рекомендательных систем и решения задач классификации посетителей Web-сайтов.
Такая классификация позволяет компаниям выявлять определенные группы клиентов и проводить маркетинговую политику в соответствии с обнаруженными интересами и потребностями клиентов. Технология DataMining для электронной коммерции тесно связана с технологией WebMining.
Основные задачи DataMining в промышленном производстве:
· комплексный системный анализ производственных ситуаций;
· краткосрочный и долгосрочный прогноз развития производственных ситуаций;
· выработка вариантов оптимизационных решений;
· прогнозирование качества изделия в зависимости от некоторых параметров
· обнаружение скрытых тенденций и закономерностей развития производственных
· прогнозирование закономерностей развития производственных процессов;
· обнаружение скрытых факторов влияния;
· обнаружение и идентификация ранее неизвестных взаимосвязей между
производственными параметрами и факторами влияния;
· анализ среды взаимодействия производственных процессов и прогнозирование
изменения ее характеристик;
· выработку оптимизационных рекомендаций по управлению производственными
· визуализацию результатов анализа, подготовку предварительных отчетов и проектов
допустимых решений с оценками достоверности и эффективности возможных реализаций.
В сфере маркетинга DataMining находит очень широкое применение.
Основные вопросы маркетинга «Что продается?», «Как продается?», «Кто является
В лекции, посвященной задачам классификации и кластеризации, подробно описано использование кластерного анализа для решения задач маркетинга, как, например, сегментация потребителей.
Также успешно здесь используется поиск временных закономерностей.
В сфере розничной торговли, как и в маркетинге, применяются:
· алгоритмы поиска ассоциативных правил (для определения часто встречающихся наборов
товаров, которые покупатели покупают одновременно). Выявление таких правил помогает
размещать товары на прилавках торговых залов, вырабатывать стратегии закупки товаров
и их размещения на складах и т.д.
· использование временных последовательностей, например, для определения
необходимых объемов запасов товаров на складе.
· методы классификации и кластеризации для определения групп или категорий клиентов,
знание которых способствует успешному продвижению товаров.
Вот список задач фондового рынка, которые можно решать при помощи технологии Data
Mining :· прогнозирование будущих значений финансовых инструментов и индикаторов поих
инструмента и его силы (сильный, умеренно сильный и т.д.);
· выделение кластерной структуры рынка, отрасли, сектора по некоторому набору
· динамическое управление портфелем;
· предсказание наступления кризиса и прогноз его развития;
· выбор активов и др.
Кроме описанных выше сфер деятельности, технология DataMining может применяться в самых разнообразных областях бизнеса, где есть необходимость в анализе данных и накоплен некоторый объем ретроспективной информации.
Применение DataMining в CRM
Одно из наиболее перспективных направлений применения DataMining – использование данной технологии в аналитическом CRM. 
При совместном использовании этих технологий добыча знаний совмещается с «добычей денег» из данных о клиентах.
Важным аспектом в работе отделов маркетинга и отдела продаж является составление целостного представления о клиентах, информация об их особенностях, характеристиках, структуре клиентской базы. В CRM используется так называемое профилирование клиентов, дающее полное представление всей необходимой информации о клиентах.
Профилирование клиентов включает следующие компоненты: сегментация клиентов, прибыльность клиентов, удержание клиентов, анализ реакции клиентов. Каждый из этих компонентов может исследоваться при помощи DataMining, а анализ их в совокупности, как компонентов профилирования, в результате может дать те знания, которые из каждой отдельной характеристики получить невозможно.
WebMining можно перевести как «добыча данных в Web». WebIntelligence или Web.
Интеллект готов «открыть новую главу» в стремительном развитии электронного бизнеса. Способность определять интересы и предпочтения каждого посетителя, наблюдая за его поведением, является серьезным и критичным преимуществом конкурентной борьбы на рынке электронной коммерции.
Системы WebMining могут ответить на многие вопросы, например, кто из посетителей является потенциальным клиентом Web-магазина, какая группа клиентов Web-магазина приносит наибольший доход, каковы интересы определенного посетителя или группы посетителей.
Методы
Классификация методов
Недостаток такой классификации: и статистические, и кибернетические алгоритмы тем или иным образом опираются на сопоставление статистического опыта с результатами мониторинга текущей ситуации.
Рассмотрим подробнее представленные выше группы.
Статистические методы Data mining
В эти методы представляют собой четыре взаимосвязанных раздела:
Арсенал статистических методов Data Mining классифицирован на четыре группы методов :
Кибернетические методы Data Mining
К этой группе относятся такие методы :
Далее рассмотрим некоторые из представленных методов.
Кластерный анализ
Кластеризация является описательной процедурой, она не делает никаких статистических выводов, но дает возможность провести разведочный анализ и изучить «структуру данных».
Само понятие «кластер» определено неоднозначно: в каждом исследовании свои «кластеры». Переводится понятие кластер (cluster) как «скопление», «гроздь». Кластер можно охарактеризовать как группу объектов, имеющих общие свойства.
Характеристиками кластера можно назвать два признака:
Вопрос, задаваемый аналитиками при решении многих задач, состоит в том, как организовать данные в наглядные структуры, т.е. развернуть таксономии.
Наибольшее применение кластеризация первоначально получила в таких науках как биология, антропология, психология. Для решения экономических задач кластеризация длительное время мало использовалась из-за специфики экономических данных и явлений.
Кластеры могут быть непересекающимися, или эксклюзивными (non-overlapping, exclusive), и пересекающимися (overlapping) [22].
Следует отметить, что в результате применения различных методов кластерного анализа могут быть получены кластеры различной формы. Например, возможны кластеры «цепочного» типа, когда кластеры представлены длинными «цепочками», кластеры удлиненной формы и т.д., а некоторые методы могут создавать кластеры произвольной формы.
Приведем краткую характеристику подходов к кластеризации.
Алгоритмы, основанные на разделении данных (Partitioningalgorithms), в т.ч. итеративные:
Методы, основанные на концентрации объектов (Density-basedmethods):
Модельные методы (Model-based):
Методы кластерного анализа. Итеративные методы.
При большом количестве наблюдений иерархические методы кластерного анализа не пригодны. В таких случаях используют неиерархические методы, основанные на разделении, которые представляют собой итеративные методы дробления исходной совокупности. В процессе деления новые кластеры формируются до тех пор, пока не будет выполнено правило остановки.
Такая неиерархическая кластеризация состоит в разделении набора данных на определенное количество отдельных кластеров. Существует два подхода. Первый заключается в определении границ кластеров как наиболее плотных участков в многомерном пространстве исходных данных, т.е. определение кластера там, где имеется большое «сгущение точек». Второй подход заключается в минимизации меры различия объектов
Алгоритм k-средних (k-means)
Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. Полное описание алгоритма можно найти в работе Хартигана и Вонга (HartiganandWong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров.
Общая идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга.
1. Первоначальное распределение объектов по кластерам.
Выбор начальныхцентроидов может осуществляться следующим образом:
В результате каждый объект назначен определенному кластеру.
2. Итеративный процесс.
Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.
Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:
На рисунке приведен пример работы алгоритма k-средних для k, равного двум.
Пример работы алгоритма k-средних (k=2)
Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.
Проверка качества кластеризации
После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т.е. оценить, насколько кластеры отличаются друг от друга).
Для этого рассчитываются средние значения для каждого кластера. При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части.
Достоинства алгоритма k-средних:
Недостатки алгоритма k-средних:
Байесовские сети
В теории вероятности понятие информационной зависимости моделируется посредством условной зависимости (или строго: отсутствием условной независимости), которая описывает, как наша уверенность в исходе некоего события меняется при получении нового знания о фактах, при условии, что нам был уже известен некоторый набор других фактов.
Удобно и интуитивно понятно представлять зависимости между элементами посредством направленного пути, соединяющего эти элементы в графе. Если зависимость между элементами x и y не является непосредственной и осуществляется посредством третьего элемента z, то логично ожидать, что на пути между x и y будет находиться элемент z. Такие узлы-посредники будут «отсекать» зависимость между x и y, т.е. моделировать ситуацию условной независимости между ними при известном значении непосредственных факторов влияния. Такими языками моделирования являются байесовские сети, которые служат для описания условных зависимостей между понятиями некой предметной области.
1. Использование всех переменных и определение всех зависимостей между ними.
2. Наличие двух предположений относительно переменных:
Различают два основных сценария применения байесовских сетей:
1. Описательный анализ. Предметная область отображается в виде графа, узлы которого представляют понятия, а направленные дуги, отображаемые стрелками, иллюстрируют непосредственные зависимости между этими понятиями. Связь между понятиями x и y означает: знание значения x помогает сделать более обоснованное предположение о значении y. Отсутствие непосредственной связи между понятиями моделирует условную независимость между ними при известных значениях некоторого набора «разделяющих» понятий. Например, размер обуви ребенка, очевидно, связан с умением ребенка читать через возраст. Так, больший размер обуви дает большую уверенность, что ребенок уже читает, но если нам уже известен возраст, то знание размера обуви уже не даст нам дополнительной информации о способности ребенка к чтению.
В качестве другого, противоположного, примера рассмотрим такие изначально несвязанные факторы как курение и простуда. Но если нам известен симптом, например, что человек страдает по утрам кашлем, то знание того, что человек не курит, повышает нашу уверенность того, что человек простужен.
Отмечают такие достоинства байесовских сетей как метода DataMining:
• в модели определяются зависимости между всеми переменными, это позволяет легко обрабатывать ситуации, в которых значения некоторых переменных неизвестны;
• байесовские сети достаточно просто интерпретируются и позволяют на этапе прогностического моделирования легко проводить анализ по сценарию «что, если»;
• байесовский метод позволяет естественным образом совмещать закономерности, выведенные из данных, и, например, экспертные знания, полученные в явном виде;
• использование байесовских сетей позволяет избежать проблемы переучивания (overfitting), то есть избыточного усложнения модели, что является слабой стороной многих методов (например, деревьев решений и нейронных сетей).
Наивно-байесовский подход имеет следующие недостатки:
• перемножать условные вероятности корректно только тогда, когда все входные переменные действительно статистически независимы; хотя часто данный метод показывает достаточно хорошие результаты при несоблюдении условия статистической независимости, но теоретически такая ситуация должна обрабатываться более сложными методами, основанными на обучении байесовских сетей;
• на результат классификации в наивно-байесовском подходе влияют только индивидуальные значения входных переменных, комбинированное влияние пар или троек значений разных атрибутов здесь не учитывается. Это могло бы улучшить качество классификационной модели с точки зрения ее прогнозирующей точности, однако,увеличило бы количество проверяемых вариантов.
Искусственные нейронные сети
Слоистые сети, в свою очередь, могут быть однослойными и многослойными.
Однослойная сеть — сеть, состоящая из одного слоя.
Многослойная сеть — сеть, имеющая несколько слоев.
В полносвязных сетях каждый нейрон передает свой выходной сигнал остальным нейронам, включая самого себя. Выходными сигналами сети могут быть все или некоторые выходные сигналы нейронов после нескольких тактов функционирования сети.
Все входные сигналы подаются всем нейронам.
Обучение нейронных сетей
Сложность может вызвать вопрос о количестве наблюдений в наборе данных. И хотя существуют некие правила, описывающие связь между необходимым количеством наблюдений и размером сети, их верность не доказана. Количество необходимых наблюдений зависит от сложности решаемой задачи. При увеличении количества признаков количество наблюдений возрастает нелинейно, эта проблема носит название «проклятие размерности». При недостаточном количестве данных рекомендуется использовать линейную модель.
Аналитик должен определить количество слоев в сети и количество нейронов в каждом слое. Далее необходимо назначить такие значения весов и смещений, которые смогут минимизировать ошибку решения. Веса и смещения автоматически настраиваются таким образом, чтобы минимизировать разность между желаемым и полученным на выходе сигналами, которая называется ошибка обучения. Ошибка обучения для построенной нейронной сети вычисляется путем сравнения выходных и целевых (желаемых) значений. Из полученных разностей формируется функция ошибок.
Переобучение нейронной сети
