Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Модуль поддержки принятия управленческих решений на медицинском предприятии

Модуль поддержки принятия управленческих решений на медицинском предприятии

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 11.04.2013
Размер файла 1,9 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Страница:

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

Аналитические методы дают конечному пользователю возможность осуществить весь цикл работы с исходными данными, имеющими большие объемы и невыясненную статистическую структуру. Этот цикл называется разведкой данных (DataMining) и состоит из нескольких этапов: выборка, исследование, модификация, моделирование, оценка результатов (Sample, Explore, Modify, Model, Assess).

Средства DataMining дают возможность ставить и решать как традиционные, так и нетрадиционные задачи анализа. Например, традиционной является постановка задачи: "Определить, имеется ли статистическая связь между такими показателями, как объем производства товара и объем его реализации (продажи)".

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

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

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

1.6 Анализ данных в медицинских информационных системах и СППР

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

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

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

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

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

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

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

Выводы по разделу 1

Рассмотрение экспертных систем, представляющие собой самодостаточную среду для разработки, внедрения и сопровождения приложений в широком диапазоне отраслей. Они объединяют в себе как универсальные технологии построения современных информационных систем (стандарты открытых систем, архитектура клиент/сервер, объектно-ориентированное программирование, использование ОС, обеспечивающих параллельное выполнение в реальном времени многих независимых процессов), так и специализированные методы (рассуждения, основанные на правилах, рассуждения, основанные на динамических моделях, или имитационное моделирование, процедурные рассуждения, активная объектная графика, структурированный естественный язык для представления базы знаний), а также интегрирует технологии систем, основанных на знаниях с технологией традиционного программирования (с пакетами программ, с СУБД, с контроллерами и концентраторами данных и т.д.).

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

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

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

2. Аналитическая часть

2.1 Ассоциативные правила (AssociationRules)

В последнее время неуклонно растет интерес к методам "обнаружения знаний в базах данных" (knowledge discovery in databases). Объемы современных баз данных, которые весьма внушительны, вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил.

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

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

Определение 1. Пусть I = (i1, i2, i3,. in) - множество (набор) товаров, называемых элементами. Пусть D - множество транзакций, где каждая транзакция T - это набор элементов из I, TI. Каждая транзакция представляет собой бинарный вектор, где t [k] =1, если ik элемент присутствует в транзакции, иначе t [k] =0. Мы говорим, что транзакция T содержит X, некоторый набор элементов из I, если XT. Ассоциативным правилом называется импликация XY, где XI, YI и XY=. Правило XY имеет поддержку s (support), если s% транзакций из D, содержат XY, supp (XY) = supp (XY). Достоверность правила показывает какова вероятность того, что из X следует Y. Правило XY справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат Y, conf (XY) = supp (XY) /supp (X).

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

Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил X Y, причем поддержка и достоверность этих правил должны быть выше некоторых наперед определенных порогов, называемых соответственно минимальной поддержкой (minsupport) и минимальной достоверностью (minconfidence).

Задача нахождения ассоциативных правил разбивается на две подзадачи:

1. Нахождение всех наборов элементов, которые удовлетворяют порогу minsupport. Такие наборы элементов называются часто встречающимися.

2. Генерация правил из наборов элементов, найденных согласно п.1. с достоверностью, удовлетворяющей порогу minconfidence.

Один из первых алгоритмов, эффективно решающих подобный класс задач, - это алгоритм APriori [2]. Кроме этого алгоритма в последнее время был разработан ряд других алгоритмов: DHP [5], Partition [6], DIC [7] и другие.

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

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

Численные ассоциативные правила (QuantitativeAssociationRules)

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

Пример численного ассоциативного правила: [Возраст: 30-35] и [Семейное положение: женат] [Месячный доход: 1000-1500 тугриков].

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

Как было сказано, задача поиска ассоциативных правил впервые была представлена для анализа рыночной корзины. Ассоциативные правила эффективно используются в сегментации покупателей по поведению при покупках, анализе предпочтений клиентов, планировании расположения товаров в супермаркетах, кросс-маркетинге, адресной рассылке. Однако, сфера применения этих алгоритмов не ограничивается лишь одной торговлей. Их также успешно применяют и в других областях: медицине, для анализа посещений веб-страниц (WebMining), для анализа текста (TextMining), для анализа данных по переписи населения [7], в анализе и прогнозировании сбоев телекоммуникационного оборудования и т.д.

