Подсистема сопоставления записей в хранилище данных (часть 2)

Автор: Дмитрий Орлов

Как работает подсистема

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

Подсистема работает по принципу трехступенчатого фильтра, т.е. имеет в своем составе три ступени «фильтрации»³ данных:

• Точное сравнение – первая стадия «фильтрации». На этой стадии происходит точное сравнение элементов рабочего набора с синонимами соответствующего эталонного набора. Все элементы рабочего набора, точно совпавшие с синонимами эталона, считаются связанными и в дальнейшем процессе не участвуют (см. п.11)
• Нечеткое сравнение – вторая стадия «фильтрации». Здесь данные сравниваются с применением методов нечеткого сравнения. Эффективность данной стадии зависит от грамотно подобранных критериев идентичности, согласно которым и делается вывод об удачном сопоставлении. Разработка и уточнение этих критериев является одной из самых сложных задач при проектировании и эксплуатации подсистемы.
  Исходя из того, что имеются вполне работоспособные критерии, некоторая часть данных, возможно, также будет успешно сопоставлена с эталонным набором на этой стадии
• Ручное связывание – это та самая стадия, где необходимо применить человеческий интеллект и поработать руками. Собственно, на входе имеется список похожих пар «эталон-рабочий образец», а окончательное решение об их идентичности принимает оператор. Для взаимодействия оператора с системой необходимо разработать GUI программу, аспекты создания которой выходят за рамки статьи. Здесь стоит заметить, что данная GUI программа должна позволить сформировать набор связанных записей оператору, не обладающему навыками программирования.

По завершении рабочих стадий необходимо произвести расширение набора синонимов эталона за счет вновь выявленных, на втором и третьем этапе, связей «эталон-рабочий образец» (согласно п.7). Расширение словаря синонимов возможно реализовать, как дополнительную функцию GUI программы, используемой оператором на стадии ручного связывания, либо как хранимую процедуру (stored procedure).

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

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

IDEF0 диаграмма процесса

На диаграмме процесса средствами IDEF0, по сути, изложено то, о чем уже говорилось выше. Но все же, не помешают некоторые дополнительные пояснения.

Рис.1 IDEF0 диаграмма процесса сопоставления записей (щёлкните для просмотра)

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

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

1. Данные, которые не связались с эталоном – просто мусор, что согласуется с п.5 (и многими реальными системами, где в поле «Наименование» какого-либо справочника можно встретить строку типа: «$$$_OTLADKA_NE_UDALIAT!!_$$$»). Для фильтрации подобных записей можно создать специальный «Справочник мусора», который будет содержать записи такого рода, что позволит исключить их из процесса сопоставления еще до начала первой стадии;
2. Эталонный набор не покрывает все пространство значений и его необходимо дополнить. Это противоречит п.5, однако соответствует большинству реальных ситуаций. В этом случае несвязанные записи можно добавить в эталонный набор;
3. Реализация методов нечеткого сравнения неудовлетворительна, т.е. критерии идентичности реализованы так, что «не замечают» часть похожих записей.

Автор при испытании прототипа подсистемы получил на выходе такой набор, и хотя записей было достаточно мало, что делало его пригодным для ручного связывания (около десятка записей), попробовал пропустить его еще раз через стадию нечеткого сравнения с менее строгими условиями. Это дало определенный эффект – несколько записей «нашли» свои эталоны, но были и неверные соответствия. Так что, в принципе, возможно применение повторного цикла нечеткого сравнения с более мягкими критериями, при наличии на выходе несвязанных записей.

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

Критерий качества

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

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

³⁾ Сравнение с фильтром и термин «фильтрация» использован не случайно, т.к. на каждой стадии происходит отсеивание данных (согласно п.8), что уменьшает нагрузку на каждую последующую стадию. Заметьте - только в последней стадии подразумевается участие оператора-человека, что полностью согласуется с одной из целей создания подсистемы.

⁴⁾ Величина критерия качества во многом зависит от предметной области, характера данных, полноты эталонных наборов и качества критериев идентичности, используемых при нечетком сравнении, что делает его достаточно объективным.

Продолжение следует...

• Часть 1
• Часть 3

Для удобства отслеживания новых публикаций на сайте рекомендую подписаться на рассылку или подписаться на канал RSS.

Если вы нашли в сети интересные ссылки на ресурсы по технологиям хранилищ данных, OLAP, CRM или data mining, и хотите поделиться ими с другими, присылайте их. Я с удовольствием размещу их на этом сайте.