Problems, Methods, and Challenges in Comprehensive Data Cleansing (2003)

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

Когда находишься в ситуации «а с чего начать» помогает таксономия «грязных данных». Хотя в учебниках и дают список проблем, но он обычно неполный, вот постоянно искал исследования, которые рассматривают эту тему подробней. Попалась работа T.Gschwandtner, J.Gartner, W.Aigner, S.Miksch хотя они ее делали для рассмотрения способов очистки данных связанных с датами и временем но, на мой взгляд, это оказалось исключение, которое потребовало разобраться с правилами поглубже чем в учебниках. По собственному опыту знаю, что сопряжение дат и времени «вынос мозга» практически в прямом смысле и поэтому и зацепился за исследование этих авторов.

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

Это третья статья из цикла

1. Таксономия форматов времени и дат в неочищенных данных, 2012 г.

2. Очистка данных: проблемы и современные подходы 2000 г.

3. Таксономия «грязных данных» 2003 г.

4. Проблемы, методы и вызовы комплексной очистки данных 2003 г.

5. Формульное определение проблем качества данных 2005 г.

6. Обзор инструментов качества данных 2005 г.

Предисловие

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

1. Введение

Применение и использование огромных объемов данных играет все возрастающую роль в современной экономике, государственном управлении и исследованиях. Аномалии и примеси в данных вызывают раздражение и препятствуют их эффективному использованию, блокируя высокопроизводительную обработку и подтверждение результатов и выводов, полученных в результате интерпретации и анализа данных. Это приводит к более высокой стоимости и меньшей выгоде для обработки данных, что, возможно, делает его приложение бесполезным для потребителя. В [Eng00] перечислено несколько проблем, вызванных аномалиями данных, среди прочего, что неверные данные о ценах в розничных базах данных обходятся американским потребителям в 2,5 миллиарда долларов в виде ежегодных завышенных цен. В этом контексте очистка данных с годами вызывает все больший интерес. Мы полагаемся на безошибочные данные и способность использовать их в соответствии с нашими потребностями. Это развертывание включает эффективную интеграцию, применение, интерпретацию и анализ данных для поддержки бизнес-процессов, административных задач, принятия решений и научного обоснования.

Наличие аномалий и примесей в реальных данных хорошо известно. В [Orr98, Red98] их типичные показатели оцениваются в 5%. Это привело к разработке широкого спектра методов, направленных на выявление и устранение их в существующих данных. Мы относим все это к термину «очистка данных»; другие названия - очистка данных, очистка или согласование. Нет единого описания целей и масштабов комплексной очистки данных. Очистка данных применяется с разным пониманием и потребностями в различных областях обработки и обслуживания данных. Первоначальной целью очистки данных было устранение дубликатов в сборе данных - проблема, возникающая уже в отдельных приложениях базы данных и усугубляющаяся при интеграции данных из разных источников. Поэтому очистка данных часто рассматривается как неотъемлемая часть процесса интеграции данных. Помимо устранения дубликатов, процесс интеграции включает преобразование данных в форму, желаемую предполагаемое приложение и соблюдение доменно-зависимых ограничений на данные.

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

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

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

Структура статьи следующая. В следующем разделе мы мотивируем необходимость очистки данных, описывая различные способы управления данными, возникающие проблемы и вытекающие из них последствия аномалий в данных. В разделе 3 мы более подробно классифицируем аномалии данных. В Разделе 4 определяется наше восприятие очистки данных и указывается набор критериев качества, которые представляют меры для состояния данных - до и после выполнения процесса очистки. Следовательно, эти критерии могут использоваться для измерения необходимости и успеха приложений для очистки данных. В Разделе 5 мы описываем различные этапы очистки данных. В разделе 6 перечислены и кратко описаны методы, используемые при очистке данных. В разделе 7 дается обзор и сравнение существующих проектов очистки данных в соответствии с нашей спецификацией комплексной очистки данных. Раздел 8 описывает существующие проблемы и открытые проблемы в области исследований очистки данных. Мы завершаем раздел 9.

2. Мотивация

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

Основная цель сбора и обработки данных - выполнение различных задач в (i) администрировании, например, отслеживание сотрудников компании, клиентов нашей компании или объем продаж филиалов нашей компании, (ii) поддержка бизнес-процесс, например, использование списка адресов клиентов для прямой рассылки с целью рекламы новых продуктов, и (iii) анализ и интерпретация для поддержки принятия решений и генерирования новой информации и знаний. Принятие решений в бизнесе и правительстве основано на анализе данных для выявления тенденций и отслеживания событий и инвестиций. Ученые анализируют данные, чтобы получить новую информацию и знания о разделе мира, который они исследуют.

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

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