2.2 Apriori - масштабируемый алгоритм поиска ассоциативных правил

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

Для того, чтобы было возможно применить алгоритм, необходимо провести предобработку данных: во-первых, привести все данные к бинарному виду; во-вторых, изменить структуру данных.

Таблица 1

Обычный вид базы данных транзакций:

Номер транзакции

Наименование элемента

Количество

1001

А

2

1001

D

3

1001

E

1

1002

А

2

1002

F

1

1003

B

2

1003

A

2

1003

C

2

Таблица 2

Нормализованный вид:

TID

A

B

C

D

E

F

G

H

I

K

.

1001

1

0

0

1

1

0

0

0

0

0

…

1002

1

0

0

0

0

1

0

0

0

0

…

1003

1

1

1

0

0

0

0

0

1

0

…

Количество столбцов в таблице равно количеству элементов, присутствующих в множестве транзакций D. Каждая запись соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0 в противном случае. (см. Определение 1). Заметим, что исходный вид таблицы может быть отличным от приведенного в таблице 1. Главное, чтобы данные были преобразованы к нормализованному виду, иначе алгоритм не применим.

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

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

Свойство анти-монотонности

Выявление часто встречающихся наборов элементов - операция, требующая много вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи - простой перебор всех возможных наборов элементов. Это потребует O (2|I|) операций, где |I| - количество элементов. Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора (Хлеб, Масло, Молоко) будет всегда меньше или равна поддержке 2-элементных наборов (Хлеб, Масло), (Хлеб, Молоко), (Масло, Молоко). Дело в том, что любая транзакция, содержащая (Хлеб, Масло, Молоко), также должна содержать (Хлеб, Масло), (Хлеб, Молоко), (Масло, Молоко), причем обратное не верно.

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

Свойству антимонотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же. Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1) - элементные подмножества будут часто встречающимися.

Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне 1-элементные наборы, на 2-м - 2-элементные и т.д. На k уровне представлены k-элементные наборы, связанные со всеми своими (k-1) - элементными подмножествами.

Рассмотрим рисунок 1, иллюстрирующий набор элементов I - (A, B, C, D). Предположим, что набор из элементов (A, B) имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству антимонотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с (A, B), выделена фоном. Использование этой эвристики позволяет существенно сократить пространство поиска.

Алгоритм Apriori

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

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

Описанный выше алгоритм можно записать в виде следующего псевдокода:

1. F1 = (часто встречающиеся 1-элементные наборы)

2. для (k=2; Fk-1<>; k++) (

3. Ck = Apriorigen (Fk-1) // генерация кандидатов

4. для всех транзакций t T (

5. Ct = subset (Ck, t) // удаление избыточных правил

6. для всех кандидатов c Ct

7. c. count ++

8. )

9. Fk = ( c Ck | c. count>= minsupport) // отбор кандидатов

10. )

11. Результат Fk

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

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

1. Объединение. Каждый кандидат Ck будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1) - элементного набора.

2. Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса.

3. insertintoCk select p. item1, p. item2, …, p. itemk-1, q. itemk-1 From Fk-1 p, Fk-1 q where p. item1= q. item1, p. item2 = q. item2, …, p. itemk-2 = q. itemk-2, p. itemk-1< q. itemk-1

4. Удаление избыточных правил. На основании свойства анти-монотонности, следует удалить все наборы c Ck если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.

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

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

Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е. CkTi = Ck. На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам и т.д. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.

После того, как каждая транзакция из исходного набора данных "пропущена" через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения (k+1) - элементных наборов и т.д.

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

Извлечение правил - менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Например, имеется часто встречающийся набор (A, B, C) и требуется подсчитать достоверность для правила AB C. Поддержка самого набора нам известна, но и его множество (A, B), лежащее в условии правила, также является часто встречающимся в силу свойства антимонотонности, и значит его поддержка нам известна. Тогда мы легко сможем подсчитать достоверность. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался в том случае если бы это поддержка была неизвестна.

Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s мы сможем сформулировать правило s (F - s), если достоверность правила conf (s (F - s)) = supp (F) /supp (s) не меньше порога minconf.

Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил. Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A BCDE удовлетворяет минимальному порогу достоверности minconf, тогда AB CDE также удовлетворяет. Для того, чтобы извлечь все правила используется рекурсивная процедура. Важное замечание: любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора. Например, если набор состоит из элементов (A, B, C), то правило A B не должно рассматриваться.

