Foundations of soft case-based reasoning

FOUNDATIONS OF SOFT

CASE-BASED REASONING

SANKAR K. PAL

Indian Statistical Institute

SIMON C. K. SHIU

Hong Kong Polytechnic University

A JOHN WILEY & SONS, INC., PUBLICATION

FOUNDATIONS OF SOFT

CASE-BASED REASONING

WILEY SERIES ON INTELLIGENT SYSTEMS

Editors: James S. Albus, Alexander M. Meystel, and Lotfi A. Zadeh

Engineering of Mind: An introduction to the Science of Intelligent

Systems
James S. Albus and Alexander M. Meystel

Intelligence through Simulated Evolution: Forty Years of Evolutionary

Programming
Lawrence J. Fogel

The RCS Handbook: Tools for Real-Time Control Systems Software

Development
Veysel Gazi, Mathew L. Moore, Kevin M. Passino,

William P. Shackleford, Frederick M. Proctor, and James S. Albus

Intelligent Systems: Architecture, Design, and Control
Alexander M.

Meystel and James S. Albus

Neuro-Fuzzy Pattern Recognition: Methods in Soft Computing
Sankar K.

Pal and Sushmita Mitra

Computing with Words
Paul P. Wang, Editor

Foundations of Soft Case-Based Reasoning
Sankar K. Pal and

Simon C. K. Shiu

FOUNDATIONS OF SOFT

CASE-BASED REASONING

SANKAR K. PAL

Indian Statistical Institute

SIMON C. K. SHIU

Hong Kong Polytechnic University

A JOHN WILEY & SONS, INC., PUBLICATION

Copyright # 2004 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or

by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as

permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior

written permission of the Publisher, or authorization through payment of the appropriate per-copy fee

to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400,

be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken,

NJ 07030, (201) 748-6011, fax (201) 748-6008.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts

in preparing this book, they make no representations or warranties with respect to the accuracy or

completeness of the contents of this book and specifically disclaim any implied warranties of

merchantability or fitness for a particular purpose. No warranty may be created or extended by sales

representatives or written sales materials. The advice and strategies contained herein may not be suitable

for your situation. You should consult with a professional where appropriate. Neither the publisher nor

author shall be liable for any loss of profit or any other commercial damages, including but not limited

to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department

within the U.S. at 877-762-2974, outside the U.S. at 317-572-3993 or fax 317-572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print,

however, may not be available in electronic format.

Library of Congress Cataloging-in-Publication Data:

Pal, Sankar

Foundations of soft case-based reasoning / Sankar Pal, Simon Shiu

p. cm. – (Wiley series on intelligent systems)

‘‘A Wiley-Interscience publication.’’

Includes bibliographical references and index.

ISBN 0-471-08635-5

1. Soft computing. 2. Case-based reasoning I. Shiu, Simon C. K.

II. Title. III. Series.

QA76.9.S63 S55 2004

006.3–dc22 2003021342

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

fax 978-646-8600, or on the web at www.copyright.com.Requests to the Publisher for permission should

To

Anshu, Arghya, and Amita

SKP

Pak Wah, Yee Shin, and Mei Yee

SCKS

CONTENTS

FOREWORD xiii

PREFACE xvii

ABOUT THE AUTHORS xxi

1 INTRODUCTION 1

1.1 Background / 1

1.2 Components and Features of Case-Based Reasoning / 2

1.2.1 CBR System versus Rule-Based System / 4

1.2.2 CBR versus Human Reasoning / 5

1.2.3 CBR Life Cycle / 6

1.3 Guidelines for the Use of Case-Based Reasoning / 9

1.4 Advantages of Using Case-Based Reasoning / 9

1.5 Case Representation and Indexing / 11

1.5.1 Case Representation / 12

1.5.2 Case Indexing / 15

1.6 Case Retrieval / 15

1.7 Case Adaptation / 18

1.8 Case Learning and Case-Base Maintenance / 19

1.8.1 Learning in CBR Systems / 19

1.8.2 Case-Base Maintenance / 20