Администрация: Правительство анализирует данные, полученные в результате переписи населения, чтобы решить, какие регионы страны требуют дополнительных инвестиций в инфраструктуру, например школы и другие образовательные учреждения, из-за ожидаемых будущих тенденций. Если уровень рождаемости в одном регионе увеличился за последние пару лет, существующих школ и учителей может не хватить, чтобы справиться с ожидаемым количеством учеников. Таким образом, потребуются дополнительные школы или найм учителей. Неточности в проанализированных данных могут привести к ложным выводам и неверно направленным инвестициям. В этом примере ошибочные данные могут привести к избытку или недостатку образовательных учреждений, если информация о рождаемости была неточной или если многие люди переехали в другие регионы.
Поддержка бизнес-процессов: ошибочные данные приводят к ненужным расходам и, возможно, к потере репутации при использовании для поддержки бизнес-процессов. Рассмотрим компанию, использующую список потребителей с их адресами, покупательскими привычками и предпочтениями для рекламы нового продукта посредством прямой рассылки. Недействительные адреса приводят к тому, что письма возвращаются как недоставленные. Люди, дублирующиеся в списке рассылки, составляют несколько писем, отправляемых одному и тому же человеку, что приводит к ненужным расходам и разочарованию. Неточная информация о покупательских привычках и предпочтениях потребителей загрязняет и фальсифицирует целевую группу, что приводит к рекламе продуктов, не соответствующих потребностям потребителей. Компании, торгующие такими данными, сталкиваются с возможностью дополнительной потери репутации в случае ошибочных данных.

Анализ: в исследовании генома функциональная аннотация белков используется для оценки функции не охарактеризованных белков путем сравнения их аминокислотных последовательностей и передачи функциональной аннотации в случае высокого сходства последовательностей. Таким образом, существующие ошибки в аннотациях распространяются на недавно обнаруженный белок. В [Bre99] частота ошибок для функциональной аннотации белков оценивается более чем в 8% при сравнении результатов анализа трех независимых исследовательских групп, аннотирующих протеом Mycoplasma genitalium. С увеличением зависимости от методов автоматического аннотирования из-за большого объема данных можно ожидать, что частота ошибок только возрастет.

3. Аномалии данных

Перед описанием и классификацией аномалий данных мы определяем термины и концепции, касающиеся схемы и экземпляров сбора данных. Здесь мы внимательно следуем определениям в [EN00] и расширяем их для наших нужд.

3.1 Модель данных

Мы предполагаем существование непустого множества D = {D1, ..., Dm} областей, значениями которых являются последовательности символов из конечного непустого алфавита £ D. Для каждой области Di, 1 <i <m, существует произвольная грамматика, описывающая синтаксис значений домена. Таким образом, домены представляют собой регулярные языки, то есть слова из ZD, порожденные грамматикой G(Di), называемой форматом домена.

Схема отношения R - это имя и список атрибутов A1, ..., An, обозначенный R(A1, ..., An). Степень #R схемы отношения R - это количество атрибутов n. Каждый атрибут A - это имя роли, которую играет некоторый домен из D, обозначенный dom(A) в схеме отношения. Отношение (или экземпляр отношения) r схемы отношения R представляет собой набор n-кратных кортежей r = {t1, ..., tn}. Каждый ti представляет собой список из n значений ti = <vi1, …, Vin>, где каждое значение vj 1 <j <n является элементом dom (Aj). Степень #t кортежа - это количество значений n. Набор значений для атрибута Aj, например r для R (A1,., An), обозначается val(r, Aj).

Схема базы данных S содержит набор реляционных схем {R1,., Rk} и набор ограничений целостности r, которые должны выполняться для каждого экземпляра S = ({R1, ..., Rk}, T). Экземпляр s схемы базы данных - это список экземпляров отношения, обозначенный s = <r1,., Rk>, где каждый экземпляр ri, 1 <i <k, является экземпляром реляционной схемы Ri, удовлетворяющим ограничениям в r . Каждое ограничение целостности y e r - это функция, которая связывает логическое значение с экземпляром s. Экземпляр базы данных s удовлетворяет y, если y(s) = true. Мы называем экземпляр базы данных сбором данных, если схема и ограничения целостности не полностью выполняются программными компонентами, называемыми системой управления базой данных.

3.2. Классификация аномалий данных

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

3.2.1 Синтаксические аномалии

Лексическими ошибками называются несоответствия между структурой элементов данных и заданным форматом. Это тот случай, если количество значений неожиданно низкое / высокое для кортежа t, то есть степень кортежа #t отличается от #R, степени ожидаемой схемы отношения для кортежа. Например, предположим, что данные хранятся в виде таблицы, где каждая строка представляет кортеж, а каждый столбец - атрибут (рисунок 1). Если мы ожидаем, что таблица будет иметь пять столбцов, потому что каждый кортеж имеет пять атрибутов, но некоторые или все строки содержат только четыре столбца, то фактическая структура данных не соответствует указанному формату. Лексически правильные данные могут быть проанализированы в указанную структуру токена, выводимую из реляционной схемы.