2.3 FPG - альтернативный алгоритм поиска ассоциативных правил

Узким местом в алгоритме a priori является процесс генерации кандидатов в популярные предметные наборы. Например, если база данных (БД) транзакций содержит 100 предметов, то потребуется сгенерировать 2100~1030sup> кандидатов. Таким образом, вычислительные и временные затраты, которые нужны на их обработку, могут быть неприемлемыми. Кроме этого, алгоритм a priori требует многократного сканирования базы данных транзакций, а именно столько раз, сколько предметов содержит самый длинный предметный набор. Поэтому был предложен ряд алгоритмов, которые позволяют избежать генерации кандидатов и сократить требуемое число сканирований набора данных.

Одним из наиболее эффективных процедур поиска ассоциативных правил является алгоритм, получивший название FrequentPattern-Growth (алгоритм FPG), что можно перевести как "выращивание популярных (часто встречающихся) предметных наборов". Он позволяет не только избежать затратной процедуры генерации кандидатов, но уменьшить необходимое число проходов БД до двух. Рассмотрим его более подробно.

Алгоритм Frequent Pattern-Growth Strategy (FPG)

В основе метода лежит предобработка базы транзакций, в процессе которой эта база данных преобразуется в компактную древовидную структуру, называемую Frequent-PatternTree - дерево популярных предметных наборов (откуда и название алгоритма). В дальнейшем для краткости будем называть эту структуру FP-дерево. К основным преимуществам данного метода относятся:

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

2. При построении FP-дерева используется технология разделения и захвата (англ.: divideandconquer), которая позволяет выполнить декомпозицию одной сложной задачи на множество более простых;

3. Позволяет избежать затратной процедуры генерации кандидатов, характерной для алгоритма a priori.

Рассмотрим работу алгоритма FPG на конкретном примере. Пусть имеется БД транзакций (табл.1).

Таблица 1

N

Предметный набор

1

a b c d e

2

a b c

3

a c d e

4

b c d e

5

b c

6

b d e

7

c d e

Для данной БД требуется обнаружить все популярные предметные наборы с минимальной поддержкой, равной 3, используя алгоритм FPG.

1. Производится первое сканирование БД транзакций, и отбирается множество часто встречающихся предметов, т.е. предметов, которые встречаются три или более раза.

Упорядочим обнаруженные частые предметы в порядке возрастания их поддержки и получим следующий набор: (c,6), (b,5), (d,5), (e,5), (a,3).

2. Построим FP-дерево. Сначала упорядочим предметы в транзакциях по убыванию значений их поддержек (табл.2).

Таблица 2

N

Исходный предметный набор

Упорядоченный предметный набор

1

a b c d e

c b d e a

2

a b c

c b a

3

a c d e

c d e a

4

b c d e

c b d e

5

b c

c b

6

b d e

b d e

7

c d e

c d e

Сначала создадим начальный (корневой) узел FP-дерева, который обычно обозначают ROOT (от англ. root - корень).

Начнем построение дерева с транзакции №1 для упорядоченных предметных наборов, т.е. (c b d e a), рис.1. При построении дерева будем придерживаться следующего правила.

Правило 1. Если для очередного предмета в дереве встречается узел, имя которого совпадает с именем предмета, то предмет не создает нового узла, а индекс соответствующего узла в дереве увеличивается на 1. В противном случае для этого предмета создается новый узел и ему присваивается индекс 1.

Рис.1. Построение FP-дерева на транзакции № 1

Сначала берем предмет с из транзакции №1. Поскольку он является первым, то формируем для него узел и соединяем с родительским (корневым) (рис.1, а). Затем берем следующий предмет b и поскольку других узлов с тем же именем дерево пока не содержит, добавляем его в виде нового узла, потомка узла с (рис 1, б). Таким же образом формируем узлы для предметов d, e и a из транзакции № 1 (случаи в, г, и д на рис 1). На этом использование первой транзакции для построения дерева закончено.

