Использование алгоритма Fuzzy Match для очистки данных
1 Использует алгоритм Fuzzy Match для очистки данных Ing. Давид Пейчоч, DS. Секция автострахования, Kooperatva, pojšťovna, a.s., Venna Insurance Group, Templová 747, Прага 1, Чешская Республика Департамент информации и инженерных знаний, FIS-VŠE Прага. Опубликовано: Аннотация С огромным увеличением объема обрабатываемых данных в компаниях мы все чаще сталкиваемся с проблемой качества данных. Разреженность данных влечет за собой как экономические, так и аналитические последствия. В некоторых случаях, таких как военная логистика или космическая программа, отсутствие данных даже решает вопрос о жизни или смерти отдельных лиц и их групп. В рамках процесса очистки данных может быть определен этап стандартизации, на котором текущие данные сравниваются с эталонными данными и, при наличии достаточного совпадения, заменяются эталонными данными. Для этой цели классический подход, основанный только на абсолютном совпадении с использованием SQL JOIN, в большинстве случаев оказывается недостаточным. Поэтому необходимо использовать теорию нечеткого логарифма и использовать подход под названием Fuzzy Match. Этот подход оценивает степень соответствия между сравниваемым и эталонным набором с помощью так называемой функции smlarty. Записи с функцией smlarty выше установленного порога затем автоматически объединяются. Другие случаи с оценкой ниже порогового значения могут быть оценены двояко с точки зрения слияния. Ключевые слова Качество данных, нечеткое совпадение, частота данных, нечеткий журнал. Введение в проблему качества данных и частоты данных Во введении считаю целесообразным кратко упомянуть проблему качества данных, описать процесс качества данных и определить функцию Fuzzy Merge на ее конкретном шаге. Качество данных Проблема качества данных (англ. Data Quality) и вытекающая из нее проблема качества информации (англ. Informaton Quality), особенно в связи с огромным увеличением объема обрабатываемых данных в компаниях, достиглав последнее десятилетие на первый план. Компании впервые поняли, что данные для них в век информации означают очень ценный актив 1, эффективное оружие в борьбе за удержание и приобретение новых клиентов. С растущим осознанием важности собственных данных роль качества данных перешла от приоритета к необходимости. Любой, кто расстраивает своих клиентов, неоднократно связываясь с ними в маркетинговых кампаниях благодаря дублирующимся записям в данных клиентов, рано или поздно потеряет этих клиентов. Тот, кто присылает своим клиентам постоянно неправильно заполненные счета-фактуры, закончит тем же. На следующем этапе компании начали понимать, что ретроактивный подход к качеству данных с использованием разовых частых действий с данными становится неэффективным, если он не отражается на изменении бизнес-процессов, в рамках которых происходят эти нарушения. В то же время компании начали осознавать необходимость интеграции часто встречающихся данных в рамках различных источников данных. Они начали говорить об одном представлении о клиенте (или продукте) и использовать такие термины, как управление мастер-данными (MDM) или интеграция данных о клиенте (CDI) 2. В связи с качеством данных фактически (например, [2]) они говорить о характеристиках данных, таких как точность, объективность, достоверность, репутация, доступность, безопасность доступа, актуальность, полезность данных, своевременность, полнота, объем, интероперабельность, понятность, краткое и лаконичное представление, последовательное представление и т. д. Уже с первого взгляда ясно, что часть этих свойств данных поддается численному измерению (речь идет о так называемых объективных метриках), а часть этих свойств представляет собой 1 E.g. [10] утверждает, что если информация является валютой новой экономики, то данные являются сырьем, необходимым для успеха. 2 Согласно [9], CDI представляет собой набор процессов, правил, механизмов и навыков, необходимых для стандартизации и интеграции данных о клиентах, поступающих из разных источников. MDM в основном одинаков во всех предметных областях компании.1
2 субъективных показателя, которые с трудом поддаются количественной оценке (например, [3]). В связи с нечетким слиянием эта работа направлена на обеспечение таких свойств данных, как точность, полнота и непротиворечивое представление, то есть свойств, которые можно измерить с помощью объективных показателей. Процесс качества данных (DQ) В этой части работы я хотел бы упомянуть в качестве примера процесса DQ процесс, используемый для нужд CDI (Customer Data Integraton), как указано в [9] и определенный в нем Функция нечеткого совпадения. Цель CDI — создать единую базу данных о клиентах, т.е. источник единой правды о клиентах. По этой причине эта концепция процесса DQ включает в себя шаг, описывающий определение предполагаемой результирующей структуры данных этой единой базы данных, так называемого Data Customer Hub. Я упоминаю этот ордер процесса DQ из-за его большей наглядности, которая отличается, например, от довольно сложного процесса TQdM (Total Quality data Management) гуру DQ Ларри Энглша, представленного в [12]. Как и многие другие процессы (например, различные варианты процесса KDD 3), процесс DQ характеризуется цикличностью, что указывает на то, что он не является разовым шагом. Диаграмма процесса качества данных для профилирования данных CDI (профилирование данных) Этот шаг включает в себя изучение структуры данных. Сначала данные проверяются с точки зрения их соответствия метаданным (с точки зрения типа данных, длины атрибута, уникальности данных и отсутствующих значений). Кроме того, проверяется, соответствует ли структура отдельных атрибутов их предположениям, т. е. соответствует ли содержание атрибута, который должен содержать номер рождения, правилам для номера рождения (модульная проверка, проверка действительных ордеров на зачисление). . На следующем шаге рассчитываются описательные статистики и на их основе выявляются выбросы, которые представляют собой потенциальных кандидатов на ошибочные значения. Стандартизация В рамках стандартизации выполняется парсинг данных, т.е. разделениестрок, содержащихся в отдельных атрибутах, на их часть. Например. содержимое атрибута адреса делится на название улицы, номер ориентации и описательный номер, содержимое атрибута имени делится на заголовок, имя и фамилию. Кроме того, осуществляется семантическое сопоставление различных вариантов слов, возникших, например, в рамках разных диалектов, а также сравнение и сопоставление форматов с существующими стандартами 4. Развертывание защиты Сравнение и слияние Сравнение и слияние МОНИТОРИНГ Локализация Теперь мы получаем к фазам процесса DQ, в которых находит свое применение техника Fuzzy Match. Целью этого этапа является устранение дубликатов и возможное объединение дубликатов в итоговую лучшую версию записи. В случае CDI это также включает определение домохозяйств. Стандартизация Профилирование данных Источник: перерисовано в соответствии со схемой DQ, представленной в [9] Определение На этом этапе процесса DQ происходит определение результирующей базы данных, формулировка требований к содержанию данных с точки зрения бизнеса, требований к форматам, представляющим это содержание и связь исходных данных с другим содержанием данных. Локализация На этапе локализации собирается информация о доступных источниках данных и последующем управлении ими. Поиск эталонных наборов данных является важным шагом здесь. Развертывание В описании процесса DQ, приведенном в [9], эта фаза процесса снова помечена как специфичная для CDI и представляет собой передачу результирующего набора данных в Customer Data Hub. В обычном проекте DQ этот шаг будет означать возврат очищенных данных в исходную систему или исправить данные в исходном файле для данных mng. Монтаж Данные Kvaltu должны, конечно, постоянно монтироваться. И это на всех этапах процесса DQ. В частности, необходимо отслеживать улучшение качества данных, чтобы определить рентабельность инвестиций в проекты DQ. 3 Обнаружение знаний n Базы данных 4 Большое количество инструментов качества данных позволяет нам сравнивать со стандартом написанияадреса, определенные США Почтовая служба и другие почтовые стандарты 2
3 Ошибка классического SQL JOIN и LOOKUP Использование классического SQL JOIN на этапах сравнения и слияния, как правило, возможно только в том случае, если ключ сравнения полностью совпадает. Таким случаем является, например, ион через номер социального страхования или номер социального страхования в том случае, если этот атрибут содержит только поддельные действительные значения 5. Пример ситуации, когда классический SQL JOIN как метод сравнения и слияния выборки данных со справочными данными недостаточно, дается, например, Чарльзом Патриджем 6 в [13]. Описывает ситуацию, когда программистам было дано указание объединить список потенциальных клиентов со списком существующих клиентов. Цель состояла в том, чтобы выявить из списка потенциальных сотрудников тех сотрудников, которые уже являются сотрудниками компании в данный момент. Набор данных потенциальных клиентов не имел уникального ключа. Программист попытался связать его с помощью комбинации почтового индекса и имени клиента. Однако результаты оказались плачевными. Используя слияние (эквивалент шага данных SAS), программистам удалось объединить только 21% записей, в то время как помощник менеджера, который попытался сделать то же самое путем ручного сравнения, смог проверить первые 100 записей за то же время (т. весь список был порядка сотен записей). Причина отказа приложения SQL JOIN заключалась в разных ордерах на запись содержимого атрибута имени клиента и почтового индекса в сравниваемом и справочном файле (см. ниже). Аналогичные проблемы возникают при использовании LOOKUP, независимо от того, как он реализован (в SAS, например, с помощью формата или загрузки справочной таблицы в память с помощью хеш-объекта). Проблемы могут возникнуть, особенно при использовании различных гарантий на имя. Например. Роберт/Боб, Чарльз/Чак, в окружении Česká kotlna, например, Мрек/Мрослав или Дана/Данела. Кроме того, например, с использованием различных сокращений ордеров (Road / Rd, Drve / Dr, náměstí / nám. / n.). Кроме того, в текущеминтерпретации, я пока абстрагировался от возможности того, что содержание атрибута, по которому мы выполняем конкатенацию, не только написано иначе, но и неправильно. 5 Для IČO RČ (с 1954 г.) нулевой остаток после целочисленного деления на число служит проверкой.Чарльз Патрдж является пионером в использовании техники Fuzzy Match в инструментах SAS. Другой способ ввода адресов в примере из [13] Список потенциальных клиентов Chuck Patrdge P D PC, Ltd. 172 Monce Road Burlngton, Ct Источник: [13] Справочный список нечетких совпадений Patrdge, Charles PDPC, Ltd. Монс Роуд. Burlngton, Ct В случае невозможности использования классического SQL JOIN на основе уникального ключа (так называемый детерминированный подход) и его несостоятельности в случае использования составного ключа приходится использовать более изощренные методы, часто в совокупности называются вероятностным объединением. В эту группу входят применение методов машинного обучения, использование оператора Fuzzy Jon и методы, использующие принципы теории информационного поиска (IR). Метод Fuzzy Match, представленный в данной работе, относится к последней упомянутой группе. Давайте теперь остановимся на происхождении термина Fuzzy Match. [4] объясняет значение термина «нечеткий» как отсутствие точности в определении, например, в смысле размытых фотографий при перемещении камеры во время экспозиции. [6] утверждает, что термин fuzzy означает неопределенный, неясный, пушистый, и указывает, что этот термин нежелательно переводить и целесообразно использовать в оригинальной английской версии. История этого термина восходит к 1960-м годам и в основном связана с фигурой Лотфа А. Заде, профессора Калифорнийского университета в Беркли, и теорией нечетких множеств, т.е. математической дисциплиной, программно ориентированной на моделирование явления неопределенности. В девяностых годах прошлого века понятие fuzzy стало настолько популярным, что (как сообщает [6]) это слово было оценено как наиболее употребляемое в японском языке. [16] объясняетконцепция нечеткого сопоставления как противоядие от поиска точного совпадения. Нечеткое соответствие, хотя и сохраняет релевантность, менее строго, чем точное соответствие. Интерпретация термина Fuzzy Match как усовершенствования классической функции SQL JOIN/LOOKUP появляется, например, в [1] или как Fuzzy Match/Merge в [13]. [17] описывает аналогичные методы, которые [1] называют нечетким соответствием под термином объединение записей 7 — подход к базе данных. В этой работе я продолжу рассматривать Fuzzy Match как применение техник объединения записей для решения проблемы их дедупликации в базах данных. 7 английский Связь записи 3
4 [1] определяет проблему K-нечеткого соответствия следующим образом: Пусть у нас есть эталонное отношение R и минимальный порог совпадения c из интервала , функция подобия f и входная запись u. Давайте найдем множество Нечеткие совпадения FM(u) не более чем с K эталонными записями из R, такими что: () fmsu v c, для всех v z FM(u) () u, v fmsu, v’ fms для некоторых v z FM(u) и v z R -ФМ(у). В общем, вместо Фмс, точное значение которой будет выяснено в следующем тексте, можно рассматривать любую функцию подобия. Цель алгоритма Fuzzy Match — найти K эталонных записей, наиболее похожих на входную запись u. Существуют разные подходы к использованию Fuzzy Match. Некоторые (например, [13]) приложения Fuzzy Match используют дополнительную информацию из определенной предметной области. Примером может служить применение словаря синонимов для предметной области 8 для нормализации/стандартизации данных. Совершенно другой подход (опубликованный, например, в [1]) — это попытка разработать решение, не зависящее от предметной области. В данной диссертации основное внимание уделяется изложению предметно-независимых методов, поскольку область предметно-зависимых решений настолько обширна, что описать все конкретные правила в этом относительно небольшом пространстве было бы невозможно. Включение Fuzzy Match в этап сравнения и слияния процесса DQ в концепции [1] показано на диаграмме ниже. После неудачного SQL JOIN илиЗатем функция Fuzzy Match выполняет ПРОСМОТР по эталонной таблице, и когда достигается заданный уровень согласия, сравниваемая запись загружается в базу данных (или заменяется эталоном). Следует отметить, что эта схема не касается случая, когда установленному уровню согласия соответствует более одной справочной записи. На мой взгляд, причины, по которым Fuzzy Match не применяется напрямую и сначала выполняется попытка SQL JOIN, являются чисто причинами производительности. Несмотря на все методы оптимизации, описанные ниже в этой статье, поиск с нечетким совпадением выполняется менее быстро, чем классический SQL JOIN/поиск. Диаграмма 1: Образец для applkac Нечеткое совпадение Справочная таблица Источник: [1] Точное совпадение Успешный поиск? НЕТ Коэффициент совпадения с нечетким соответствием > 0,8? НЕТ Последующая очистка ДА Ввод данных ДА Загрузить данные в базу данных (например, СХД) В дальнейшем объяснении я буду использовать тот же набор эталонных записей и входных (сравненных) данных, что и в [1], в дополнительных примерах. Идентификатор справочной записи Название компании Город Штат Zp R1 Компания Boeng Seattle WA R2 Bon Corporaton Seattle WA R3 Companons Seattle WA Сопоставимые данные ID образца Название компании Город Штат Zp I1 Компания Beong Сиэтл WA I2 Beong Co. Seattle WA I3 Boeng Corporaton Seattle WA I4 Company Beong Seattle NULL Классификация мер подобия, применимая к Fuzzy Match 8 E.g. ориентированный только на дедупликацию адресов, [17] предлагает классификацию различных мер подобия, которые можно использовать для сравнения строк. Он делит их на три категории. В первую группу входят измерители на основе поправок (Soundex, расстояние Левенштейна/расстояние edt, расстояние Яро и расстояние Яро-Внклера). 4
из них
5 общим признаком является расчет затрат на операции вставки, удаления и замены частей цепочки для преобразования во вторую цепочку. Вторую группу составляют метрики, основанные на токенах (косинусное сходство TF-IDF, Jaccardкоэффициентные и вероятностные модели). Третья группа состоит из гибридных счетчиков и [17] включает в себя FMS (Fuzzy Smlarty Functon), которым будет уделено больше всего места в этой работе. Время их образования и их соединения показано на рисунке ниже. Историческая ось развития используемых мер подобия Источник: [17] Большинство этих мер будут кратко описаны в следующем тексте. Коэффициент Жаккара Коэффициент Жаккара — это мера сходства, которая применяется к отдельным токенам. Токенизация в концепции [1] представляет собой декомпозицию эталонной записи R td, A1. An, где A 1. An — отдельные столбцы ссылочной записи, а td представляет ее единственный dentfactor, к набору потоков токенов, элементы которых разделены в ссылочной записи некоторым разделителем (например, пробелом). Например. набор токенов tok (v[1]) для справочной записи v = R[R1, Boeng Company, Seattle, WA, 98004] равен
6, то (a,b) соединены. Если true LOWER 7 s2 = corporaton c o m p a n y c o r a t o n ed 7 11 s s 0.64 1. 2 s1 = bon s2 = boeng b o n b o e n g ed 3 6 s s 0.5 1. 2 Применение типа q-tce для аппроксимации переменных через переменные детальописывает, например, [7]. Однако при создании q-tc происходит иначе, чем [17] с косинским подобием и [1] с fms. Q-цы в начале и конце строки имеют меньшую длину, чем q, и поэтому они дополняются символами # (в начале) и $ (в конце) до длины q. В то же время он дополняет q-tce информацией о порядке и называет построенную таким образом пару позиционным q-tce. Таким образом, разложение строки Боэнга будет представлять собой набор возможных q-tc <(1, ##b), (2, #bo), (3, boe), (4, oe), (5, en) , (6, ng ), (7, ng$), (8, g$$)>Последовательно [7] выполняет двухшаговое сравнение, где на первом этапе отсеивают ошибочно не отклоненные ссылки с помощью простого фильтра , а на втором этапе они устраняют ссылки, помеченные неправильно, путем включения условий ed в where. Эту процедуру можно применять только в среде систем баз данных, поддерживающих определяемые пользователем функции (например, Oracle и DB2). Запрос для второго шага будет выглядеть, например, так: SELECT a.name, b.name FROM a, b WHERE edt_dstance(a.name, b.name, k) Здесь K — минимальное пороговое значение для ed. Следует отметить, что из-за того, что реляционные движки выполняются при запуске этого запроса в качестве фильтра после его выполнения, эта процедура достаточно неэффективна. Fuzzy Smlarty Functon (fms) [1] вводит функцию FMS (Fuzzy match smlarty), использование которой одновременно универсально в рамках всех предметных областей и устраняет недостатки ED, рассматривая строку как последовательность токенов и учитывая разная важность отдельных токенов. Он использует IDF (обратная частота документа) для определения важности отдельных токенов. Эта метрика основана на предположении, что важность токенов зависит от частоты их появления в справочных данных. В то же время ФМС рассматривает случаи, когда вводимые записи неверны, и может разобраться с такой ситуацией. Функция весов IDF Незнание важности отдельных токенов может быть решено путем включения их весов. Для этой цели [1] используетсяmodfkac IDF (Inverse Document Frequency), который можно рассчитать как логарифм отношения общего количества записей к частоте конкретного токена в конкретном столбце 10, т.е. по следующей формуле. R wt, IDF t, log freq t, Затраты на преобразование. Если рассматривать операции преобразования замены лексемы, вставки лексемы и удаления лексемы, то можно определить относительно отдельных видов операций преобразования минимальную стоимость преобразования множества токены от u[] до v[]. Сумма затрат на преобразование для всех наборов токенов (т. е. атрибутов) представляет собой общую стоимость преобразования записи данных u в эталонную запись v. Таким образом, общие затраты на преобразование можно выразить с помощью следующей формулы: u, v tc u v tc, [1] устанавливает значения для отдельных видов трансформационных издержек по-разному. Стоимость замены токена t1 в множестве tok(u[]) на токен t2 из множества tok(v[]) может быть выражена как произведение расстояния между строками ed(t1,t2) и веса токена t1 w(t1,). Стоимость вставки новой фишки t в набор фишек u[] равна произведению константы cns и веса фишки t w(t,). Он называет константу cns [1] коэффициентом вставки токена и присваивает ей значение из интервала . Стоимость удаления токена t из множества токенов u[] соответствует его весу w(t,). В качестве примера можно привести расчет затрат на преобразование входящей записи по адресу [beong Corporaton, Seattle, WA, 98004] в справочную запись по адресу [boeng Company, Seattle, WA, 98004]. Эта операция требует двух частичных преобразований: замены beong на boeng и 10. В общем, логарифм отношения общего количества документов в базах данных к количеству документов, содержащих заданный термин. 7
8 замена корпорации на компанию. Таким образом, общая стоимость трансформации представляет собой сумму стоимости трансформации этих двух операций. ed(beong, boeng) = 0,33 w(beong,1) = log (3/1) = 0,477 ed(корпорация, компания) = 0,64 w(corporaton,1) = log (3/1) = 0,477 tc(u,v) = tc(u[1],v[1]) = ed(beong, boeng) * w(beong,1) + ed(corporaton , компания ) * w( корпорация,1) = 0,33 * 0, 0,64 * 0,477 = 0,463 Метрика сходства нечетких совпадений (fms) Функция сходства нечетких совпадений fms(u, v) входной записи u и эталонной записи v [1] определяется следующей формулой: fms u, v u, v tc 1 mn, 1, где w u tc(u, v) — минимальная стоимость преобразования входной записи u в эталонную запись v, а w(u) — сумма веса всех токенов в наборе токенов tok(u) входа записи u. Таким образом, для входной записи u[beong Corporation, Seattle, WA, 98004] и эталонной записи v[boeng Company, Seattle, WA, 98004], расчет fms(u, v) следующий: ; 1) = 0,544 Соотношение fms и ed Следующее переписывание соотношения для определения расстояния между строками ed(u, v) подчеркивает vlv неявное присвоение весов отдельным токенам и позволяет лучше сравнить использование ed (u, v) и фмс. Lu Lu, u Lu v ed u, max, v ed u, v max Lv L(u) представляет собой сумму длин всех токенов во входной записи u (аналогично для эталонной записи v). Из модифицированного выражения видно, что ed неявно присваивает веса отдельным токенам, прямо пропорциональные их длине, то есть пропорциональные отношению max(u, v)/L(u). Таким образом, более длинные токены автоматически имеют более высокий вес при использовании ed. Aproxmac fms [1] дополнительно формулирует aproxmac fms для случаев, когда порядок токенов во входной и справочной записи может различаться, и поэтому можно сравнивать каждый токен во входной записи с каждым токеном в каждой справочной записи. Мера fms apx образует верхний предел fms. Записи, отличающиеся только порядком токенов в атрибутивной рамке, оцениваются fms apx как дентальные. Algortmus fms apx заключается в применении fms к множеству q-tc QG q(s), созданных путем разложения исходных токенов на подцепьзаданная длина. Например. для q = 3 и токена s = corporaton, QG3(corporaton) — это множество
9 В другом варианте оптимизации используется ED Игнорирование гласных [13] рекомендует пропустить в процессе сравнения и слияниягласные в сравниваемых строках. Это связано с частыми ошибками, вызванными плохой орфографией. В английском языке, например, Чарли звучит так же, как Чарли. Если гласные опущены, этот способ оценки расстояния между строками с использованием ed показал бы их полное совпадение. charlecharley 0 0 X 0 0 X X Кодирование с использованием алгоритма SOUNDEX Другим, несколько более сложным способом оптимизации ED, который вскользь упоминается в [13], является использование алгоритма SOUNDEX. Это фонетический алгоритм (см., например, [14], [15]), то есть алгоритм, индексирующий слова в соответствии с их произношением. В частности, алгоритм SOUNDEX одинаково кодирует слова с очень похожим произношением. Алгоритм был разработан специально для англоязычной среды, и его использование в другой среде потребовало бы его адаптации. Точная процедура алгоритма выглядит следующим образом: 1. Сохранение 1-й буквы строки 2. Удаление букв A,E,H,I,O из строки 3.Замена оставшихся согласных цифрами в соответствии со следующей таблицей: Исходная буква B, F, P, V 1 C, G, J, K, Q, S, X, Z 2 D, T 3 L 4 M, N 5 R 6 Заменить цифрой 4. Если несколько букв закодированы одинаково , удалите все, кроме первого. Далее я представляю несколько примеров использования алгоритма SOUNDEX на определенных парах строк. В первом примере алгоритм SOUNDEX 11 работает в англоязычной среде, когда строки SMITH и SMYTHIE перепутаны и помечает их как идентичные (но вопрос в том, правильно ли). SMITH S53 = SMYTHIE S53 Однако во втором примере KAROL и CAROL не помечаются как идентичные строки (из-за упомянутого выше 1-го пункта процедуры алгоритма). Здесь использование результата алгоритма SOUNDEX в качестве входных данных для ed приведет к результату 1/3, а применение ed к исходным строкам приведет к лучшему результату 1/5. KAROL K64!= CAROL C64 В третьем примере алгоритм приводит к идентичному кодированию на чешском языке часто путаемых слов сапожник и сапожник 12. ŠEVC S12 = ŠVEC S12 Аналогичнокак и в четвертом и пятом примерах, он кодирует сходную по звучанию пару слов коса/козел и луп/луб. KOSA K2 = KOZA K2 LUP L1 = LUB L1 В шестом примере алгоритм работает с парой чешских имен IVANA и IVONA. IVANA I15 = IVONA I15 Тем не менее, вопрос о реальной применимости алгоритма SOUNDEX для нечеткого сопоставления optmalzac остается открытым. Поэтому необходимо заранее определить, какие именно слова следует использовать. В этом контексте необходимо указать, что в [13] этот вариант упоминается лишь в качестве примечания, при том, что самого автора данной статьи эксперименты с алгоритмом SOUNDEX не убедили в гарантии его полезность. Присвоение весов отдельным столбцам [1] как одно из дополнительных усовершенствований приложения fms apx указывает на возможность дополнения существующих весов на основе IDF субъективными весами важности отдельных атрибутов. Таким образом, новые веса, используемые при вычислении fms, представляют собой сумму исходных весов токена IDF w(t) и весов столбцов W. 11 В этом примере использовалась реализация алгоритма SOUNDEX в инструменте SAS. Шевца, и к нему часто обращаются как к г-ну Швецу. 9
10 Проблемы с производительностью при использовании Fuzzy Match Взаимное сравнение токенов (или их q-tc) может представлять значительную проблему с производительностью в реальных ситуациях. Внутренний алгоритм ищет меры сходства эталонного отношения R и сравнивает каждую его запись с входной записью u. Однако в рамках оптимизации рекомендуется создать индекс для эталонного отношения. Однако, как отмечается в [1], о прямом применении индексов классических B+-деревьев не может быть и речи, так как они могут быть использованы только в том случае, если предполагается точное совпадение сравниваемых признаков. Использование M-tree ndex Об использовании M-tree ndex в случае «запроса на сходство» в мультимедийных базах данных с упором на унифицированное управление голосом, видео, изображениями, текстом и числовыми данными сообщает [23]. . М-деревосоздает парттон объектов на основе их относительного расстояния, измеренного с помощью произвольного измерителя 13. Для оценки подобия в [23] рассматривается использование диапазона и алгоритм k ближайших соседей. Запрос диапазона возвращает все проиндексированные объекты, расстояние которых от заданного объекта меньше или равно указанному максимальному расстоянию. Запрос с использованием алгоритма k-ближайших соседей Недостатком использования этого метода (как и, например, R-tree ndex) является его неприменимость в среде классических хранилищ данных. По сути, таким образом можно создать индекс по произвольным данным, для которого можно рассчитать метрику сходства. Использование устойчивых к ошибкам ndex Эффективное решение для индексации при использовании fms apx предлагается [1] в виде так называемого устойчивых к ошибкам ndex (ETI). Фактически ETI представляет собой вспомогательную таблицу, которая сопоставляет каждой подписи mnhash ее позицию во фрейме атрибута, номер атрибута, абсолютную частоту во фрейме эталонного сеанса R и набор идентификаторов строк во фрейме эталонного сеанса, содержащих подпись 14. Затем над этой таблицей создается кластер ndex с помощью атрибутов Q-point, Coordinate и Column. Разложение входной строки u на mn-хэш-сигнатуру o q=3, H=2 Beong [eo, ng] S 1, S 2 Company [com, pan] S 3, S 4 Seattle [sea, ttl] S 5, S 6 13 В этом отношении М-дерево полностью параметризовано, и конкретная функция, используемая в качестве критерия, является для него черным ящиком. 14 Реализация таблицы ETI с использованием стандартных SQL-запросов, естественно, требует создания промежуточного шага [Q-tce, Coordnát, Column, Td]. WA [wa] S [980, 004] S 8, S 9 Пример создания ETI для всей ссылки relac R Q-tce Coordinate Column Freq Td lst oe
11 вставляется новый td с оценкой, соответствующей доле веса токена и длине данного q-tce. 8. Для каждого mn-хэша подписи RemWt -= вес q-tce 9. Выбрать все записи из эталонной сессии R, для td со счетом >= c корректирующий термин 10. С помощью f сравнить каждую такую эталонную запись с входной записью u 11. Получить набор из не более чем K эталонных записей со сходством выше w(u)*c. Еще одно оптимальное использование ETI [1] встречается в использовании так называемого оптмстк-короткого замыкания (англ. optmstc short crcutng), радикально сокращающего количество обращений к таблице ETI за счет учета весов отдельных токенов. . Вес отдельных mn-хэш-подписей определяется как отношение веса токена к длине соответствующего q-tce. Этот вес, конечно же, одинаков для всех mn-hash sgnaturs, происходящих из одного токена. Расширение темы Другой пример решения, не зависящего от предметной области, дан, например, в [22]. Это решение проблемы выделения нечетких дубликатов в рамках размерных таблиц хранилища данных. То есть о ретроспективном решении проблем, которые уже должны были быть решены, например, в рамках CDI на уровне Customer Hub. Hstorcky использовались либо одинаково для этой целиметоды, основанные на мере расстояния, такие как были представлены в этой работе выше (например, ed, косинусный коэффициент и т. д.), или правила, специфичные для предметной области (например, для дедупликации адресов в инструменте Trllum). Из-за частоты ошибок некоторых из описанных метрик и усилий по разработке решения, независимого от предметной области, [22] предлагает свой собственный алгоритм DELPHI (Дублировать ELmnaton в присутствии иерархий). Это решение использует иерархическую структуру некоторых измерений и предлагает эффективную стратегию группировки, благодаря которой записи сравниваются только с небольшим набором эталонных записей в каждом отношении. Например. если мы рассмотрим иерархию Название компании Город Штат Страна 15, он сравнивает, например, только записи в измерении Штат, если они относятся к одной и той же стране, или две записи для разных стран, относящиеся только к одному государству. Заключение В настоящее время утверждение, опубликованное в [7], о том, что коммерческие системы баз данных сами по себе не поддерживают так называемое приблизительное соединение строк (по сути, еще один синоним Fuzzy Match) и что оно 15 имеет смысл для США, Канады, Великобритании. Для большинства стран ЕС более подходящей была бы иерархия Название Город Регион Государство. поэтому решать эту проблему необходимо с помощью функций, созданных пользователем, или путем приобретения специализированного программного обеспечения (с проблемами, связанными с необходимой интеграцией с БД). В следующей таблице показано использование различных методов соединения записей в коммерческих системах. Commercal System SQL Server Integraton Servces 2005 OracleBI Warehouse Bulder 10gR2 Pars IBM with Entty Analytc Solutions, QualtyStage Источник: [17] Record Lnkage Methodology Fuzzy Lookup; нечеткая группировка; использует правила сопоставления-слияния индекса устойчивости к ошибкам; детерминированное и вероятностное сопоставление вероятностное сопоставление (информационное содержание); многопроходная блокировка; merngg на основе правил Применение метода Fuzzy Match, но всегда необходимо помнить, что достоверность этого метода пока не доказана, несмотря на все усилия исследователей.всегда 100% В области применения Fuzzy Match все еще есть определенные проблемы, которые я хотел бы продолжить рассматривать в своей диссертации: 1. [17] обращает внимание на отсутствие сравнительных исследований отдельных алгоритмов с точки зрения их качества. Он призывает к разработке стандартных контрольных показателей в этой области. 2. Разработка модификации алгоритма SOUNDEX, которая может быть использована для идентичного кодирования сходных по звучанию слов в чешской среде, со строгим определением случаев, когда этот алгоритм может применяться. 3. Еще одной проблемой является более высокая степень автоматизации применения алгоритмов без необходимости принятия случайных решений человеком. Например. с возможным совпадающим значением функции подобия для нескольких эталонных записей. Ссылки [1] Чаудхур С., Ганджам К., Гант В., Мотван Р.: Надежное и эффективное нечеткое сопоставление для онлайновой очистки данных, SIGMOD 2003, 9-12 июня 2003 г., Сан-Дего, Калифорния. [2] Wang, R,Y., Zad, M., Lee, Y.,W.: Data Quality, The Kluwer International Seres on Advances n Database Systems Volume 23, Sprnger, Berlin, [3] Král J., Ţemlčka М.: Качество данных и информация, основные ограничения ИТ в государственном управлении, Systems Integraton 2006, p [4] Merram-Webster Online Dctonary, интерпретация концепции нечеткости: 11
12 [5] Рубенс Н. О.: Применение нечетких логик к построению функции ранжирования информационно-поисковых систем // Компьютерное моделирование и новые технологии. 10., нет. 1, стр. [6] Новак В.: Основы нечеткого моделирования, BEN techncka lteratura, Praha 2000, ISBN [7] Gravano L., Iperots P.G., Jagadsh H.V., Koudas N., Muthukrshnan S., Srvastava D.: Approxmate strng jons базу данных (почти) бесплатно. В материалах VLDB, Рим, Италия. Сентябрь [8] Наварро Г., Баеза-Йейтс Р., Сутнен Э., Тархо Дж.: Методы индексирования для приблизительного сопоставления строк. Бюллетень IEEE Data Engineering, 24(4):19 24, 2001. [9] Дайше Дж., Леви Э.: Интеграция данных клиентов, достигающая единой версии истины, John Wley &Sons, Inc., 2006, ISBN [10] Eckerson WW: Специальный отчет хранилища данных: качество данных и нижний предел, 2002, [11] Dorr B., Herbert P.: Data Proflng: Design Blueprnt for Improved Data Quality, SUGI 30, Хранилище данных, управление и качество, Бумага, [12] Английский Л.: Методы улучшения качества хранилища данных и бизнес-информации для снижения затрат и увеличения прибыли, John Wley & Sons, 1999, ISBN: [13] Patrdge Ch.: The Fuzzy Feelng SAS Provdes: Электронное сопоставление записей без общих ключей, Observatons, технический журнал для пользователей программного обеспечения SAS, 1998, SAS Insttute Inc., Cary. [14] Wkpeda Бесплатная энциклопедия: [15] SAS Insttute Inc SAS OnlneDoc Cary, NC: SAS Insttute Inc. [16] Search Engne Dctonary Полное руководство по поиску Engne Termnology, výklad pojmu fuzzy matchng ( ): [17] Srvastava D .: Record Lnkage: подход к базе данных, AT&T Labs-Research: [18] [19] Бродер А.: О сходстве и несоответствии документов. В Compresson and Complexity of Sequences (SEQUENCES 97), [20] Cohen E.: Sze estmaton framework with applications to transtve closure andreachablety. Журнал компьютерных и системных наук, [21] Коэн В.: Интеграция разнородных баз данных без общих доменов с использованием запросов на основе текстового понимания. В Proceedngs of ACM SIGMOD, Seattle, WA, June [22] Anantakrshna R., Chaudhur S., Gant V.: Elmnatng нечеткие дубликаты в хранилищах данных. В Proceedngs of VLDB, Hong Kong, [23] Cacca P., Patella M., Zezula P.: M-Tree: эффективный метод доступа для точного поиска в n метрических пространствах. VLDB [24] Wnkler W.: Состояние документации и текущие исследования. Statstcs of Income Dvson, Internal Revenue Servce Publcaton R99/04 [25] Wnkler W.E., Thbaudeau Y.: Применение модели Felleg-Sunter Record Inkage к деценальной переписи населения США 1990 года, U.S. Burreau foCensus, [26] Балле М., Аззопард Л., Крестан Ф.: На пути к лучшим мерам: оценка оценочного качества описания ресурсов для Dstrbuted IR. 12