Рисунок 1: Таблица данных с лексическими ошибками

Ошибки формата домена определяют ошибки, когда заданное значение атрибута A не соответствует с ожидаемым форматом домена G (dom (A)). Например, атрибут NAME может есть домен, указанный как ΣD *, ΣD *. Учитывая конкретное значение «Джон Смит», в то время как это возможно правильное имя, оно не соответствует определенному формату значений домена из-за пропущенная запятая между словами.

Ошибки формата домена определяют ошибки, когда заданное значение атрибута A не соответствует ожидаемому формату домена G (dom (A)). Например, для атрибута NAME может быть указан домен ZD, ZD. Учитывая конкретное значение «Джон Смит», хотя это, возможно, правильное имя, оно не удовлетворяет заданному формату значений домена из-за отсутствия запятой между словами.

Лексические ошибки классов аномалий и ошибки формата домена часто подпадают под термин синтаксическая ошибка, поскольку они представляют собой нарушения общего формата.

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

3.2.2 Семантические аномалии

Нарушения ограничения целостности описывают кортежи (или наборы кортежей), которые не удовлетворяют одному или нескольким ограничениям целостности в r. Ограничения целостности используются для описания нашего понимания мини-мира путем ограничения набора допустимых экземпляров. Каждое ограничение - это правило, представляющее знания о предметной области и значениях, разрешенных для представления определенных фактов, например, ВОЗРАСТ> 0.

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

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

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

3.2.3 Аномалии покрытия

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

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

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

4. Очистка данных и качество данных

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

4.1. Качество данных

Чтобы данные можно было обрабатывать и интерпретировать эффективным и действенным образом, они должны удовлетворять набору критериев качества. Данные, удовлетворяющие этим критериям качества, считаются высококачественными. В общем, качество данных1 определяется как агрегированное значение по набору критериев качества [Nau02]. Начиная с критериев качества, определенных в [Nau02, Ton00], мы описываем набор критериев, на которые влияет комплексная очистка данных, и определяем, как оценивать баллы по каждому из них для существующей коллекции данных.

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

Рисунок 2: Иерархия критериев качества данных

4.2. Критерии качества

Критерии качества, определенные для комплексной очистки данных, образуют иерархию. Эта иерархия является результатом разделения критериев качества на более мелкие критерии качества, т. Е. Критерии, используемые в качестве кратчайшего пути для набора критериев качества. На рисунке 2 показана итоговая иерархия критериев, определенных ниже. Для каждого из критериев мы описываем, как оценить показатель качества для данной коллекции данных. Здесь мы предполагаем, что каждый набор состоит только из одного реляционного экземпляра, то есть S = ({R}, F) и, следовательно, s = r. Мы не предполагаем соблюдения ограничений целостности на r, т.е. не каждое ограничение y e r истинно для всех кортежей в r. Набор сущностей в мини-мире обозначен буквой M. На оценку каждого критерия качества влияет одна или несколько аномалий, определенных в разделе 3.2. В таблице 1 мы показываем критерии качества и аномалии, влияющие на них.

Точность в [Nau02] определяется как отношение количества правильных значений в сборе данных к общему количеству значений. Здесь мы используем термин «точность» по-другому.

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

Точность описывается как агрегированное значение по критериям качества «Целостность», «Последовательность» и «Плотность». Интуитивно это описывает точное, единообразное и полное представление мини-мира, то есть сбор данных, не содержащий каких-либо определенных аномалий, кроме Дубликатов. Мы определяем критерии качества «Целостность», «Последовательность» и «Плотность» следующим образом.

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

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

Достоверность - это отношение сущностей из M, представленных кортежами в r, и общего количества кортежей в r, т.е. Процент кортежей в r, представляющих (действительные) сущности из M. Как упоминалось в разделе 3.2.2, идентификация недействительных Кортежи сложны, а иногда и невозможны из-за невозможности или высокой стоимости повторных измерений для проверки правильности измеренного значения. Достоверность может быть приблизительно определена с использованием ограничений целостности, указанных в r. Ограничения целостности отражают наше понимание закономерностей мини-мира. Поэтому кортежи, нарушающие ограничения целостности, считаются недопустимыми. Нарушения ограничений возникают в системах, которые не обеспечивают полное соблюдение ограничений целостности. Это может быть из-за системных ограничений или по требованию пользователя, возможно, из-за проблем с производительностью. Мы аппроксимируем достоверность как отношение кортежей, удовлетворяющих всем ограничениям целостности в r, и общего количества кортежей в r.

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

Соответствие схеме - это отношение кортежей в r, соответствующих синтаксической структуре, определенной схемой R, и общему количеству кортежей в r. Это включает в себя форматы домена G (dom (Ai)) атрибутов Ai, ... An в R. Некоторые системы не обеспечивают полную синтаксическую структуру, что позволяет использовать кортежи в коллекции, которые не полностью соответствуют формату. Это особенно верно для систем реляционных баз данных, где соблюдение форматов доменов является обязанностью пользователя.