Для транзакции № 2, содержащей предметы c, b и a, выбираем первый предмет, c. Поскольку дочерний узел с таким именем уже существует, то в соответствии с правилом построения дерева новый узел не создается, а добавляется к уже имеющемуся (рис.2, а). При добавлении следующего предмета b используем то же правило: поскольку узел b является дочерним по отношению к текущему (т.е. c), то мы также не создаем новый узел, а увеличиваем индекс для имеющегося (рис.2, б). Для следующего предмета из второй транзакции a в соответствии с правилом построения FP-дерева придется создать новый узел, поскольку у узла b дочерние узлы с именем a отсутствуют (рис.2, в).

Рис.2. Построение FP-дерева на транзакции № 2

И, наконец, последняя транзакция № 7, содержащая предметный набор (c d e), увеличит на 1 индексы соответствующих узлов. Получившееся дерево, которое также является результирующим для всей БД транзакций, представлено на рис.7.

Рис.7. Результирующее дерево, построенное по всей БД транзакций

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

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

Извлечение частых предметных наборов из FP-дерева

Для каждого предмета в FP-дереве, а точнее, для связанных с ними узлов, можно указать путь, т.е. последовательность узлов, которую надо пройти от корневого узла до узла, связанного с данным предметом. Если предмет представлен в нескольких ветвях дерева (что чаще всего и происходит), то таких путей будет насколько. Например, для FP-дерева на рис.7 для предмета a можно указать 3 пути: (cbdea, cba, cdea). Такой набор путей называется условным базисом предмета (англ.: conditionalbase). Каждый путь в базисе состоит из двух частей - префикса и суффикса. Префикс - это последовательность узлов, которые проходит путь для того чтобы достичь узла, связанного с предметом. Суффикс - это сам узел, к которому "прокладывается" путь. Таким образом, в условном базисе все пути будут иметь различные префиксы и одинаковый суффикс. Например, в пути cbdea префиксом будет cbde, а суффиксом - a.

Процесс извлечения из FP-дерева частых предметных наборов будет заключаться в следующем.

1. Выбираем предмет (например, a) и находим в дереве все пути, которые ведут к узлам этого предмета Иными словами, для a это будет набор (cbdea, cba, cdea). Затем для каждого пути подсчитываем, сколько раз данный предмет встречается в нем, и записываем это в виде (cbdea, 1), (cba, 1) и (cdea, 1).

2. Удалим сам предмет (суффикс набора) из ведущих к нему путей, т.е. (cbdea, cba, cdea). После это останутся только префиксы: (cbde, cb, cde).

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

4. На его основе построим новое FP-дерево, которое назовем условным FP-деревом (conditional FP-tree), поскольку оно связано только с одним объектом (в нашем случае, a).

5. В этом FP-дереве найдем все предметы (узлы), для которых поддержка (количество появлений в дереве) равна 3 и больше, что соответствует заданному уровню минимальной поддержки. Если предмет встречается два или более раза, то его индексы, т.е. частоты появлений в условном базисе, суммируются.

6. Начиная с верхушки дерева, записываем пути, которые ведут к каждому узлу, для которого поддержка/индекс больше или равны 3, возвращаем назад предмет (суффикс шаблона), удаленный на шаге 2, и подсчитываем индекс/поддержку, полученную в результате. Например, если предмет a имеет индекс 3, то можно записать (c b a,3), что и будет являться популярным предметным набором.

Префиксы путей, ведущих в условном дереве к узлам, связанным с предметом e, будут: (c b d e,2) (c d e,2) (b d e, 1). Подсчитав суммарную поддержку каждого предмета в условном дереве и упорядочив предметы по ее убыванию, получим: (d,5), (c,4), (b,3). Следовательно, популярными предметными наборами для предмета e будут: (d, e,5), (d, c, e,4), (d, b, e,3).

Таким образом, мы получили следующие популярные предметные наборы: (c, a,3), (c, b,4), (c, d,4), (b, d,3), (d, e,5), (d, c, e,4), (d, b, e,3).

Сравнительные исследования классического алгоритма a priori и FPG показали, что с увеличением числа транзакций в БД временные затраты на поиск частых предметных наборов растут для FPG намного медленнее, чем для a priori (рис.12).

Рис. 12. Сравнение алгоритмов FPG и a priori

3 Модуль поддержки принятия управленческих решений

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

