Алгоритмы кластеризации
Алгоритм Enhanced k-means Clustering
В этом алгоритме число кластеров изначально задается пользователем. Кластеризация проводится только по числовым атрибутам, их число не должно быть слишком велико. Количество записей может быть каким угодно.
Алгоритм O-Cluster
Этот алгоритм, в отличие от предыдущего, автоматически определяет число кластеров. Он может работать как с числовыми, так и с категориальными атрибутами. Может работать с большим числом атрибутов, т.е. более 10, и с большим количеством записей, более 1000.
Аналитическая платформа Deductor
Состав и назначение аналитической платформы Deductor (разработчик - компания BaseGroup Labs [115]). Deductor состоит из двух компонентов: аналитического приложения Deductor Studio и многомерного хранилища данных Deductor Warehouse [48] .
Архитектура системы Deductor представлена на рис. 26.1.
Рис. 26.1. Архитектура системы Deductor
Deductor Warehouse - многомерное хранилище данных, аккумулирующее всю необходимую для анализа предметной области информацию. Использование единого хранилища позволяет обеспечить непротиворечивость данных, их централизованное хранение и автоматически создает всю необходимую поддержку процесса анализа данных. Deductor Warehouse оптимизирован для решения именно аналитических задач, что положительно сказывается на скорости доступа к данным.
Deductor Studio - это программа, предназначенная для анализа информации из различных источников данных. Она реализует функции импорта, обработки, визуализации и экспорта данных. Deductor Studio может функционировать и без хранилища данных, получая информацию из любых других источников, но наиболее оптимальным является их совместное использование.
Архитектура Deductor Studio
Вся работа по анализу данных в Deductor Studio базируется на выполнении следующих действий:
импорт данных;обработка данных;визуализация;экспорт данных.На рис. 26.3 показана схема функционирования Deductor Studio. Отправной точкой для анализа всегда является процедура импорта данных. Полученный набор данных может быть обработан любым из доступных способов.
Рис. 26.3. Схема функционирования Deductor Studio
Результатом обработки также является набор данных, который, в свою очередь, опять может быть обработан. Импортированный набор данных, а также данные, полученные на каждом этапе обработки, могут быть экспортированы для последующего использования в других, например, в учетных системах. Поддерживаются следующие форматы:
хранилище данных Deductor Warehouse ;Microsoft Excel;Microsoft Word;HTML;XML;Dbase;буфер обмена Windows;текстовой файл с разделителями.Результаты каждого действия можно отобразить различными способами:
OLAP-кубы (кросс-таблица, кросс-диаграмма);плоская таблица;диаграмма, гистограмма;статистика;анализ по принципу "что-если";граф нейросети;дерево - иерархическая система правил;прочее.Способ возможных отображений зависит от выбранного метода обработки данных. Например, нейросеть содержит визуализатор "Граф нейросети", специфичный только для нее. Некоторые способы визуализации пригодны почти для всех методов обработки, например, в виде таблицы, диаграммы или гистограммы.
Последовательность действий, которые необходимо провести для анализа данных, называется сценарием.
Сценарий можно автоматически выполнять на любых данных. Типовой сценарий изображен на рис. 26.4.
Рис. 26.4. Типовой сценарий Deductor Studio
Архитектура Deductor Warehouse
Deductor Warehouse - многомерное хранилище данных, аккумулирующее всю необходимую для анализа предметной области информацию. Вся информация в хранилище содержится в структурах типа "звезда", где в центре расположены таблицы фактов, а "лучами" являются измерения. Пример такой структуры представлен на рис. 26.5.
Рис. 26.5. Пример структуры типа "звезда"
Такая архитектура хранилища наиболее адекватна задачам анализа данных.
Каждая "звезда" называется процессом и описывает определенное действие.
В Deductor Warehouse может одновременно храниться множество процессов, имеющим общие измерения.
Что представляет собой хранилище Deductor Warehouse ? Физически - это реляционная база данных, которая содержит таблицы для хранения информации и таблицы связей, обеспечивающие целостное хранение сведений. Поверх реляционной базы данных реализован специальный слой, который преобразует реляционное представление к многомерному. Многомерное представление используется потому, что оно намного лучше реляционного соответствует идеологии анализа данных. Благодаря этому слою пользователь оперирует многомерными понятиями, такими как "измерение" или "факт", а система автоматически производит все необходимые манипуляции, необходимые для работы с реляционной СУБД.
Deductor Warehouse реализует универсальное многомерное хранение, т.е. может содержать множество процессов с различным количеством измерений и фактов. Настройка процессов, задание измерений, свойств и фактов задается при первой загрузке в хранилище данных. Вся работа с хранилищем осуществляется средствами Deductor Studio.
Краткая характеристика алгоритмов классификации
Алгоритмы Naive Bayes (NB):
Работает быстрее, чем ABN (по времени построения модели).Этот алгоритм лучше использовать для числа атрибутов < 200.Точность алгоритма меньше, чем в ABN.Adaptive Bayes Network (ABN):
Этот алгоритм лучше для большого числа атрибутов.Наглядность модели (генерация правил).Более точные модели, чем в NB.Больше параметров настройки.Support Vector Machine.
Описание аналитических алгоритмов
Кроме консолидации данных, работа по созданию законченного аналитического решения содержит несколько этапов.
Очистка данных. На этом этапе проводится редактирование аномалий, заполнение пропусков, сглаживание, очистка от шумов, обнаружение дубликатов и противоречий.
Трансформация данных. Производится замена пустых значений, квантование, табличная замена значений, преобразование к скользящему окну, изменение формата набора данных.
Data Mining. Строятся модели с использованием нейронных сетей, деревьев решений, самоорганизующихся карт, ассоциативных правил.
Интерпретация результатов.
На рис. 26.6 представлены алгоритмы, используемые в программе, сгруппированные по назначению.
Рис. 26.6. Алгоритмы, используемые в Deductor
Группа 1. Очистка данных
Редактирование аномалий
Автоматическое редактирование аномальных значений осуществляется с применением методов робастной фильтрации, в основе которых лежит использование робастных статистических оценок, таких, например, как медиана. При этом можно задать эмпирически подобранный критерий того, что считать аномалией. Например, задание в качестве степени подавления аномальных данных значения "слабая" означает наиболее терпимое отношение к величине допустимых выбросов.
Заполнение пропусков
В программе предусмотрено два способа заполнения пропущенных данных.
Аппроксимация - пропущенные данные восстанавливаются методом аппроксимации.Максимальное правдоподобие - алгоритм подставляет наиболее вероятные значения вместо пропущенных данных.Метод аппроксимации рекомендуется использовать в рядах, где данные упорядочены. В этом методе применяется последовательный рекуррентный фильтр второго порядка (фильтр Калмана). Входные данные последовательно подаются на вход фильтра, и если очередное значение ряда отсутствует, оно заменяется значением, которое экстраполируется фильтром.
Метод максимального правдоподобия рекомендуется применять на неупорядоченных данных. При использовании этого метода строится плотность распределения вероятностей, и отсутствующие данные заменяются значением, соответствующим ее максимуму.
Сглаживание
Для сглаживания рядов данных в программе используются два алгоритма.
Первый способ сглаживания - это низкочастотная фильтрация с использованием быстрого преобразования Фурье. При этом задается верхнее значение полосы пропускаемых частот. При подавлении шумов на основе анализа распределения составляющих Фурье спектра на выход фильтра пропускаются спектральные составляющие, которые превышают некоторый порог, рассчитанный по эмпирическим формулам в соответствии с заданным критерием степени вычитания шума. Чем больше требуется сгладить данные, тем меньше должно быть значение полосы. Однако слишком узкая полоса может привести к потере полезной информации. Следует заметить, что этот алгоритм наиболее эффективен, если анализируемые данные есть сумма полезного сигнала и белого шума.
Второй способ сглаживания - это вейвлет-преобразование. Если выбран данный метод, то необходимо задать глубину разложения и порядок вейвлета. "Масштаб" отсеиваемых деталей зависит от глубины разложения: чем больше эта величина, тем более "крупные" детали в исходных данных будут отброшены. При достаточно больших значениях параметра (порядка 7-9) выполняется не только очистка данных от шума, но и их сглаживание ("обрезаются" резкие выбросы). Использование слишком больших значений глубины разложения может привести к потере полезной информации из-за слишком высокой степени "огрубления" данных. Порядок вейвлета определяет гладкость восстановленного ряда данных: чем меньше значение параметра, тем ярче будут выражены "выбросы", и наоборот - при больших значения параметра "выбросы" будут сглажены.
Очистка от шумов
При выборе режима очистки от шумов необходимо задать степень вычитания шума: малую, среднюю или большую. При использовании вычитания шума следует соблюдать осторожность, т.к. реализованный здесь эвристический алгоритм гарантирует удовлетворительные результаты лишь при выполнении двух условий:
дисперсия шума значительно меньше энергии полезного сигнала;шум имеет нормальное распределение.Обнаружение дубликатов и противоречий
Суть обработки состоит в том, что определяются входные и выходные поля. Алгоритм ищет во всем наборе записи, для которых одинаковым входным полям соответствуют одинаковые (дубликаты) или разные (противоречия) выходные поля. На основании этой информации создаются два дополнительных логических поля - "Дубликат" и "Противоречие", принимающие значения "правда" или "ложь".
Группа 2. Трансформация данных
Анализируемая информация, представленная в виде набора данных, имеет определенный формат. Для анализа различных аспектов информации может потребоваться изменение ее формата, или трансформация. Трансформация данных состоит из трех этапов, выполняемых в строгой последовательности (каждый из которых однако, может быть пропущен).
Квантование значений
При выполнении этой операции осуществляется разбиение диапазона числовых значений на указанное количество интервалов определенным методом и замена каждого обрабатываемого значения на число, связанное с интервалом, к которому оно относится, либо на метку интервала. Интервалы разбиения включают в себя нижнюю границу, но не включают верхнюю, кроме последнего интервала, который включает в себя обе границы. Результатом преобразования может быть: номер интервала (от нуля до значения, на единицу меньшего количества интервалов), значение нижней или верхней границы интервала разбиения, среднее значение интервала разбиения, метка интервала.
Квантование может быть осуществлено интервальным или квантильным методом.
Интервальное квантование подразумевает разбиение диапазона значений на указанное количество значений равной длины. Например, если значения в поле попадают в диапазон от 0 до 10, то при интервальном квантовании на 10 интервалов мы получим отрезки от 0 до 1, от 1 до 2 и т.д. При этом 0 будет относиться к первому интервалу, 1 - ко второму, а 9 и 10 - к десятому.
Квантильное квантование подразумевает разбиение диапазона значений на равновероятные интервалы, то есть на интервалы, содержащие равное (или, по крайней мере, примерно равное) количество значений. Нарушение равенства возможно только тогда, когда значения, попадающие на границу интервала, встречаются в наборе данных несколько раз. В этом случае все они относятся к одному определенному интервалу и могут вызвать "перевес" в его сторону.
Табличная замена значений
В результате выполнения этой операции производится замена значений по таблице подстановки, которая содержит пары, состоящие из исходного и выходного значения. Например, 0 - "красный", 1 - "зеленый", 2 - "синий". Или "зима" - "январь", "весна" - "апрель", "лето" - "июль", "осень" - "октябрь". Для каждого значения исходного набора данных ищется соответствие среди исходных значений таблицы подстановки. Если соответствие найдено, то значение меняется на соответствующее выходное значение из таблицы подстановки. Если значение не найдено в таблице, оно может быть либо заменено значением, указанным для замены "по умолчанию", либо оставлено без изменений (если такое значение не указано).
"Скользящее окно"
При решении некоторых задач, например, при прогнозировании временных рядов с помощью нейросети, требуется подавать на вход анализатора значения несколько смежных отсчетов из исходного набора данных. Такой метод отбора данных называется скользящим окном (окно - поскольку выделяется только некоторый непрерывный участок данных, скользящее - поскольку это окно "перемещается" по всему набору). При этом эффективность реализации заметно повышается, если не выбирать данные каждый раз из нескольких последовательных записей, а последовательно расположить данные, относящиеся к конкретной позиции окна, в одной записи.
Преобразование даты
Разбиение даты необходимо для анализа всевозможных показателей за определенный период (день, неделя, месяц, квартал, год). Суть разбиения заключается в том, что на основе столбца с информацией о дате формируется другой столбец, в котором указывается, к какому заданному интервалу времени принадлежит строка данных. Тип интервала задается аналитиком, исходя из того, что он хочет получить, - данные за год, квартал, месяц, неделю, день или сразу по всем интервалам.
Группировка
Трудно делать какие-либо выводы по данным каждой записи в отдельности. Аналитику для принятия решения часто необходима сводная информация. Совокупные данные намного более информативны, тем более если их можно получить в разных разрезах. В Deductor Studio предусмотрен инструмент, реализующий сбор сводной информации, - "Группировка". Группировка позволяет объединять записи по полям-измерениям, агрегируя данные в полях-фактах для дальнейшего анализа.
Разгруппировка
Группировка используется для объединения фактов по каким-либо измерениям. При этом под объединением понимается применение некоторой функции агрегации. Если в исходном наборе данных присутствовали какие-либо другие измерения, то теряется информация о значениях фактов в разрезе этих измерений. Алгоритм разгруппировки позволяет восстановить эти факты, но их значения восстанавливаются не точно, а пропорционально вкладу в сгруппированные значения.
Комплексная предобработка
Термин "предобработка" можно трактовать шире, а именно, как процесс предварительного экспресс-анализа данных. Например, как оценить, является ли фактор значимым или нет, все ли факторы учтены для объяснения поведения результирующей величины и так далее. Для этих целей используются такие алгоритмы как корреляционный анализ, факторный анализ, метод главных компонент, регрессионный анализ. Подобный анализ в Deductor Studio называется комплексной предобработкой, в рамках которой осуществляется понижение размерности входных данных и/или устранение незначащих факторов.
Понижение размерности пространства факторов
Понижение размерности необходимо в случаях, когда входные факторы коррелированы друг с другом, т.е. взаимозависимы. Имеется возможность пересчитать их в другую систему координат, выделяя при этом главные компоненты. Понижение размерности получается путем отбрасывания компонент, в наименьшей степени объясняющих дисперсию результирующих значений (при этом предполагается, что исходные факторы полностью объясняют дисперсию результирующих факторов).
Требуется указать порог значимости, задающий дисперсию результата. Значение порога значимости может изменяться от 0 до 1.
Устранение незначащих факторов
Устранение незначащих факторов основано на поиске таких значений, которые в наименьшей степени коррелированы (взаимосвязаны) с выходным результатом. Такие факторы могут быть исключены из результирующего набора данных практически без потери полезной информации. Критерием принятия решения об исключении является порог значимости. Если корреляция (степень взаимозависимости) между входным и выходным факторами меньше порога значимости, то соответствующий фактор отбрасывается как незначащий.
Группа 3. Data Mining
Алгоритмы Data Mining в пакете Deductor представлены таким набором:
нейронные сети;линейная регрессия;прогнозирование;автокорреляция;деревья решений;самоорганизующиеся карты;ассоциативные правила.Использование нейронных сетей, самоорганизующихся карт и ассоциативных правил на примере пакета Deductor было рассмотрено нами во втором разделе курса лекций.
Oracle Data Mining
В марте 1998 компания Oracle [112] объявила о совместной деятельности с 7 партнерами - поставщиками инструментов Data Mining. Далее последовало включение в Oracle8i средств поддержки алгоритмов Data mining. В июне 1999 года Oracle приобретает Darwin (Thinking Machines Corp.). В 2000-2001 годах выходят новые версии Darwin, Oracle Data Mining Suite. В июне 2001 года выходит Oracle9i Data Mining.
Oracle Data Mining является опцией или модулем в Oracle Enterprise Edition (версия Oracle Database 10g). Опция Oracle Data Mining (ODM) предназначена для анализа данных методами, относящимися к технологии извлечения знаний, или Data Mining. В редакциях Personal Edition, Standard Edition, OneStandard Edition эта опция недоступна.
ODM поддерживает все этапы технологии извлечения знаний, включая постановку задачи, подготовку данных, автоматическое построение моделей, анализ и тестирование результатов, использование моделей в реальных приложениях [113].
Существенно, что модели строятся автоматически на основе анализа имеющихся данных об объектах, наблюдениях и ситуациях с помощью специальных алгоритмов. Основу опции ODM составляют процедуры, реализующие различные алгоритмы построения моделей классификации, регрессии, кластеризации.
На этапе подготовки данных обеспечивается доступ к любым реляционным базам, текстовым файлам, файлам формата SAS. Дополнительные средства преобразования и очистки данных позволяют изменять вид представления, проводить нормализацию значений, выявлять неопределенные или отсутствующие значения. На основе подготовленных данных специальные процедуры автоматически строят модели для дальнейшего прогнозирования, классификации новых ситуаций, выявления аналогий. ODM поддерживает построение пяти различных типов моделей. Графические средства предоставляют широкие возможности для анализа полученных результатов, верификации моделей на тестовых наборах данных, оценки точности и устойчивости результатов. Уточненные и проверенные модели можно включать в существующие приложения путем генерации их описаний на С, C++, Java, а также разрабатывать новые специализированные приложения с помощью входящего в состав среды ODM средства разработки Software Development Kit (SDK).
Важной особенностью системы ODM являются его технические характеристики: работа в архитектуре клиент-сервер, широкое использование техники параллельных вычислений, высокая степень масштабируемости при увеличении вычислительных ресурсов.
Характеристики Oracle Data Mining [114]:
Встроенные в Oracle Database алгоритмы извлечения знаний (DataMining Server).DM-инфраструктура вместо готовой инструментальной среды.API для разработки.Встроенные алгоритмы извлечения знаний позволяют упростить процесс извлечения знаний, устраняют необходимость дополнительного перемещения и хранения данных. Обладают производительностью и масштабируемостью.
Oracle Data Mining API. Использование Java API для разработки на Java основано на принципах JDM (стандарт для Data Mining).
Версия Data Mining 10g поддерживает спектр алгоритмов, которые приведены в таблице 26.1.
| Классификационные модели | Na_ve Bayes, Adaptive Bayes Network |
| Классификации и регрессионные модели | Support Vector Machine |
| Поиск существенных атрибутов | Minimal Descriptor Length |
| Кластеризация | Enhanced K-means, O-cluster |
| Поиск ассоциаций | Apriory Algorithm |
| Выделение признаков | Non-Negative Matrix Factorization |
Oracle Data Mining - функциональные возможности
Функции - Oracle Data Mining строит прогнозирующие и дескрипторные модели.
Прогнозирующие модели:
классификация;регрессия;поиск существенных атрибутов.Дескрипторные модели:
кластеризация;поиск ассоциаций;выделение признаков.Поддержка процесса от разведочного анализа до отображения данных
Deductor Studio позволяет пройти все этапы анализа данных. Схема на рис. 26.2 отображает процесс извлечения знаний из данных.
Рис. 26.2. Процесс извлечения знаний из данных в Deductor Studio
Рассмотрим этот процесс более детально.
На начальном этапе в программу загружаются или импортируются данные из какого-либо произвольного источника. Хранилище данных Deductor Warehouse является одним из источников данных. Поддерживаются также другие, сторонние источники:
текстовый файл с разделителями;Microsoft Excel;Microsoft Access;Dbase;CSV-файлы; ADO-источники - позволяют получить информацию из любого ODBC-источника (Oracle, MS SQL, Sybase и прочее).Обычно в программу загружаются не все данные, а какая-то выборка, необходимая для дальнейшего анализа.
После получения выборки можно получить подробную статистику по ней, посмотреть, как выглядят данные на диаграммах и гистограммах.
После такого разведочного анализа можно принимать решения о необходимости предобработки данных. Например, если статистика показывает, что в выборке есть пустые значения (пропуски данных), можно применить фильтрацию для их устранения.
Предобработанные данные далее подвергаются трансформации. Например, нечисловые данные преобразуются в числовые, что необходимо для некоторых алгоритмов. Непрерывные данные могут быть разбиты на интервалы, то есть производится их дискретизация.
К трансформированным данным применяются методы более глубокого анализа. На этом этапе выявляются скрытые зависимости и закономерности в данных, на основании которых строятся различные модели. Модель представляет собой шаблон, который содержит формализованные знания.
Последний этап - интерпретация - предназначен, чтобы из формализованных знаний получить знания на языке предметной области.
Поиск существенных атрибутов
Основная задача - выявление атрибутов, наиболее важних для прогнозирования целевых значений. Используется для ускорения процесса построения классификационной модели.
Используемый алгоритм - Minimum Descriptor Length (MDL).
Регрессия
Регрессия применяется для прогнозирования непрерывных величин. Простейшим случаем является линейная регрессия. Используется также метод Support Vector Machine.