Однородность напрямую связана с неоднородностями, то есть с правильным использованием значений в каждом атрибуте. Семантика и использование значений должны быть единообразными в пределах val (r, Ai) для каждого Ai в R. Однородность - это отношение атрибутов, не содержащих отклонений в их значениях, и n, общего количества атрибутов в r.

Плотность - это отношение отсутствующих значений в кортежах r и общего количества значений, которые должны быть известны, поскольку они существуют для представленного объекта. По-прежнему могут существовать несуществующие значения или свойства, которые должны быть представлены нулевыми значениями, имеющими точное значение «неизвестность». Это не ухудшение качества данных. Если мы попытаемся оценить их ценность, это будет означать снижение рейтинга.

Уникальность - это отношение кортежей, представляющих одну и ту же сущность в мини-мире, к общему количеству кортежей в r. Уникальная коллекция не содержит дубликатов. Ссылаясь на определение точности как на коллекцию, не содержащую никаких аномалий, кроме дубликатов, сбор данных, являющийся точным и уникальным, не содержит никаких аномалий, определенных в разделе 3. Это описывает сбор данных, который не нуждается в очистке данных.

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

Таблица 1. Аномалии данных, влияющие на критерии качества данных

5. Перспективы процесса очистки данных

Комплексная очистка данных определяется как совокупность операций, выполняемых с существующими данными для удаления аномалий и получения сбора данных, являющегося точным и уникальным представлением мини-мира. Это (полу) автоматический процесс операций, выполняемых с данными, которые выполняют, предпочтительно в этом порядке, (i) адаптацию формата для кортежей и значений, (ii) обеспечение соблюдения ограничений целостности, (iii) вывод отсутствующих значений из существующих, (iv) устранение противоречий внутри или между кортежами, (v) слияние и удаление дубликатов и (vi) обнаружение выбросов, т. е. кортежей и значений, имеющих высокий потенциал недействительности. Очистка данных может включать в себя структурное преобразование, то есть преобразование данных в формат, который лучше поддается управлению или лучше подходит для мини-мира. Однако качество схемы не является прямым вопросом очистки данных и, следовательно, не входит в список критериев качества, определенных выше. Более подробно методы очистки данных мы перечислим в разделе 6.

Согласно [MM00, RH01], процесс очистки данных включает три основных этапа (i) аудит данных для определения типов аномалий, снижающих качество данных, (ii) выбор подходящих методов для их автоматического обнаружения и удаления и (iii) ), применяя методы к кортежам в сборе данных. Шаги (ii) и (iii) можно рассматривать как спецификацию и выполнение рабочего процесса очистки данных. Мы добавляем еще одну задачу (iv), этап постобработки или контроля, на котором мы проверяем результаты и выполняем обработку исключений для кортежей, не исправленных в фактическая обработка. На рисунке 3 показаны этапы процесса очистки данных. Спецификация процесса очистки данных и контроль его выполнения осуществляется одним или несколькими экспертами в предметной области, то есть экспертами со знаниями о мини-мире, его закономерностях и особенностях.

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

Рисунок 3: Процесс очистки данных

5.1. Аудит данных

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

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

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

5.2. Спецификация рабочего процесса

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

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

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

В [RD00] после определения рабочего процесса очистки и перед его выполнением определяется следующий шаг - проверка. Здесь проверяется и оценивается правильность и эффективность рабочего процесса. Мы предполагаем, что этот этап проверки является неотъемлемой частью спецификации рабочего процесса.

5.3 Выполнение рабочего процесса

Рабочий процесс очистки данных выполняется после уточнения и проверки правильности. Реализация должна обеспечивать эффективную работу даже с большими наборами данных. Это часто является компромиссом, потому что выполнение операции очистки данных может потребовать значительных вычислительных ресурсов, особенно если требуется полное и 100% полное устранение аномалий. Поэтому нам нужна эвристика, чтобы достичь максимальной точности, сохраняя при этом приемлемую скорость выполнения [GFSSS01b].

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

5.4. Постобработка и контроль

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

6. Методы, используемые для очистки данных

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

6.1. Парсинг

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

Наличие и количество синтаксических ошибок в сборе данных зависит от степени применения схемы в среде, в которой хранятся данные. Если данные содержатся в плоских файлах, существует вероятность лексических ошибок и ошибок домена. В этом случае используется грамматика, полученная из файловой структуры, а строки представляют собой полные кортежи. Ожидается, что данные, управляемые системами управления базами данных, не будут содержать лексических или доменных ошибок. Тем не менее, ошибки формата домена могут существовать для каждого из атрибутов. Грамматика, используемая для синтаксического анализа, - это формат домена G(A). Спецификация форматов предметной области может поддерживаться методами изучения шаблонов, подобными описанным в [RH01]. Они используют примерный набор значений, чтобы определить формат домена. Они также генерируют детектор несоответствия, который используется для обнаружения аномалий.

6.2. Преобразование данных

Преобразование данных предназначено для преобразования данных из заданного формата в формат, ожидаемый приложением [ACMM + 99]. Преобразования влияют на схему кортежей, а также на области их значений. Преобразование схемы часто выполняется одновременно с очисткой данных. Данные из различных источников отображаются в общую схему, которая лучше соответствует потребностям предполагаемого приложения. Корректировку значений необходимо производить только в тех случаях, когда входные данные не соответствуют его схеме, что приводит к сбоям в процессе преобразования. Это делает очистку данных и преобразование схемы дополнительными задачами.

Стандартизация и нормализация - это преобразования на уровне экземпляра, используемые с целью удаления несоответствий в данных. Это включает в себя простые функции преобразования или преобразования значений, а также нормализацию числовых значений, чтобы они лежали в фиксированном интервале, заданном минимальным и максимальным значениями [SS01].

6.3 Обеспечение соблюдения ограничений целостности

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

В [EBRS + 01] показано, что применение ограничений целостности в некоторой степени применимо к очистке данных, но также имеет некоторые ограничения. Основная идея состоит в том, чтобы автоматически идентифицировать из набора ограничений целостности серию модификаций и применять их к сбору данных, чтобы впоследствии коллекция не содержала никаких дальнейших нарушений ограничений целостности. Авторы описывают некоторые ограничения применения этих методов для очистки данных (или согласования данных, как они это называют). Основное ограничение основано на том факте, что методы обеспечения целостности работают с действительными состояниями базы данных и отдельными транзакциями, нарушая некоторые ограничения. При очистке данных у нас есть большой объем данных и нарушений ограничений и, следовательно, большое пространство поиска, соответственно еще больший объем исправлений (потому что мы могли бы сначала восстановить кортеж 1, а затем на основе этого кортежа 2 или наоборот, что привело бы к другим результатам). Кроме того, сгенерированные ремонты в первую очередь сосредоточены на вставке или удаление кортежей вместо исправления отдельных значений для устранения нарушений ограничений. Другая проблема основана на том факте, что существующие подходы используют стратегии для ограничения набора возможных ремонтов. Показано, что эти стратегии устраняют важные ремонты с точки зрения их области применения.

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

6.4. Удаление дубликатов

Существует несколько подходов к удалению дубликатов или связыванию записей, что является частью очистки данных. Каждый предложенный метод обнаружения дублирования требует алгоритма для определения того, являются ли два или более кортежа дублированными представлениями одного и того же объекта. Для эффективного обнаружения дублирования каждый кортеж должен сравниваться с любым другим кортежем с использованием этого метода обнаружения дублирования. В [HS95] разработан быстрый метод (метод отсортированной окрестности) для уменьшения количества требуемых сравнений. Кортежи сортируются по ключу, возможно, созданному из атрибутов отношения, что, как мы надеемся, сближает повторяющиеся кортежи с другими. Затем только кортежи в небольшом окне (плавающем над отношением) сравниваются друг с другом для поиска дубликатов. Идентификация того, являются ли два кортежа дубликатами, выполняется с помощью правил, основанных на знании предметной области. Для повышения точности результаты нескольких проходов обнаружения дубликатов могут быть объединены путем явного вычисления транзитивного замыкания всех обнаруженных попарно повторяющихся кортежей. О том, как объединяются дубликаты, сказано не так много. В [LLLK99] этот подход дополнительно расширен на кортежи с синтаксически структурированными атрибутами, то есть не соответствующими формату домена. Из-за ошибок формата повторяющиеся кортежи могут не располагаться близко друг к другу после сортировки. Следовательно, значения атрибутов токенизируются в лексические единицы, а затем токены сортируются внутри каждого атрибута перед сортировкой всего отношения. Алгоритмы попарного сопоставления кортежей, использованные в большинстве предыдущих работ, были специфичными для приложения. В [ME97] используется независимый от предметной области алгоритм сопоставления, который может использоваться без каких-либо изменений в различных приложениях. Поэтому используется алгоритм расстояния редактирования, основанный на алгоритме Смита-Уотермана [SM81]. В [ACG02] авторы предлагают подход, позволяющий избежать проблем, связанных с методами сортировки. Они полагаются на иерархии измерений, обычно связанные с таблицами измерений в хранилище данных [ACG02]. Это иерархии таблиц, обычно в отношениях 1: n, выраженные отношениями ключ-внешний ключ. Каждый кортеж в 1-отношении связан с набором кортежей в n-отношении. Степень перекрытия между наборами, связанными с двумя кортежами из отношения 1, является мерой совместной встречаемости между ними и может использоваться для обнаружения дубликатов.

6.5. Статистические методы

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

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

