Classi cation of Voice Signals through Mining Unique Episodes in Temporal Information Systems: A Rough Set Approach

Abstract

Classi cation of voice signals in a time domain for detecting some disturbances can be made through mining unique episodes in temporal information systems. In ideal case, a voice signal is periodic and signal shapes in each period are the same. In case of larynx diseases, some disturbances in a voice signal can be distinguished. Selected time windows (sequences of signal samples) of a voice signal constitute a temporal information system. Appearing unique episodes in such a system can indicate disturbances in the signal. In the paper, we show the methodology, based on a rough set approach, of mining unique episodes in temporal information systems as well as its application for classi cation of voice signals.

Keywords

• voice signal classi cation
• temporal information systems
• episodes
• rough sets

-

Temporal data mining is an important issue in computer science research (cf. [ 4 ]). There exists a huge literature concerning this topic. One of the frequently examined problems is mining episodes de ned as partially ordered sets of events for consecutive and xed-time intervals in sequences. Most of studies consider analyzing simple or complex sequences to nd frequent episodes (cf. [ 2 ], [ 3 ]), i.e., collections of events occurring frequently together. In our research, we consider a slightly di erent problem. We assume that a set of episodes of the same length is given. Our task is to nd episodes which, in some sense (i.e., according to a given criterion), clash with other episodes in the set. In our case, the criterion is the so-called consistency factor de ned in terms of rough sets.

In the paper, classi cation of voice signals in a time domain is considered. A voice signal can be treated as a time series, i.e., a sequence of signal samples. The main idea of the proposed approach is based on recognition of temporal patterns and their replications in the fragment of a voice signal being examined (cf. [ 15 ], [ 16 ]). It allows detecting all non-natural disturbances in articulation of selected phonemes by patients. Preliminary observations showed that signi cant replication disturbances in time appear for patients with the clinical diagnosis of disease.

In [ 15 ], [ 16 ], there have been used neural networks with the capability of extracting the phoneme articulation pattern for a given patient (articulation is an individual patient feature) and the capability of assessment of its replication in the whole examined signal. In this case, the process consists of two stages: training and testing a neural network. The approach similar to the cross-validation strategy is used. One time window is taken for training the neural network and the remaining ones for testing the neural network. The network learns a selected time window. If the remaining windows are similar to the selected one in terms of the time patterns, then for such windows an error generated by the network in a testing stage is small. If signi cant replication disturbances in time appear for patients having some problems with the voice organ, then an error generated by the network is greater. In this case, the time pattern is not preserved in the whole signal. Therefore, the error generated by the network re ects non-natural disturbances in the patient phonation.

In this paper, instead of neural networks, the technique, based on a rough set approach, of mining unique episodes in temporal information systems is proposed. As distinct from the approach based on neural networks, there is only one step in the proposed approach. This step consists of mining unique episodes. If episodes representing selected time windows of a voice signal of a given patient are similar (there is a lack of non-natural disturbances), then a special coe cient, called a consistency factor, calculated for these episodes is close to 1. If signi cant replication disturbances in time appear for patients with the larynx disease, then some episodes with consistency factors deviating from 1 are identi ed.

To represent time windows of voice signals, we use temporal information systems, i.e., information systems whose rows (objects) are ordered in time. The temporal information systems may lead us to dynamic information systems proposed by Z. Suraj (see [ 14 ]). The dynamic information systems represent the knowledge of states of systems and transitions between states. The transitions between states were described by binary transition relations. In this paper, we use a notion of multistage dynamic information systems proposed in [ 7 ]. These systems enable us to represent multistage transitions among states (observed sequences of states, also called episodes). Transitions among states are described by polyadic transition relations. The multistage decision transition systems are used to represent such relations. To transform a given temporal information system into the multistage decision transition system we select a set of time windows. Each time window includes consecutive states constituting a cohesive part of the temporal information system.

