Диссертация (1137259), страница 19
Текст из файла (страница 19)
Данные, по которым строитсямодель, получены из открытого хранилища UCI [37]. Эти данныесодержаться в хранилище под именем “MSNBC.com AnonymousWeb Data”1 . Эти данные получены из логов IIS сервера для сайтовmsnbc.com и новостной ленты сайта msn.com за 28 сентября 1999года. Каждая запись в этих данных соответствует последовательности просмотра страниц пользователем. Каждый элемент последовательности – один запрос через IIS по соответствующей группе адресов.
Такой элемент представлен как категория этой группы адресови может быть, например, “заглавной страницей” или “спортивныминовостями”. В каждую категорию входит от 10 до 5000 различныхссылок. Средняя длина последовательности в этой выборке данных5,7 обращений к страницам. Общее количество записей или последовательностей в этих данных: 989818.
Например, одной из первыхзаписей в данной выборке является:⟨; ; ; ; ℎ⟩ .Здесь news – это главные новости, local – региональные, а tech– новинки техники.Данные такого рода являются примером процессов с простымисостояниями. В данной работе они обрабатываются так же как исложные, с чем связаны дополнительные накладные расходы. Темне менее данная выборка являются одной из лучших публичных вы1http://archive.ics.uci.edu/ml/datasets/MSNBC.com+Anonymous+Web+Data117Время (с)·1051 ℓ=3ℓ=40.8ℓ=50.60.40.2000.2 0.4 0.6 0.81Количество записей ·106Рисунок 5.1: Время построения узорных понятий в зависимости отколичество обработанных записейборок данных последовательностей.
Именно поэтому она используется для экспериментального измерения вычислительной сложностимоделей.На рисунке 5.1 показаны времена построения решётки узорныхпонятий для различного количества обрабатываемых записей. Так,например, для того чтобы обработать все 106 записей при использовании ПМД-проекции для минимальной длины ℓ = 3 потребовалось 105 секунд. Как мы видим время вычислений растёт достаточнобыстро от размера выборки. Проекции для ℓ < 3 здесь не представлены, так как при уменьшении параметра ПМД-проекции, времявычислений растёт очень быстро.
Более того, при уменьшении этогопараметра до 2, результирующая решётка перестаёт влазить в оперативную память компьютера, и поэтому вычисления ещё сильнеезамедляются. Также стоит отметить, что для процессов с простымисостояниями, алфавитная проекция не имеет смысла и поэтому здесьне исследуется.Рассмотрим какие закономерности могут быть найдены при моделировании при помощи узорных структур на последовательностях.Таблица 5.1 показывает некоторые закономерности, выделенные индексом устойчивости. Первая колонка показывает номер понятия,118#ПМДСодержаниеРанк Уст. Поддержка1ℓ=3⟨ ; ; ⟩125111 (2.5%)2ℓ=3⟨ ; ; ⟩216584 (1.6%)3ℓ=3⟨ ; ; ; ; ⟩116660 (0.6%)16660 (0.6%)4 ℓ ∈ {4, 5} ⟨ ; ; ; ; ⟩ℓ=4⟨ ; ; ; ⟩26328 (0.6%)56ℓ=5⟨ ; ; ; ; ⟩32587 (0.2%)ℓ=5⟨ ; ; ; ; ⟩52614 (0.2%)7Таблица 5.1: Некоторые интересные закономернсти, для разныхПМД проекций, найденные для выборки последовательностей посещений страниц пользователями.
FP – главная страница; News –главные новости; Business – новости бизнеса; Misc – различныеновости; OnAir – живая трансляция; Local – региональные новости; Sport – спортивные новости.вторая колонка задаёт параметр ПМД проекции, для которого приведена закономерность в строке. Колонка “Содержание” показывает содержание узорного понятия, то есть само описание закономерности.Следующая колонка показывает индекс понятия по устойчивости:все понятия сортируются по устойчивости, и, тогда, ранк понятия– это его порядковый номер в этом списке.
Последние две колонкипоказывает какое количество записей покрываются этим описанием.Закономерность #1 группирует пользователей, которые переходят с главной страницы на главные новости и обратно. Несмотряна то, что таких пользователей относительно мало, это самая значимая группа, потому что её устойчивость является первой.
Эта закономерность может быть найдена только при ℓ = 3, при большихℓ она будет исключена из выдачи. Следующая важная группа пользователей задаётся закономерностью #2 – это пользователи, которыхинтересуют бизнес-новости. Закономерности #3 и #4 соответствуютпользователям, которые переходят между разделом “разные новости”и текущим вещанием. Скорее всего – это те пользователи, которыесмотрят новости, чтобы хоть что-то посмотреть, потому как они незнают, что ищут. Заметим, что закономерности #3 и #4 отличаются только параметром проекции, при котором они найдены.
Но при119этом при ℓ = 3 это понятие является только 11, в то время как дляℓ ∈ {4, 5} – это первое устойчивое понятие.При увеличении параметра ПМД-проекции до более высоких значений попадают более длинные закономерности. Так в закономерности #5 происходит многократная смена рубрики “разные новости”и рубрики “региональные новости”. Последние две закономерностихарактеризуют группы пользователей, которые многократно перемещаются между разными новостями или спортом и главной страницей. Эти закономерности интересны тем, что несмотря на то, что#6 имеет меньшую поддержку, чем #7, последний отобран устойчивостью как менее важный, что в частности означает возможныерасширения закономерности #6 дальше (в поддержке) от самой закономерности, чем для #7.Подобный анализ выборки посещаемости сайтов, может быть использован экспертом предметной области для оптимизации навигации сайта или для более эффективного размещения цепочек рекламы, привязанной к типичным шаблонам посещений.5.3Моделирование процесса госпитализации пациентовИсследуемая выборка данных построена для процесса госпитализации пациентов за один год с момента обнаружения у них раковых заболеваний пищеварительной системы.
Это пример процесса ссостояниями сложной структуры. Данные получены из французскойсистемы здравоохранения, называемой PMSI [36]2 . Выборка содержит около 2400 пациентов, а распределение длин показано на Рисунке 5.2. Описание одной госпитализации состоит из трех составляющих: имя больницы или клиники с ассоциированной таксономиейрасположения по городам и регионам, причина госпитализации (рак,химиотерапия и др.) в таксономии диагнозов и множество медицинских процедур, которым подвергался пациент в течение этой гос2Programme de Médicalisation de Systèmes d’Information120питализации. Так история некоторого пациента могла бы выглядетьследующим образом:⟨[CH1 , Рак, {1 , 2 }]; [CH2 , Хим.Тер., {}]; [CH2 , Хим.Тер., {}]⟩ .Данная последовательность моделирует историю госпитализации пациента с тремя госпитализациями, первая из которых имеет местов больнице CH1 , и в течение которой диагностируется рак посредством процедур 1 и 2 .
В течении двух последующих госпитализаций пациент проходит курс химиотерапии в больнице 2 . В большинстве случаев курс химиотерапии производится в одной больнице без каких либо дополнительных процедур, поэтому для эффективной обработки узоров и для возможности исследовать вариациючисла госпитализаций для курса химиотерапии, все подряд идущиегоспитализации с химиотерапией объединяются в одну госпитализацию, с дополнительным указанием числа повторов. Таким образом,представленная ранее история госпитализаций пациента будет иметьследующий вид:⟨[CH1 , Рак, {1 , 2 }]; [CH2 , Хим.Тер., {}][2]⟩ .Диагнозы заданы в рамках международно классификации болезней ICD10.
Это классификация задаёт таксономию с 5 уровнямиточности описания: корень таксономии, глава (chapter), блок (block),3х-буквенное описание, 4х-буквенное описание, листья дерева таксономии. Всего в данной таксономии содержится 1544 вершины, включая листья.Таксономия географического расположения больниц содержит 5уровней точности: корневая вершина (соответствует Франции), регион, район, город и листья таксономии, которые соответствуют конкретным больницам. На рисунке 5.3 показана часть этой таксономии. На этом рисунке конкретная больница и город объединены водин лист дерева, в котором первые 5 цифр соответствуют индексугорода, а оставшиеся 4 коду больницы в этом городе.
Так, например,1215003001000Количество пациентов14711151923273135394347Длина госпитализацииРисунок 5.2: Распределение количества госпитализаций для пациентов выборки.Рисунок 5.3: Часть таксономии расположения больницуниверситетская больница города Нанси (код: 540002078) находитсяв районе Мёрт-е-Мосель (Meurthe et Mossel) региона Лотарингия воФранции. В данной таксономии 304 вершины.Медицинские процедуры закодированы согласно французскойклассификации “Classification Commune des Actes Médicaux” (CCAM).На алфавите состояний, описанных выше, естественной представляется следующая решёточная операция сходства.
Пусть естьдва элемента этого алфавита 1 , 2 ∈ , Здесь = ( , , , ),где – это элемента таксономии расположения больниц, напри-122мер 540002078, 1 – элемент таксономии медицинских процедур,например, химиотерапия, – множество медицинских процедур,которым подвергался пациент и – интервал повторения схожихгоспитализаций, например для исходных данных это всегда конкретное число и, если госпитализации была повторена 5 раз, то соответствующий интервал выглядит как [5, 5]. Тогда операция сходстварассчитывается как покомпонентная операция сходства компонент1 ⊓ 2 = (1 ⊓ 2 , 1 ⊓ 2 , 1 ∩ 2 , 1 ⊓ 2 ), где операции ⊓ и ⊓– операции получения наименьшего общего предка двух элементовв соответствующих таксономиях, а операция ⊓ – операция получения наименьшего интервала, покрывающего компоненты, например,[1, 3] ⊓ [4, 5] = [1, 5].Рассмотрим два подхода, которые могут быть реализованы дляанализа процессов, описанных выше.
Первый – так называемый наивный подход, который не учитывает таксономии и работает в рамках известного ранее представления последовательности, то есть последовательности, в которой каждый элемент является множеством.Второй подход использует вышеприведённую операцию сходства и,соответственно, может находить более сложные закономерности.5.3.1Наивный подход моделирования процессов госпитализацииВо многих работах [24; 30; 96; 129] каждый элемент последовательности является подмножеством некоторого множества.Такие последовательности представляют частный случай последовательностей, заданных определениями 17 и 19. В качестве первой части эксперимента посмотрим какие зависимости может обнаружить предложенный подход в данных о реализациях процесса госпитализации, представленных такими последовательностями.В этом случае невозможно рассматривать иерархии для территориального расположения и причин госпитализаций, также как и информацию о числе повторов.
Поэтому каждый элемент последо123вательности представляется как множество процедур, объединённое с именем больницы (нижний элемент иерархии территориального расположения), с причиной госпитализации (нижний элемент иерархии причин госпитализации). Например, последовательность ⟨[CH1 , Рак, {1 , 2 }]; [CH2 , Хим.Тер., {}]; [CH2 , Хим.Тер., {}]⟩ нужно переписать как ⟨{CH1 , Рак, 1 , 2 } ; {CH2 , Хим.Тер.} ; {CH2 , Хим.Тер.}⟩ . В последнем случае, каждый элемент последовательности, рассматривается как множество равнозначных элементов.При таком описании процесса госпитализации, алфавитная проекции имеет мало смысла и, поэтому, рассматриваются только ПМДпроекции. Таблица 5.2 показывает время построения и размеры решёток для разных проекций. Так, например, для проекции, допускающей только последовательности не короче двух элементов (ℓ = 2),решётка строится за 4510 секунд и содержит 554332 понятий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