Еще одна аномалия, которую обрабатывают статистические методы, - это пропущенные значения. Пропущенные значения обрабатываются на основе заполнения (подстановки) одного или нескольких правдоподобных значений [Win99]. Генерация вменений требует вычислительно-интенсивных алгоритмов увеличения данных, как описано в [Sch97, Tan96].

7. Существующие подходы к очистке данных

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

7.1. AJAX

AJAX [GFSS00, GFSSS01b] - это расширяемая и гибкая структура, пытающаяся разделить логический и физический уровни очистки данных. Логический уровень поддерживает структуру рабочего процесса очистки данных и спецификацию выполняемых операций очистки, а физический уровень касается их реализации. Основная проблема AJAX - преобразование существующих данных из одной или нескольких коллекций данных в целевую схему и устранение дубликатов в этом процессе. Для этого определен декларативный язык, основанный на наборе из пяти операций преобразования. Преобразования - это отображение, просмотр, сопоставление, кластеризация и слияние.

Оператор сопоставления выражает произвольные сопоставления «один ко многим» между одним входным отношением и одним или несколькими выходными отношениями. Оператор представления эквивалентен оператору представления в SQL, просто выражая ограниченные сопоставления «многие-к-одному» с некоторой дополнительной проверкой целостности. Оператор сопоставления вычисляет приблизительное соединение между двумя отношениями, присваивая значение расстояния каждой паре в декартовом произведении с использованием произвольной функции расстояния.

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

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

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

7.2. FraQL

FraQL [SCS00, SS01] - еще один декларативный язык, поддерживающий спецификацию процесса очистки данных. Этот язык является расширением SQL на основе объектно-реляционной модели данных. Он поддерживает спецификацию преобразований схемы, а также преобразования данных на уровне экземпляра, то есть стандартизацию и нормализацию значений. Это можно сделать с помощью пользовательских функций. Реализация определяемой пользователем функции должна выполняться в соответствии с требованиями домена в рамках индивидуального процесса очистки данных.

Благодаря расширенным операторам соединения и объединения в сочетании с определяемыми пользователем функциями согласования FraQL поддерживает идентификацию и устранение дубликатов. Подобно SQL, операторы объединения и объединения могут быть уточнены предложением on, указав атрибуты сравнения (для оператора объединения) соответственно. выражение сравнения (для операторов соединения). Операторы объединения и объединения могут применяться с дополнительным условием согласования по, которое обозначает используемую определенную функцию для разрешения противоречий между кортежами, выполняющими предложение сравнения.

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

7.3. Potter’s Wheel

Potter’s Wheel [RH01] - это интерактивная система очистки данных, которая объединяет преобразование данных и обнаружение ошибок с использованием интерфейса, подобного электронным таблицам. Эффект от выполненных операций сразу отображается на кортежах, видимых на экране. Обнаружение ошибок для всего сбора данных выполняется автоматически в фоновом режиме. Определен набор операций, называемых преобразованиями, которые поддерживают преобразования общей схемы без явного программирования. Это преобразования значений, которые применяют функцию к каждому значению в столбце, сопоставления «один-к-одному», которые представляют собой операции столбца, преобразующие отдельные строки, и сопоставления строк «многие-ко-многим», решающие схематические неоднородности, где информация хранится частично в значениях данных, и частично в схеме. Аномалии, устраняемые этим подходом - это синтаксические ошибки и нарушения.

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

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

7.4. ARKTOS

ARKTOS [VVSKS01] - это фреймворк, способный моделировать и выполнять процесс ExtractionTransformation-Load (процесс ETL) для создания хранилища данных. Авторы рассматривают очистку данных как неотъемлемую часть этого процесса ETL, который состоит из отдельных шагов, которые извлекают соответствующие данные из источников, преобразуют их в целевой формат и очищают их, а затем загружают в хранилище данных. Указана метамодель, позволяющая моделировать весь процесс ETL. Отдельные шаги (операции очистки) внутри процесса называются действиями. Каждое действие связано с отношениями ввода и вывода. Логика, выполняемая действием, декларативно описывается SQL-оператором. Каждый оператор связан с определенным типом ошибки и политикой, которая определяет поведение (действие, которое необходимо выполнить) в случае возникновения ошибки.

В рамках процесса ETL, указанного и выполняемого в среде ARKTOS, можно рассматривать шесть типов ошибок. НАРУШЕНИЕ ПЕРВИЧНОГО КЛЮЧА, НАРУШЕНИЕ УНИКАЛЬНОСТИ и НАРУШЕНИЕ ССЫЛКИ - это особые случаи нарушения ограничений целостности. Тип ошибки NULL EXISTENCE связан с устранением пропущенных значений. Остальные типы ошибок - это DOMAIN MISMATCH и FORMAT MISMATCH, относящиеся к лексическим ошибкам и ошибкам формата домена.