Sequences of temporal consecutive states are called episodes. In the proposed application, we take into consideration the so-called unique episodes. A unique episode is de ned as an episode which is weakly consistent with the knowledge extracted from the remaining episodes included in the system. The presented approach for mining unique episodes is based on extensions of multistage decision transition systems (see [ 7 ], [ 9 ]). Such extensions have been used in an ant based clustering of time series discrete data (see [ 11 ]). A consistent extension of a given multistage decision transition system consists of new transitions among states, which are totally consistent or consistent only to a certain degree (partially consistent) with the knowledge included in the original multistage decision transition system. The degree of consistency can be between 0 and 1, 0 for the total inconsistency and 1 for the total consistency. We assume that the knowledge included in multistage decision transition systems is expressed by transition rules (see [ 10 ]), which are minimal decision rules understood from the rough set point of view. To calculate the degree of consistency we use an approach presented in [ 9 ]. That approach originates from the e cient algorithm given in [ 5 ] enabling us to determine which transitions (episodes) in the original multistage decision transition system generate transition rules not satis ed by the tested episode from the extension. It is worth noting that we do not calculate any transition rules in a multistage decision transition system. This is an important property from the point of view of computational complexity. 2

Basic Notions

Information systems are used to represent some knowledge of elements of a universe of discourse. An information system is a pair S = (U; A), where U is a nonempty, nite set of objects, A is a nonempty, nite set of attributes, i.e., a : U ! Va for a 2 A, where Va is called a value set of a. A decision system is a pair S = (U; A), where A = C [ D, C \ D = ;, and C is a set of condition attributes, D is a set of decision attributes. Any information (decision) 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.

Let S = (U; A) be an information system. Each subset B A of attributes determines an equivalence relation on U , called an indiscernibility relation Ind(B), de ned as Ind(B) = f(u; v) 2 U U : 8 a(u) = a(v)g. The equivalence class a2B containing u 2 U will be denoted by [u]B.

Let X U and B A. The B-lower approximation BX of X and the Bupper approximation BX of X are de ned as BX = fu 2 U : [u]B Xg and BX = fu 2 U : [u]B \ X 6= ;g, respectively.

A temporal information system is a kind of an information system S = (U; A), with a set U of objects ordered in time, i.e., U = fut : t = 1; 2; : : : ; ng, where ut is the object observed at time instant t. By a time window on S of the length in a point we understand an information system S0 = (U 0; A0), where U 0 = fu ; u +1; : : : ; u + 1g, 1 , + 1 n, and A0 is a set of all attributes from A de ned with value sets restricted to those for objects from U 0. The length of S0 is de ned as = card(U 0). In the sequel, the set A0 of all attributes in any time window S0 = (U 0; A0) of S = (U; A) will be marked, for simplicity, with the same letter A like in S.

Example 1. Let us consider a simple temporal information system with two attributes marked with a and b. Seven objects (global states) are collected in Table 1. Formally, we have a temporal information system S = (U; A), for which: { a set of objects (global states) U = fu1; u2; : : : ; u7g, { a set of attributes A = fa; bg, { sets of attribute values: Va = f 1; 1g, Vb = f 1; 0; 1g. In [ 14 ], dynamic information systems have been proposed for a description of concurrent systems. A dynamic information system additionally (in relation to information systems) includes information about transitions between global states observed in a given concurrent system. In this section, we recall some crucial notions concerning multistage decision transition systems and their extensions (see [ 7 ], [ 9 ], [ 10 ], [ 14 ]).

A multistage transition system is a pair M T S = (U; T ), where U is a nonempty set of states and T U k is a polyadic transition relation, where k > 2. A multistage dynamic information system is a tuple M DIS = (U; A; T ), where S = (U; A) is an information system called the underlying system of M DIS, U is called a set of global states of M DIS, and M T S = (U; T ) is a multistage transition system.

A multistage transition system is created on the basis of a temporal information system according to Algorithm 1.

Example 2. Let us take into consideration a temporal information system S from Example 1. We can create a multistage transition system on the basis of S. Assuming = 3 (a number of consecutive objects from U taken for a polyadic transition relation), after performing Algorithm 1, we obtain a multistage transition system M T S = (U; T ), such that a set of global states U = fu1; u2; : : : ; u7g, and a polyadic transition relation

T = f(u1; u2; u3); (u2; u3; u4); (u3; u4; u5); (u4; u5; u6); (u5; u6; u7)g: end

Create M T S = (U; T ); Algorithm 1: Algorithm for creating a multistage transition system on the basis of a temporal information system.

Input : A temporal information system S = (U; A), where

U = fut : t = 1; 2; : : : ; ng, - a number of consecutive objects from U taken for a polyadic transition relation.

Output: A multistage transition system M T S = (U; T ) corresponding to S. T ;; for each = 1 : : : n + 1 do

Get a sequence u ; u +1; : : : ; u + 1 of consecutive objects from U ;

T T [ (u ; u +1; : : : ; u + 1);

Let M DIS = (U; A; T ) be a multistage dynamic information system, where T U k. Each element (u1; u2; : : : ; uk) 2 T , where u1; u2; : : : ; uk 2 U , is called an episode in M DIS.

Let M T S = (U; T ) be a multistage transition system. A multistage decision transition system is a pair M DT S = (UT ; A1 [ A2 [ : : : [ Ak), where each t 2 UT corresponds exactly to one element of the polyadic transition relation T whereas attributes from the set Ai determine global states of the i-th domain of T , where i = 1; 2; : : : ; k. Each object in a multistage decision transition system represents one episode in a given multistage dynamic information system M DIS. Example 3. Let us take into consideration a temporal information system S from Example 1. For the system S, we can create ve time windows of length 3. All sequences of objects in time windows de ne a polyadic transition relation T (see Example 2). On the basis of T , we de ne a multistage decision transition system M DT S shown in Table 2. We have ve episodes t1, t2, t3, t4, and t5. We can say that attributes from the set A1 = fa1; b1g determine global states at time instant , attributes from the set A2 = fa2; b2g determine global states at time instant + 1 and attributes from the set A3 = fa3; b3g determine global states at time instant + 2.

For a given multistage decision transition system, we can consider its elementary decision transition subsystems de ned as follows.

An elementary decision transition subsystem of a multistage decision transition system M DT S = (UT ; A1 [ A2 [ : : : [ Ak) is a decision transition system DT S(i; i + 1) = (UT ; Ai [ Ai+1), where: i 2 f1; :::; k 1g.

Example 4. Let us take into consideration a multistage decision transition system M DT S from Example 3. For M DT S, we obtain two elementary decision transition subsystems DT S(1; 2) and DT S(2; 3) shown in Table 3.

Any nontrivial extension of a given multistage decision transition system M DT S = (UT ; A1 [ A2 [ : : : [ Ak) includes episodes existing in M DT S as well as new ones added to M DT S.

Let DT S(i; i + 1) = (UT ; Ai [ Ai+1) be the elementary decision transition subsystem. For each attribute a 2 Ai and the new episode t , we can transform DT S(i; i + 1) into the system with irrelevant values of attributes. If a(t ) 6= a(t), where t 2 UT , then we replace a(t) by the value * (denoting an irrelevant value). This means that we create a new system for which appropriate sets of attribute values are extended by the value *. The transformed system can be treated as an incomplete system. Therefore, instead of an indiscernibility relation and equivalence classes, we use a characteristic relation and characteristic sets (cf. [ 1 ]). For the transformed elementary decision transition subsystem DT S(i; i + 1) = (UT ; Ai [ Ai+1), we de ne a characteristic relation R(Ai). R(Ai) is a binary relation on UT de ned as follows:

R(Ai) = f(t; v) 2 UT2 : a29Ai a(t) 6= ^ a28Ai(a(t) = _ a(t) = a(v)) g: (1)

For each episode t from the extension of M DT S, we de ne a consistency factor of t (see [ 8 ], [ 9 ]). The consistency factor MDT S (t ) of the episode t with the knowledge included in M DT S is calculated as: 0 card(

S S fAiXava : AiXava 6= ; ^ a(t ) 6= vag) 1 a2Ai+1 va2Va card(UT )

C ; (2) A k 1 MDT S(t ) = Y B1

i=1 @ where { Xava = ft 2 UT : a(t) = vag, { AiXava = ft 2 UT : KAi (t) 6= ; ^ KAi (t)

tion of Xava , { KAi (t) = fv 2 UT : (t; v) 2 R(Ai)g is a characteristic set.

Xava g is an Ai-lower approxima

From the point of view of rough set theory, we have that a lower approximation consists of episodes for which values of global states described by attributes from Ai (i.e., global states at time instant ) uniquely de ne values of global states described by attributes from Ai+1 (i.e., global states at next time instant + 1). It means that, for such episodes, we can de ne certain transition rules (rules describing transitions between states), see [ 9 ]. If we add a new episode for which Ai de nes the same values of a global state as for episodes belonging to some lower approximation, but the next global state is di erent, then this new episode does not satisfy a certain transition rule valid in a given multistage decision transition system M DT S. We say that such a new episode is not consistent with the knowledge included in M DT S and expressed by transition rules. It can be consistent only partially.

Example 5. Let us take into consideration an elementary decision transition subsystem DT S(1; 2) from Example 4. Taking Xa12 = ft2; t3g, we have A1Xa12 = ft3g, where A1 = fa1; b1g, because: { For the episode t3, A1 describes the state a1(t) = 1 and b1(t) = 1, where t 2 UT , and this state uniquely de nes the next state in which a2(t) = 1. { For the episodes t1 and t2, A1 describes the state a1(t) = 1 and b1(t) = 1, where t 2 UT , and this state does not uniquely de ne the next state, i.e., for the next state we have a2(t) = 1 (for the episode t1) or a2(t) = 1 (for the episode t2). { Episodes t4 and t5 are out of interest, because, for these episodes, in the next state a2(t) 6= 1.

Therefore, we have, for example, that:

{ A transition rule IF a1(t) = 1 and b1(t) = 1, THEN a2(t) = 1 is a certain rule in DT S(1; 2). { A transition rule IF a1(t) = 1 and b1(t) = 1, THEN a2(t) = 1 is not a certain rule in DT S(1; 2).

Let us add a new episode shown in Table 5 to DT S(1; 2). The episode t does not satisfy a rule IF a1(t) = 1 and b1(t) = 1, THEN a2(t) = 1. It is not totally consistent with the knowledge included in DT S(1; 2).

Algorithm 2: Algorithm for mining unique episodes in a given multistage decision transition system

end end Input : A multistage decision transition system

M DT S = (UT ; A1 [ A2 [ : : : [ Ak), a threshold value 2 [0; 1] determining uniqueness of episodes in M DT S.

Output: A set T UT of unique episodes in M DT S with respect to .

T ;; for each t 2 UT do

Create M DT S0 by removing t from UT in M DT S; Compute MDT S0 (t) according to Formula 2; if MDT S0 (t) then

T T [ t;

On the basis of consistency factors calculated for episodes in a given multistage decision transition system, we can determine which episodes are unique ones in the considered system.

De nition 1. Let M DT S = (UT ; A1 [ A2 [ : : : [ Ak) be a multistage decision transition system, t 2 UT , M DT S0 be a multistage decision transition system emerged from M DT S by the removal of t, and 2 [0; 1] be a threshold value determining uniqueness of t. The episode t is called a unique episode with respect to if and only if MDT S0 (t) .

The process of mining unique episodes may be automated, see Algorithm 2. Example 6. Let us take into consideration the elementary decision transition subsystems DT S(1; 2) and DT S(2; 3) from Example 4. M DT S0 is a multistage decision transition system emerged from M DT S by the removal of the episode t1. Analogously DT S0(1; 2) and DT S0(2; 3) are elementary decision transition subsystems emerged from DT S(1; 2) and DT S(2; 3), respectively, by the removal of t1. We transform DT S0(1; 2) and DT S0(2; 3) into the systems DT S00(1; 2) and DT S00(2; 3), respectively, with irrelevant values of attributes (see Table 5).

We obtain the following non-empty lower approximations:

{ A1Xa12 = ft2g, { A1Xb12 = ft2; t4g, { A2Xa31 = ft3g, { A2Xb03 = ft4; t5g, { A2Xb13 = ft3g.

The remaining lower approximations, i.e.,

A1Xa21; A1Xb21; A1Xb02 ; A2Xa13 ; A2Xb31; are empty.

Let a threshold value determining uniqueness of the episodes be equal to 0:5. Performing Algorithm 2, we have DT S(1;2)(t1) = 0:5 and DT S(2;3)(t1) = 0:25. Finally, we have that a consistency factor of the episode t1 with the knowledge included in the multistage decision transition system M DT S0 is: MDT S0 (t1) = 0:125. According to = 0:5, we can say that the episode t1 is unique in a temporal information system S. 4

Classi cation of Voice Signals

The proposed approach can be used in classi cation of voice signals in the time domain for diagnosis of larynx diseases. A voice signal can be treated as a time series. The classi cation procedure is as follows. We divide the voice signal of an examined patient into time windows corresponding to phonemes. Next, we select randomly a number of time windows. Consecutive signal samples of selected time windows can be presented in the tabular form as a multistage decision transition system. This idea is depicted in Figure 1.

In Table 6, we give some example of such a multistage decision transition system M DT S. Each row of M DT S corresponds to one time window. Each time window consists of 100 signal samples. Values of signal samples are normalized to the interval [ 1:0; 1:0]. Each time window can be treated as an episode. M DT S includes information about ve episodes (time windows). Each episode is described by 100 attributes, a1, a2, ..., a100. The attribute ai, where i = 1; 2; : : : ; 100, determines the value of the i-th signal sample of a given time window. In this example, we have formally M DT S = (UT ; A1 [A2 [: : :[A99 [A100), where UT = ft1; t2; t3; t4; t5g,A1 = fa1g, A2 = fa2g, A3 = fa3g, ..., A99 = fa99g, and A100 = fa100g.

Next, we transform each episode in M DT S 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. [ 11 ]). This transformation enables us to obtain a multistage decision transition system with discrete values. For example, after the transformation of M DT S given in Table 6, we obtain a new multistage decision transition system M DT S shown in Table 7.

UT =A1 [ A2 [ A3 [ : : : [ A99 [ A100 a1

In the transformed multistage decision transition system M DT S , we search for unique episodes using Algorithm 2. If time windows, into which a voice signal is divided, are similar (there are no disturbances), then the unique episodes are not present in M DT S . If signi cant replication disturbances in time appear for patients with the larynx disease, then time windows di er from each other and unique episodes appear in M DT S . Hence, the result of searching for unique episodes is an indicator used to classify patient voice signals according to larynx diseases.

In Table 8, we present selected results of experiments carried out using the proposed approach. Data were collected by J. Warchol [ 18 ]. The results of searching for unique episodes in voice signals of six patients (three from a control group and three with con rmed pathology) are shown. A table includes values of consistency factors of ve episodes calculated for selected patients.

Let a threshold value determining uniqueness of episodes = 0:80. For patients p1, p2, and p3, there are no unique episodes. These patients belong to the control group. For patient p4, one unique episode (time window t3) is detected. For patient p5, three unique episodes (time windows t1, t2, and t3) are detected. For patient p6, one unique episode (time window t2) is detected. Patients p4, p5, and p6 had larynx disease con rmed by clinicians.

The presented methodology has been implemented in the LARDISS system - a tool for computer aided diagnosis of laryngopathies [ 17 ]. The tool is created for the Java platform. 5

Conclusions

In the paper, we have shown how to use multistage decision transition systems and their extensions de ned in [ 7 ] and [ 9 ] for mining unique episodes in temporal information systems as well as how to apply the proposed approach for classication of voice signals in a time domain for detecting some disturbances. The presented approach is based on algorithms with polynomial time complexity. In the future we plan to propose a modi ed consistency factor to improve a quality of classi cation of voice signals.

References

1. Grzymala-Busse , J.W. : Data with missing attribute values: Generalization of indiscernibility relation and rule induction . In: Peters, J. , et al. (eds.) Transactions on Rough Sets I, pp. 78 { 95 . Springer-Verlag, Berlin, Germany ( 2004 )

2. Huang , K.Y. , Chang , C.H.: E cient mining of frequent episodes from complex sequences . Information Systems 33 ( 1 ), 96 { 114 ( 2008 )

3. Mannila , H. , Toivonen , H. , Verkamo , A. : Discovering frequent episodes in event sequences . Data Mining and Knowledge Discovery 1 ( 3 ), 259289 ( 1997 )

4. Mitsa , T. : Temporal Data Mining . CRC Press ( 2010 )

5. Moshkov , M. , Skowron , A. , Suraj , Z. : On testing membership to maximal consistent extensions of information systems . In: Greco, S. , et al. (eds.) Rough Sets and Current Trends in Computing, Lecture Notes in Arti cial Intelligence , vol. 4259 , pp. 85 { 90 . Springer-Verlag, Berlin Heidelberg ( 2006 )

6. Moshkov , M. , Skowron , A. , Suraj , Z. : Maximal consistent extensions of information systems relative to their theories . Information Sciences 178 ( 12 ), 2600 { 2620 ( 2008 )

7. Pancerz , K. : Extensions of dynamic information systems in state prediction problems: the rst study . In: Magdalena, L. , Ojeda-Aciego , M. , Verdegay , J . (eds.) Proceedings of the 12th International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems (IPMU' 2008 ). pp. 101 { 108 . Malaga , Spain ( 2008 )

8. Pancerz , K. , Suraj , Z. : Rough sets for discovering concurrent system models from data tables . In: Hassanien, A. , et al. (eds.) Rough Computing. Theories, Technologies and Applications , pp. 239 { 268 . Information Science Reference, Hershey ( 2008 )

9. Pancerz , K. : Extensions of multistage decision transition systems: The rough set perspective . In: Cyran, K. , et al. (eds.) Man-Machine Interactions , pp. 209 { 216 . Springer-Verlag, Berlin Heidelberg ( 2009 )

10. Pancerz , K. : Some issues on extensions of information and dynamic information systems . In: Foundations of Computational Intelligence ( 5 ), Studies in Computational Intelligence , vol. 205 , pp. 79 { 106 . Springer-Verlag, Berlin Heidelberg ( 2009 )

11. Pancerz , K. , Lewicki , A. , Tadeusiewicz , R.: Ant based clustering of time series discrete data - a rough set approach . In: Panigrahi, B.K. , et al. (eds.) Swarm, Evolutionary, and Memetic Computing, Lecture Notes in Computer Science , vol. 7076 , pp. 645 { 653 . Springer-Verlag, Berlin Heidelberg ( 2011 )

12. Pawlak , Z.: Rough Sets . Theoretical Aspects of Reasoning about Data . Kluwer Academic Publishers, Dordrecht ( 1991 )

13. Pawlak , Z. : Concurrent versus sequential - the rough sets perspective . Bulletin of EATCS 48 , 178 { 190 ( 1992 )

14. Suraj , Z. : The synthesis problem of concurrent systems speci ed by dynamic information systems . In: Polkowski, L. , Skowron , A . (eds.) Rough Sets in Knowledge Discovery 2 . Applications , Case Studies and Software Systems , pp. 418 { 448 . Physica-Verlag, Heidelberg, Germany ( 1998 )

15. Szkola , J. , Pancerz , K. , Warchol , J.: Computer diagnosis of laryngopathies based on temporal pattern recognition in speech signal . Bio-Algorithms and Med-Systems 6 ( 12 ), 75 { 80 ( 2010 )

16. Szkola , J. , Pancerz , K. , Warchol , J.: Recurrent neural networks in computer-based clinical decision support for laryngopathies: An experimental study . Computational Intelligence and Neuroscience 2011 ( 2011 ), article ID 289398

17. Szkola , J. , Pancerz , K. , Warchol , J. , Olchowik , G. , Klatka , M. , Wojecka-Gieroba , R. , Wrobel , A. : LARDISS - a tool for computer aided diagnosis of laryngopathies . In: Proc. of the FedCSIS'2012 . Wroclaw, Poland ( 2012 ), to appear

18. Warchol , J.: Speech Examination with Correct and Pathological Phonation Using the SVAN 912AE Analyser (in Polish) . Ph.D. thesis , Medical University of Lublin ( 2006 )