Solutions Manual for Data Mining and Analysis: Fundamental Concepts and Algorithms by Mohammed J. Zaki & Wagner Meira Jr.

Data Mining and Analysis:
Fundamental Concepts and Algorithms

Mohammed J. Zaki
Wagner Meira Jr.

,CONTENTS i




Contents

Preface 1

1 Data Mining and Analysis 4
1.1 Data Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Data: Algebraic and Geometric View . . . . . . . . . . . . . . . . . . 7
1.3.1 Distance and Angle . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Mean and Total Variance . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Orthogonal Projection . . . . . . . . . . . . . . . . . . . . . . 14
1.3.4 Linear Independence and Dimensionality . . . . . . . . . . . . 15
1.4 Data: Probabilistic View . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.1 Bivariate Random Variables . . . . . . . . . . . . . . . . . . . 24
1.4.2 Multivariate Random Variable . . . . . . . . . . . . . . . . . 28
1.4.3 Random Sample and Statistics . . . . . . . . . . . . . . . . . 29
1.5 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.5.1 Exploratory Data Analysis . . . . . . . . . . . . . . . . . . . . 31
1.5.2 Frequent Pattern Mining . . . . . . . . . . . . . . . . . . . . . 33
1.5.3 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.5.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36


I Data Analysis Foundations 37

2 Numeric Attributes 38
2.1 Univariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.1 Measures of Central Tendency . . . . . . . . . . . . . . . . . . 39
2.1.2 Measures of Dispersion . . . . . . . . . . . . . . . . . . . . . . 43
2.2 Bivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2.1 Measures of Location and Dispersion . . . . . . . . . . . . . . 49
2.2.2 Measures of Association . . . . . . . . . . . . . . . . . . . . . 50

,CONTENTS ii


2.3 Multivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.4 Data Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.5 Normal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.5.1 Univariate Normal Distribution . . . . . . . . . . . . . . . . . 61
2.5.2 Multivariate Normal Distribution . . . . . . . . . . . . . . . . 63
2.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3 Categorical Attributes 71
3.1 Univariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1.1 Bernoulli Variable . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1.2 Multivariate Bernoulli Variable . . . . . . . . . . . . . . . . . 74
3.2 Bivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2.1 Attribute Dependence: Contingency Analysis . . . . . . . . . 88
3.3 Multivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.1 Multi-way Contingency Analysis . . . . . . . . . . . . . . . . 95
3.4 Distance and Angle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.5 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4 Graph Data 105
4.1 Graph Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.2 Topological Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Centrality Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3.1 Basic Centralities . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3.2 Web Centralities . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.4 Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.4.1 Erdös-Rényi Random Graph Model . . . . . . . . . . . . . . . 129
4.4.2 Watts-Strogatz Small-world Graph Model . . . . . . . . . . . 133
4.4.3 Barabási-Albert Scale-free Model . . . . . . . . . . . . . . . . 139
4.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

5 Kernel Methods 150
5.1 Kernel Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.1.1 Reproducing Kernel Map . . . . . . . . . . . . . . . . . . . . 156
5.1.2 Mercer Kernel Map . . . . . . . . . . . . . . . . . . . . . . . . 158
5.2 Vector Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.3 Basic Kernel Operations in Feature Space . . . . . . . . . . . . . . . 166
5.4 Kernels for Complex Objects . . . . . . . . . . . . . . . . . . . . . . 173
5.4.1 Spectrum Kernel for Strings . . . . . . . . . . . . . . . . . . . 173
5.4.2 Diffusion Kernels on Graph Nodes . . . . . . . . . . . . . . . 175

, CONTENTS iii


5.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

6 High-Dimensional Data 182
6.1 High-Dimensional Objects . . . . . . . . . . . . . . . . . . . . . . . . 182
6.2 High-Dimensional Volumes . . . . . . . . . . . . . . . . . . . . . . . . 184
6.3 Hypersphere Inscribed within Hypercube . . . . . . . . . . . . . . . . 187
6.4 Volume of Thin Hypersphere Shell . . . . . . . . . . . . . . . . . . . 189
6.5 Diagonals in Hyperspace . . . . . . . . . . . . . . . . . . . . . . . . . 190
6.6 Density of the Multivariate Normal . . . . . . . . . . . . . . . . . . . 191
6.7 Appendix: Derivation of Hypersphere Volume . . . . . . . . . . . . . 195
6.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

7 Dimensionality Reduction 204
7.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . 209
7.2.1 Best Line Approximation . . . . . . . . . . . . . . . . . . . . 209
7.2.2 Best Two-dimensional Approximation . . . . . . . . . . . . . 213
7.2.3 Best r-dimensional Approximation . . . . . . . . . . . . . . . 217
7.2.4 Geometry of PCA . . . . . . . . . . . . . . . . . . . . . . . . 222
7.3 Kernel Principal Component Analysis (Kernel PCA) . . . . . . . . . 225
7.4 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . 233
7.4.1 Geometry of SVD . . . . . . . . . . . . . . . . . . . . . . . . 234
7.4.2 Connection between SVD and PCA . . . . . . . . . . . . . . . 235
7.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238


II Frequent Pattern Mining 240

8 Itemset Mining 241
8.1 Frequent Itemsets and Association Rules . . . . . . . . . . . . . . . . 241
8.2 Itemset Mining Algorithms . . . . . . . . . . . . . . . . . . . . . . . 245
8.2.1 Level-Wise Approach: Apriori Algorithm . . . . . . . . . . . 247
8.2.2 Tidset Intersection Approach: Eclat Algorithm . . . . . . . . 250
8.2.3 Frequent Pattern Tree Approach: FPGrowth Algorithm . . . 256
8.3 Generating Association Rules . . . . . . . . . . . . . . . . . . . . . . 260
8.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263