Lecture Notes in Computer Science 4400 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. James F. Peters Andrzej Skowron Victor W. Marek Ewa Orłowska Roman Słowin´ski Wojciech Ziarko (Eds.) Transactions on Rough Sets VII Commemorating the Life and Work of Zdzisław Pawlak, Part II 1 3 Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Editors-in-Chief JamesF.Peters UniversityofManitoba,Winnipeg,Canada E-mail:[email protected] AndrzejSkowron WarsawUniversity,Poland E-mail:[email protected] VolumeEditors VictorW.Marek UniversityofKentucky,Lexington,USA E-mail:[email protected] EwaOrłowska NationalInstituteofTelecommunications,Warsaw,Poland E-mail:[email protected] RomanSłowin´ski PoznanUniversityofTechnology,Poznan,Poland E-mail:[email protected] WojciechZiarko UniversityofRegina,Canada E-mail:[email protected] LibraryofCongressControlNumber:2007922187 CRSubjectClassification(1998):F.4.1,F.1,I.2,H.2.8,I.5.1,I.4 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-71662-9SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-71662-4SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2007 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12042814 06/3180 543210 Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Preface Volume VII of the Transactions on Rough Sets (TRS) is a sequel to volume VI of the TRS. Both volumes commemorate the life and work of Zdzis(cid:2)law Pawlak (1926-2006)1. It is evident from the wide spectrum of contributions to these volumesthatZdzis(cid:2)lawPawlak’slegacyisrichandvaried.Prof.Pawlak’sresearch contributions have had far-reaching implications inasmuch as his works have served as cornerstones in establishing new frontiers for scientific research in a number of fields. Fromanearlyage,Zdzisl(cid:2)awPawlakdevotedhislifetoscientificresearch.His pioneering work included research on modeling industrial processes, the design of computers, information retrieval, modeling conflict analysis and negotiation, geneticgrammarsandmolecularcomputing.Hisresearchledtotheintroduction of knowledge representation systems during the early 1970s and the discovery of rough sets during the early 1980s. Added to that was Prof. Pawlak’s lifelong interest in painting, photography and poetry. During his lifetime, he nurtured worldwide interest in approximation, approximate reasoning and rough set the- ory and its applications2. Evidence of the influence of Prof. Pawlak’s work can be seen in the growth of rough-set literature that now includes over 4000 pub- lications by more than 1600 authors in the rough set database3 as well as the growthandmaturityoftheInternationalRoughSetSociety4.Moreover,numer- ous biographies of Zdzis(cid:2)law Pawlak have been published5. This volume of the TRS presents papers that reflect the profound influence of a number of research initiatives by Zdzisl(cid:2)aw Pawlak. In particular, it intro- ducesanumberofnewadvancesinthefoundationsandapplicationsofartificial intelligence, engineering, logic, mathematics, and science. These advances have significant implications in a number of research areas. In addition, it is evident fromthepapersincludedinthisvolumethatroughsettheoryanditsapplication form a very active research area worldwide. A total of 42 researchers from 13 countries are represented in this volume, namely, Australia, Canada, Germany, India,Italy,Japan,Poland,P.R.China,Sweden,Thailand,Taiwan,UK(Wales) andtheUSA.Evidenceofthevigor,breadthanddepthofresearchinthetheory and applications of rough sets can be found in the articles in this volume. 1 Prof. Pawlak passed away on 7 April 2006. 2 See, e.g., Pawlak, Z., Skowron, A.: Rudiments of rough sets, Information Sciences 177 (2007) 3–27; Pawlak, Z., Skowron, A.: Rough sets: Some extensions, Informa- tion Sciences 177 (2007) 28–40; Pawlak, Z., Skowron, A.: Rough sets and Boolean reasoning, Information Sciences 177 (2007) 41–73. 3 http://rsds.wsiz.rzeszow.pl/rsds.php 4 http://roughsets.home.pl/www/ 5 See, e.g., Peters, J.F. and Skowron, A., Zdzis(cid:2)law Pawlak: Life and Work. Transac- tions on Rough Sets V, LNCS 4100 (2006) 1-24. See, also, R. S(cid:2)lowin´ski, Obituary, Prof. Zdzis(cid:2)law Pawlak (1926-2006), Fuzzy Sets and Systems 157 (2006) 2419-2422. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. VI Preface Most of the contributions of this commemorative volume of the TRS are on an invitational basis and every paper has been refereed in the usual way. This special issue of the TRS contains 19 papers that explore a number of research streams that are either directly or indirectly related to research initiatives by Zdzisl(cid:2)aw Pawlak. These research streams are represented by papers on intelli- gentsignalprocessingtechniques(AndrzejCzyz˙ewski),beliefnetworks(JerzyW. Grzyma(cid:2)la-Busse, Zdzis(cid:2)law S. Hippe, Teresa Mroczek), relational attribute sys- tems(IvoDu¨ntsch,Gu¨ntherGediga,EwaOrl(cid:2)owska),dominance-basedroughset approach(SalvatoreGreco,BenedettoMatarazzo,RomanSl(cid:2)owin´ski),roughsets inbioinformatics(TorgeirR.Hvidsten,JanKomorowski),selectionofimportant attributesformedicaldiagnosissystems(GrzegorzIlczuk,AlicjaWakulicz-Deja), rough clustering (Pawan Lingras), case-based reasoning classifiers (Yan Li, Si- mon Chi-Keung Shiu, Sankar Kumar Pal, James Nga-Kwok Liu), Web infor- mation gathering (Yuefeng Li, Ning Zhong), rough sets in pattern recognition (Sushmita Mitra, Haider Banka), possibilistic information (Michinori Nakata, Hiroshi Sakai), hybrid rough sets-population-based system (Puntip Pattarain- takorn, Nick Cercone), intelligent system for survival analysis based on hybrid roughsets(PuntipPattaraintakorn,NickCercone,KanlayaNaruedomkul),clas- sifyingremotelysensedimages(B.UmaShankar),roughfeatureselection(Qiang Shen), granulation in information security (Da-Wei Wang, Churn-Jung Liau, Tsan-sheng Hsu), definability and approximation (Yiyu Yao), audiovisual emo- tionrecognition(YongYang,GuoyinWang,PeijungChen,JianZhou,KunHe). Theeditorsofthisvolumeextendtheirheartythankstothefollowingreview- ers: Jan Bazan, Maciej Borkowski, Beata Konikowska, Boz˙ena Kostek, Pawan Lingras, Son Nguyen, Wladysl(cid:2)aw Skarbek, Marcin Szczuka, Sheela Ramanna, Dominik S´le¸zak,JerzyStefanowski,PiotrSynak,DimiterVakarelov,HuiWang, Piotr Wasilewski, Marcin Wojnarski, Jakub Wro´blewski, and Yiyu Yao. This issue of the TRS has been made possible thanks to the laudable efforts ofa greatmanygenerouspersons andorganizations.The editorsand authorsof this volume also extend an expression of gratitude to Alfred Hofmann, Ursula Barth, Christine Gu¨nther and the LNCS staff at Springer for their support in making this volume of the TRS possible. In addition, the editors extend their thanks to Marcin Szczuka for his consummate skill and care in the compilation of this volume. December 2006 Victor Marek Ewa Orl(cid:2)owska James F. Peters Roman Sl(cid:2)owin´ski Andrzej Skowron Wojciech Ziarko Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. LNCS Transactions on Rough Sets This journal subline has as its principal aim the fostering of professional ex- changes between scientists and practitioners who are interested in the founda- tionsandapplicationsofroughsets.Topicsincludefoundationsandapplications ofroughsetsaswellasfoundationsandapplicationsofhybridmethodscombin- ingroughsetswithotherapproachesimportantforthedevelopmentofintelligent systems. The journal includes high-quality research articles accepted for publication on the basis of thorough peer reviews. Dissertations and monographs up to 250 pagesthatincludenewresearchresultscanalsobeconsideredasregularpapers. Extended and revised versions of selected papers from conferences can also be included in regular or special issues of the journal. Honorary Editor: Zdzisl(cid:2)aw Pawlak – deceased Editors-in-Chief: James F. Peters, Andrzej Skowron Editorial Board M. Beynon M. do C. Nicoletti G. Cattaneo H.S. Nguyen M.K. Chakraborty S.K. Pal A. Czyz˙ewski L. Polkowski J.S. Deogun H. Prade D. Dubois S. Ramanna I. Du¨ntsch R. Sl(cid:2)owin´ski S. Greco J. Stefanowski J.W. Grzymal(cid:2)a-Busse J. Stepaniuk M. Inuiguchi Z. Suraj J. Jrvinen R. S´winiarski D. Kim M. Szczuka J. Komorowski S. Tsumoto C.J. Liau G. Wang T.Y. Lin Y. Yao E. Menasalvas N. Zhong M. Moshkov W. Ziarko T. Murai Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Table of Contents Contributed Papers Speech Coding Employing Intelligent Signal Processing Techniques..... 1 Andrzej Czyzewski Relational Attribute Systems II: Reasoning with Relations in Information Structures ........................................... 16 Ivo Du¨ntsch, Gu¨nther Gediga, and Ewa Orl(cid:2)owska Dominance-Based Rough Set Approach as a Proper Way of Handling Graduality in Rough Set Theory ................................... 36 Salvatore Greco, Benedetto Matarazzo, and Roman S(cid:2)lowin´ski Deriving Belief Networks and Belief Rules from Data: A ProgressReport ............................................... 53 Jerzy W. Grzymal(cid:2)a-Busse, Zdzisl(cid:2)aw S. Hippe, and Teresa Mroczek Selection of Important Attributes for Medical Diagnosis Systems....... 70 Grzegorz Ilczuk and Alicja Wakulicz-Deja Using Approximate Reduct and LVQ in Case Generation for CBR Classifiers....................................................... 85 Yan Li, Simon Chi-Keung Shiu, Sankar Kumar Pal, and James Nga-Kwok Liu Mining Rough Association from Text Documents for Web Information Gathering....................................................... 103 Yuefeng Li and Ning Zhong Applications of Rough Set Based K-Means, Kohonen SOM, GA Clustering ...................................................... 120 Pawan Lingras Characterizing Pawlak’s Approximation Operators ................... 140 Victor W. Marek Application of Rough Sets in Pattern Recognition.................... 151 Sushmita Mitra and Haider Banka Lower and Upper Approximations in Data Tables Containing Possibilistic Information .......................................... 170 Michinori Nakata and Hiroshi Sakai Hybrid Rough Sets-PopulationBased System........................ 190 Puntip Pattaraintakorn and Nick Cercone Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. X Table of Contents Hybrid Rough Sets Intelligent System Architecture for Survival Analysis ........................................................ 206 Puntip Pattaraintakorn, Nick Cercone, and Kanlaya Naruedomkul Rough Sets in Bioinformatics...................................... 225 Torgeir R. Hvidsten and Jan Komorowski Rough Feature Selection for Intelligent Classifiers .................... 244 Qiang Shen Granulation as a Privacy Protection Mechanism ..................... 256 Da-Wei Wang, Churn-Jung Liau, and Tsan-sheng Hsu A Note on Definability and Approximations ......................... 274 Yiyu Yao Feature Selection in Audiovisual Emotion Recognition Based on Rough Set Theory...................................................... 283 Yong Yang, Guoyin Wang, Peijun Chen, Jian Zhou, and Kun He Monographs Novel Classification and Segmentation Techniques with Application to Remotely Sensed Images.......................................... 295 B. Uma Shankar Author Index.................................................. 381 Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Speech Coding Employing Intelligent Signal Processing Techniques Andrzej Czyzewski Multimedia SystemsDepartment Gdansk Universityof Technology ul. Narutowicza 11/12, 80-952 Gdansk,Poland [email protected] Abstract. Theconceptsandexperimentspresentedarefocusedonmod- ifications of an existing parametric speech coding algorithm (CELP) introduced in order to improve subjective speech quality in telephone connections. The perceptual coding to bit rate limiting was added and algorithms qualifying speech components to the categories of ”voiced”, ”unvoiced”, ”transients” using rough sets were studied. The speech sig- nal quality achieved with the proposed hybrid codec was compared to thequality offered by some standard speech codecs. Keywords: CELP residual coding, hybrid codec architecture, percep- tual speech coding, rough set decision algorithm. 1 Introduction Themajorityofspeechtelecommunicationsystemsintoday’suseofferanarrow- band transmission, limited to about 200– 4000 Hz. The principal effect of band limiting is the degradation of intelligibility of speech occurring mostly due to the influence of upper band limiting to the perception of plosives and fricatives. Moreover,recognizingco-talkersisimpededbecauseofthemeaningofvocaltone band located in the range of low frequencies. Typicalapplicationsofcomputertechnologiesindigitalsignalprocessingonly rarely consider the opportunities of data processing with the use of methods which stem from artificial intelligence or soft computing. In the meantime the area of DSP (Digital Signal Processing) has an extensive demand for applica- tions of intelligent signal processing because of unrepeatability and uncertainty of real-life signals and the lack of adequate mathematical models of signal pro- duction processes. That is why learning algorithms and data mining techniques are important to this kind of applications. Inmostoftheapplicationsrelatedtotransmissionofspeechsignal,parametric coding algorithms are used (CELP, ACELP, LD-CELP, etc.). These algorithms reducebit-rateofthesignalsignificantly,sacrificingqualityofthesignaltosome degree.Formanyyears,bit-rateanddelaywerethemaincriteriainspeechcodec assessment, while subjective signal quality, expressed using the mean opinion score (MOS) scale, was considered less important. Most of parametric speech J.F.Petersetal.(Eds.):TransactionsonRoughSetsVII,LNCS4400,pp.1–15,2007. (cid:2)c Springer-VerlagBerlinHeidelberg2007 Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 2 A.Czyzewski codecsusedincurrentapplicationsprovidessignalqualityfrom3.2to4.0inthe MOS scale (where 5.0 means the best possible quality) [26]. The meaning of wideband speech is now recognized in some newer ITU-T standards. Two of them, called AMRWB and VMRWB, can be viewed as pure speech coding algorithms based on the ACELP technology. They do not pro- vide, however, at least satisfactory quality of non-speech signals representation [19,24]. Therefore, an extended AMRWB+ codec was introduced to overcome this limitation. Unfortunately, as the AMRWB+ codec takes an advantage of hybrid ACELP/transformcoding techniques, it introduces a coding delay up to 90ms,thusingeneralitisnotsuitableforthereal-timetwo-waycommunication. Accordingly,onecannoticethatthereisstillaneedforAwideband,highquality, mid-delay speech codec with improved ability to encode non-speech signals. Contrarilytocodingtechniquesbasedonthespeechproductionmodel,thatis insufficient for more complex signals, the codec proposed in this paper employs theanalysistechniqueforextractingsines,noiseandtransientpartsofthesignal. The analysisis supported by a soft computing algorithm.In the next step, each part of the entire signal is encoded using an adequate technique, including the perceptual criteria. It has to be mentioned that sines+residual model is widely used as a powerful tool for signal modification (e.g. pitch, time-scale) [20]. The sines+residual signal representation was also employed for efficient narrowband speech coding at about 8 kbps rate. Additionally, it was found that it is a ro- bust method for coding both speechsignals and mixed audio content[18,21,23]. Concerning this, it was also expected that extending the sines+residual model with transient selection module will further improve the signal representation accuracy. As the aim is to present the super-wideband signal to the listener, the spectrum components exceeding 7 kHz are reconstructed artificially in the proposedapproach.It has to be mentioned that during some stagesof encoding processtheperceptualcriterionwasapplied,allowingareductionofthebit-rate requirements for the codec bit stream [5,22]. The main problem in the parametric approach to speech coding is how to encode transients, voiced and unvoiced signal components, efficiently. Encod- ing of transient states is especially important here, because an inappropriate encoding of transients may result in significantly decreased signal quality, Vari- ous parametric codecs use different approach to this problem, yet none of these approaches provide sufficiently accurate transient encoding, which is reflected in quality values (MOS). One of the concepts of the hybrid codec presented in this paper is extraction of transient, voiced and unvoiced components from the signal and using an appropriate approach for each of these groups. In the synthesisofmusicalinstruments,the introductionoftransientanalysisandsyn- thesis to the “sine and noise” model resulted in improved signal quality. Hence, it may be expected that using a similar “voiced-transient-unvoiced” approach to speechsignalwillprovideanimprovementofsignalquality,aswell.However, no research on this topic has been done so far by the author and his team of researchers. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.