Введение
1 Постановка задачи
1.1 Уровни структуризации данных
1.2 Формулировка задачи выявления дубликатов структурированных документов
1.3 Средства и методы выявления дубликатов 9
2 Особенности решения задачи в РМИС 11
2.1 Структура ЭМК 11
2.2 Состав демографических признаков и причины возникновения
дубликатов 12
3 Алгоритмы поиска дубликатов ЭМК 13
3.1 Схема реализации метода шинглирования 13
3.2 Канонизация ЭМК 14
3.3 Алгоритм Shingles 15
3.4 Алгоритм MinHash 16
3.5 Алгоритм Sketch формирования краткого образа ЭМК 18
4 Экспериментальные исследования 20
4.1 Описание программы 20
4.2 Результаты вычислительных экспериментов 20
Заключение 22
Список использованных источников 23
Региональная медицинская информационная система (РМИС) - это единая информационная база медицинского обслуживания пациентов всех клиник некоторого региона. В настоящее время такие системы создаются и внедряются во многих регионах Российской федерации, включая Красноярский край. База данных РМИС включает в себя фонд электронных медицинских карт (ЭМК) пациентов, единый регистр застрахованных лиц (РСЛ), архив медицинских документов (результатов функциональной диагностики, лабораторных исследований и др.). Вся эта информация поступает из различных источников, не гарантирующих полноту указания основных демографических данных и отсутствие опечаток, неточностей. В результате сведения, относящиеся к истории болезни одного и того же пациента, в РМИС могут быть привязаны к различным доку-ментам (ЭМК или записям РСЛ), которые в основном совпадают, но все же имеют некоторые различия. Такие документы принято называть почти дубликатами или просто дубликатами. Два документа считаются дубликатами, если не-которая количественная оценка их сходства превышает определённый порог.
Наличие дубликатов в РМИС затрудняет идентификацию пациентов, а в ряде случаев может привести к серьёзным последствиям. Основным препятствием для успешного решения описанной выше проблемы является очень большой объем (порядка нескольких миллионов) хранимых в РМИС документов, каждый из которых может содержать несколько тысяч символов. Такой объем данных делает практически невозможным (в разумное время) непосредственное попарное сравнение ЭМК. Одним из путей решения этой проблемы в настоящее время является разработка методов создания кратких образов (скетчей) документов для последующей обработки.
Объектом исследования выпускной квалификационной работы являются методы формирования кратких образов текстовых документов, а предметом исследования - выявление дубликатов документов в РМИС на основе их кратких образов. Методы исследования: методы анализа текстовых данных.
Цель работы: разработка алгоритмов и программ выявления дубликатов текстовых документов, используемых для идентификации пациентов в РМИС.
Для достижения поставленной цели в работе необходимо
- сформулировать задачу выявления дубликатов структурированных документов;
- изучить основные особенности ЭМК пациента, выявить демографические признаки, по которым осуществляется идентификация пациентов, установить причины возникновения дубликатов ЭМК;
- изучить известные методы и средства выявления дубликатов структурированных документов и исследовать возможности их применения в РМИС;
- разработать модель краткого образа документа, алгоритмы и программу её формирования;
- разработать алгоритм и программу выявления дубликатов ЭМК;
- выполнить вычислительные эксперименты.
Выпускная квалификационная работа состоит из введения, четырех разделов, заключения, списка использованных источников и приложения. В разделе 1 приводятся формулировка задачи и краткий обзор методов ее решения. Раздел 2 посвящен установлению особенностей заполнения ЭМК и идентификации пациентов в РМИС. В разделах 3, 4 представлены разработанные алгоритмы и программы выявления дубликатов ЭМК, также приведены результаты вычислительных экспериментов. В приложении приведен текст программ.
В работе сформулирована задача выявления дубликатов структурированных документов. Определены причины возникновения дубликатов ЭМК пациентов, составляющих значительную часть базы данных РМИС и на основании которых осуществляется идентификация пациентов. Поставленная задача решена с помощью метода шинглирования, модифицированного с учетом специфики ЭМК и причин возникновения дубликатов ЭМК. Дубликаты выявляются на основе кратких числовых образов сравниваемых документов. Созданы алгоритмы и программа формирования краткого образа документа и выявления дубликатов ЭМК. Выполнены вычислительные эксперименты.
