Проблема извлечения знаний

 

w1 – количество  кальцинозов / cм3; 

w2 – объем  кальциноза, cм3;

w3 – общее  количество кальцинозов. 

Мы рассматриваем  признак x1 как функцию ν(w1, w2, w3), которую  надо определить. 

Аналогично, новый признак: x2 – «Форма и плотность  кальциноза» со значениями ((1) –  «рак» и (0) – «доброкачественная») является обобщением признаков:

y1 – «нерегулярность  в форме индивидуальных кальцинозов»,  

y2 – «изменение  в форме кальцинозов»,

y3 – «изменение  в размере кальцинозов»,

y4 – «изменение  в плотности кальцинозов», 

y5 – «плотность  кальцинозов». 

Мы рассматриваем x2 как функцию x2 = ψ(y1, y2, y3, y4, y5), которая  должна быть определена для диагностики  рака.

В результате мы получим декомпозицию задачи определения  булевой функции  f(x1, x2, x3, x4, x5) как  это представлено на рис. 1. 

Будем предполагать,  что следующие признаки имеют  бинарные значения 0 – «доброкачественный», 1 – «рак» : 

x1 – «количество  и объем, занятый кальцинозами»; 

x2 – «форма  и плотность кальцинозов»;

x3 – «ориентация  протоков»; 

x4 – «сравнение  с предыдущей экспертизой»;

x5 – «ассоциированные  результаты исследования». 

3. Свойство  монотонности

Чтобы понять,  как монотонность может быть использована для диагностики рака груди, рассмотрим оценку кальцинозов в маммограмме. Используя данные выше определения, мы можемпредставить клинические случаи в терминах бинарных векторов с пятью  обобщенными признаками (x1, x2, x3, x4, x5).  Рассмотрим два клинических случая,  которые представлены двумя двоичными  последовательностями: (10110)  и (10100).  Если радиолог правильно диагностировал

 

 

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

Это заключение основано на кодировании всех признаков  «подозрительных на рак»  как 1.

Заметим, что в (10100) мы имели два показания  для рака: 

x1 = 1  (количество  и объем кальцинозов со значением  1; указание на рак);

x3 = 1  (протоковая  ориентация, имеющая значение 1; подозрительна  на рак). 

Во втором клиническом случае (10110) мы имеем  эти два наблюдения для рака и  также x4 = 1 (сравнение с предыдущими  экспертизами, подозрительными на рак). Аналогично, если мы знаем, что (01010) не подозрительно на рак, то и случай (01000) также нельзя считать подозрительным.

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

Медику-эксперту было объяснено свойство монотонности и диалог,  который следовал, подтверждал  законность предположения.  Точно  так же функция x2 = ψ(y1, y2, y3, y4, y5)  для  обобщенного признака  x2  «форма и плотность кальциноза»  была подтверждена как монотонная Булева функция. 

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

Таким образом,  основными шагами извлечения правил из медика-эксперта являются следующие:

― разработать  иерархию понятий и представить  их как ряд монотонных Булевых  функций; 

― восстановить каждую из этих функций минимальной  последовательностью вопросов эксперту; 

― объединить обнаруженные функции в полную диагностическую  функцию;

― представить  полную функцию как традиционный набор диагностических правил вида «если–то».

Опишем  далее шаг восстановления каждой монотонной Булевой функции с  помощью минимального количества вопросов к эксперту. Это предусматривает интервьюирование эксперта с помощью минимальной динамической последовательностью вопросов. Эта последовательность основана на фундаментальной лемме Hansel [Hansel G., 1966, Kovalerchuk B., Talianski V., 1996].

Мы опускаем детальное описание математических шагов. Они могут быть найдены  в [Kovalerchuk B., Talianski V., 1996].  Общая идея дается на примере интерактивной  процедуры в табл. 1.

Минимальная последовательность вопросов означает, что мы достигаем минимума Шенноновской функции,  т. е.  за минимальное количество вопросов мы можем восстановить самую сложную монотонную Булевую функцию с n  аргументами.  Последовательность вопросов не написана заранее.  Она зависит от предыдущих ответов эксперта,  поэтому каждый последующий вопрос определяется динамически. Таблица 1 иллюстрирует эту последовательность. 

Столбцы 2 и 3 представляют собой значения определенных выше функций f и ψ. Мы опускаем восстановление функции ν(w1, w2, w3),  потому что нужно немного вопросов для восстановления этой функции, но общая схема – та же самая, что и для функций f и ψ и начинается с рассмотрения всех бинарных наборов троек (010), (110). 

