close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
7. Zlotko A.A. IT management starts from Service Desk.
T-Comm: Telekommunikatsii i transport [T-Comm – Telecommunications and Transport]. Media Publ., 2010, no. 3, pp. 28–31 (in
Russ.).
8. Dehinbo O.J. Enhancing service desks customers relationship management in a South African contact and e-service organizations. Proc. of the World Congress on Engineering and Computer
Science 2011 (WCECS 2011), San Francisco, USA, 2011, vol. I,
pp. 72–78.
9. Romanenko A.G., Leshchev V.I. Organizing technical
support service for information systems in company. Mezhotraslevaya informatsionnaya sluzhba [Interindustry information service].
2007, pp. 26–36 (in Russ.).
10. Halverson C.A., Erickson T., Ackerman M.S. Behind the
Help Desk: evolution of a knowledge management system in a large organization. Proc. of CSCW 2004. NY, ACM Press, 2004,
pp. 304–313.
11. Desyatov A.D., Sirota A.A. Evaluation of response time
УДК 004.855.5, 004.853
when managing structural dynamics of a complex system (in case
of IT company support service). Vestnik Voronezhskogo gos. univ.,
Seriya: Sistemny analiz i informatsionnye tekhnologii [The bulletin
of Voronezh State Univ. “System analysis and IT” series]. 2009,
no. 1, pp. 5–12 (in Russ.).
12. Grishakov V.G., Loginov I.V., Khristenko D.V. Administrative management of mis modernization based on lifecycle information support. Informatsionno-upravlyayushchie sistemy [Information and Control Systems]. Politekhnika Publ., 2012, no. 3 (58),
pp. 84–90 (in Russ.).
13. Bakaev V.V., Sudov E.V., Gomozoev V.A. Informatsionnoe obespechenie, podderzhka i soprovozhdenie zhiznennogo tsikla
izdeliya [Information support and maintenance for a product life
cycle]. Moscow, Mashinostroenie-1 Publ., 2004, 624 p.
14. Grishakov V.G. IT infrastructure hybrid model support
system using external services. Informatsionnye sistemy i tekhnologii [Information systems and technologies]. 2012, no. 2, pp. 39–47
(in Russ.).
Дата подачи статьи: 10.06.2014
АЛГОРИТМ КЛАССИФИКАЦИИ ГРАФИКОВ С ПОСЛЕДОВАТЕЛЬНЫМ
УКРУПНЕНИЕМ ПРИЗНАКОВ
Н.Н. Филатова, д.т.н., профессор; Д.М. Ханеев, аспирант; К.В. Сидоров, аспирант
(Тверской государственный технический университет,
наб. Аф. Никитина, 22, г. Тверь, 170026, Россия, nfilatova99@mail.ru)
Для решения ряда прикладных задач могут оказаться полезными классификаторы, работающие с выборками
двухмерных графических зависимостей. В статье рассматривается новый подход к решению задачи классификации
графических зависимостей, объединяющий ее с задачей сегментации. Описывается алгоритм выделения интервальных последовательно укрупненных признаков при работе классификатора на основе нейроподобной иерархической
структуры. Данный классификатор основан на идее растущей пирамидальной сети, адаптированной для работы с нечеткими описаниями объектов. В процессе обучения в иерархической структуре классификатора формируются модели классов, которые интерпретируются в нечеткие высказывания (правила) для системы нечеткого логического
вывода. Нечеткие высказывания отражают основные характеристики всех объектов обучающей выборки и представляются в понятной эксперту форме. Интервалы укрупнения признаков находятся путем анализа правил, полученных
после обучения классификатора на первичных данных. Алгоритм автоматической генерации интервальных признаков позволяет локализовать участки с одинаковыми значениями нечетких признаков, что фактически приводит к
сегментации исследуемых графических зависимостей на участки с близкими оценками их структурных свойств.
Особенности работы алгоритма выделения последовательно укрупненных признаков подробно рассмотрены на примере искусственно сформированных данных. Программная реализация алгоритма протестирована на искусственно
сформированных данных, а также на реальных клинических данных, представленных записями дыхательных шумов,
речевых сигналов и электроэнцефалограмм. В статье исследовано влияние применения последовательно укрупненных признаков на результаты успешности классификации рассмотренных данных.
Ключевые слова: нейроподобная иерархическая структура, растущие пирамидальные сети, сигнал, графическая
зависимость, алгоритм, нечеткое множество, обучающая выборка, тестовая выборка, сегментация.
Received 10.06.2014
DIAGRAMS CLASSIFICATION ALGORITHM WITH CONSEQUENT ENLARGING OF FEATURES
Filatova N.N., Dr.Sc. (Engineering), Professor; Khaneev D.M., Postgraduate Student; Sidorov K.V., Postgraduate Student
(Tver State Technical University, Quay Nikitin, Tver, 22, 170026, Russian Federation, nfilatova99@mail.ru)
Abstract. In order to solve a number of applied tasks the classifiers for samples of two-dimensional graphic dependencies could be useful. The paper discusses a new approach to solving the problem of graphic dependences classification combining it with the segmentation problem. The article also describes an algorithm of interval consequently enlarged features allocation when the classifier works based on neuron-like hierarchical structure. This classifier is based on the idea of growing
pyramidal network that is adapted for work with fuzzy objects descriptions. While learning, the classes models are being
formed in the classifier hierarchical structure. The models are interpreted to fuzzy expressions (rules) for fuzzy inference system. The fuzzy expressions reflect the major characteristics of all objects of training set and are presented in a form understandable for an expert. Features enlarging intervals are obtained by analyzing the rules after training the classifier on primary data. The algorithm of interval features automatic generation allows localizing areas with the same values of fuzzy
features. This actually results in investigated graphic dependences segmentation on areas with similar structural properties estimation. The operational peculiarities of consequentially enlarged features allocation algorithm are discussed in detail on the
example of an artificially generated data. The algorithm software implementation is tested on artificially generated data and
78
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
on real clinical data (recordings of respiratory sounds, voice and electroencephalograms). The paper studies consistently enlarged features application influence on success of the examined data classification results.
Keywords: neural-like hierarchical structure, growing pyramidal networks, signal, graphical dependance, algorithm,
fuzzy set, training set, test set, segmentation.
нечеткими описаниями объектов и дополненной
системой нечеткого логического вывода. Исследование особенностей работы подобных алгоритмов
показало, что создаваемые правила классификации на основе НИС обладают более широким
набором свойств, помимо разделения классов.
В частности, в работе [7] было отмечено, что применение подобных классификаторов позволяет
выделять на графиках интервалы с одинаковой
топологией (характером изменений). Эти результаты позволяют по-новому взглянуть на общую
стратегию решения задач классификации графических зависимостей, объединив ее с задачей сегментации сигналов [8].
В системах автоматической диагностики широко используются средства классификации объектов, представленных дискретным набором признаков. Успешность решения задачи во многом
зависит от соблюдения компромисса между числом признаков и точностью описания свойств
объектов. Очевидно, что при повышении точности
отображения свойств необходимо увеличивать количество признаков. Однако чрезмерная детализация и внимание к субъективным особенностям
объектов могут привести к усложнению алгоритмов классификации и увеличению ошибок. Это
особенно часто проявляется при создании нейросетевых классификаторов. Анализ выборок описаний объектов можно построить на основе последовательного расширения признаков, что связано
с уточнением деталей в описании объекта. Но при
таком подходе возникает вопрос о том, какие признаки необходимо добавлять. Более простым, на
взгляд авторов, является построение классификаций на основе идей последовательного формирования вторичных понятий, которые позволяют
укрупнять признаки, создавая, в конце концов, лаконичные описания классов объектов наиболее
общими признаками [1].
Для решения ряда прикладных задач могут
оказаться полезными классификаторы, работающие с выборками двухмерных графических зависимостей. Задача анализа графических зависимостей подробно рассматривается в работах [2–5].
В работе [6] был предложен новый подход к решению этой задачи на основе создания нейроподобной иерархической структуры (НИС). Он
представляет собой развитие идеи растущей пирамидальной сети, адаптированной для работы с
Описание объектов классификации
Исходные графики, являющиеся объектами
классификации, обычно представлены большим
числом точек. Если каждую точку графика использовать как признак, размерность вектора описания объекта может возрасти до нескольких тысяч признаков. В то же время визуальный анализ
графических зависимостей, выполняемый экспертом, как правило, сводится к выделению не более
десяти качественных признаков, характеризующих морфологические (или топологические) особенности. Например, на рисунке 1 приведены графики спектров мощности дыхательных шумов,
каждый из которых можно представить вектором
из 200 признаков.
Приведенные примеры говорят о существовании большого разброса значений спектров мощности на всех частотах для всех объектов класса
Патология. Аналогичный вывод получается и при
95
HI
HI
MID
LOW
MID
65
Supp(10)
35
LOW
Supp(30)
5
0
20
40
60
80
100
120
140
160
180
200
– Патология
– Норма
Рис. 1. Графическое представление спектров мощности дыхательных шумов:
абсцисса – номер признака (шаг по частоте 11 Гц); ордината – значение спектра мощности
Fig. 1. Graphical representation of respiratory noises power spectrum:
abscissa – feature number (frequency step 11 Hz); ordinate – power spectrum value
79
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
оценке свойств класса Норма. Эти факты, а также
существующие индивидуальные особенности источников сигналов (субъективные особенности
пациентов) позволяют выдвинуть гипотезу о целесообразности перехода к лингвистическим переменным при описании подобных графиков.
Пусть координаты точек графика по оси абсцисс рассматриваются как список признаков. Тогда для каждого признака его значение будет
определяться как нечеткое множество, Supp которого задается на оси ординат. Таким образом, нечеткими становятся все оценки ординат точек
графика.
Для нелинейных графиков разброс значений
каждого признака на множестве объектов одного
класса будет различный. В связи с этим для фазификации каждого признака необходимо создавать
индивидуальную лингвистическую шкалу. Так как
все признаки характеризуют точки одного графика, для построения всех нечетких шкал можно использовать одно и то же терм-множество, включающее три терма: HI, MID, LOW (рис. 1).
Тогда описанию графика вида X={x1, x2, …, xi,
…, xu}, где xi – координаты i -й точки и шаг по оси
абсцисс постоянный, будет соответствовать множество пар вида
200
XF = ∪ {(T1 \ µ1 ), (T2 \ µ 2 ), (T3 \ µ3 )}i ,
i =1
где µ1,2,3 – соответствие значения признака терму
T1,2,3.
Подобная процедура фазификации применяется в алгоритме классификации графических зависимостей, построенных на основе НИС [6]. В результате работы алгоритма для n классов обучающей выборки формируются n классификационных
правил, которые отражают основные характеристики всех объектов обучающей выборки с соответствующими разделительными метками.
В рабочем режиме интеграция созданной НИС
и алгоритма нечеткого логического вывода позволяет определить для каждого нового объекта
класс, степень принадлежности объекта к которому является максимальной.
Проведенный анализ результатов работы НИСклассификатора [7] показал, что программа позво-
ляет локализовать участки с одинаковыми значениями нечетких признаков, но это фактически
приводит к сегментации наших графиков на участки с близкими оценками их структурных
свойств.
Выдвинута гипотеза о возможности использования процедуры сегментации графиков для формирования нового пространства укрупненных
признаков. Для проверки этого предположения
создан новый алгоритм, расширяющий возможности НИС-классификатора.
Алгоритм генерации
интервальных признаков
Рассмотрим решение задачи классификации на
примере двух классов графиков. Для каждого
класса определяется собственный набор значимых
признаков Mk; k = 1, K , K – количество классов.
На каждом множестве Mk (рис. 2) выполняется
поиск участков, внутри которых лингвистическая
переменная признака принимает одинаковые значения. Такие участки множества Mk будем называть интервалами постоянства:
 P = P , i = m, z

