Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
6. ОСНОВНЫЕ МЕТОДЫ АНАЛИЗА И ИНТЕРПРЕТАЦИИ ДАННЫХ 6.1. Предварительная обработка данных Практическое применение методов Data Mining предполагает многоэтапную процедуру, основные этапы которой изложены в раз- деле 3.1. Одним из ключевых этапов этой процедуры, предваряю- щей, собственно, применение методов Data Mining, является этап предварительной обработки данных, включающий различные типы преобразований. Рассмотрим их более подробно. Одним из ключевых преобразований этапа предварительной об- работки данных является «очистка» данных (англ. Data Cleaning, Data Cleansing, Data Scrubbing), предполагающая обнаружение и корректировку / удаление поврежденных элементов данных. Дан- ные, имеющие такие повреждения (неточные, неполные, дублиро- ванные, противоречивые, зашумленные), называют «грязными». Источниками «грязных» данных могут быть поврежденные инстру- менты сбора данных, проблемы во введении исходных данных, «человеческий фактор» в случае неавтоматического варианта фор- мирования данных, проблемы в каналах передачи данных, ограни- чения технологий передачи данных, использование разных наиме- нований в пределах одной номенклатуры и т.п. Особую актуальность очистки грязных данных подтверждает известное в информатике выражение: «Мусор на входе – мусор на выходе» (англ. Garbage In – Garbage Out, GIGO 1 ). Оно означает, что при неверных входных данных будут получены неверные резуль- таты работы в принципе верного алгоритма. Действительно, прак- тически полезными результаты применения каких бы то ни было 1 В отличие от известной дисциплины обслуживания FIFO встречается нечасто, а жаль… 6. Основные методы анализа и интерпретации данных 51 методов Data Mining будут только в случае использования ими корректных достоверных данных. Учитывая, что такие данные могут быть доставлены из разных источников и быть достаточно существенными в объеме, задача получения и обработки «чистых» данных может быть крайне непростой. Более того, следует отметить, что наличие «грязных» данных порой более проблематично, чем их отсутствие вовсе – извлечение полезных знаний из таких данных может потребовать значитель- ного времени, причем безрезультатно. При этом еще более пробле- матичным будет успешное извлечение из таких данных недостовер- ных знаний и дальнейшее их практическое использование с трудно предсказуемыми последствиями. Именно поэтому этапу получения «чистых», готовых к анализу данных придают большое значение, а по затратам времени этот этап может быть одним из самых дли- тельных [36]. Сегодня проблемам получения «чистых» данных посвящены от- дельные достаточно емкие исследования [31]. В них обсуждается целый спектр различных особенностей этой проблематики, начиная от концептуальных вопросов и завершая деталями современных технологических решений в базах данных и хранилищах данных. Отметим здесь некоторые наиболее принципиальные моменты. Все проблемы очистки данных разделяют на две группы, вызван- ные интеграцией различных источников данных (англ. Multi-Source Problems) или обусловленные проблемами единственного источ- ника данных (англ. Single-Source Problems). В свою очередь, каждая из групп может быть разделена на две самостоятельные группы, определяемые либо несовершенством схем интегрируемых баз дан- ных (англ. Schema Level),либо несовершенством на уровне соб- ственно элементов данных (англ. Instance Level):записей, объектов и т.п. Далее каждая из ветвей полученного дерева классификации детализируется конкретным перечнем возможных проблем очистки данных (рис. 11). В табл. 4 и 5 приведены некоторые примеры «грязных» данных, порожденные на разных уровнях – на Schema Level и на Instant Level. Интеллектуальный анализ данных 52 Рис. 11. Пример классификации проблем качества данных в различных источниках Т а б л и ц а 4 Примеры «грязных» данных единственного источника на уровне схемы данных Проблема «Грязные» данные Причины Атрибут Недопустимые значения дата рождения = 30.13.70 Значение за пределами диапазона Запись Нарушение зависимости атрибутов возраст = 22 дата рождения = 12.02.70 Возраст = (теку- щая дата – дата рождения) Тип записи Нарушение уникальности сотр. 1 = (имя = Иван, SSN = 123) сотр. 2 = (имя = Петр, SSN = 123) SNN должен быть уникальным Источник Нарушение ссылочной целостности сотр. 1 = (имя = Иван, отд. = 789) Отдела с номером 789 не существует Проблемы качества данных Единственный источник данных Различные источники данных Несовершен- ство схем БД (отсутствие ограничений целостности, плохая архи- тектура) Несовершен- ство на уровне элементов данных (ошибки ввода данных) Несовершен- ство схем БД (гетероген- ные модели данных и ар- хитектура) Несовершенство на уровне эле- ментов данных (перекрытие и противоречи- вость данных) 6. Основные методы анализа и интерпретации данных 53 Т а б л и ц а 5 Примеры «грязных» данных единственного источника на уровне записей Причина «Грязные» данные Причина Атрибут Пропущенное значение тел. = 9999-999999 Недопустимые (некорректные, null и т.п.) значе- ния при вводе Орфографические ошибки город = Тамск город = Москваа Орфографическая ошибка Сокращения и аббревиатуры должность = А, отдел = ЛТО Объединенные значения имя = Иван 12.07.70 Томск Несколько значений в атрибуте Запись Нарушение зависимости атрибутов город = Томск, инд. = 666777 Город и индекс не соответствуют друг другу Тип записи Дубликаты записей сотр. 1 = (имя = Иван, SSN = 123) сотр. 2 = (имя = Иван, SSN = 123) Противоречащие записи сотр. 1 = (имя = Иван, SSN = 123) сотр. 1 = (имя = Иван, SSN = 321) Записи одного и того же сотруд- ника с разным SSN Источник Неверные ссылки сотр. = (имя = Иван, отд. = 789) Отдел с номером 789 существует, но указан не- верно Выделяют следующее этапы очистки данных: 1. Анализ данных (англ. Data analysis). Для того чтобы опреде- лить, какие виды ошибок и несоответствий должны быть удалены, требуется детальный анализ данных. В дополнение к инспекции данных или отдельных выборок данных «вручную» следует исполь- зовать и метаданные. 2. Определение способов трансформации потоков данных и правил отображения (англ. Definition of transformation workflow and mapping rules). На данном этапе выполняется оценка количества Интеллектуальный анализ данных 54 источников данных, степени их неоднородности и «загрязненно- сти». На основе этой информации создаются схемы потоков дан- ных, позволяющие преобразовать множество источников данных в один, избегая создания ошибок Multi-Source слияния (например, появление дублирующих записей). 3. Верификация (англ. Verification). Оценка корректности и результативности выполнения предыдущего этапа (например, на небольшой выборке данных). При необходимости производится возврат к этапу 2 для его повторного выполнения. 4. Трансформация (англ. Transformation). Загрузка данных в единое хранилище с использованием правил трансформации, опре- деленных и отлаженных на этапах 2 и 3. Очистка данных уровня Single-Source. 5. Обратная загрузка очищенных данных (англ. Backflow of cleaned data). Имея на этапе 4 очищенный набор данных в едином хранилище, целесообразно этими «чистыми» данными заменить аналогичные «грязные» данные в исходных источниках. Это позво- лит в будущем не выполнять повторно все этапы преобразований по очистке данных. Реализовать эти этапы можно самыми различными путями с ис- пользованием существующих и созданных специально способов и технологий. Рассмотрим наиболее интересные из них. Этап анализа данных предполагает анализ использования мета- данных, которых, как правило, недостаточно для оценки качества данных из имеющихся источников. Поэтому важно анализировать реальные примеры данных, оценивая их характеристики и сигна- туры значений. Это позволяет находить взаимосвязи между атрибу- тами в схемах данных различных источников. Выделяют два под- хода решения этой задачи – профилирование данных (англ. data profiling) и извлечение данных (англ. data mining). Профилирование данных ориентировано на анализ индивидуаль- ных атрибутов, характеризующихся их конкретными свойствами: тип данных, длина, диапазон значений, частота встречаемости дис- кретных значений, дисперсия, уникальность, встречаемость «null» значений, типичная сигнатура записи (например, у телефонного 6. Основные методы анализа и интерпретации данных 55 номера). Именно набор подобных свойств (профиль) позволяет оце- нить различные аспекты качества данных. Извлечение данных предполагает поиск взаимосвязей между несколькими атрибутами достаточно большого набора данных. Учитывая то, что этот способ получил название data mining, здесь используют упоминавшиеся выше (см. табл. 1) методы кластериза- ции, подведения итогов, поиска ассоциаций и последовательно- стей. Кроме того, для дополнения пропущенных значений, коррек- тировки недопустимых значений или идентификации дубликатов могут быть использованы существующие ограничения целостности (англ. integrity constraints), принятые в реляционных базах данных, наложенные дополнительно на бизнес-связи между атрибутами. Например, известно, что «Total = Quantity × Unit_Price». Все за- писи, не удовлетворяющие этому условию, должны быть изучены более внимательно, исправлены или исключены из рассмотрения. Для разрешения проблем очистки данных в одном источнике (single-source problems), в том числе перед его интеграцией с дру- гими источниками данных, реализуют следующие этапы: – Извлечение значений из атрибутов свободной формы (раз- биение атрибутов, англ. Extracting values from free-form attributes (attribute split)). В данном случае речь может идти о строковых зна- чениях, сохраняющих несколько слов подряд (например, адрес или полное имя человека). В этом случае требуется четкое понимание того, на какой позиции этого значения находится интересующая нас часть атрибута. Возможно, потребуется даже сортировка составных частей такого атрибута. – Валидация и коррекция (англ. Validation and correction). Данный этап предполагает поиск ошибок ввода данных и их исправ- ление наиболее автоматическим способом, например используя автоматическую проверку правописания во избежание орфографи- ческих ошибок и опечаток. Словарь географических названий и почтовых кодов также следует использовать для корректировки значений вводимых адресов. Зависимость атрибутов (дата рожде- ния – возраст; Total = Quantity × Unit_Price и т.п.) также способ- ствует избеганию множества ошибок в данных. Интеллектуальный анализ данных 56 – Стандартизация (англ. Standardization). Этот этап предпола- гает приведение всех данных к единому универсальному формату. Примерами таких форматов являются формат написания даты и времени, размер регистра в написании строковых значений. Тексто- вые поля должны исключать префиксы и суффиксы, аббревиатуры в них должны быть унифицированы, исключены проблемы с раз- личной кодировкой. Одной из основных проблем, вызванных интеграцией различных источников (multi-source problems) данных, является устранение дублирования записей. Этот этап выполняется после подавляющего большинства преобразований и чисток. Он предполагает сначала идентификацию сходных в некотором смысле записей, а затем их слияние с объединением атрибутов. Очевидно, решение этой задачи при наличии у дублирующих записей первичного ключа достаточно просто. Если такого однозначно идентифицирующего признака нет, то задача устранения дубликатов значительно осложняется, требуя применения нечетких (англ. fuzzy) подходов сравнения (близости в некотором смысле) записей между собой. 6.2. Оптимизация признакового пространства Современные массивы данных, к которым могут быть приме- нены те или иные методы Data Mining, могут характеризоваться большим числом признаков, формирующих признаковое простран- ство большой размерности. Поэтому актуальной является задача снижения размерности такого пространства до размерности, позво- ляющей без лишних затруднений осуществлять обработку данных и / или их визуализацию. Решение такой задачи называют оптими- зацией признакового пространства или поиском значимых призна- ков (англ. Feature Selection, иногда – Feature Engineering). Ее реше- ние сегодня часто становится самостоятельной исследовательской задачей, которую решают с применением различных подходов. При этом все подходы к снижению размерности исходного при- знакового пространства могут быть разделены на два больших класса. 6. Основные методы анализа и интерпретации данных 57 Первый класс предусматривает трансформацию признакового пространства. Один из наиболее известных и применяемых на прак- тике подходов этого класса – метод главных компонентов (МГК, англ. Principal Component Analysis) [50, 67]. Рассмотрим его кратко в разд. 6.2.1. Другой класс методов заключается в выборе наиболее инфор- мативных, полезных признаков и исключении из рассмотрения неинформативных признаков без трансформации исходного пространства [32, 33]. Применяют различные методы и подходы, с которыми можно подробнее ознакомиться в специальной лите- ратуре [51]: – полного или усеченного перебора; – ветвей и границ; – эволюционные; – со случайным выбором. Ознакомимся здесь с одним из подходов (разд. 6.2.2), который может быть использован при усеченном переборе признаков, в основе которого лежит критерий попарной разделимости Джеффриса– Матуситы (ДМ) [33]. 6.2.1. С трансформацией пространства признаков Одним из широко используемых традиционных методов реше- ния задачи трансформации исходного пространства признаков в но- вое является МГК [50]. В основе МГК лежит идея нахождения для исходного набора признаков x = {x i , i = 1, …, P} размерности P та- кого набора скрытых (латентных) переменных y = {y i , i' = 1, …, P'} (главных компонент) размерности P', который бы максимально объ- яснял дисперсии многомерных переменных x при выполнении условия P' < P. Главные компоненты представляют собой новое множество ис- следуемых признаков y, каждый из которых получен в результате некоторой линейной комбинации исходных признаков x. Причем полученные в результате преобразования новые признаки y некор- релированы между собой и упорядочены по степени рассеяния Интеллектуальный анализ данных 58 (дисперсии) таким образом, что первый признак обладает наиболь- шей дисперсией. В общем случае[i']-й главной компонентой исходного признако- вого пространства с ковариационной матрицей и вектором средних µ называется нормированная линейная комбинация компо- нент исходного P-мерного признакового вектора x y i' = l i'1 x 1 + l i'2 x 2 + … + l i'P x P = L i' x, (6.1) где L i' = (l i'1 , l i'2 , …, l i'P )–[i']-й собственный вектор матрицы про- странства . Геометрическая модель МГК для двумерного случая показана на рис. 12. 125 100 75 50 25 0 25 50 75 100 125 x 2 x 1 y 2 y 1 μ 2 μ 1 Рис. 12. Пример двумерной модели главных компонент Множество признаковых векторов x j = (x 1 j , x 2 j ), j = 1, …, N, рас- полагается примерно в очертаниях эллипсоида рассеивания, и оси главных компонент y 1 и y 2 проходят вдоль его осей. Обобщенная дисперсия y и сумма дисперсий (Dy 1 + Dy 2 + … + Dy P ') главных компонент y равны обобщенной дисперсии x и сумме дисперсий (Dx 1 + Dx 2 + … + Dx P ) исходных признаков x. На основании этого выносится решение о том, сколько последних главных компонент P' следует практически без ущерба для информативности изъять из рассмотрения, сократив тем самым размерность исследуемого про- странства . 6. Основные методы анализа и интерпретации данных 59 Анализируя изменение относительной доли дисперсии (P') (𝑃 ′ ) = 𝐷𝑦 1 +𝐷𝑦 2 +⋯+𝐷𝑦 𝑃′ 𝐷𝑥 1 +𝐷𝑥 2 +⋯+𝐷𝑥 𝑃 ,(1 P' P), (6.2) вносимой первыми главными компонентами, в зависимости от числа этих компонент можно разумно определить число компонент P', которое целесообразно оставить в рассмотрении. Выбрав предельную величину относительной доли дисперсии (P'), можно задать порог, определяющий количество главных компонент P', используемых в дальнейшем для классификации. Несмотря на относительную простоту, МГК обладает двумя су- щественными недостатками. Во-первых, при использовании МГК предполагается, что распределение исходных многомерных данных подчинено нормальному закону и трансформация происходит отно- сительно многомерного гиперэллипсоида рассеивания (хотя исход- ные измерения могут быть распределены не в рамках такого гипер- эллипсоида). Во-вторых, трансформация исходного признакового пространства способна повлечь за собой значительные искажения признакового пространства, что может привести к снижению разде- лимости в таком новом признаковом пространстве для объектов и снизить итоговое качество классификации. |