Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing : 10th International Conference, RSFDGrC 2005, Regina, Canada, August 31 - September 3, 2005, Proceedings, Part I

The two volume set LNAI 3641 and LNAI 3642 constitutes the refereed proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, RSFDGrC 2005, held in Regina, Canada in August/September 2005. The 119 revised full papers presented were carefully reviewed and selected from a total of 277 submissions. They comprise the two volumes together with 6 invited papers, 22 approved workshop papers, and 5 special section papers that all were carefully selected and thoroughly revised. The first volume includes 75 contributions related to rough set approximations, rough-algebraic foundations, feature selection and reduction, reasoning in information systems, rough-probabilistic approaches, rough-fuzzy hybridization, fuzzy methods in data analysis, evolutionary computing, machine learning, approximate and uncertain reasoning, probabilistic network models, spatial and temporal reasoning, non-standard logics, and granular computing. The second volume contains 77 contributions and deals with rough set software, data mining, hybrid and hierarchical methods, information retrieval, image recognition and processing, multimedia applications, medical applications, web content analysis, business and industrial applications, the approved workshop papers and the papers accepted for a special session on intelligent and sapient systems. Front matter......Page 1 Rough Sets......Page 23 Flow Graphs......Page 24 Certainty and Coverage Factors......Page 28 Flow Graph and Decision Algorithms......Page 30 Conclusion......Page 32 Introduction......Page 34 Information Systems and Informational Relations......Page 35 The Information Logic IND......Page 37 Equivalence of the Abstract, Standard and Non-standard Semantics of IND......Page 38 A Complete Axiomatization of IND......Page 41 Decidability of IND......Page 42 Open Problems and Concluding Remarks......Page 44 Introductory Comments......Page 45 Shadowed Sets as a Symbolic Manifestation of Fuzzy Sets......Page 46 The Development of Shadowed Sets......Page 48 Relational Calculus with Shadowed Sets and Relational Equations......Page 50 Taxonomy of Data in Structure Description......Page 51 References......Page 53 Introduction......Page 55 Approximation Spaces and Their Inductive Extensions......Page 56 Approximate Reasoning About Vague Concepts Based on Adaptive Learning and Reasoning......Page 57 An Example: Inducing Concept Descriptions Consistent with Constraints Specified by Experts......Page 61 Conclusions......Page 63 Introduction......Page 65 Formal Contexts and Rough Approximation Operators......Page 66 Attribute Reduction in Concept Lattices......Page 70 Object Reduction in Concept Lattices......Page 72 Conclusions......Page 74 Introduction......Page 76 Problem Statement......Page 77 Dominance Relations......Page 78 Dominance Principle......Page 80 Decision and Condition Granules......Page 81 Dominance-Based Rough Approximations......Page 82 Conclusions......Page 85 Introduction......Page 86 Standard and Generalized Rough Sets......Page 87 New Approach for Rough Sets......Page 89 Conclusion......Page 94 Introduction......Page 96 Basic Definitions in Formal Concept Analysis......Page 97 Basic Connection Between FCA and RST......Page 98 Relationship Between Concept Lattice and the Power Set of Partition......Page 99 Transformation Between Concept Lattice and Partition......Page 100 Example......Page 103 Conclusions......Page 104 Introduction......Page 106 Consistent Generalized Approximation Representation Spaces......Page 107 Characterizations of Attributes in Consistent Generalized Approximation Representation Spaces......Page 111 Conclusions......Page 114 Introduction......Page 116 Proximity Structures......Page 117 Proximal Frege Structures......Page 119 Ortholattice of Exact Sets......Page 120 Models of PFS......Page 121 Conclusion......Page 123 Introduction......Page 126 The Basic Theory of Rough Sets......Page 127 Rough Group and Rough Subgroup......Page 128 Rough Coset......Page 129 Homomorphism and Isomorphism of Rough Group......Page 130 Examples......Page 133 Conclusion......Page 134 Introduction......Page 136 Formal Contexts and Concept Lattices......Page 137 Information Systems and Approximation Spaces......Page 138 General Approximation Spaces......Page 139 Representations......Page 141 Concept Lattices and Approximation Spaces......Page 142 Introduction......Page 146 Matrices Representations of Rough Sets......Page 147 Approximation Operators in Boolean Algebras......Page 149 Rough Set Algebras......Page 151 Conclusions......Page 153 Introduction......Page 154 Preliminaries......Page 155 The General Case......Page 157 Other Properties......Page 160 Conclusion......Page 162 Introduction......Page 163 Definitions and Notations......Page 164 Logic with Rough Double Stone Algebraic Semantics......Page 166 Conclusion......Page 169 Introduction......Page 171 Greedy Algorithm for Partial Cover Construction......Page 173 Greedy Algorithm for Partial Test Construction......Page 174 Results of Experiments......Page 176 Conclusion......Page 177 Introduction......Page 178 The Reduct Algorithm Based on Attribute Order [1]......Page 179 The Second Attribute and the Second Attribute Theorem......Page 180 Rules on Attribute Moving [2]......Page 182 Basic Decision Theorem......Page 183 The Second Attribute Algorithm......Page 184 The Second Attribute Algorithm......Page 185 Computational Complexity......Page 186 Conclusion......Page 187 Introduction......Page 188 Cores and Reducts......Page 189 Pairwise Core Graph......Page 192 Application of the Pairwise Cores for Reducts Finding......Page 194 Experimental Results......Page 195 Conclusions......Page 197 Introduction......Page 198 Kappa Coefficient......Page 199 Non-supervised Kappa Coefficient......Page 200 Choice Procedure......Page 201 Experimentation......Page 202 Conclusion......Page 205 Introduction......Page 207 Principle of Incremental Attribute Reduction......Page 208 Incremental Attribute Reduction Algorithm Based on Elementary Sets......Page 209 Experiment Results......Page 211 Test on Inconsistent Dataset......Page 212 Continuous Incremental Learning Test......Page 213 Conclusion......Page 214 Introduction......Page 216 Rough Set Attribute Reduction......Page 217 Discernibility Matrix-Based Selection......Page 219 Finding Rough Set Reducts......Page 221 Evaluation......Page 223 Conclusion......Page 224 Introduction......Page 226 Brief of Feature Selection......Page 227 Evolution of Rough Sets Based Feature Selection......Page 228 Average Support Heuristic......Page 229 Lower Approximation with Unknown a Priori Probability......Page 230 Lower Approximation with Known a Priori Probability......Page 231 Comparison of PASH with the Other Three Methods......Page 232 Approximate Reducts with Different Parameter Levels......Page 233 Concluding Remarks......Page 234 Introduction......Page 236 Rough Set Approach......Page 237 Relative Attribute Dependency Based on Rough Set Theory......Page 238 A Heuristic Algorithm for Finding Optimal Reducts......Page 239 Experiments......Page 241 Related Work......Page 242 Summary and Future Work......Page 243 Introduction......Page 246 Preliminaries......Page 247 Extensions of Information Systems......Page 248 Generating Extensions of Information Systems......Page 252 Conclusions......Page 254 Introduction......Page 256 Categories of Information Tables......Page 257 Relations......Page 258 Granularity......Page 259 Discernibility and Reduction......Page 260 Galois Connection......Page 263 Discussion......Page 264 Conclusion......Page 265 Introduction......Page 266 Blocks of Attribute-Value Pairs......Page 268 Definability......Page 271 Lower and Upper Approximations......Page 272 Conclusions......Page 274 Introduction......Page 276 Basic Definitions......Page 277 Theoretical Foundations of Rule Generation in NISs......Page 278 A Problem on Minimal Rule Generation in NISs......Page 280 Discernibility Functions and Minimal Certain Rules......Page 281 Minimal Certain Rule Generation in DGC Class......Page 282 Minimal Possible Rule Generation in Other Classes......Page 284 Concluding Remarks......Page 285 Introduction......Page 287 Definitions......Page 288 Studies in the Propositional Case......Page 290 Studies in `Multiple Rows Per Example' Case......Page 292 Application to Predictive Toxicology......Page 294 Conclusions......Page 295 Introduction......Page 297 Background: Rough Sets and Rough Relational Database......Page 298 Rough Functional Dependencies......Page 299 Rough Normal Forms......Page 300 Rough Third Normal Form......Page 301 References......Page 303 Introduction......Page 305 Classification and Probabilistic Knowledge......Page 306 Probabilistic Dependencies Between Sets......Page 307 Probabilistic Rules......Page 308 Probabilistic Approximation Regions......Page 309 Elementary, Composed and Binary Attributes......Page 311 Probabilistic Dependencies Between Attributes......Page 312 Optimization and Evaluation of Attributes......Page 313 Conclusion......Page 314 Introduction......Page 316 Preliminaries and Notations......Page 317 Rough Sets Approach Based on Information Gain......Page 318 Extraction Method of Decision Rules from Approximate Regions......Page 320 Applications to Human Sensory Evaluation Data......Page 323 Conclusions......Page 325 Introduction......Page 326 Decision Tables......Page 327 Rough Sets and Variable Precision Rough Sets......Page 329 Agreement Ratio......Page 330 Upper Estimation of a Rough Membership Value......Page 331 Modified Approximations and Modified Agreement Ratios......Page 332 A Numerical Example......Page 333 Introduction......Page 336 Confirmation Measures......Page 338 Decision Rules and Decision Algorithm......Page 339 Confirmation Measures and Decision Algorithms......Page 340 Parameterized Rough Sets......Page 343 Conclusions......Page 346 Introduction......Page 347 Methods Based on Rough Sets......Page 348 Methods of Possible Tables......Page 350 Methods of Valued Tolerance Relations......Page 351 Revising Methods of Valued Tolerance Relations......Page 352 Conclusions......Page 355 Introduction......Page 357 Bayesian Networks......Page 358 Rough Set Flow Graphs......Page 359 The Complexity of Inference......Page 362 Other Remarks on Rough Set Flow Graphs......Page 364 Conclusion......Page 365 Introduction......Page 367 Fuzzy Plausibility and Belief Functions......Page 368 Fuzzy Rough Sets......Page 369 Connections Between Fuzzy Approximation Spaces and Fuzzy Belief Structures......Page 371 Conclusion......Page 373 Introduction......Page 376 Decision Tables with Fuzzy Attributes......Page 377 Similarity Relations for Condition and Decision Attributes......Page 378 Variable Precision Fuzzy Rough Approximations......Page 379 Example......Page 382 Conclusions......Page 384 Introduction......Page 386 Compatibility Relations......Page 387 Generalized Rough Set Approximations......Page 388 Generalized Rough Membership Functions......Page 390 An Illustrative Example......Page 392 Conclusions......Page 393 Introduction......Page 395 Fuzzy Sets and Mass Assignment......Page 396 Rough Fuzzy Sets......Page 397 Roughness Measures of Fuzzy Sets......Page 398 Rough Approximation Quality of a Fuzzy Classification......Page 399 An Illustration Example......Page 401 Conclusions......Page 403 Induction of Decision Rules Based Upon Rough Sets Theory......Page 405 Rules in Fuzzy Form......Page 408 The Genetic Algorithm Application for Rules Fuzzification......Page 409 Numerical Examples......Page 410 Conclusions......Page 411 Introduction......Page 414 FLC Design for MIMO System......Page 415 RST-Based Rapid Algorithm of Fuzzy Rules Extraction......Page 417 Simulation Research......Page 420 Conclusion......Page 422 Introduction......Page 424 Interpretable Rule Extraction from I/O Data Using Grid Partitioning......Page 425 Interpretable Rule Extraction from I/O Data Using Clustering Partitioning......Page 427 Example of Interpretable Rule Extraction Using the TaSe Model......Page 429 Conclusions......Page 432 Introduction......Page 434 The ReliefF Algorithm......Page 435 The Feature Weighted Clustering Algorithm......Page 436 Experiment with Numerical Data Set......Page 438 Experiment with Categorical Data Set......Page 439 Experiment with Mixed Data Set......Page 440 Conclusions......Page 441 Introduction......Page 443 Unsupervised Fuzzy Partition of the Feature Space......Page 444 Structural Data Analysis......Page 446 Partially Supervised Clustering for Semantic Classification......Page 448 Experimental Results......Page 450 Conclusions......Page 451 Introduction......Page 453 Similartaxis and Dissimilation......Page 454 The Application of MEA......Page 455 Clone Mind Evolutionary Algorithm (CMEA)......Page 456 Convergence Analysis of CMEA......Page 458 Research Example......Page 460 Conclusion......Page 461 Introduction......Page 463 Estimation of Distribution Algorithm with Infinite Population Size......Page 464 Upper Bounds on Time Complexity of Global Convergence......Page 466 Computation of Global Convergence Stopping Time......Page 469 References......Page 471 Introduction......Page 473 Related Rough Set Concepts......Page 474 Standard PSO Algorithm......Page 475 Representation of Velocity......Page 476 Velocity Limitation (Maximum Velocity, Vmax)......Page 477 Experiments......Page 478 Conclusions......Page 480 Introduction......Page 483 Influence on LFMCW Radar of Nonlinearities of VCO......Page 484 Brief Introduction of MEA......Page 486 The Conception of the Subsection Nonlinearity Correction Method Based on MEA......Page 487 Structure for Fitness Function......Page 488 Experiment Results......Page 489 Conclusion......Page 491 Introduction......Page 493 Notations......Page 494 Rank of Contingency Table (Multi-way)......Page 495 Rank and Subdeterminant......Page 496 Determinantal Divisors......Page 497 Divisors and Degree of Dependence......Page 498 Degree of Granularity and Dependence......Page 499 Conclusion......Page 501 Introduction......Page 503 The Problem of Learning from the Statistical Point of View......Page 504 Bounds for Classifier Error Estimation......Page 505 Model Selection and Assessment......Page 511 Introduction......Page 513 Causal Discovery with Graphical Models......Page 514 DepenBag......Page 515 Empirical Study......Page 517 Comparison on Generalization Error......Page 518 Error-Ambiguity Decomposition......Page 519 Conclusion......Page 520 Introduction......Page 523 Metric Based Generalization of Minimal Consistent Rules......Page 524 Effective Classification by Minimal Consistent Rules......Page 525 Metric Based Generalization of Classification by Minimal Consistent Rules......Page 526 Combination of k Nearest Neighbors with Generalized Rule Induction......Page 529 Experimental Results......Page 531 Conclusions......Page 532 Introduction......Page 534 Classifier Combination for WSD......Page 536 Bayesian Combination Strategy......Page 537 The Combination Strategy Based on OWA Operators......Page 538 Multi-representation of Context for WSD......Page 540 Experimental Results......Page 541 Conclusion......Page 542 Introduction......Page 544 Fusion of Degradation Factors Sequenced by Time......Page 548 Machine Learning in Time-Sequenced Data Fusion Model......Page 550 Example of Predicting Jet Engine Disintegration......Page 551 Conclusion......Page 552 Introduction......Page 554 Definitions......Page 556 The Block Algorithm......Page 557 Multidimensional U-Scoring......Page 559 Application of the Method......Page 560 Conclusions......Page 561 Introduction......Page 563 Paper Structure......Page 564 Objectiveness, Subjectiveness and Vagueness......Page 565 Similarity Spaces......Page 566 Approximations and Vagueness......Page 567 Examples......Page 569 Relation to Other Approaches and Conclusion......Page 571 Introduction......Page 573 Measuring Problem Solving Performance: Optimization Under Bounded Resources......Page 574 The $-Calculus Algebra of Bounded Rational Agents......Page 576 The $-Calculus Syntax......Page 577 The $-Calculus Semantics: The $k\Omega$-Search......Page 578 Probabilistic, Fuzzy Sets and Rough Sets Performance Measure......Page 579 The $-Calculus Support for Intractability: Optimization Under Bounded Resources and Total Optimality......Page 581 Conclusions......Page 582 Introduction......Page 583 The Preliminaries......Page 585 The Entropy and Partitions......Page 586 The Graph-Theoretical Representation of Partitions and Entropy......Page 590 Conclusions......Page 591 Introduction......Page 593 Data Preparation......Page 595 Method for Comparison......Page 596 Experimental Result......Page 597 Discussion......Page 601 Introduction......Page 603 Background......Page 604 Computational Complexity of Exact Inference: The Consensus......Page 605 Inconsistency in the Consensus......Page 606 Exploring the Inconsistency......Page 607 A Variant of the 3SAT Problem......Page 608 The Complexity of Exact Inference in Singly Connected BNs......Page 610 Concluding Remarks......Page 611 Introduction......Page 613 The Semantics of Processes......Page 614 An Example: Pendulum and Balls Scenario......Page 615 An Axiomatization of Pendulum and Balls Scenario......Page 616 Soundness and Completeness Theorem......Page 618 Implementation......Page 621 References......Page 622 Introduction......Page 623 Goyal and Egenhofer's Model......Page 624 Mathematical Morphological Model......Page 625 Fuzzy Set Theory......Page 628 Modeling and Refining Cardinal Directional Relationships Between Fuzzy Regions......Page 629 Computational Problems......Page 630 Simulation Experiment......Page 631 Conclusions......Page 632 Introduction......Page 634 Data Structure......Page 635 Target Series Selection......Page 636 Data Cleansing and Interpretation......Page 637 Multiscale Comparison of Pass Sequences......Page 638 Grouping of Sequences by Rough Clustering......Page 640 Experimental Results......Page 641 Conclusions......Page 642 Introduction......Page 644 Basic Definitions......Page 645 Information Maps of Data Tables......Page 646 Spatio-temporal Modelling of Objects......Page 647 Hierarchical Information Maps......Page 649 Constructing Higher Levels of Hierarchical Maps by Information Granulation......Page 651 Conclusions......Page 652 Introduction......Page 654 Direct Fusion in Epistemic Logic......Page 655 Ordered Fusion in Epistemic Logic......Page 656 Direct Fusion in Possibilistic Logic......Page 658 Level Cutting Fusion in Possibilistic Logic......Page 659 Level Skipping Fusion in Possibilistic Logic......Page 660 Concluding Remarks......Page 662 Introduction......Page 664 A Quick Overview of First-Order Modal Logic......Page 665 Fuzzy First-Order Modal Logic with Believable Degrees......Page 666 Fuzzy Reasoning and Satisfiability......Page 669 Conclusion and Further Works......Page 672 Introduction......Page 673 Decision Logic......Page 674 Arrow Logic......Page 675 Pairwise Comparison Table......Page 676 Formulas and Semantics of ADL......Page 677 An Example......Page 678 Conclusions......Page 679 Introduction......Page 682 P-Systems, Classification and Approximation......Page 683 From Information Systems to Information Quantum Relational System......Page 685 Comparing Information Systems......Page 686 Transforming Perception Systems......Page 688 Example......Page 689 Dichotomic, Functional and Nominal Systems......Page 690 Conclusions......Page 691 Introduction......Page 693 EVALPSN Overview......Page 694 EVALPSN Stable Model......Page 696 Cat and Mouse Example......Page 697 Cat and Mouse Control in EVALPSN......Page 698 Examples......Page 701 Conclusion......Page 702 Introduction......Page 704 Tolerance Relation System......Page 705 The Nested Tolerance Covering System......Page 706 The Construction of Tolerance Relation Based Granular Space......Page 708 Decision Granular Lattice......Page 710 Conclusion......Page 712 Introduction......Page 714 Reduction and Partition......Page 715 Discernible Granularity......Page 717 Evaluation of Granularity......Page 718 Experiments......Page 719 Conclusion......Page 721 Introduction......Page 723 Positive Approximation......Page 724 Application......Page 726 Case Study......Page 727 Conclusions......Page 729 Introduction......Page 731 A Granular Logic with Closeness Relation $ im_\lambda$......Page 732 Closeness Relation $ im_\lambda$ and Its Relative Properties......Page 734 Reasoning Rules......Page 735 Reasoning in Granular Logic with Closeness Relation $ im_\lambda$......Page 736 Conclusion......Page 737 Introduction......Page 740 Approximation Spaces......Page 741 Rough Information Granules and Transducers......Page 742 Approximation of Concepts and Dependencies from Ontology......Page 743 Models of Real World Entities......Page 750 Geometric and Algebraic Views......Page 751 Knowledge Representations......Page 752 Relational Tables - Representations of Partitions......Page 753 Granular Tables......Page 754 Topological Tables......Page 756 Conclusions......Page 758 Back matter......Page 760 This volume contains the papers selected for presentation at the 10th Int- national Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, RSFDGrC 2005, organized at the University of Regina, August 31st–September 3rd, 2005. This conference followed in the footsteps of inter- tional events devoted to the subject of rough sets, held so far in Canada, China, Japan,Poland,Sweden, and the USA. RSFDGrC achievedthe status of biennial international conference, starting from 2003 in Chongqing, China. The theory of rough sets, proposed by Zdzis law Pawlak in 1982, is a model of approximate reasoning. The main idea is based on indiscernibility relations that describe indistinguishability of objects. Concepts are represented by - proximations. In applications, rough set methodology focuses on approximate representation of knowledge derivable from data. It leads to signi?cant results in many areas such as?nance, industry, multimedia, and medicine. The RSFDGrC conferences put an emphasis on connections between rough sets and fuzzy sets, granularcomputing, and knowledge discoveryand data m- ing, both at the level of theoretical foundations and real-life applications. In the case of this event, additional e?ort was made to establish a linkage towards a broader range of applications. We achieved it by including in the conference program the workshops on bioinformatics, security engineering, and embedded systems, as well as tutorials and sessions related to other application areas.