Политики исправления ошибок - просто ИГНОРИРОВАТЬ, но без явной пометки ошибочного кортежа, УДАЛИТЬ, а также ЗАПИСАТЬ В ФАЙЛ и ВСТАВИТЬ В ТАБЛИЦУ с ожидаемой семантикой. Последние два предоставляют единственную возможность взаимодействия с пользователем.

Успех очистки данных можно измерить для каждого действия, выполнив аналогичный оператор SQL, подсчитывая совпадающие / нарушающие кортежи. Авторы определяют два языка для декларативного описания процесса ETL. Это сопровождается графическим построителем сценариев.

7.5. IntelliClean

IntelliClean [LLL00, LLL01] - это основанный на правилах подход к очистке данных с основным упором на устранение дубликатов. Предлагаемая структура состоит из трех этапов. На этапе предварительной обработки устраняются синтаксические ошибки, а значения стандартизируются по формату и последовательности используемых сокращений. Подробно не уточняется, как это делается. Этап обработки представляет собой оценку правил очистки для условных элементов данных, которые определяют действия, которые необходимо предпринять при определенных обстоятельствах. Есть четыре разных класса правил. Правила идентификации дубликатов определяют условия, при которых кортежи классифицируются как дубликаты. Правила слияния / очистки определяют, как следует обрабатывать повторяющиеся кортежи. Не указано, как должно выполняться слияние или как его функциональность может быть объявлена. Если правило слияния / очистки не указано, повторяющиеся кортежи также можно объединить вручную на следующем этапе. Правила обновления определяют способ обновления данных в конкретной ситуации. Это позволяет специфицировать правила применения ограничений целостности. Для каждого ограничения целостности правило обновления определяет, как изменить кортеж, чтобы удовлетворить ограничению. Правила обновления также можно использовать, чтобы указать, как должны быть заполнены отсутствующие значения. Правила предупреждений определяют условия, при которых пользователь получает уведомление о разрешении определенных действий.

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

7.6. Сравнение

В таблице 2 сравниваются описанные подходы к очистке данных в соответствии с типами обрабатываемых ими аномалий и кратким указанием используемых методов и приемов, как определено каждым из них. Термин «Определяется пользователем» означает, что обнаружение и устранение конкретной аномалии возможно, но не уточняется подробно.

Таблица 2. Сравнение подходов к очистке данных

8. Вызовы и открытые проблемы

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

8.1. Исправление ошибок и разрешение конфликтов

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

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

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

8.2. Ведение очищенных данных

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

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

8.3. Очистка данных в виртуально интегрированных средах

Проблемы, упомянутые в предыдущем разделе, усиливаются при выполнении очистки данных в средах с виртуально интегрированными источниками, такими как IBM DiscoveryLink [HSKK + 01]. В таких средах часто невозможно вносить поправки в источники из-за их автономности. Следовательно, очистка данных должна выполняться каждый раз при доступе к данным. Это значительно сокращает время отклика. Путем сбора и управления соответствующими метаданными, такими как очистка происхождения и выполняемых операций в промежуточном программном обеспечении для очистки данных, производительность может быть значительно увеличена. Это также может предотвратить ненужную очистку данных, если данные в источниках не меняются между обращениями к источникам. По-прежнему остается выбор между сбором огромных объемов метаданных и материализацией полного интегрированного сбора данных. Промежуточное ПО должно собирать столько данных, сколько необходимо, но при этом обеспечивать быструю очистку данных.

8.4. Структура очистки данных

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

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

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

9. Заключение

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

Literature

[ACG02] R. Ananthakrishna, S. Chaudhuri, V. Ganti Eliminating Fuzzy Duplicates in Data Warehouses.Proceedings of the 28^th VLDB Conference, Hong Kong, China, 2002

[ACMM+99] S. Abiteboul, S. Cluet, T. Milo, P. Mogilevsky, J, Simeon, S. Zohar Tools for Data Translation and Integration. Bulletin of the Technical Committee on Data Engineering, March 1999, Vol. 22, No. 1, 3-8

[AIS93] R. Agrawal, T. Imielinski, A. Swami Mining Association Rules between Sets of Items in Large Databases.Proceedings of the ACM SIGMOD on Management of Data, 1993, 207-216

[AU79] A.V. Aho, J.D. Ullman Principles of Compiler Design. Addison-Wesley Publishing Company, 1979, ISBN 0-201-00022-9

[Bre99] S. E. Brenner Errors in genome annotation Trends in Genetics, 1999, 15, 4, 132-133

[EBRS+01] S. M. Embury, S. M. Brand, J. S. Robinson, I. Sutherland, F. A. Bisby, W.
A. Gray, A. C. Jones, R. J. White Adapting integrity enforcement techniques for data reconciliation Information Systems, Vol. 26, 2001, 657-68

[EN00] R. Elmasri, S.B. Navathe, Fundamentals of Database Systems. Addison Wesley Pub Co., ISBN 0201542633