Дается описание созданного информационного модуля, его структуры и руководство пользователя и программиста.

Назначение и общие сведения о модуле ППУР

Модуль поддержки принятия управленческих решений на медицинском предприятии предназначен для помощи и сокращения времени принятия управленческих решений директором клиники.

Исходными данными для работы модуля являются данные из БД информационной системы ОАО "Центр Эндохирургических технологий".

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

Эксплуатационное назначение системы:

- обеспечение поддержки принятия решений для директора медицинского предприятия;

Состав основных выполняемых функций:

- поиск ассоциативных правил в БД ОАО "Центр Эндохирургических технологий";

- построение графиков приобретения услуг;

- расчет загруженности персонала

Техническое обеспечение.

Информационная система разработана в среде визуального программирования Borland Developer Studio на языке Delphi. Минимальные требования к аппаратному и программному обеспечению компьютера для надежной работы программного модуля следующие:

- операционная система: WindowsXP, Vista, 7;

- процессор: Pentium - 4 и выше;

- оптимальный объем оперативной памяти: 512Mb;

- минимальный объем свободного дискового пространства: 10Mb (не считая места, отводимого под данные).

Модуль состоит из пяти блоков: пользовательский интерфейс, нормализатор БД; поиск ассоциативных правил; построение графиков приобретения услуг; загруженность персонала.

Структура информационной системы

В структуре разработанной информационной системы выделяются пять основные подсистем (рисунок 7):

- подсистема нормализации базы данных

- подсистема поиска ассоциативных правил

- подсистема расчета и построения графиков приобретения услуг

- подсистема расчета коэффициента загруженности персонала

- подсистема считывания базы данных.

Рисунок 9 - Структура модуля ППУР

Описание основных подсистем

Подсистема нормализации базы данных

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

Таблица 5 - Пример участка исходной БД

Клиент

Услуга

Количество

Врач

1

3

3

1

1

2

1

2

Таблица 6 - Пример нормализованного участка исходной БД из таблицы 5

Клиент

Услуга 1

Услуга 2

Услуга 3

Услуга.

1

0

1

3

.

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

Создание отдельного файла для хранения нормализованной БД обусловлено необходимостью увеличения надежности процесса поиска ассоциативных правил за счет разбиения всего процесса на две части: считывание БД и ее нормализация и поиск ассоциативных правил. Данная необходимость возникает из-за большого (~5-10c) времени считывания и нормализации БД и (~3-5с) времени поиска ассоциативных правил.

Подсистема поиска ассоциативных правил

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

Поиск ассоциативных правил осуществляется с помощью FPG-алгоритма.

Результатом работы данной подсистемы является таблица ассоциативных правил.

Подсистема расчета и построения графиков приобретения услуг

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

Подсистема использует данные о транзакциях из корпоративной БД (полученных с помощью модуля считывания), на основе которых производится суммирование приобретенных услуг за выбранный период времени. Вывод результатов осуществляется в графическом виде.

Подсистема расчета коэффициента загруженности персонала

Данная подсистема предназначена для расчета и отображения информации о занятости персонала.

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

Подсистема считывания базы данных.

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

Руководство пользователя

Порядок работы с модулем ППУР

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

Рисунок 10. Основная форма модуля.

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

Выбрав "График приобретенных услуг" пользователь попадает на новую форму (Рисунок х2).

Рисунок 11 - График приобретения услуг

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

Выбрав "Загруженность персонала" из главного окна пользователь попадает на новую форму (рисунок х3).

Рисунок 12 - Форма загруженности персонала.

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

Выбрав "Поиск ассоциативных правил" пользователь попадает на новую форму (Рисунок 13).

Рисунок 13 - Форма ассоциативных правил.

Здесь пользователю предлагается выбрать диапазон поддержки и ограничение на размер наборов (по умолчанию ограничения нет). После нажатия на кнопку "Рассчитать" в таблицу слева заносятся ассоциативные правила с их поддержками. Таблица сортируется по убыванию поддержки.

Выход из модуля ППУР производится по закрытию окна главного меню.

Возможные неисправности программного обеспечения

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

Руководство программиста

Программные средства представляет собой совокупность классов, которые представлены на рисунке 17.

Рисунок 14 - Диаграмма классов

1. ТClient - класс работает с базой данных, а именно с таблицей Clients (загружает и подготавливает информацию для расчетов).