В таблице  первый вопрос: «Представляет ли последовательность (01100)  случай, подозрительный на рак  или нет?» Здесь, x1 = 0 и (01100) = (x1, x2, x3, x4, x5). Если ответ «да» (1), то следующий вопрос будет о подозрительности на рак случая (01010).  Если ответ  «нет» (0),  то следующий вопрос будет о подозрительности на рак случая (11100).  Эта последовательность вопросов не случайна. Как было упомянуто выше, это выведено из леммы Hansel [Hansel G., 1966].

Все 32 возможных  случая для пяти бинарных признаков (x1, x2, x3, x4, x5) представлены в столбце 1 табл. 1.  Они сгруппированы в группы и называются цепями Hansel [Hansel G., 1966].

Последовательность  цепей начинается с самой короткой цепи «цепь 1» (01100) и (11100). Эта цепь состоит из двух случаев (01100) < (11100). Наибольшая «цепь 10» состоит из 6 случаев: (00000) < (00001) < (00011) < (00111) < (01111) < (11111). Случаи упорядочены как векторы в каждой цепи.  

Чтобы строить  цепи, представленные в табл. 1 (с  пятью измерениями, например x1, x2, x3, x4, x5 или y1, y2, y3, y4, y5), используется следующий процесс.  Каждый шаг порождения цепи состоит в использовании текущей i–размерной цепи и построения (i + 1)-размерной цепи. Поколение цепей для следующего измерения (i + 1) появляется в результате следующего процесса.

• Мы клонируем 1-мерную цепь (0) < (1) и производим ее копию  (0) < (1). 

• После  этого мы наращиваем цепь, добавляя второе измерение:

цепь 1 : (00) < (01); 

цепь 2 : (10) < (11). 

• Затем  мы отделяем главный случай (11) от цепи 2 и добавляем его в качестве головы к цепи 1, создавая две 2-мерные цепи:

новая цепь 1 – (00) < (01) < (11); 

новая цепь 2 – (10).  

• Затем  снова клонируем цепи и добавляем 0 и 1:

(000) < (001) < (011); 

(100) < (101) < (111); 

(010) < (110).

• Отделяем главный случай:

(000) < (001) < (011) < (111); 

(100) < (101);

(010) < (110).

• Затем  снова клонируем цепи и т.д.

В результате получаем цепи из таблицы 1.

 

 

 

 

Цепи пронумерованы  от 1  до 10,  каждый случай имеет  свой номер в цепи.  Например, 1.2 означает второй случай в первой цепи. Знак « * » в столбцах 2 и 3 маркируют  ответы, полученные от эксперта.  Например, 1*  для случая (01100)  в столбце 2  означает,  что эксперт ответил  «да».

Остающиеся  ответы для той же самой цепи в  столбце 2  автоматически получены,  используя монотонность.  Признак f(01100) = 1   для случая 1.1  распространяется на случаи 1.2, 6.3  и 7.3, представленные в колонке  1→1  монотонного продолжения.  Аналогично,  используя таблицу 1, вычисляются значения второй монотонной Булевой функции ψ. Признаки в последовательности (10010) интерпретируются как y1, y2, y3, y4, y5 вместо x1, x2, x3, x4, x5, которые использовались для f.

Цепи Hansel в этом случае такие же, т.к. количество признаков тоже.

В столбцах 4  и 5  выписаны случаи,  распространяющие значения функций по свойству монотонности без опроса эксперта. Столбец 4 предназначен для расширения значений функции со значением 1, столбец 5 для распространения значений функции со значением 0. Если эксперт дал другой ответ f(01100) = 0  по сравнению с табл. 1,  то значение 0 может быть распространено  (в столбце 2) на случаи 7.1 (00100) и 8.1 (01000). Эти случаи перечислены в столбце 5  для случая (01100). Тогда нет необходимости спрашивать у эксперта случаи 7.1 (00100) и 8.1 (01000), т.к. они следуют из монотонности.  Отрицательный ответ f(01100) = 0  не может быть распространен на случай f(11100), поэтому у эксперта надо спросить относительно значения функции f(11100). Если его/её ответ отрицательный  f(11100) = 0, то эти значения могут быть распространены на случаи 5.1 и 3.1, перечисленные в столбце 5 для случая 1.2. 

Общее количество случаев со знаком « * » в столбце 1 равно 13, для столбцов 2 и 3 они равны соответственно 13  и 12.  Эти количества показывают,  что 13  вопросов необходимы для восстановления функции f  как функций от x1, x2, x3, x4, x5   и 12  вопросов необходимы для восстановления функции ψ как функций от y1, y2, y3, y4, y5.

Полное  восстановление любой функций f  с 11  аргументами без оптимизации  процесса интервью потребовало бы до  2 11

= 2048  вопросов  к медику-эксперту.  Согласно лемме  Hansel оптимальный (т. е. минимальный) диалог для восстановления монотонной Булевой функции с 11 аргументами потребовал бы не более следующего числа вопросов: Это число в 2.36  раза меньше,  чем 2048  вопросов.  Однако даже этот верхний предел 924 можно уменьшить.  Введение иерархии уменьшает максимальное количество вопросов для восстановления монотонной Булевой функции с 11 переменными до 12+13+8 = 33 вопросов. 

 Извлечение  правил, используя монотонные Булевы  функции  

Полученная  таблица позволяет явно выписать Булеву функцию экспертного правила  принятия решений.  Выпишем сначала Булеву функцию для признака  x2 = ψ(y1, y2, y3, y4, y5)  на основании информации из столбца 3, следуя следующим шагам: 

i) найти  все максимальные нижние единицы  для всех цепей в виде элементарных  конъюнкций; 

ii) исключить  избыточные термины (конъюнкции) из окончательной формулы. 

Таким образом, из столбца 3 мы получим x2 = y2y3 ∨ y2y4 ∨ y1y2 ∨ y1y4 ∨ y1y3 ∨ y2y3y4 ∨ y2y3y5 ∨ y2 ∨ y1 ∨ y3y4y5 .

В цепях 1-5, 8-9 нижними единицами являются минимальные  элементы цепей, поэтому соответствующие им конъюнкции состоят из двух элементов для цепей 1-5 и одному элементу для цепей 8-9,  а в цепях 6-7, 10  минимальными единицами являются соответственно элементы (01110), (01101), (00111), которым соответствуют конъюнкции y2y3y4, y2y3y5, y3y4y5.

Полученную  дизъюнкцию конъюнкций можно упростим до выражения

x2 = ψ(y1, y2, y3, y4, y5) = y2 ∨ y1 ∨ y3y4y5.

Из столбца 2 мы получим Булеву функцию от переменных x1, x2, x3, x4, x5 для диагностики рака f(x) = x2x3 ∨ x1x2x4 ∨ x1x2 ∨ x1x3x4 ∨ x1x3 ∨ x3x4 ∨ x3 ∨ x2x5 ∨ x1x5 ∨ x4x5.

Эту дизъюнкцию можно упростим до выражения:

f(x) =  x1x2 ∨ x3 ∨ (x2 ∨ x1 ∨ x4)x5 

Для функции  ν(w1, w2, w3)  второго уровня иерархии мы в интерактивном режиме получили следующую функцию

x1 = ν (w1, w2, w3) = w2 ∨ w1w3.

Объединяя все функции, получим Булеву функцию  для всех 11 признаков f(x) = x1x2 ∨ x3 ∨ (x2∨x1∨x4)x5 = (w2∨w1w3)(y1∨y2∨y3y4y5) ∨ x3 ∨ (y1∨y2∨y3y4y5 ∨ w2∨w1w3 ∨ x4)x5 .

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

1. Hansel G. Sur le nombre des fonctions Boolenes monotones den variables, C. R. Acad. Sci. Paris (in French). 1966.

Vol. 262, №  20. P. 1088–1090.

2. Kovalerchuk B., Vityaev E., Ruiz J.F. Design of consistent system for radiologists to support breast cancer diagnosis //

Joint Conf. of Information Sciences, Duke University,  NC, 1997. Vol. 2. P. 118–121. 

3. Kovalerchuk, B., Vityaev, E., Ruiz, J. Consistent Knowledge Discovery in Medical Diagnosis. IEEE Engineering in

Medicine and Biology Magazine. Special issue: «Medical Data Mining», July / August, 2000. P. 26–37.

4. Kovalerchuk, B., Vityaev, E., Ruiz, J.F. Consistent and Complete Data and «Expert»  Mining in Medicine // Medical

Data Mining and Knowledge Discovery, Springer. 2001. P. 238–280.

5. Kovalerchuk B., Talianski V. Comparison of empirical and computed fuzzy values of conjunction // Fuzzy Sets and

Systems. 1996. Vol. 46. P. 49–53.

6. Kovalerchuk B., Triantaphyllou E., Ruiz J. Monotonicity and logical analysis of data: a mechanism for evaluation of

mammographic and clinical data,  in Kilcoyne RF, Lear JL, Rowberg AH (eds): Computer applications to assist radiology,

Carlsbad, CA, Symposia Foundation. 1996. P. 191–196.

7. Wingo P.A., Tong T., Bolden S. Cancer Statistics, Ca-A Cancer Journal for Clinicians. Vol. 45, № 1. P. 8–30.