Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing
Research in engineering, biology, economics, and other fields is often related to the analysis of observed processes that have a repetitive nature over time. One of the promising approaches to solving the problem of analyzing and interpreting such signals is based on transforming the original cyclic...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2022 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2022
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/210892 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing / L. Fainzilberg // Проблеми керування та інформатики. — 2022. — № 3. — С. 112-123. — Бібліогр.: 16 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860002798122303488 |
|---|---|
| author | Fainzilberg, L. |
| author_facet | Fainzilberg, L. |
| citation_txt | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing / L. Fainzilberg // Проблеми керування та інформатики. — 2022. — № 3. — С. 112-123. — Бібліогр.: 16 назв. — англ. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Research in engineering, biology, economics, and other fields is often related to the analysis of observed processes that have a repetitive nature over time. One of the promising approaches to solving the problem of analyzing and interpreting such signals is based on transforming the original cyclic signal into a sequence of symbols from a certain alphabet, for which methods of mathematical linguistics can be used. The linguistic approach to processing cyclic signals involves constructing a codegram that characterizes the dynamics of changes in the shape of successive cycles. It is proposed to use binary and ternary indicator functions to construct codegrams. A procedure for determining the optimal threshold value of insensitivity to changes in signal parameters is proposed, which ensures the minimum within-class distances and maximum between-class distances. Reference classes are constructed based on the pairwise Levenshtein distance matrix between the codegrams of the training sample of each class and the determination of the codegram that is at the minimum total distance from other codegrams of the analyzed class. Computational procedures are proposed that allow determining the dominant patterns of classes in the form of three-character patterns of codegrams.
Дослідження в техніці, біології, економіці та інших областях часто повʼязані з аналізом спостережуваних процесів, які мають характер, що повторюється в часі. Один із перспективних підходів до вирішення проблеми аналізу та інтерпретації таких сигналів заснований на перетворенні вихідного циклічного сигналу на послідовність символів деякого алфавіту, для якої можуть бути використані методи математичної лінгвістики. Лінгвістичний підхід до оброблення циклічних сигналів передбачає побудову кодограми, що характеризує динаміку зміни форми послідовних циклів. Для побудови кодограм запропоновано використовувати двозначні та тризначні індикаторні функції. Запропоновано процедуру визначення оптимального значення порогу нечутливості до зміни параметрів сигналу, що забезпечує мінімум внутрішньокласових відстаней та максимум міжкласових відстаней. Побудову еталонів класів, що розпізнаються, засновано на матриці парних відстаней Левенштейна між кодограмами навчальної вибірки кожного зкласів і визначенні кодограми, яка знаходиться на мінімальній сумарній відстані від інших кодограм аналізованого класу. Запропоновано обчислювальні процедури, що дозволяють визначати домінантні патерни класів у вигляді трисимвольних патернів кодограм. Розробленовирішальні правила, що дозволяють класифікувати оброблювані циклічні сигнали за еталонами кодограм та домінантними патернами.На прикладах оброблення електрокардіограм продемонстровано ефективність запропонованого підходу. Встановлено, що побудоване вирішальне правило забезпечує чутливість і специфічність при класифікації електрокардіограм хворих на ішемічну хворобу серця і здорових добровольців навіть за відсутності на ЕКГ загальноприйнятих діагностичних ознак ішемії міокарда. Доцільно продовжити дослідження, спрямовані на вивчення можливості подальшого підвищення ефективності запропонованого підходу, зокрема, на основі оброблення кодограм з використанням алгоритмів вирівнювання послідовностей, які активно застосовують у біоінформатиці.
|
| first_indexed | 2026-03-18T12:28:16Z |
| format | Article |
| fulltext |
© L. FAINZILBERG, 2022
112 ISSN 2786-6491
UDC 004.021
L. Fainzilberg
CYCLIC SIGNALS CLASSIFICATION BY
CODEGRAMS CHARACTERIZING THE DYNAMICS
OF CYCLES SHAPE CHANGING
Leonid Fainzilberg
Information Technologies and Systems of the National Academy of
Sciences of Ukraine and the Ministry of Education and Science
of Ukraine, Kyiv,
fainzilberg@gmail.com
Research in engineering, biology, economics and other areas is often associated
with the analysis of observed processes that are repetitive in time. One of the
promising approaches to solving the problem of analyzing and interpreting such
signals is based on converting the original cyclic signal into a sequence of sym-
bols of some alphabet, for which methods of mathematical linguistics can be
used. The linguistic approach to the processing of cyclic signals involves the
construction of a codogram that characterizes the dynamics of changes in the
shape of successive cycles. To construct codograms, it is proposed to use two-
valued and three-valued indicator variables. A procedure is proposed for deter-
mining the optimal value of the threshold of insensitivity to changes in signal
parameters, which provides a minimum of intra-class distances and a maximum
of inter-class distances. The construction of standards for recognizable classes is
based on the Levenshtein matrix of paired distances between the codograms of
the training sample of each of the classes and the definition of a codogram that is
at the minimum total distance from the rest of the codograms of the class under
consideration. Computational procedures are proposed that allow determining
the dominant patterns of classes in the form of three-character patterns of codo-
grams. Decision rules have been developed to classify processed cyclic signals
according to both codegram standards and dominant patterns. The effectiveness
of the proposed approach has been demonstrated using examples of processing
electrocardiograms. It has been established that the constructed decision rule
provides sensitivity and specificity in the classification of electrocardiograms of
patients with coronary heart disease and healthy volunteers, even in the absence
of generally accepted diagnostic signs of myocardial ischemia on the ECG. It is
advisable to continue research aimed at studying the possibility of further im-
proving the efficiency of the proposed approach, in particular, based on the pro-
cessing of codograms using sequence alignment algorithms that are actively
used in bioinformatics.
Keywords: cyclic signal, codegram, Levenshtein distance, decision rule.
Introduction
Fundamental and applied research in engineering, biology, economics and other
areas are often associated with the analysis of observed processes that are repetitive in
time [1, 2]. Such processes generate specific signals, which are usually called cyclic in
the scientific literature [3–5]. Typical examples of cyclic signals are electrocardiograms,
rheograms, photoplethysmograms and other biomedical signals reflecting to the cyclic
nature of the work of the circulatory and respiratory systems of a living organism.
Many scientific publications, in particular, works [6, 7], are devoted to the study of
the cyclic signals properties and the construction of mathematical models for their de-
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 113
scription. One of the promising methods for processing such signals is based on con-
verting the original signal into a sequence of symbols that characterize the dynamics of
the cycles shape changes. For computer analysis of the obtained sequence, methods of
mathematical linguistics [8, 9] can be used, the effectiveness of which was demonstrat-
ed in [10] using the example of the electrocardiogram classification problem.
The purpose of the article is the further development of the linguistic method for
analysis and interpretation of cyclic signals.
Main idea of the proposed approach
The linguistic analysis of the cyclic signal ( )z t is based on the transition from the
k -th realization ( )kz t observed on a limited time interval [0, ]t T to the word
1 2k KS = which is a finite chain of characters , 1, ...,j j K = from the al-
phabet . Each symbol j reflects the dynamics of shape change ( )kz t from cy-
cle to cycle. To do this following [11] we will analyze the parameters 1 , ..., Mx x char-
acterizing the shape of individual cycles ( )kz t and by the difference of the m -th pa-
rameter ( 1, ...,m M= ) on successive cycles, we will calculate the values of two-valued
indicator functions
( )( )
1( )
( )( )
1
1, if 0,
1, if 0,
mm
n nm
n mm
n n
x x
V
x x
=
−
+ −
=
− −
1, ...,m M= , 2, ...,n N= . (1)
Possible combinations of values (1) (2) ( ), , ..., M
n n nV V V define 2M different symbols
n , and the string of symbols 1 2 1k NS −= forms 1N − — bit word kS
which uniquely encodes the processed signal ( )kz t .
In [10], the electrocardiogram (ECG) coding rule based on functions (1) is considered
which cycles describe two parameters — the duration of the RR -interval and the T -wave
symmetry index. In this simplest case, cycles encodes one of four characters of the al-
phabet { , , , }A B C D= according to the rule presented in Table 1.
Table 1
N
Values of indicator functions
Symbol
n
)1(
nV )2(
nV
RR-intervals T-wave symmetries
1 + 1 + 1 A
2 + 1 – 1 B
3 – 1 + 1 C
4 – 1 – 1 D
The transition from the observed signal )(tzk to the code word (codegram kS )
made it possible to use the methods of mathematical linguistics to solve the problem for
analyzing and interpreting )(tzk . The proposed method provides an estimate of the
proximity between any pair of codegrams SS , based on the Levenshtein distance
),( SSL which determines the minimum number of editing operations (insertion, de-
letion and replacement of a character) that provides a transition from S to S [12].
114 ISSN 2786-6491
For the calculation ),( SSL we use the Wagner-Fischer algorithm [13] based on
the dynamic programming method. To do this, we form NN matrix ,U where
N and N are the number of characters in words S and S , respectively.
Let us fill the first row and the first column of the matrix U as follows:
,1,),0
,1,)0,(
==
==
NjjjU
NiiiU
(2)
and the remaining elements of the matrix U ( 1,1 ji ) fill according to the rule:
)}(),(()1,1(,1),1(,1)1,(min{),( jSiSmjiUjiUjiUjiU +−−+−+−= , (3)
where
=
=
).()(if,1
),()(if,0
))(),((
jSiS
jSiS
jSiSm (4)
As a result, the Levenshtein distance ),( SSL between words S and S de-
termines the matrix element ),( NNU .
The Levenshtein distance has the traditional properties of a metric:
0),( SSL and 0),( = SSL if and only if = SS ;
),(),( = SSLSSL ;
),(),(),( + SSLSSLSSL , where S — character sequence n .
Based on the Levenshtein distance ),( SSL between pairs of codegrams SS , ,
algorithms that provide a solution to the problem of cyclic signals classifying can be
constructed. To do this we will use a training samples of signals with known belonging
to the classes G ...,,1 .
Let as a result of the experiments gQ observations of the class }...,,{ 1 Gg VVV
be registered, which are encoded by the words
)(
1
g
S ,
)(
2
g
S , …,
)(g
Qg
S in accordance with
Table 1. Let us calculate the Levenshtein distances ),( )()( gg SSL between each pair
)()( , gg SS , gQ...,,1= , gQ...,,1= , of codegrams using formulas (2)–(4), which we
represent as a square gg QQ matrix:
=
),(...),(),(
...
),(...),(),(
),(...),(),(
)()()(
2
)()(
1
)(
)()(
2
)(
2
)(
2
)(
1
)(
2
)()(
1
)(
2
)(
1
)(
1
)(
1
)(
g
Q
g
Q
gg
Q
gg
Q
g
Q
ggggg
g
Q
ggggg
g
gggg
g
g
SSLSSLSSL
SSLSSLSSL
SSLSSLSSL
. (5)
The class }...,,{ 1 Gg VVV standard will determine as row of the matrix (5), which
sum of elements is minimal, i.e.
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 115
=
=
Qg
gg
Q
g
SSLS
g 1
)()(
1
)(
0 ),(minarg . (6)
Letʼs define the standards
)(
0
)1(
0 ...,,
G
SS of other classes G ...,,1 in a similar way.
The constructed standards ensure the adoption of subsequent decisions about the
current signal codegram tS according to the rule:
),(min),(if,CLASS
)(
0
1
)(
0
g
t
Gg
t SSLSSL
= , ],1[ G . (7)
To evaluate the effectiveness of the rule (7), studies were conducted using a data-
base that included 100 ECG records from verified patients with chronic coronary artery
disease (CAD) and 100 ECG records from healthy volunteers [10]. The diagnosis was
previously established by the results of coronary angiography.
It is important to note that there were no traditional diagnostic features of myocar-
dial ischemia on the CAD patients ECG. Nevertheless, even on such a complex clinical
material, the proposed approach made it possible to classify the available data with sen-
sitivity %72=ES and specificity %79=PC according to the rule
),(),(if,CAD
)2(
0
)1(
0 SSLSSL tt , (8)
),(),(ifHEALTHY,
)2(
0
)1(
0 SSLSSL tt , (9)
where tS is the codegram of the analyzed ECG, and
)1(
0S ,
)2(
0S respectively are the stand-
ards of CAD patients and healthy volunteers codegrams, calculated according to (6).
Fig. 1 shows estimates of conditional distributions )),((
)1(
0SSLP t and
)),((
)2(
0SSLP t of Levenshtein distances between the training sample codegrams with
respect to the standards
)1(
0S and
)2(
0S . Testing the hypothesis about the homogeneity
of conditional distributions )),((
)1(
0SSLP t and )),((
)2(
0SSLP t according to the Kol-
mogorov-Smirnov criterion showed that the hypothesis about the equality of distribu-
tions should be rejected with high statistical significance )001,0( p [10]. A similar
fact confirmed the Man-Whitney test for independent samples.
Fig. 1
)),((
)1(
0SSLP t
116 ISSN 2786-6491
Continuation of the figure 1
Useful improvements and generalizations
Procedures (2)–(4) make it possible to calculate the Levenshtein distance
),( SSL in the general case, when the signals )(tz and )(tz have a different num-
ber of cycles, which means that the numbers N and N of symbols in both words
S and S are not the same. Obviously, for NN the Levenshtein distance satis-
fies the condition − NNSSL ),( , and −= NNSSL ),( , even if the sig-
nals are identical )()( tztz .
From this follows that at NN , the Levenshtein distance ),( SSL charac-
terizes not only the difference in the shape )(tz and )(tz , but also the difference in
the duration of the signals, which introduces ambiguity into the interpretation of
),( SSL . Therefore, before forming the matrix (5), it is proposed to equalize the dura-
tion of observations, ensuring the same number of cycles k
k
NN min0 = for all observa-
tions of the training sample.
Let us consider another possibility to improve the estimation of cycles shape dy-
namics which consists in the transition from two-valued indicator functions (1) to three-
valued ones:
−−−
−
−+
=
−
−
=
,if,1
,if,0
,if,1
)(
1
)(
)(
1
)(
)(
1
)(
)(
m
n
m
n
m
n
m
n
m
n
m
n
m
n
xx
xx
xx
V Mm ...,,1= , 0...,,2 Nn = , (10)
where is threshold of insensitivity to the change of the m -th parameter
( Mm ...,,1= ) on successive cycles.
Unlike (1), functions (10) evaluate not only the direction, but also the degree of
change in the values of the m -th parameter, which expands the possibilities of the
method. In this case the alphabet already contains M3 various symbols n ,
with the help of which the 10 −N bit codegrams 121 0 −
= NkS of the signal
)(tzk are generated.
Table 2 shows the rule for coding ECG cycles based on the values of the ind i-
cator functions )1(
nV ,
)2(
nV ,
)3(
nV , characterizing the dynamics of three diagnostic
indicators — the duration of the RR -intervals, the symmetries of the T -waves and the
amplitudes of the R -waves. In this case, the alphabet contains 27 characters.
)),((
)2(
0SSLP t
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 117
Table 2
N
Values of indicator functions
Symbol
n
)1(
nV )2(
nV )3(
nV
RR-intervals T-wave symmetries R-wave amplitudes
0 0 0 0 =
1 0 0 -1 A
2 0 0 +1 B
3 – 1 0 0 C
4 – 1 0 – 1 D
5 – 1 0 +1 E
6 + 1 0 0 F
7 + 1 0 – 1 G
8 + 1 0 + 1 H
9 0 – 1 0 I
10 0 – 1 – 1 J
11 0 – 1 + 1 K
12 – 1 – 1 0 L
13 – 1 – 1 – 1 M
14 – 1 – 1 + 1 N
15 + 1 – 1 0 O
16 + 1 – 1 – 1 P
17 + 1 – 1 + 1 Q
18 0 + 1 0 R
19 0 + 1 – 1 S
20 0 + 1 + 1 T
21 – 1 + 1 0 U
22 – 1 + 1 – 1 V
23 – 1 + 1 + 1 W
24 + 1 + 1 0 X
25 + 1 + 1 – 1 Y
26 + 1 + 1 + 1 Z
Fig. 2 shows the fragment of the signal )(tz and graphs of changes in the durations of
RR -intervals, the symmetries of the T -wave and the amplitudes of the R -wave.
P
R
S Q
T
ECG signal z(t)
P
R
Q
T
S
P
R
Q
T
S
P
R
Q
T P
R
Q
T
S
P
R
Q
T
S
P
R
Q
T
S
P
R
Q
T
S
P
R
Q
T
S
P
R
Q
T
S
P
R
Q
T
S
RR-intervals
900
800
T-wave symmetries
R-wave amplitudes
1,0
0,9
0,8
1,0
20 10 0 50 40 30
Fig. 2
118 ISSN 2786-6491
As can be seen from Table 3, which shows the codegrams of the same signal for
different values of threshold, the variety of symbols participating in the codegram
decreases and at the same time the number of symbols « = » encoding stable fragments
of the signal increases with increasing threshold. Therefore, the problem is to choose an
acceptable value of threshold that provides control over only those changes in the
signal that are of diagnostic value.
Table 3
Threshold Codegram
1 QSMWNVMZPQYOQ=MXWVZQYKZVKWMZGMZZVIZYPTDMWMZQYJTMNTPSQY
2 QSMWNVDZAQSIQ=MRWVZQGKZVKWMZAMTZSIZGITCMWMZQYITJNTPSKS
3 QSJRNDAZAQSIQ=MRTSTOAKZSKWLZAJTTRIZAITCMTLXQSITJNTJSKR
4 QSJRNDAZAOSIK=MRTATIAKTSKTLZAJTTRIZAITCMTLXQSITJKTJ=BR
5 QSJRNDATAORIK=MRTATIAKTSKRLT=JTTRIZAIT=JRLXKSITJITJ=BR
6 OSJRKD=TAORIB=JRTATIAKTSKRLT=JTTRIZAIT=JRLXISITJIRI=BR
7 ISJRKD=TAIRIB=JRBATIAITSKRIT=JTBRIZAIT=JRLXISITJIRI=BR
8 ISIRKD=TA=RIB=JR=ATIAITSKRIT=JT=RITAIR=A=LXISITJIRI=BR
9 IRIRID=TA=RIB=JR=ABIAITSKRIT=JT=RITAIR=A=LXIR=TJIRI=BR
10 IRIRID=TA=RI===R=ABIAITSKRIT=JR=RITAIR=A=IXIR=TJIRI==R
While constructing a binary classifier when obeserved signal belongs to one of two
classes 1 or 2 , the following procedure for determining the optimal threshold
value is proposed.
Let us assume that we have training sample 1Q of observations from the class 1
and 2 ,Q observations from the class 2 . We will encode 1 class observations in ac-
cordance with (10) for different fixed threshold values from given interval
max0 with a certain step . As a result, we construct
max matrices of intra-
class Levenshtein distances for various discrete values :
=
),(...),(),(
...
),(...),(),(
),(...),(),(
)1()1()1(
2
)1()1(
1
)1(
)1()1(
2
)1(
2
)1(
2
)1(
1
)1(
2
)1()1(
1
)1(
2
)1(
1
)1(
1
)1(
1
)1(
1111
1
1
QQQQ
Q
Q
SSLSSLSSL
SSLSSLSSL
SSLSSLSSL
, max...,,0 = . (11)
Using each of the matrices (11), we calculate depending on the average intra-
class distance:
= =
−
=
1 1
1 1
)1()1(
11
)1( ),(
))1(
2
Q Q
SSL
QQ
L . (12)
Similarly, by the elements of the matrices
)2(
, we calculate the average intraclass
distance for the second class depending on :
= =
−
=
2 2
1 1
)2()2(
22
)2( ),(
))1(
2
Q Q
SSL
QQ
L . (13)
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 119
Now let us construct 21 QQ matrices of interclass distances ),( )2()1(
SSL be-
tween all pairs of codegrams for classes 1 and 2 with fixed values in the interval
max0 :
=
),(...),(),(
...
),(...),(),(
),(...),(),(
)2()1()2(
2
)1()2(
1
)1(
)2()1(
2
)2(
2
)1(
2
)2(
1
)1(
2
)2()1(
1
)2(
2
)1(
1
)2(
1
)1(
1
)2,1(
2111
2
2
QQQQ
Q
Q
SSLSSLSSL
SSLSSLSSL
SSLSSLSSL
, max...,,0 = . (14)
Using the elements of matrices (14), we calculate the average interclass distance
depending on :
= =
=
2 1
1 1
)2()1(
21
)2,1( ),(
1
Q Q
SSL
QQ
L , (15)
Using quantities (12), (13) and (15) we will form the optimality criterion
)2,1(
)2()1(
)(
+
=
L
LL
. (16)
The criteria (16) allows, by enumeration of discrete values given with a certain
step in the interval max0 , to determine the optimal value
)(minarg
max0
0 =
, (17)
Since 0)1( L , 0)2( L , 0)2,1( L the optimization procedure (17) simultane-
ously provides the minimum of average intraclass distances
)1(
L ,
)2(
L and the maxi-
mum of average interclass distance
)2,1(
L .
Validity of cyclic signals classification can be increased by additionally analyzing
individual parts of the code word in the form of characteristic patterns (substrings), for
example, three-character patterns = , where ,, [14]. A simplified sys-
tem structure that implements this technology is shown in Fig. 3.
To build a classification algorithm, we calculate the average frequency of patterns
= occurrence in the gQ observation codegrams of each class
}...,,{ 1 Gg :
=
−
=
gQ
l
g
g
l
g
N
W
Q
P
1 0
)(
)(
2
)(1
)(ˆ , Ll ...,,1= , (18)
here )()(
l
gW is the number of the l -th three-character pattern l occurrences in the
-th codegram of the training sample for class }...,,{ 1 Gg VVV , and L is the number
of three-character patterns = variants from the elements of the alphabet .
To speed up the procedure (18) it is advisable to use the Boyer-Moore string
matching algorithm [15] for determining )()(
l
gW .
120 ISSN 2786-6491
Selection Patterns =
The rule for determ class
Cyclical signal )(tz
Parameters )()1(
1 ...,,
M
Nxx
Indicator variables )()1(
2 ...,,
M
NVV
Coding word 121 −= NkS
Fig. 3
Let us introduce the notation of the g -th class dominant pattern
)(ˆmaxarg
)(
1
)(
0 l
g
Ll
g
P =
, Gg ...,,1= . (19)
If the differences in average frequencies )(ˆ )1(
0
)1( P , )(ˆ )2(
0
)2( P , …, )(ˆ )(
0
)( GGP
are statistically significant, and the patterns themselves
)1(
0 , ,
)2(
0 …,
)(
0
G
are not the
same, then this allows us to use ,
)1(
0 ,
)2(
0 …,
)(
0
G
found according to (19) as
1, ..., G classes standards for the following decision rule:
),,(minarg),(if,CLASS
)(
0
1
)(
0
g
t
Gg
t LL =
(20)
where t is the pattern that has the largest number of occurrences in the analyzed signal
codegram tS and ),(
)(
0
g
tL are the Levenshtein distances between t and the refer-
ence patterns ,
)1(
0 ,
)2(
0 …, .
)(
0
G
Let us show that the rule (20) makes it possible to increase the reliability of the
decisions made. According to the training sample set of codegrams built on the ba-
sis of two-valued indicator functions (1), it was found that with high statistical sig-
nificance ( 01,0p ) the pattern DAD=
)1(
0 dominates on the codegrams of CAD pa-
tients (class 1 ) and the pattern CAA=
)2(
0 dominates on the codegrams of healthy
volunteers (class 2 ). This made it possible to expand the decision rule (8), (9), sup-
plementing it with analysis of the number of dominant patterns occurrences )(DADGt
and )(CAAGt in the analyzed codegram .tS
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 121
Fig. 4 shows two examples of real ECG whose codegrams contain patterns
DAD=
)1(
0
and .
)2(
0 CAA= Despite the fact that fragments are visually almost indis-
tinguishable, the proposed computer procedures provide an unambiguous assignment of
such fragments to the pattern DAD=
)1(
0 or to the pattern .
)2(
0 CAA=
DAD
CAA
Fig. 4
This allowed us to expand the decision rule on the basis of which screening exami-
nations can identify patients with an increased risk of coronary artery disease:
( )
( ) ( )
uncertain.Else
,and),(),(ifHealthy,
),(and),(),(if,CAD
)2(
0
)1(
0
)2(
0
)1(
0
CAAGDADGSSLSSL
CAAGDADGSSLSSL
tttt
tttt
(21)
It has been established that in 87,5% of cases the rule (21) allows making unam-
biguous decisions regarding classes 1 and 2 with sensitivity %7,74=ES and speci-
ficity %5,79=PS even if generally accepted features of myocardial ischemia on the
ECG — ST -segment depression or a negative T -wave are absent.
Conclusion
The article shows that the transition from an observed cyclic signal to a code word
that characterizes the dynamics of changes in the shape of successive cycles makes it
possible to increase the reliability of signal classification results based on the use of
methods of mathematical linguistics. In particular, the proposed approach made it pos-
sible to make diagnostic decisions about an increased risk of coronary heart disease us-
ing electrocardiograms that do not show traditional signs of myocardial ischemia.
It is advisable to continue theoretical research aimed at finding additional methods
for analyzing and interpreting codegrams. In particular, it is useful to study the possibil-
ity of further development of the proposed approach based on the use of sequence
alignment algorithms, which are actively used in bioinformatics [16].
122 ISSN 2786-6491
Л.С. Файнзільберг
КЛАСИФІКАЦІЯ ЦИКЛІЧНИХ СИГНАЛІВ
ЗА КОДОГРАМАМИ, ЩО ХАРАКТЕРИЗУЮТЬ
ДИНАМІКУ ЗМІНИ ФОРМИ ЦИКЛІВ
Файнзільберг Леонід Соломонович
Міжнародний науково-навчальний центр інформаційних техно-
логій і систем НАН України та МОН України, м. Київ,
fainzilberg@gmail.com
Дослідження в техніці, біології, економіці та інших областях часто
повʼязані з аналізом спостережуваних процесів, які мають характер, що
повторюється в часі. Один із перспективних підходів до вирішення
проблеми аналізу та інтерпретації таких сигналів заснований на пере-
творенні вихідного циклічного сигналу на послідовність символів де-
якого алфавіту, для якої можуть бути використані методи математич-
ної лінгвістики. Лінгвістичний підхід до обробролення циклічних сиг-
налів передбачає побудову кодограми, що характеризує динаміку зміни
форми послідовних циклів. Для побудови кодограм запропоновано ви-
користовувати двозначні та тризначні індикаторні функції. Запропоно-
вано процедуру визначення оптимального значення порогу нечутли-
вості до зміни параметрів сигналу, що забезпечує мінімум внутрішньокла-
сових відстаней та максимум міжкласових відстаней. Побудову
еталонів класів, що розпізнаються, засновано на матриці парних відста-
ней Левенштейна між кодограмами навчальної вибірки кожного з
класів і визначенні кодограми, яка знаходиться на мінімальній су-
марній відстані від інших кодограм аналізованого класу. Запропонова-
но обчислювальні процедури, що дозволяють визначати домінантні па-
терни класів у вигляді трисимвольних патернів кодограм. Розроблено
вирішальні правила, що дозволяють класифікувати оброблювані
циклічні сигнали за еталонами кодограм та домінантними патернами.
На прикладах оброблення електрокардіограм продемонстровано ефек-
тивність запропонованого підходу. Встановлено, що побудоване
вирішальне правило забезпечує чутливість і специфічність при кла-
сифікації електрокардіограм хворих на ішемічну хворобу серця і здо-
рових добровольців навіть за відсутності на ЕКГ загальноприйнятих
діагностичних ознак ішемії міокарда. Доцільно продовжити до-
слідження, спрямовані на вивчення можливості подальшого підвищен-
ня ефективності запропонованого підходу, зокрема, на основі оброб-
лення кодограм з використанням алгоритмів вирівнювання послідов-
ностей, які активно застосовують у біоінформатиці.
Ключові слова: циклічний сигнал, кодограма, відстань Левенштейна,
вирішувальне правило.
REFERENCES
1. Kanjilal P.P., Bhattacharya J., Saga G. Robust method for periodicity detection and characterisa-
tion of irregular cyclical series in terms of embedded periodic components. Phys. Rev. 1999. 59.
P. 4013–4025.
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 123
2. Fainzilberg L.S. Generalized method of processing cyclic signals of complex form in multi-
dimension space of patameters. Journal of Automation and Information Sciences. 2015. 47,
N 3. P. 24–39. https://doi.org/10.1615/JAutomatInfScien.v47.i3.30.
3. Lupenko S.A. Deterministic and random cyclic functions as models of oscillatory phenomena and
signals: definition and classification. Electronic modeling. 2006. 28, N 4. P. 29–45 (in Russian).
4. Dragan J.P. Mathematical and algorithmic software support of computer tools for statistical pro-
cessing of stochastic fluctuations (rhythmic processes). Bulletin of the National Lviv Polytechnic
University: Information systems and networks. 2008. № 621. P. 124–130 (in Ukrainian).
5. Zvarich V.N., Marchenko B.G. Linear autoregressive processes with periodic structures as mod-
els of information signals. Radioelectronics and Communications Systems. 2011. 54, N 7.
P. 367–372.
6. Shachikov A.D., Shulyak A.P. Development of principles for analyzing the structure of cyclic bi-
omedical signals for their detection, recognition and classification. Bulletin of NTUU «KPI». Se-
ries Instrumentation. 2015. 49, N 1. P. 169–179. (in Russian).
7. Lytvynenko I.V. The problem of segmentation of the cyclic random process with a segmental
structure and the approaches to its solving. Journal of Hydrocarbon Power Engineering. 2016. 3,
N 1. P. 30–37.
8. Pavlidis T. Linguistic analysis of waveforms. Software Eng. 1971. 2, N 4. P. 203–225.
https://doi.org/10.1016/B978-0-12-696202-4.50019-X.
9. Mottl N.V., Muchnik I.B., Jakovled V.G. Linguistic analysis of experimental curves. Proceedings
of the IEEE. 1979. 67, N 5. P. 12–39.
10. Fainzilberg L.S., Dykach Ju.R. Linguistic approach for estimation of electrocardiogramsʼs subtle
changes based on the Levenstein distance. Cybernetics and Computer Engineering. 2019. N 2
(196). P. 3–26. https://doi.org/10.15407//kvt196.02.003.
11. Uspenskiy V.M. Diagnostic system based on the information analysis of electrocardiogram.
Proceedings of MECO 2012. Advances and Challenges in Embedded Computing (Montene-
gro, June 19–21). 2012. P. 74–76.
12. Levenshtein V.I. Binary codes with correction of occurrences, inserts and symbol substitutions.
Reports USSR Academy of Sciences. 1965. 163, N 4. P. 845–848 (in Russian).
13. Wagner R.A., Fischer M.J. The string-to-string correction problem. Journal of the ACM. 1971.
21, N 1. P. 168–173. https://doi:10.1145/321796.321811.
14. Fainzilberg L.S., Dykach Ju.R. Development of a linguistic approach to the problem of
the computer electrocardiogramʼs classifications. Control systems and computers. 2021. N. 2–3.
P. 28–39. https://doi.org/10.15407/csc.2021.02.028.
15. Cole R. Tight bounds on the complexity of the Boyer-Moore string matching algorithm. SIAM
Journal on Computing. 1994. 23, N. 5. P. 1075–1091. https://doi:10.1137/ S0097539791195543
16. Althaus E., Caprara A., Lenhof H.P., Reinert K. Multiple sequence alignment with arbitrary gap
costs: computing an optimal solution using polyhedral combinatorics. Bioinformatics. 2002. N 18.
P. 4–16. https://doi: 10.1093/bioinformatics/18.suppl_2.s4.
Отримано 31.07.2022
http://dx.doi.org/10.1615/JAutomatInfScien.v47.i3.30
https://doi.org/10.1016/B978-0-12-696202-4.50019-X
https://en.wikipedia.org/wiki/Digital_object_identifier
https://doi.org/10.1145%2F321796.321811
http://usim.org.ua/?page_id=14106&lang=en
https://ru.wikipedia.org/wiki/Doi
https://dx.doi.org/10.1137%2FS0097539791195543
|
| id | nasplib_isofts_kiev_ua-123456789-210892 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | English |
| last_indexed | 2026-03-18T12:28:16Z |
| publishDate | 2022 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Fainzilberg, L. 2025-12-20T09:46:12Z 2022 Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing / L. Fainzilberg // Проблеми керування та інформатики. — 2022. — № 3. — С. 112-123. — Бібліогр.: 16 назв. — англ. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210892 004.021 10.34229/2786-6505-2022-3-9 Research in engineering, biology, economics, and other fields is often related to the analysis of observed processes that have a repetitive nature over time. One of the promising approaches to solving the problem of analyzing and interpreting such signals is based on transforming the original cyclic signal into a sequence of symbols from a certain alphabet, for which methods of mathematical linguistics can be used. The linguistic approach to processing cyclic signals involves constructing a codegram that characterizes the dynamics of changes in the shape of successive cycles. It is proposed to use binary and ternary indicator functions to construct codegrams. A procedure for determining the optimal threshold value of insensitivity to changes in signal parameters is proposed, which ensures the minimum within-class distances and maximum between-class distances. Reference classes are constructed based on the pairwise Levenshtein distance matrix between the codegrams of the training sample of each class and the determination of the codegram that is at the minimum total distance from other codegrams of the analyzed class. Computational procedures are proposed that allow determining the dominant patterns of classes in the form of three-character patterns of codegrams. Дослідження в техніці, біології, економіці та інших областях часто повʼязані з аналізом спостережуваних процесів, які мають характер, що повторюється в часі. Один із перспективних підходів до вирішення проблеми аналізу та інтерпретації таких сигналів заснований на перетворенні вихідного циклічного сигналу на послідовність символів деякого алфавіту, для якої можуть бути використані методи математичної лінгвістики. Лінгвістичний підхід до оброблення циклічних сигналів передбачає побудову кодограми, що характеризує динаміку зміни форми послідовних циклів. Для побудови кодограм запропоновано використовувати двозначні та тризначні індикаторні функції. Запропоновано процедуру визначення оптимального значення порогу нечутливості до зміни параметрів сигналу, що забезпечує мінімум внутрішньокласових відстаней та максимум міжкласових відстаней. Побудову еталонів класів, що розпізнаються, засновано на матриці парних відстаней Левенштейна між кодограмами навчальної вибірки кожного зкласів і визначенні кодограми, яка знаходиться на мінімальній сумарній відстані від інших кодограм аналізованого класу. Запропоновано обчислювальні процедури, що дозволяють визначати домінантні патерни класів у вигляді трисимвольних патернів кодограм. Розробленовирішальні правила, що дозволяють класифікувати оброблювані циклічні сигнали за еталонами кодограм та домінантними патернами.На прикладах оброблення електрокардіограм продемонстровано ефективність запропонованого підходу. Встановлено, що побудоване вирішальне правило забезпечує чутливість і специфічність при класифікації електрокардіограм хворих на ішемічну хворобу серця і здорових добровольців навіть за відсутності на ЕКГ загальноприйнятих діагностичних ознак ішемії міокарда. Доцільно продовжити дослідження, спрямовані на вивчення можливості подальшого підвищення ефективності запропонованого підходу, зокрема, на основі оброблення кодограм з використанням алгоритмів вирівнювання послідовностей, які активно застосовують у біоінформатиці. en Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Технічні засоби для вимірювань та керування Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing Класифікація циклічних сигналів за кодограмами, що характеризують динаміку зміни форми циклів Article published earlier |
| spellingShingle | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing Fainzilberg, L. Технічні засоби для вимірювань та керування |
| title | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing |
| title_alt | Класифікація циклічних сигналів за кодограмами, що характеризують динаміку зміни форми циклів |
| title_full | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing |
| title_fullStr | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing |
| title_full_unstemmed | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing |
| title_short | Cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing |
| title_sort | cyclic signals classification by codegrams characterizing the dynamics of cycles shape changing |
| topic | Технічні засоби для вимірювань та керування |
| topic_facet | Технічні засоби для вимірювань та керування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210892 |
| work_keys_str_mv | AT fainzilbergl cyclicsignalsclassificationbycodegramscharacterizingthedynamicsofcyclesshapechanging AT fainzilbergl klasifíkacíâciklíčnihsignalívzakodogramamiŝoharakterizuûtʹdinamíkuzmíniformiciklív |