In the paper, we are interested in classi cation of disturbed periodic biosignals. An ant based clustering algorithm is used to group episodes into which examined biosignals are divided. Disturbances in periodicity of such signals cause some di culties in formation of coherent clusters of similar episodes. A quality of a clustering process result can be used as an indicator of disturbances. A local function in the applied clustering algorithm is calculated on the basis of temporal rough set ow graphs representing an information ow distribution for episodes.
An increasing interest is now evident in classi cation and clustering for time
series and signals using a variety of methodologies (cf. [
Periodicity is one of the main features of some biosignals (e.g., voice, ECG).
However, in case of some diseases, this periodicity can be disturbed. Especially,
it is expressed by di erent shapes in selected time windows corresponding to
periods of biosignals. The main idea of the proposed approach is based on
recognition of temporal patterns and their replications in a selected fragment of the
signal being examined. In case of some disturbances, temporal patterns cannot
be found. This problem has been considered by us in examination of a voice
signal for a non-invasive diagnosis of selected larynx diseases. We have used
different approaches to solve this problem, for example, recurrent neural networks
[
In this paper, an ant based clustering algorithm working on the basis of
temporal rough set ow graphs is proposed. Rough set ow graphs [
Episode Information Systems and Temporal Rough Set Flow Graphs In this section, we recall the basic concepts concerning information systems and rough set ow graphs which are crucial to understand the approach proposed in the paper as well as we introduce a notion of episode information systems and show how to create rough set ow graphs for such systems.
An information system is a pair S = (U; A), where U is a set of objects, A is a set of attributes, i.e., a : U ! Va for a 2 A, where Va is called a value set of a. Any information system can be represented as a data table, whose columns are labeled with attributes, rows are labeled with objects, and entries of the table are attribute values.
In our approach, we will use information systems to represent time series data. Biosignals recorded in electronic devices have a digital form and they can be treated as time series, i.e., sequences of signal samples. Each consecutive sample represents a value of the signal at a given time instant. Therefore, we assume that a set of attributes in an information system is ordered in time, i.e., A = fat : t = 1; 2; : : : ; ng, where at is the attribute determining values of the signal at time instant t. Each object in such a system is said to be an episode and the whole system will be called an episode information system and denoted by Se. An example of the episode information system Se = (E; A), where E is a nonempty nite set of episodes and A is a nonempty nite set of attributes ordered in time, is shown in Figure 1. This system includes ve episodes of real voice signals and each episode consists of ve consecutive samples.
Rough set ow graphs have been de ned by Z. Pawlak [
An input of a node x 2 N is the set I(x) = fy 2 N : (y; x) 2 Bg, whereas an output of a node x 2 N is the set O(x) = fy 2 N : (x; y) 2 Bg. (x; y) is called a strength of a branch (x; y) 2 B. We de ne the input and the output of the graph G as I(G) = fx 2 N : I(x) = ;g and O(G) = fx 2 N : O(x) = ;g, respectively. I(G) and O(G) consist of external nodes of G. The remaining nodes of G are its internal nodes.
With each node x 2 N we associate its in ow +(x) and out ow (x) de ned by: { +(x) = { (x) =
P y2I(x)
P y2O(x) (y; x), (x; y).
For each node x 2 N , its through ow (x) is de ned as follows:
8 (x) if x 2 I(G); (x) = < +(x) if x 2 O(G); : (x) = +(x) otherwise. (1)
With each branch (x; y) 2 B we may also associate its certainty cer(x; y) = (x;y) , where (x) 6= 0. (x)
A directed path [x : : : y] between nodes x and y in G, where x 6= y, is a sequence of nodes x1; x2; : : : ; xn such that x1 = x, xn = y and (xi; xi+1) 2 B, where 1 i n 1. For each path [x1 : : : xn], we de ne its certainty as n 1 cer[x1 : : : xn] = Q cer(xi; xi+1). In our approach, we will use di erent operators i=1 (not only product) for calculating a certainty of a given path.
To represent an information ow distribution in an episode information system we can use rough set ow graphs. A very similar problem has been considered Algorithm 1: Algorithm for creating a temporal rough set ow graph corresponding to an episode information system
Input : An episode information system Se = (E; A), where
A = fat : t = 1; 2; : : : ; ng.
Output: A temporal rough set ow graph G = (N; B; ; cer) corresponding to
Se.
N ;; B ;; for each i = 1; 2; : : : ; n do
Ni ;; for each attribute value v of ai do
Create a node nv representing v and add it to Ni; end N
N [ Ni; end for each i = 1; 2; : : : ; n 1 do for each node nv 2 Ni do for each node nw 2 Ni+1 do
Create a branch b = (nv; nw); (b) card(E(acia;vr)d\(EE)(ai+1;w)) ; card(E(ai;v)\E(ai+1;w)) ;
card(E(ai;v)) cer(b) B
B [ fbg;
end
end
end
in [
Let Se = (E; A), where A = fat : t = 1; 2; : : : ; ng be an episode information system. By E(ai; v) we denote the set of all episodes in E for which the attribute ai has the value v.
Ant based clustering of time series was considered by us in [
Let P be a set of all places of the square grid G on which objects are scattered. Each place p of G is described by two coordinates, i and j, written as p(i; j). The neighborhood (p) of p(i; j), where a given object is foreseen to be dropped or whence it is foreseen to be picked up, is de ned as a square surrounding p(i; j), i.e.:
(p) = fp0(i0; j0) 2 P : abs(i0 i) <= r and abs(j0 j) <= rg; where r is a radius of perception of ants and abs denotes the absolute value.
For the neighborhood (p), a local episode information system Se(p) is created. Se(p) includes all episodes placed in (p). Next, on the basis of Se(p), a temporal rough set ow graph T RSF G(p) is built using Algorithm 1. T RSF G(p) serves as a base for calculating a local function value.
Let Se(p) = (E; A), where A = fat : t = 1; 2; : : : ; ng, be a local episode information system and e be the episode designated to pick up from or to drop at the place p. If e is described by the following attribute values: a1(e ) = v1, a2(e ) = v2, ..., an(e ) = vn, then a local function floc(e ) is calculated as: n 1 floc(e ) = Op cer(nivi ; niv+i+11 ); i=1 (2) where:
vi+1. { Op is an aggregation operator, for example, median, arithmetic average, average weighted with di erent ways, etc.,
i { nvi is the node in the i-th layer of T RSF G(p) corresponding to value vi, { niv+i+11 is the node in the (i + 1)-th layer of T RSF G(p) corresponding to value It is easy to see that a local function is calculated as the aggregation of certainty factors of branches belonging to the path in T RSF G(p) determined by attribute values of the episode e .
To avoid forming smaller clusters of very similar episodes, the threshold density minDens is used. The density dens(e) of the neighborhood (p) for the episode e designated to pick up from or to drop at the place p is calculated as a ratio of a number of all episodes placed in the neighborhood (p) to a number of all places in the neighborhood (p).
Picking and dropping decisions for the episode e can be formally expressed by the following threshold formulas: and ppick(e) = ( 1
1 (1 #spiimck)2 (floc(e) pdrop(e) = ( 1
if floc(e) <= #spiimck; 1)2 otherwise if floc(e) >= #sdirmop; 1 (#sdirmop)2 floc(e)2 otherwise: (3) (4)
Thresholds #spiimck and #sdirmop for picking and dropping operations, respectively, are xed. These values are selected experimentally for given sets of signals. 4
It was mentioned in the introduction that we are interested in periodical biosignals. The classi cation procedure proposed in this paper is as follows. We divide a given fragment of a periodic biosignal into time windows. Each time window represents one period of the signal. A signal included in one time window is called an episode. The set of episodes is used in the clustering process.
In the experiments, voice signals collected by J. Warchol [
Before clustering, we apply some pre-processing procedures:
1. Values of signal samples are normalized to the interval [ 1:0; 1:0].
2. Each episode is transformed into the so-called delta representation, i.e.,
values of samples have been replaced with di erences between values of current
samples and values of previous samples. After transformation, each episode
is a sequence consisting of three values: -1 (denoting decreasing), 0
(denoting a lack of change), 1 (denoting increasing) (cf. [
Experiments for the ant based clustering have been performed with the following parameters: { grid size: 100 100, { no. of ants: 5, { radius of perception: 2, { no. of iterations : 10000, { aggregation operator : arithmetic average.
Algorithm 2: Algorithm for Ant Based Clustering of Episodes for each episode ei 2 E do
Place ei randomly on a grid G;
Set ei as dropped; end for each ant aj 2 Ants do
Place aj randomly on a grid place occupied by one of episodes from E; Set aj as unladen; workT ime(aj ) 0; end for k 1 to N do for each ant aj 2 Ants do if aj is unladen then if place of aj is occupied by episode e then
Draw a random real number r 2 [0; 1]; if dens(e) < minDens or r ppick(e) then set e as picked; set aj as carrying the episode; else else end else end else end move aj randomly to another place occupied by one of episodes from E; move aj randomly to another place occupied by one of episodes from E; Draw a random real number r 2 [0; 1]; if r pdrop(e) then move e carried by aj randomly to a new place on a grid; set e as dropped; set aj as unladen; workT ime(aj ) 0; workT ime(aj )
workT ime(aj ) + 1; end if workT ime(aj ) > maxW orkT ime then set e carried by aj as dropped; set aj as unladen; move aj randomly to another place occupied by one of episodes from E; workT ime(aj ) 0; end end increase minDens; end After a clustering process, we expect to have two distinguishable situations. If episodes are similar (there are no disturbances), then they are grouped into very cohesive clusters. If signi cant replication disturbances appear, then episodes are grouped in several dispersed clusters or they are scattered on the grid. A result of clustering is an indicator used to classify the examined biosignal.
Exemplary results of ant based clustering, for the signals without and with disturbances of periodicity, are shown in Figures 4 and 5, respectively. For comparison, we also present a result of ant based clustering for a pure sine signal (see Figure 6). In the paper, the rst attempt to application of ant based clustering based on temporal rough set ow graphs for classi cation of disturbed periodic biosignals has been presented. At the beginning, we were interested in simple classi cation, i.e., periodicity of the examined signal is disturbed or no. In the future, we plan to make more detailed analysis of results of a clustering process. This should give us additional information about the scale and character of disturbances. Acknowledgments This paper has been partially supported by the grant No. N N519 654540 from the National Science Centre in Poland.