2. ТStaff - класс работает с базой данных, а именно с таблицей Staff (загружает и подготавливает информацию для расчетов).

3. ТServicesкласс работает с базой данных, а именно с таблицей Services (загружает и подготавливает информацию для расчетов).

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

5. TDataBaseEntity - класс от которого наследуются все классы сущности. Он содержит необходимые методы и поля для загрузки информации из БД.

6. ТController - обеспечивает передачу необходимых данных между всеми другими классами и слоями. (Например, передачу данных от классов сущностей к калькулятору или от калькулятора на формы)

7. ТCalculate - содержит алгоритмы и производит все математические расчеты

Выводы по разделу 3

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

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

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

4.1 Эффективность модуля ППУР

Эффективность применения модуля ППУР можно оценить, рассмотрев эффективность каждой из его функций в отдельности.

Эффективность поиска ассоциативных правил

Эффективность поиска ассоциативных правил обуславливается эффективностью применения данного подхода к корпоративной БД ОАО "Центр Эндохирургических технологий" и эффективностью самого алгоритма.

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

Таким образом выбранный алгоритм можно считать эффективным и оправданным.

Эффективность применения самого метода ассоциативных правил для осуществления поддержки принятия управленческих решений на медицинском предприятии не так очевидна в силу:

· высокой степени стандартизации процедур оказания услуг

· небольшим вкладом свободы выбора пользователя на наборы покупаемых им услуг

· относительно небольшим размером медицинского учреждения

Результатами работы алгоритма становилось обнаружение большого числа наборов с высокой степенью поддержки. Примерно 90% наборов оказались очевидными, еще 5% неинформативными. Но оставшиеся 5% представляли реальный интерес. Несмотря на очень хорошую осведомленность руководства о процессе оказания услуг на предприятии был обнаружен ряд "интересных" наборов, анализ которых привел к корректировки пакетов оказываемых клиникой услуг и работы некоторых отделений медицинского предприятия. (подробнее в разделе 4.2.1 Результаты поиска ассоциативных правил).

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

Эффективность графиков приобретения услуг

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

Эффективность оценки загруженности персонала

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

Хотя получаемый программой коэффициент в силу многих субъективных причин не дает полного представления о загруженности того или иного специалиста, получаемой информации достаточно для пересмотра графиков работы персонала, принятия решений об увольнении или найме новых работников, корректировке списка предоставляемых услуг (подробнее в разделе 4.2.3 Результаты оценки загруженности персонала).

4.2 Полученные результаты

В данном разделе представлены результаты работы модуля ППУР.

Результаты поиска ассоциативных правил

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

· Высоким уровнем поддержки (для некоторых троичных и четверных наборов более 100)

· Большой размерностью наборов (были обнаружены наборы из четырех и пяти элементов)

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

Рисунок 15 - Пример найденных ассоциативных правил.

В ходе анализа был выявлен ряд случаев, когда для одного и того же типа лечения получались различные наборы. Так, например, для операции лапороскопическаягерниопластика было выявлено два набора: Консультация 1; Лап_Герниопластика 1; Прием 1; Стационар 2; и Консультация 1; Лап_Герниопластика 1; Прием 1; Стационар 1; отличающиеся количеством дней в стационаре. Пакет услуг предоставляемый клиникой на эту операцию предусматривал один день стационара, в то время как в большинстве случаев (61%) клиент оставался в стационаре на еще один дополнительный день, за который приходилось платить отдельно. Это происходило в силу различного протекания реабилитации у пациентов, а также из-за разного времени попадания в стационар. Итогом стал пересмотр данного пакета услуг и включение дополнительного дня в стационаре.

Еще одним результатом работы алгоритма стало обнаружение наборов с хорошей поддержкой, которые показывали что различные клиенты приобретали несколько пакетов услуг, которые не были ранее связаны в один комплекс. Например, был обнаружен набор Консультация 2; Гистероскопия 1; Лап_Миомэктомия 1; Прием 3; Стационар 2; с поддержкой 31. Этот результат привел руководство клиники к решению о создании комплекса "Гистероскопия и Лапороскопическая Миомэктомия", который предусматривал скидку на проведение второй операции, которая должна была привлекать клиентов к повторному обращению в клинику для продолжения лечения.

Страница:


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены