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

Размещено на http://www.allbest.ru/

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

Н.А. Новоселова

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

Введение

Системы анализа данных, позволяющие генерировать множество классифицирующих правил с использованием набора данных широко используются в биологии, медицине и других областях. В последнее время широкое распространение получили нечеткие системы классификации, которые позволяют улучшить процесс классификации за счет возможности использования перекрывающихся классов, а также получить интерпретируемые результаты за счет открытой структуры нечеткой модели. Традиционно нечеткие системы строились на основе знаний экспертов в виде лингвистических высказываний. Новым направление является разработка методов построения нечетких классификаторов с использованием имеющихся числовых данных измерений. К таким методам относятся нейросетевые нечеткие методы [Nauck et al., 1999], методы генерирования нечетких классифицирующих правил на основе генетического алгоритма (ГА) [Ishibuchi et al., 1999], нечеткая кластеризация в комбинации с ГА-оптимизацией [Setnes et al., 2000]. Однако большинство разработанных методов акцентировалось на получении более точной классификации в ущерб интерпретируемости результатов. В данной статье рассматривается метод построения нечеткого классификатора с использованием результатов субтрактивной кластеризации. Использование субтрактивной кластеризации позволяет получить компактную начальную структуру нечеткого классификатора, параметры которого в дальнейшем могут быть оптимизированы с использованием обучающих алгоритмов, известных из области искусственных нейронных сетей. Использованием специальных методов оптимизации структуры нечеткого классификатора - алгоритмов отбора признаков для классификации и упрощения набора решающих правил на основе критериев сходства - позволяет в дальнейшем улучшить интерпретируемость результатов.

1. Нечеткая модель для классификации или нечеткий классификатор

Предлагаемая нечеткая модель для классификации отличается от классической и состоит из набора нечетких классифицирующих правил R_i, каждое из которых определяет принадлежность к каждому из имеющихся классов N_c с некоторой вероятностью. Предпосылки правил представляют собой нечеткие высказывания в n-мерном пространстве признаков, а следствия правил являются четкими значениями вероятностей принадлежности к классам c₁,c₂,…,c_Nc:

R_i: Если x_1,k это A_i1 и … x_n,k это A_in, тогда

y_k=с₁ с вероятностью P(c₁|R_i),…, (1.1)

y_k= c_Nc с вероятностью P(c_Nc|R_i), i=1,…,M,

где n - количество признаков, x_k=[x_1,k; x_2,k;…,x_n,k]^T - входной вектор признаков; y_k - выходы R_i-го правила, определяемые вероятностями P(c_j|R_i) принадлежности к классам c_j j=1,…, N_c; A_i1,…,A_in - нечеткие множества предпосылки. Для логической связки отдельных элементов предпосылки используется оператор произведения. Степень активации i-го правила вычисляется следующим образом:

. (1.2)

Подобно нечеткой модели Такаги-Сугено [Yager et al., 1984] правила нечеткой модели для классификации агрегируются с использованием нормализованного нечеткого среднего для каждого из определенных в следствиях правил классов. Выход классификатора определяется меткой класса, который имеет наивысшую активацию:

. (1.3)

Основным преимуществом представленного классификатора (1.1-1.3) является то, что нечеткая модель может состоять из некоторого числа правил превышающего количество классов и каждое правило может определять более одного класса. В разделе 3 представлен метод построения представленного выше классификатора с использованием субтрактивной кластеризации.

2. Метод субтрактивной кластеризации

Метод субтрактивной кластеризации не требует задания начального количества кластеров [Yager et al., 1984] и не является нечеткой кластеризацией, однако, его часто используют при синтезе нечетких правил из данных.

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

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

Потенциалы центров кластеров рассчитываются следующим образом:

, (2.1)

где M - количество начальных центров, N - количество объектов кластеризации, C_i=(c_1,i, c_2,i,…, c_n,i) - потенциальный центр i-го кластера, - положительная константа, - расстояние между потенциальным центром кластера C_i и объектом кластеризации X_k.

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

,

где , - положительная константа.

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

3. Нечеткий классификатор на основе субтрактивной кластеризации

Пусть V₁, V₂,…, V_c - центры кластеров, найденные в результате субтрактивной кластеризации. Каждый отдельный центр кластера является центром нечеткого правила, для которого функции принадлежности, определяющие набор нечетких множеств для каждого признака предпосылки этого правила, задаются в виде экспоненциальных функций следующим образом:

,(3.1)

где A_i,j - нечеткое множество соответствующее нечеткому правилу j для признака i, - i-ая координата вектора признаков , - i-ая координата центра кластера , - стандартное отклонение экспоненциальной функции, зависящее от кластерного радиуса R_i и постоянной величины .

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

. (3.2)

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

.

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

нечеткий классификатор кластеризация субтрактивный

Размещено на http://www.allbest.ru/

Рис. 1. Пример нечеткой модели классификации с двумя решающими правилами

Первый слой нейросетевого представления модели выполняет раздельную фаззификацию каждого признака X_i (i=1,2,…,n), определяя для каждого k-го правила вывода значение степени принадлежности нечеткому множеству A_ij в соответствии с функцией принадлежности (3.1). Это параметрический слой с параметрами V_i,j, sigma_i , который может быть адаптирован в процессе обучения сети. По мере настройки этих параметров, форма функции принадлежности может изменяться. Все параметры первого слоя нечеткого классификатора называются параметрами предпосылки.

Второй слой выполняет агрегирование отдельных признаков X_i, определяя результирующее значение уровня активации j-го правила вывода для вектора признаков X в соответствии с формулой (3.2). Это непараметрический слой.

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

.

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

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

4. Оптимизация структуры нечеткого классификатора

Мотивацией к использованию нечетких моделей для генерации классифицирующих правил является возможность их интерпретации. Структура нечеткой модели изначально позволяет не только получить достаточную точность классификации, но и понять принцип получения того, или иного результата. Однако для описания сложных систем количество правил, автоматически сгенерированных на данных, становится громоздким. Таким образом, для улучшения интерпретируемости результатов необходимым является оптимизация структуры классификатора, а именно использование алгоритмов отбора признаков для классификации и упрощение решающих правил на основе критериев сходства. В работе используется критерий Фишера разделимости между классами, основанный на статистических свойства классифицируемых данных [Fischer, 1936]. Алгоритм отбора признаков является пошаговой процедурой, где на каждом шаге наименее значимый признак исключается из нечеткой модели до тех пор, пока точность классификации не уменьшится более чем на заданное обычно небольшое значение. Для увеличения точности классификации на оставшемся наборе признаков повторно определяется новый классификатор с использованием субтрактивной кластеризации.

Для упрощения набора классифицирующих правил используется метод, описанный в работе [Setnes et al., 1998]. Алгоритм упрощения состоит в объединении двух наиболее подобных нечетких множеств с последующим обновлением набора правил. Процедура повторяется до тех пор, пока мера подобия превышает изначально заданный порог . Объединение нечетких множеств сокращает количество функций принадлежности, используемых в модели и, следовательно, улучшает интерпретируемость результатов. Если все нечеткие множества признака подобны универсальному множеству или если после объединения признаку соответствует только одна функция принадлежности, то данный признак может быть исключен из модели.

5. Пример использования предложенного метода

Для того чтобы проверить эффективность предложенного метода построения нечеткого классификатора с последующим его упрощением, был использован тестовый набор данных пациентов, обследуемых на предмет наличия или отсутствия сердечных заболеваний (heart dataset), заимствованный из архива баз данных для экспериментов в области машинного обучения Калифорнийского университета [UCI Machine Learning Repository]. Исследуемый набор данных состоит из 13 признаков, измеренных для 270 пациентов. Пациенты разделены на два класса: 1 - с отсутствием болезни сердца, 2 - с болезнью сердца. 150 объектов относятся к классу 1, 120 - к классу 2. С использованием описанного в данной работе метода был построен нечеткий классификатор, база правил которого соответствовала кластерам, полученным методом субтрактивной кластеризации, и состояла из 4-х правил. Точность классификации построенной нечеткой модели на обучающем множестве составила 80.4%. Структура построенной модели была достаточно сложной для интерпретации, поэтому в дальнейшем она была оптимизирована с использованием алгоритма отбора признаков и упрощения набора решающих правил на основе критериев сходства. В результате было удалено 6 признаков, причем точность классификации повысилась и стала составлять 81.5%, в то время как набор нечетких правил стал более компактным (рис.2).

В табл. 1 для двух полученных нечетких правил классификации представлены вероятности принадлежности к классам.

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

Табл. 1.

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

Рис.3. Вид двух функций принадлежности для трех признаков

Средняя точность классификации на тестовых множествах с использованием метода перекрестной проверки составила 81.3%. Таким образом, была получена удовлетворительная точность классификации, а нечеткий классификатор состоял из 2 нечетких правил с использованием 7 признаков.

Для сравнения и оценки эффективности результатов с использованием нечеткой модели были построены классические классификаторы с использованием метода дискриминантного анализа и классификационных CART-деревьев [Breiman et al., 1984]. Точность классификации объектов с использованием 7 отобранных ранее признаков методом дискриминантного анализа составила 79.6%, а полученные классификационные функции были достаточно сложными для интерпретации результатов. Классификационное CART-дерево, позволило классифицировать объекты с точностью 83%, однако количество правил, которые были выделены из структуры дерева, возросло до семи.

Заключение

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

Список литературы

1. [Breiman et al., 1984] Breiman L., Friedman J. H., Olshen R. A. and Stone C. J.. Classification and regression trees // Monterey, Calif., U.S.A.: Wadsworth, Inc., 1984.

2. [Fischer, 1936] Fischer R. A. The use of multiple measurements in taxonomic problems // Ann. Eugenics, 1936, 7:179-188.

3. [Ishibuchi et al., 1999] Ishibuchi H., Nakashima T. and Murata T. Performance evaluation of fuzzy classifier systems for multi-dimensional pattern classification problems // IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 29, no. 5, 1999.

4. [Nauck et al., 1999] Nauck D., Kruse R. Obtaining interpretable fuzzy classification rules from medical data // Artifcial Intelligence in Medicine 16, 1999.

5. [Setnes et al., 1998] Setnes M., Babuska R., Kaymak U., van Nauta Lemke H.R. Similarity measures in fuzzy rule base simplification // IEEE Trans. SMC-B 28, 1998.

6. [Setnes et al., 2000] Setnes M., Roubos J.A. GA-fuzzy modeling and classification: complexity and performance // IEEE Trans. FS, 2000.

7. [Yager et al., 1984] Yager R., Filev D. Essentials of Fuzzy Modeling and Control // USA: John Wiley & Sons., 1984.

8. [UCI Machine Learning Repository] http://www.ics.uci.edu/~mlearn/MLRepository.

Размещено на Allbest.ru