Clustering Methodology for Symbolic Data

1 Introduction 1

2 Symbolic Data: Basics 7

2.1 Individuals, Classes, Observations, and Descriptions 8

2.2 Types of Symbolic Data 9

2.2.1 Multi-valued or Lists of Categorical Data 9

2.2.2 Modal Multi-valued Data 10

2.2.3 Interval Data 12

2.2.4 Histogram Data 13

2.2.5 Other Types of Symbolic Data 14

2.3 How do Symbolic Data Arise? 17

2.4 Descriptive Statistics 24

2.4.1 Sample Means 25

2.4.2 Sample Variances 26

2.4.3 Sample Covariance and Correlation 28

2.4.4 Histograms 31

2.5 Other Issues 38

Exercises 39

Appendix 41

3 Dissimilarity, Similarity, and Distance Measures 47

3.1 Some General Basic Definitions 47

3.2 Distance Measures: List or Multi-valued Data 55

3.2.1 Join and Meet Operators for Multi-valued List Data 55

3.2.2 A Simple Multi-valued Distance 56

3.2.3 Gowda-Diday Dissimilarity 58

3.2.4 Ichino-Yaguchi Distance 60

3.3 Distance Measures: Interval Data 62

3.3.1 Join and Meet Operators for Interval Data 62

3.3.2 Hausdorff Distance 63

3.3.3 Gowda-Diday Dissimilarity 68

3.3.4 Ichino-Yaguchi Distance 73

3.3.5 de Carvalho Extensisons of Ichino-Yaguchi Distances 76

3.4 Other Measures 79

Exercises 79

Appendix 82

4 Dissimilarity, Similarity, and Distance Measures: Modal Data 83

4.1 Dissimilarity/Distance Measures: Modal Multi-valued List Data 83

4.1.1 Union and Intersection Operators for Modal Multi-valued List Data 84

4.1.2 A Simple Modal Multi-valued List Distance 85

4.1.3 Extended Multi-valued List Gowda-Diday Dissimilarity 87

4.1.4 Extended Multi-valued List Ichino-Yaguchi Dissimilarity 90

4.2 Dissimilarity/Distance Measures: Histogram Data 93

4.2.1 Transformation of Histograms 94

4.2.2 Union and Intersection Operators for Histograms 98

4.2.3 Descriptive Statistics for Unions and Intersections 101

4.2.4 Extended Gowda-Diday Dissimilarity 104

4.2.5 Extended Ichino-Yaguchi Distance 108

4.2.6 Extended de Carvalho Distances 112

4.2.7 Cumulative Density Function Dissimilarities 115

4.2.8 Mallows' Distance 117

Exercises 118

5 General Clustering Techniques 119

5.1 Brief Overview of Clustering 119

5.2 Partitioning 120

5.3 Hierarchies 125

5.4 Illustration 131

5.5 Other Issues 146

6 Partitioning Techniques 149

6.1 Basic Partitioning Concepts 150

6.2 Multi-valued List Observations 153

6.3 Interval-valued Data 159

6.4 Histogram Observations 169

6.5 Mixed-valued Observations 177

6.6 Mixture Distribution Methods 179

6.7 Cluster Representation 186

6.8 Other Issues 189

Exercises 191

Appendix 193

7 Divisive Hierarchical Clustering 197

7.1 Some Basics 197

7.1.1 Partitioning Criteria 197

7.1.2 Association Measures 200

7.2 Monothetic Methods 203

7.2.1 Modal Multi-valued Observations 205

7.2.2 Non-modal Multi-valued Observations 214

7.2.3 Interval-valued Observations 216

7.2.4 Histogram-valued Observations 225

7.3 Polythethic Methods 236

7.4 Stopping Rule R 250

7.5 Other Issues 257

Exercises 258

8 Agglomerative Hierarchical Clustering 261

8.1 Agglomerative Hierarchical Clustering 261

8.1.1 Some Basic Definitions 261

8.1.2 Multi-valued List Observations 266

8.1.3 Interval-valued Observations 269

8.1.4 Histogram-valued Observations 278

8.1.5 Mixed-valued Observations 281

8.1.6 Interval Observations with Rules 282

8.2 Pyramidal Clustering 289

8.2.1 Generality Degree 289

8.2.2 Pyramid Construction Based on Generality Degree 297

8.2.3 Pyramids from Dissimilarity Matrix 309

8.2.4 Other Issues 312

Exercises 313

Appendix 315

References 317

Index 331