[Eng00] L. P. English Plain English on Data Quality: Information Quality Management: The Next Frontier. Published in DM Review in April 2000

[GFSS00] H. Galhardas, D. Florescu, D. Shasha, E. Simon AJAX: An extensible data cleaning tool. Proceedings of the ACM SIGMOD on Management of data, Dallas, TX USA, May 2000

[GFSSSOla] H. Galhardas, D. Florescu, D. Shasha, E. Simon, C.-A. Saita
Improving data cleaning quality using a data lineage facility. Proceedings of the 3rd International Workshop on Design and Management of Data Warehouses, Interlaken, Switzerland, June 2001

[GFSSS01b] H. Galhardas, D. Florescu, D. Shasha, E. Simon, C.-A. Saita Declarative data cleaning: Language, model, and algorithms.Proceedings of the 27th VLDB Conference, Roma, Italy, 2001

[HS95] M. A. Hernandez, S.J. Stolfo The merge/purge problem for large databases. Proceedings of the ACM SIGMOD Conference, 1995

[HSKK+01] L.M. Haas, P.M. Schwarz, P. Kodali, E. Kotlar, J.E. Rice, W.C. Swope DiscoveryLink: A system for integrated access to life sciences data sources. IBM Systems Journal, 2001, Vol. 40, No. 2, 489-511

[LLLK99] Mong Li Lee, Hongjun Lu, Tok Wang Ling, Yee Teng Ko Cleansing data for mining and warehousing. Proceedings of the 10th International Conference on Database and Expert Systems Applications, Florence, Italy, August 1999

[LLL00] Mong Li Lee, Tok Wang Ling, Wai Lup Low IntelliClean: A knowledge-based intelligent data cleaner. Proceedings of the ACM SIGKDD, Boston, USA, 2000

[LLL01] Wai Lup Low, Mong Li Lee and Tok Wang Ling A knowledge-based approach for duplicate elimination in data cleaning Information Systems, Vol. 26, 2001, 585-606

[ME97] A.E. Monge, C.P. Elkan An efficient domain-independent algorithm for detecting approximately duplicate database tuples. Proceedings of the SIGMOD 1997 workshop on data mining and knowledge discovery, 1997

[MM00] J.I. Maletic, A. Marcus Data Cleansing: Beyond Integrity Analysis. Proceedings of the Conference on Information Quality, October 2000

[Mot89] A. Motro Integrity = Validity + Completeness. ACM Transactions on Database Systems (TODS), Vol. 14, No. 4, 1989, 480-502

[MT99] Enric Mayol, Ernest Teniente A Survey of Current Methods for Integrity Constraint Maintenance and View Updating. ER Workshops 1999: 62-73

[Nau02] F. Naumann Quality-Driven Query Answering for Integrated Information Systems Lecture Notes in Computer Science, LNCS 2261, Springer, 2002

[Orr98] K. Orr Data Quality and Systems Theory. Communications of the ACM, Vol. 41, No. 2, 1998, 66-71

[RD00] E. Rahm, Hong Hai Do Data Cleaning: Problems and current approaches. IEEE Bulletin of the Technical Committee on Data Engineering, 2000, 24, 4

[Red98] T. Redman The impact of Poor Data Quality on the Typical Enterprise. Communications of the ACM, Vol. 41, No. 2, 1998, 79-82

[RH01] V. Raman, J.M. Hellerstein Potter’s Wheel: An Interactive Framework for Data Transformation and Cleaning. Proceedings of the 27th VLDB Conference, Roma, Italy, 2001

[Sch97] J. L. Schafer Analysis of Incomplete Multivariate Data. Chapmann & Hall, London, 199

[SCS00] K. -U. Sattler, S. Conrad, G. Saake Adding Conflict Resolution Features to a Query Language for Database Federations. Proc. 3nd Int. Workshop on Engineering Federated Information Systems, Dublin, Ireland, 2000

[SS01] K.-U. Sattler, E. Schallehn A Data Preparation Framework based on a Multidatabase Language. International Database Engineering Applications Symposium (IDEAS), Grenoble, France, 2001

[SW81] T.F. Smith, M.S. Watermann Identification of common molecular subsequences. Journal of Molecular Biology, Vol. 147, 1981, 195-197

[Tan96] M.A. Tanner Tools for Statistical Inference (third edition). Springer, New York, 1

[Ton00] D. Tonn Data Cleansing Verfahren fur Data Warehouses. Diploma Thesis, Humboldt University Berlin, 2000

[VVSKS01] P. Vassiliadis, Z.a Vagena, S. Skiadopoulos, N. Karayannidis, T. Sellis ARKTOS: towards the modeling, design, control and execution of ETL processes Information Systems, Vol. 26, 2001, 537-561

[Win99] W. E. Winkler State of Statistical Data Editing and Current Research Problems. UN/ECE Work Session on Stat. Data Editing, Rome, Italy, 1999