1.9 Example of Building a Case-Based Reasoning System / 21

vii

1.9.1 Case Representation / 23

1.9.2 Case Indexing / 23

1.9.3 Case Retrieval / 24

1.9.4 Case Adaptation / 25

1.9.5 Case-Base Maintenance / 26

1.10 Case-Based Reasoning: Methodology or Technology? / 26

1.11 Soft Case-Based Reasoning / 27

1.11.1 Fuzzy Logic / 29

1.11.2 Neural Networks / 30

1.11.3 Genetic Algorithms / 30

1.11.4 Some CBR Tasks for Soft Computing Applications / 30

1.12 Summary / 31

References / 32

2 CASE REPRESENTATION AND INDEXING 34

2.1 Introduction / 34

2.2 Traditional Methods of Case Representation / 37

2.2.1 Relational Representation / 38

2.2.2 Object-Oriented Representation / 40

2.2.3 Predicate Representation / 41

2.2.4 Comparison of Case Representations / 42

2.3 Soft Computing Techniques for Case Representation / 43

2.3.1 Case Knowledge Representation Based on Fuzzy Sets / 43

2.3.2 Rough Sets and Determining Reducts / 46

2.3.3 Prototypical Case Generation Using Reducts

with Fuzzy Representation / 52

2.4 Case Indexing / 63

2.4.1 Traditional Indexing Method / 63

2.4.2 Case Indexing Using a Bayesian Model / 64

2.4.3 Case Indexing Using a Prototype-Based Neural Network / 69

2.4.4 Case Indexing Using a Three-Layered Back

Propagation Neural Network / 71

2.5 Summary / 72

References / 73

3 CASE SELECTION AND RETRIEVAL 75

3.1 Introduction / 75

3.2 Similarity Concept / 76

viii CONTENTS

3.2.1 Weighted Euclidean Distance / 76

3.2.2 Hamming and Levenshtein Distances / 78

3.2.3 Cosine Coefficient for Text-Based Cases / 78

3.2.4 Other Similarity Measures / 79

3.2.5 k-Nearest Neighbor Principle / 80

3.3 Concept of Fuzzy Sets in Measuring Similarity / 80

3.3.1 Relevance of Fuzzy Similarity in Case Matching / 81

3.3.2 Computing Fuzzy Similarity Between Cases / 85

3.4 Fuzzy Classification and Clustering of Cases / 90

3.4.1 Weighted Intracluster and Intercluster Similarity / 91

3.4.2 Fuzzy ID3 Algorithm for Classification / 92

3.4.3 Fuzzy c-Means Algorithm for Clustering / 96

3.5 Case Feature Weighting / 98

3.5.1 Using Gradient-Descent Technique and Neural Networks / 99

3.5.2 Using Genetic Algorithms / 102

3.6 Case Selection and Retrieval Using Neural Networks / 105

3.6.1 Methodology / 106

3.6.2 Glass Identification / 108

3.7 Case Selection Using a Neuro-Fuzzy Model / 109

3.7.1 Selection of Cases and Class Representation / 110

3.7.2 Formulation of the Network / 111

3.8 Case Selection Using Rough-Self Organizing Map / 120

3.8.1 Pattern Indiscernibility and Fuzzy

Discretization of Feature Space / 120

3.8.2 Methodology for Generation of Reducts / 121

3.8.3 Rough SOM / 122

3.8.4 Experimental Results / 124

3.9 Summary / 130

References / 131

4 CASE ADAPTATION 136

4.1 Introduction / 136

4.2 Traditional Case Adaptation Strategies / 137

4.2.1 Reinstantiation / 138

4.2.2 Substitution / 139

4.2.3 Transformation / 142

4.2.4 Example of Adaptation Knowledge in Pseudocode / 143

4.3 Some Case Adaptation Methods / 143

CONTENTS ix

4.3.1 Learning Adaptation Cases / 148

4.3.2 Integrating Rule- and Case-Based Adaptation Approaches / 149

4.3.3 Using an Adaptation Matrix / 149

4.3.4 Using Configuration Techniques / 150

4.4 Case Adaptation Through Machine Learning / 150

4.4.1 Fuzzy Decision Tree / 151

4.4.2 Back-Propagation Neural Network / 152

4.4.3 Bayesian Model / 153

4.4.4 Support Vector Machine / 154

4.4.5 Genetic Algorithms / 158

4.5 Summary / 159

References / 159

5 CASE-BASE MAINTENANCE 161

5.1 Introduction / 161

5.2 Background / 162

5.3 Types of Case-Base Maintenance / 163

5.3.1 Qualitative Maintenance / 163

5.3.2 Quantitative Maintenance / 165

5.4 Case-Base Maintenance Using a Rough-Fuzzy Approach / 166

5.4.1 Maintaining the Client Case Base / 167

5.4.2 Experimental Results / 182

5.4.3 Complexity Issues / 186

5.5 Case-Base Maintenance Using a Fuzzy Integral Approach / 187

5.5.1 Fuzzy Measures and Fuzzy Integrals / 188

5.5.2 Case-Base Competence / 190

5.5.3 Fuzzy Integral–Based Competence Model / 192

5.5.4 Experiment Results / 195

5.6 Summary / 196

References / 196

6 APPLICATIONS 201

6.1 Introduction / 201

6.2 Web Mining / 202

6.2.1 Case Representation Using Fuzzy Sets / 202

6.2.2 Mining Fuzzy Association Rules / 203

6.3 Medical Diagnosis / 205

6.3.1 System Architecture / 205

x CONTENTS

6.3.2 Case Retrieval Using a Fuzzy Neural Network / 206

6.3.3 Case Evaluation and Adaptation Using Induction / 207

6.4 Weather Prediction / 209

6.4.1 Structure of the Hybrid CBR System / 209

6.4.2 Case Adaptation Using ANN / 209

6.5 Legal Inference / 213

6.5.1 Fuzzy Logic in Case Representation / 213

6.5.2 Fuzzy Similarity in Case Retrieval and Inference / 215

6.6 Property Valuation / 216

6.6.1 PROFIT System / 216

6.6.2 Fuzzy Preference in Case Retrieval / 217

6.7 Corporate Bond Rating / 219

6.7.1 Structure of a Hybrid CBR System Using GAs / 219

6.7.2 GA in Case Indexing and Retrieval / 220

6.8 Color Matching / 221

6.8.1 Structure of the Color-Matching Process / 221

6.8.2 Fuzzy Case Retrieval / 222

6.9 Shoe Design / 223

6.9.1 Feature Representation / 224

6.9.2 Neural Networks in Retrieval / 225

6.10 Other Applications / 226

6.11 Summary / 226

References / 227

APPENDIXES 229

A FUZZY LOGIC 231

A.1 Fuzzy Subsets / 232

A.2 Membership Functions / 234

A.3 Operations on Fuzzy Subsets / 236

A.4 Measure of Fuzziness / 236

A.5 Fuzzy Rules / 237

A.5.1 Definition / 238

A.5.2 Fuzzy Rules for Classification / 238

References / 240

B ARTIFICIAL NEURAL NETWORKS 242

B.1 Architecture of Artificial Neural Networks / 243

B.2 Training of Artificial Neural Networks / 244

CONTENTS xi

B.3 ANN Models / 246

B.3.1 Single-Layered Perceptron / 246

B.3.2 Multilayered Perceptron Using a

Back-Propagation Algorithm / 247

B.3.3 Radial Basis Function Network / 249

B.3.4 Kohonen Neural Network / 251

References / 252

C GENETIC ALGORITHMS 253

C.1 Basic Principles / 253

C.2 Standard Genetic Algorithm / 254

C.3 Examples / 256

C.3.1 Function Maximization / 256

C.3.2 Traveling Salesman Problem / 259

References / 260

D ROUGH SETS 262

D.1 Information Systems / 262

D.2 Indiscernibility Relation / 264

D.3 Set Approximations / 265

D.4 Rough Membership / 266

D.5 Dependency of Attributes / 267

References / 268

INDEX 271

xii CONTENTS