i
i +1




для ∀M k при i = z , Pz +1 ≠ Pz
,


ɶ
ɶ
ɶ
интервал Ink , m : Pm , Pm +1 , …, Pz 


где i – номер признака; Pɶ – нечеткое значение
(
)
i
признака Pi.
На рисунке 2 представлено описание фрагмента временного ряда (графика), представляющего
собой конъюнкцию признаков (107∧118∧…∧258).
Для объектов класса 1 из описания выделено
множество M1, в котором все признаки (указанные
в конъюнкции) имеют значение «HI» (однако следует отметить, что основания у всех термов могут
быть разные в зависимости от состава обучающей
выборки (ОВ)). Особенность фазификации признаков рассмотрена в работе [7].
В классе 2 выделяется множество M2, в котором все признаки (указанные в конъюнкции) имеют значение LOW. Множества M1 M2 имеют пересечение: PP=M1∩M2= 150, 161, 172, 183, 193, 204,
P_ln 1,0
ln 1,0
ln 1,13
№
Имя
0
107
1
118
2
129
3
139
4
150
5
161
6
172
7
183
8
193
9
204
10
215
11
226
12
236
13
247
14
258
М1
hi:17
hi:17 hi:17
hi:17
hi:17
hi:17
hi:17
hi:17
hi:17
hi:17
hi:17
hi:17 mid:7
hi:16
hi:17
mid:7
mid:7 low:8 low:8 low:8 low:8 low:8 low:8 low:8 low:8 low:8 low:8 low:8
М2
ln 2,4
P_ln 2,4
Рис. 2. Пример распределения значимых признаков двух классов
Fig. 2. Example of two classes significant features distribution
80
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
215, 226, то есть объекты класса 1 имеют высокие
значения этих признаков, а для объектов класса 2
характерны малые значения этих же признаков. Из
приведенного примера следует, что на всем выделенном интервале PP первичные признаки имеют
одинаковые значения по лингвистической шкале.
Значения изменяются только при переходе из одного класса в другой. Отмеченная закономерность
позволяет рассматривать весь выделенный интервал признаков PP как новый признак PP4-11, который характеризует целый фрагмент графика (временного ряда).
Процедура введения нового признака включает
следующую последовательность действий.
Определяются пересечения классов на выделенных интервалах признаков (∀k) Ink,m.
Пусть имеется фрагмент описания класса 1
11
ем PP4–11 для объекта l1 будет множество точек на
интервале (P3≤P2≤P1)::∆P. Интервал ∆P будет рассматриваться как Supp(PP), то есть носитель нечеткого множества PP. Вершина ܲܲ соответствует
середине интервала ∆P.
При рассмотрении участка (f1, fn) на всех объектах обучающей выборки получаем конечное
число нечетких множеств (рис. 4) l1, l2, …, lk=L.
Объединяя все эти нечеткие множества, получим
новое нечеткое множество, определяющее значение нового признака: PP4–11 = l1∪l2∪ …∪lk.
lk l2
l1
M
In1,0 = ∪ Pi ; Кл1 = ∪ Pi . Фрагмент описания класi =0
i
14
T
i =4
k
са 2 In2,4 = ∪ Pi ; Кл2 = ∪ Pk , где T, M – число признаков, определяющих класс 1 и класс 2 соответственно, причем (∀i) {Pi∈In1,0Pi=HI}, (∀i)
{Pi∈In2,4Pi=LOW}.
Введем новый признак (PP4–11), общий для In1,0
и In2,4 (значения признаков не важны, они могут
различаться). Тогда на всем интервале образуются
свои подынтервалы для каждого из классов:
PIn1,0 ⊆ In1,0 , P _ In2,4 ⊆ In2,4 , P_In1,0 и P_In2,4 содержат одни и те же признаки, но значения неодинаковые. Для использования подынтервала P_In1,0
в качестве самостоятельного признака необходимо рассмотреть объединение нечетких множеств.
Рассмотрим объединение на примере подынтервала P_In1,0(f1, fn), который описывается одноименными термами и может рассматриваться как
значение нового признака PP4–11 (рис. 3). Значени-
Pk
∆P
P1
Рис. 4. Нечеткие множества нового признака
Fig. 4. New feature fuzzy sets
Основанием PP4–11 является интервал [minPP,
maxPP]. Используя эту процедуру, можно построить для нового признака всю лингвистическую
шкалу, то есть определить новые значения. Например: HI PP4−11 = HI l1 ∪ HI l2 ∪ ...∪ HI lk . В итоге
можно изменить описания классов:
m
P1
4 −11 ); PP
4 −11 = P _ In ,
Кл1 = ∪ Pɶi ∪ ( PP
1,0
i=0
t
∆P
4 −11 ); PP
4−11 = P _ In ,
Кл2 = ∪ Pɶk ∪ ( PP
2,4
P2
k =0
P3
l1
l2
f1
fn
P_ln1,0
Рис. 3. Объединяемые признаки
Fig. 3. Unified features
где m=M\PP4–11; t=T\PP4–11.
Из старых признаковых пространств классов
удаляются подынтервалы PIn1,0 , P _ In2,4 и добавляется новый признак PP4–11 (рис. 5). В описаниях
классов участвуют значения признаков, поэтому
1 = (Кл1\P_In1,0) ∪ PP
4 −11 , Кл
2 = (Кл2\P_In2,4)
а) Кл
4 −11 ; б) значения удаляемых признаков равны
∪ PP
значению нового признака. Если условие (б) не
выполняется, то есть ∪ Pɶi ≠ Pɶ4 −11 , нужно корректировать границу подынтервала, изменяя число
объединенных признаков, вошедших в PP4–11.
81
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
№ признака
Имя признака
0
107
Класс 1 (К1)
hi:17
Класс 2 (К2)
1
118
2
129
hi:17
hi:17
3
139
mid:7
4 (PP4-11)
150–226
5
236
6
247–258
hi:17
hi:17
mid:17
hi:17
mid:7
low:8
Рис. 5. Распределение признаков после обучения НИС на новом признаковом пространстве
Fig. 5. Features distribution after training NIS on the new feature space
ния классу 1 поставлены в соответствие два контрольных элемента (КЭ), классу 2 и классу 3 – по
одному КЭ (рис. 7).
Выдвинута гипотеза о том, что такое распределение КЭ связано с тем, что класс 1 имеет два пересечения (1–2, 1–3), а классы 2 и 3, соответственно, имеют по одному пересечению.
Алгоритм построения классификационных
правил включает в правила выделения класса 3
признаки из КЭ, описывающие участок 0<X<27,
на котором класс 3 имеет существенное расстояние от классов 1 и 2 (линейно разделим). Аналогичная ситуация наблюдается в правиле для
класса 2, в котором КЭ использует признаки, характеризующие объекты, от X>28, на этом участке
значения Y класса 2 существенно превышают значения объектов класса 1 и класса 3.
С учетом монотонности изменения X на выделенных интервалах, которые отражены в КЭ, для
класса 2 и класса 3 формируются вторичные признаки. Для класса 3 вторичный признак описывает
интервал 0<X<27. Для класса 2 НИС позволяет
выделить интервал 48<X<91, который не содержит
промежутков, использующихся для идентификации объектов других классов. Это позволило интервал X>48 также конвертировать во вторичный
признак (PP48–90).
Анализ выборки показывает, что выделение
таких интервалов классификатор осуществляет
для участков, на которых соответствующий класс
Тестирование алгоритма
на искусственных данных
Искусственная ОВ представлена тремя классами монотонных линейных графиков (рис. 6).
Графики класса 1 характеризуются наибольшей
производной dy/dx, значение которой во всем интервале меньше 0. Максимальное значение производной лежит в интервале 0<X<10. Графики класса 2 имеют производную в абсолютной величине,
близкую к нулю. Графики классов 1 и 2 имеют пересечение на интервале 0<X<25. Графики класса 3
имеют такой же характер производной, как и графики класса 2, однако значения по оси ординат (Y)
класса 3 всегда меньше значений Y класса 2 (графики класса 2 лежат выше класса 3). Графики
класса 3 пересекаются с графиками класса 1 на
интервале 35<X<70. При X>70 объекты класса 1 и
класса 3 идут параллельно друг другу, пересечений нет, но оба имеют объекты, лежащие у самой
границы классов.
Общая характеристика трех классов: графики
во всех трех классах представлены полосой одинаковой ширины во всем диапазоне X, таким образом, они могут рассматриваться как 3 нечетких
графика (нечеткими являются значения по оси ординат (Y), X – четкая величина).
Три класса графиков использованы в качестве
ОВ для НИС, каждый график представляется в
НИС с помощью 91 признака. В результате обуче-
4,5
6
Класс 1
5
Класс 2
4,25
Класс 2
4
4
3,75
3
Класс 3
3,5
2
0
10
20
30
40
50
60
70
80
90
60
62,5
65
67,5
Рис. 6. Графические зависимости, представленные в ОВ искусственных данных
Fig. 6. Graphical dependencies presented in an artificial data training set
82
70
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
№
0
1
2
0
Имя 28 29
27
КЭ1.1
hi mid mid
К1
:18 :19 :19
КЭ2.1
hi hi
К2
:22 :22
КЭ3.1
low low low
К3
:22 :22 :22
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
20 21
48
47 90
КЭ1.1
low
:19
КЭ1.2
mid mid mid mid mid
:19 :19 :19 :18 :17
hi hi hi hi hi hi hi hi hi hi hi hi hi hi hi hi hi hi hi
:22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22 :22
low low low
:22 :22 :22
Рис. 7. Распределение признаков по классам после обучения НИС на ОВ искусственных данных
Fig. 7. Features distribution by classes after training NHS on an artificial data training set
наиболее сильно отделяется от других классов
(там, где расстояние между описываемым классом
и прочими наибольшее). В нашем примере для
участка X>48 таким классом является класс 2,
классы 1 и 3 на участке имеют существенное пересечение (фактически сливаются). На участке
X≤28 наибольшее расстояние от других классов
имеет класс 3.
Таким образом, для классификации (распознавания объектов) класса 3 выделен участок, объекты которого имеют наибольшее удаление от
прочих классов. Для выделения объектов класса 2
тоже используется участок, в котором только наиболее удаленные объекты.
Более сложными для классификации являются
объекты класса 1, НИС для их идентификации
включила в состав правила описания двух КЭ.
В классе 1 есть объекты с максимальными значениями Y из всей выборки (при X=0), а также объекты с минимальными значениями Y (70<X<80).
Выдвинута гипотеза о том, что именно такой
характер выборки привел к включению в правила
класса 1 двух КЭ, один из которых, КЭ2, определяет объекты, не лежащие на пересечении с другими классами (26<X<35), и КЭ1, который опирается на два фрагмента графиков класса 1: фрагмент 1 при X<20 включает не только объекты на
пересечении с классом 2, но и графики, имеющие
максимальное значение Y на этой выборке; фрагмент 2 содержит графики с участком X>70, на котором ординаты объектов класса принимают наименьшее значение на этой выборке.
Таким образом, в правиле для класса 1 объединяются условия для объектов, лежащих вблизи
ядра класса (КЭ2), и условия, характеризующие
объекты с минимальными и максимальными значениями признаков на выборке, несмотря на то,
что эти объекты могут находиться вблизи пересечений с другими классами (КЭ1).
Причина объединения в КЭ1 участков с максимальными значениями Y и участков с пересече-
ниями классов 1 и 2 можно объяснить нечеткостью оценки ординат графиков, так как оценки
ординат Y1 и Y2 при X<20 достаточно близки и
оказываются в области действия одного и того же
терма, то есть входят в одно и то же нечеткое
множество, итог – загрубение условий правила.
Классификационные правила, полученные с
применением алгоритма объединения признаков,
лучше описывают исследуемые классы кривых и
позволяют добиться увеличения точности классификации (табл. 1). Максимально допустимый уровень шума, обеспечивающий разделение объектов,
~ 20 %. Объекты классов 1 и 3 трудно разделить
при уровне шума свыше 21 %.
Таблица 1
Результаты эксперимента
c искусственными данными
Table 1
Results of an artificial data experiment
Параметр
Общее число
признаков
Ошибки при классификации ОВ
Ассоциативные
элементы
Множество
вершин Vc
Количество
связей
Контрольные элементы
Ошибки при классификации ТВ
Без интерваль- С интервальныных признаков ми признаками
91
52
0
0
167
247
45
61
606
771
Кл1: 2; Кл2: 2;
Кл3: 1
Кл1: 4; Кл2: 2;
Кл3: 2
5 (Кл3 → Кл1)
3 (Кл3 → Кл1)
Тестирование алгоритма
на реальных клинических данных
Тестирование алгоритма рассмотрено на реальных клинических данных и проведено для двух
типовых задач: классификации речевых сигналов
83
Software & Systems
Программные продукты и системы
(РС) и электроэнцефалограмм (ЭЭГ), отображающих изменение знака эмоций человека, и классификации дыхательных шумов (ДШ) человека.
Экспериментальная выборка, образцы которой
отображают изменение знака эмоций человека при
предъявлении ему видеостимулов различного эмоционального окраса, включает 210 РС (русских
фраз) различных дикторов продолжительностью
3–10 секунд, с частотой дискретизации 22 050 Гц
и разрешением 16 бит и соответствующие им 240
паттернов ЭЭГ продолжительностью по 12 секунд, с частотой дискретизации 250 Гц. Регистрация ЭЭГ проводилась по стандартной системе отведений «10-20», включающей 19 отведений
(O2-A2, O1-A1, P4-A2, P3-A1, C4-A2, C3-A1,
F4-A2, F3-A1, Fp2-A2, Fp1-A1, T6-A2, T5-A1,
T4-A2, T3-A1, F8-A2, F7-A1, Pz-A1, Cz-A2,
Fz-A1). В формировании выборки участвовали
мужчины и женщины в возрасте от 18 до 60 лет.
Экспериментальная выборка записей ДШ
представлена образцами, записанными с помощью
устройства регистрации 3M Littmann 4100, и с добавлением образцов, взятых из открытых источников (база примеров патологий Rale, 3M Littmann
collection, Unmc). Регистрация ДШ (частота дискретизации 8 кГц, разрешение 16 бит) производилась у здоровых людей и у пациентов с патологическими изменениями функции дыхания. ДШ
классифицированы экспертом (врачом высокой
квалификации с хорошим состоянием органов
слуха) на два класса: норма, патология.
В таблице 2 приведен состав экспериментальной выборки сигналов (показаны составы ОВ и
тестовых выборок (ТВ)). (Классы 1, 2, 3 – положительные эмоции, нейтральное состояние, отрицательные эмоции соответственно.)
Для описания приведенных образцов сигналов
можно применять как гомогенный, так и гетерогенный набор признаков, однако в обоих случаях
необходимо учитывать амплитудно-частотный состав сигнала. Для этой задачи в качестве разделяющих признаков могут быть использованы
спектральные характеристики, что обосновано наличием характерного частотного состава у патологических образцов ДШ и у образцов РС и ЭЭГ с
характерным эмоциональным окрасом.
Таблица 2
Структура экспериментальной выборки сигналов
Table 2
The structure of signals test sample
Сигнал Выборка
Классы объектов
ОВ (110)
РС
ТВ (100)
ОВ (90)
ЭЭГ
ТВ (150)
Классы объектов
ОВ (32)
ДШ
ТВ (37)
84
Количество объектов
Класс 1 Класс 2 Класс 3
31
29
50
39
24
37
30
30
30
50
50
50
Норма
Патология
17
15
24
13
no. 3 (107), 2014
№ 3 (107), 2014 г.
В качестве спектральных характеристик используются отсчеты спектральной плотности
мощности (СПМ (PSD)), найденные по методу
Уэлча с применением оконного быстрого преобразования Фурье (FFT) [6]. Каждый объект представляется вектором вида X={x1, x2, …, xi, …, xu},
где xi – ордината спектра мощности на частоте
fi=∆f⋅i; xi соответствует значению i-го признака; ∆f
– шаг по частоте, ∆f =fx/Fw, fx – частота дискретизации, Fw – ширина окна FFT. В работе применялось окно преобразования Хемминга (ширина
1024 для РС и ДШ, ширина 128 для ЭЭГ). Границы частотного диапазона для РС составляют
0–11 кГц, для ДШ – 0–4 кГц, для ЭЭГ – 0–125 Гц.
Описание каждого объекта выборки (табл. 2)
представляется в следующем виде:
X(l)РС=〈{x1, x2, …, xk}, X(v)ДШ=〈{x1, x2, …, xb}〉,
X(s)ЭЭГ=〈{x1, x2, …, xr}1, {x1, x2, …, xr}2, …,
{x1, x2, …, xr}z〉,
(1)
где X(l)РС, X(v)ДШ, X(s)ЭЭГ – векторы признаков
СПМ; l – номер объекта РС, l=1, …, 210; v – номер
объекта ДШ, v=1, …, 69; s – номер объекта ЭЭГ,
s=1, …, 240; z – номер отведения ЭЭГ, z=1, …, 19;
k – номер признака СПМ для РС, k=1, …, 1 000
(шаг расчета СПМ составляет 11 Гц); b – номер
признака СПМ для ДШ, b=1, …, 363 (шаг расчета
СПМ составляет 11 Гц); r – номер признака СПМ
для ЭЭГ, r=1, …, 62 (шаг расчета СПМ составляет
2 Гц).
Исследования СПМ сигналов на основе НИС
показали возможность выделения интервалов
наиболее информативных признаков, позволяющих обеспечить хороший уровень обобщения и
уточнения описания объектов в классах. Для ДШ
наиболее информативные признаки СПМ находятся в диапазоне 0–2 100 Гц (рис. 1), для РС – в
диапазоне 1 100–5 100 Гц (рис. 8). Для паттернов
ЭЭГ таковыми оказались признаки, получаемые
из отведений только правого полушария головного мозга (O2-A2, P4-A2, C4-A2, F4-A2, Fp2-A2,
T6-A2, T4-A2, F8-A2, Cz-A2) (рис. 9). В конечном
итоге каждый объект ДШ вида X(v)ДШ описывается 200 признаками, объект РС вида X(l)РС – 400, а
представление объекта ЭЭГ вида X(s)ЭЭГ рассматривается вектором из 558 признаков.
Картина распределения образцов сигналов
экспериментальной выборки по признакам СПМ
имеет довольно сложную структуру. Для образцов
ДШ (рис. 1) характерна ситуация, при которой
класс Патология имеет весьма большой диапазон
разброса значений спектра мощности, в составе
которого класс Норма имеет узкий соответствующий диапазон. Для образцов РС (рис. 8) и паттернов ЭЭГ (рис. 9) характерна ситуация множественного пересечения границ классов на всем частотном диапазоне.
С помощью НИС созданы правила, описывающие объекты ДШ (норма, патология) и объек-
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
62
57
52
47
42
37
32
100
150
200
– Класс 1;
Примечание:
250
300
350
400
450
500
– Класс 2; . . . . . – Класс 3 (разброс признаков СПМ для РС).
Рис. 8. Представление ОВ РС: абсцисса – номер признака, ордината – СПМ, усл. ед. (1)
Fig. 8. Voice signals training set representation: abscissa – feature number, ordinate – PSD, c.u. (1)
50
40
30
20
10
0
-10
-20
0
5
Примечание:
10
– Класс 1
15
20
25
30
35
40
45
50
55
60
– Класс 2 . . . . . – Класс 3 (разброс признаков СПМ для ЭЭГ (на примере отведения F4–A2)).
Рис. 9. Представление ОВ ЭЭГ: абсцисса – номер признака; ордината – СПМ, усл. ед. (1)
Fig. 9. The EEG training set representation: abscissa - feature number; ordinate - PSD, c. u. (1)
ты РС и ЭЭГ (классы 1, 2, 3), их применение к ОВ
и ТВ сигналов иллюстрируют таблицы 3 и 4.
Таблица 3
Результаты классификации ДШ
по признакам СПМ (X(v)ДШ)
Table 3
Respiratory noises classification results
on the PSD features (X(v)ДШ)
Параметр
Без интерваль- С интервальныных признаков ми признаками
Общее число
200
31
признаков
Ошибки при клас- 5 (Патология → 2 (Патология →
сификации ОВ
Норма)
Норма)
Ассоциативные
179
214
элементы
Множество
29
37
вершин Vc
Количество связей
980
1058
Контрольные
Норма (6) / Па- Норма (6) / Патоэлементы
тология (4)
логия (6)
Ошибки при клас- 3 (Патология → 2 (Патология →
сификации ТВ
Норма)
Норма)
Результаты экспериментов с ДШ (табл. 3) показывают, что выделение интервальных признаков
способствует сокращению признакового пространства, улучшению результатов классификации, однако при этом НИС приобретает более
сложную конфигурацию, что видно в увеличении
количества ассоциативных элементов и связей
между ними.
Особо следует отметить тот факт, что НИС
безошибочно разделяет объекты класса норма,
ошибки возникают при попытке классифицировать объекты из класса патология. Использование
графиков СПМ в качестве объектов классификации позволяет НИС выделить (при формировании
правил) наиболее информативные интервалы частот для ДШ.
Таблица 4
Результаты классификации сигналов ЭЭГ и РС
по признакам СПМ (X(s)ЭЭГ и X(l)РС), %
Table 4
EEG and voice signals classification results
on the PSD features (X(s)ЭЭГ and X(l)РС)
Успешность
классификации
Общая
Класс 1
Класс 2
Класс 3
ЭЭГ
ОВ
ТВ
100
77
100
86
100
73
100
71
РС
ОВ
100
100
100
100
ТВ
87
91
83
87
Получены результаты классификации образцов
РС и паттернов ЭЭГ при использовании двух режимов обучения НИС (режим 1 – без интервальных признаков, режим 2 – с интервальными при-
85
Software & Systems
no. 3 (107), 2014
№ 3 (107), 2014 г.
Программные продукты и системы
знаками (табл. 4)). Переход от режима 1 к режиму
2 позволил выявить ряд тенденций: 1) уменьшилось общее число признаков (минимум на 30 %),
обеспечивающих хороший уровень обобщения и
уточнения описания объектов в классах; 2) увеличилось число составляющих НИС ассоциативных
элементов, вершин (Vc), характеризующих группы
близких объектов, связей и контрольных элементов по классам объектов; 3) в большинстве случаев отмечается увеличение успешности (точности)
классификации, то есть сократилось число ошибок
при распознавании ОВ и ТВ.
Полученные результаты исследований показали приемлемую точность классификации образцов
РС и паттернов ЭЭГ в соответствии со знаком порождаемой эмоции (классы 1, 2, 3). Объединение
результатов классификации показывает, что неправильно классифицированные образцы РС и
паттерны ЭЭГ принадлежат одним и тем же людям. НИС безошибочно разделяет два крайних
класса (классы 1 и 3), ошибки возникают при попытке разделить объекты из классов 2 и 3 или
объекты из классов 2 и 1.
На основании изложенного можно сделать
следующие выводы. Дополнение интерпретатора
на основе НИС алгоритмом автоматической генерации интервальных признаков позволяет выделять наиболее информативные интервалы признакового пространства и тем самым сократить размерность описаний объектов, а также уменьшить
погрешность классификации.
Как видно из результатов тестирования, проведенных на искусственных и реальных клинических данных, алгоритм позволяет работать с различными типами экспериментальных графиков.
Набор сгенерированных классификационных правил, отображающих закономерности в структуре
НИС, и результаты классификации выборок сигналов (ДШ, РС и ЭЭГ) в большинстве случаев согласуются по форме с логическими выводами,
сделанными экспертами при анализе этих же выборок.
УДК 62.192:519.248
Литература
1. Гладун В.П. Растущие пирамидальные сети // Новости
искусственного интеллекта. 2004. № 1. С. 30–40.
2. Лоскутов А.Ю. Анализ временных рядов: курс лекций.
М.: Изд-во МГУ, 2006. 113 с.
3. Ifeachor E.C., Jervis B.W. Digital Signal Processing: A
Practical Approach (2nd ed.). Pearson Education, Upper Saddle
River, NJ, USA, 2002, 933 p.
4. Mirowski P., Madhavan D., LeCun Y., Kuzniecky R. Classification of patterns of EEG synchronization for seizure prediction.
Clinical neurophysiology, 2009, no. 120 (11), pp. 1927–1940.
5. Rangayyan R.M. Biomedical Signal Analysis: A CaseStudy Approach. IEEE Press and Wiley, NY, 2002, 516 p.
6. Филатова Н.Н., Ханеев Д.М., Сидоров К.В. Интерпретатор сигналов на основе нейроподобной иерархической структуры // Программные продукты и системы. 2014.
№ 1 (105). С. 92–97.
7. Ханеев Д.М., Филатова Н.Н. Применение нейроподобных сетевых структур для генерации гипотез правил классификации // Нечеткие системы и мягкие вычисления. 2013. Т. 8.
№ 1. С. 43–58.
8. Keogh E., Chu S., Hart D., Pazzani M. An online
algorithm for segmenting time series. IEEE Intern. Conf. on Data
Mining, 2001, pp. 289–296.
References
1. Gladun V.P. Growing pyramidal networks. Novosti
iskusstvennogo intellekta [News of artificial intelligence]. 2004,
no. 1, pp. 30–40 (in Russ.).
2. Loskutov A.Yu. Analiz vremennykh ryadov: Kurs lektsiy
[Time Series Analysis: Lectures]. Moscow, Moscow State Univ.
Publ., 2006, 113 p. (in Russ.).
3. Ifeachor E.C., Jervis B.W. Digital signal processing: a
practical approach. 2nd ed., Pearson Education Publ., Upper Saddle River, NJ, USA, 2002, 933 p.
4. Mirowski P., Madhavan D., LeCun Y., Kuzniecky R.
Classification of patterns of EEG synchronization for seizure prediction. Clinical neurophysiology. 120 (11), 2009, pp. 1927–1940.
5. Rangayyan R.M. Biomedical signal analysis: a case-study
approach. IEEE Press and Wiley, NY, 2002, 516 p.
6. Filatova N.N., Khaneev D.M., Sidorov K.V. Signals interpreter based on neural-like hierarchical structure. Programmnye
produkty i sistemy [Software & Systems]. 2014, no. 1 (105),
pp. 92–97 (in Russ.).
7. Khaneev D.M., Filatova N.N. Use of neurolike structures
for automatic generation of hypotheses for classification rules.
Nechetkie sistemy i myagkie vychisleniya [Fuzzy systems and soft
computing]. 2013, vol. 8, no. 1, pp. 43–58 (in Russ.).
8. Keogh E., Chu S., Hart D., Pazzani M. An online algorithm for segmenting time series. IEEE Int. Conf. on Data Mining.
2001, pp. 289–296.
Дата подачи статьи: 08.05.2014
МЕТОД ОЦЕНКИ ТЕХНИЧЕСКОГО УРОВНЯ ИЗДЕЛИЯ
ПО МОНИТОРИНГУ РЕКЛАМАЦИЙ
В СИСТЕМЕ УПРАВЛЕНИЯ КАЧЕСТВОМ ПРОИЗВОДСТВА
А.В.
И.Б. Арефьев, д.т.н., профессор
(Морская Академия, ул. Хенрика Побожного, 11, г. Щецин, 70-507, Польша,
i.arefyev@am.szczecin.pl);
Воловик, к.т.н., старший научный сотрудник; А.А. Клавдиев, к.т.н., доцент
(Национальный минерально-сырьевой университет «Горный»,
21 линия, 2, г. Санкт-Петербург, 199106, Россия)
В технике существует класс изделий, рассматриваемых как единый функциональный элемент, для которых показатели надежности не нормируются. Качество таких устройств оценивают по рекламациям.
86
Документ
Категория
Без категории
Просмотров
7
Размер файла
869 Кб
Теги
последовательного, графиков, алгоритм, признаков, укрупнение, pdf, классификация
1/--страниц
Пожаловаться на содержимое документа