Data Mining Mehmed Kantardzic (good english books to read .txt) 📖

perform complete link hierarchical clustering. Show your results by drawing a dendrogram. The dendrogram should clearly show the order in which the points are merged.

(b) How many clusters exist if the threshold similarity value is 0.5. Give the elements of each cluster.

(c) If DBSCAN algorithm is applied with threshold similarity of 0.6, and MinPts ≥ 2 (required density), what are core, border,and noise points in the set of points pi given in the table. Explain.

14. Given the points x1 = {1, 0}, x2 = {0,1}, x3 = {2, 1}, and x4 = {3, 3}, suppose that these points are randomly clustered into two clusters: C1 = {x1, x3} and C2 = {x2, x4}. Apply one iteration of K-means partitional clustering algorithm and find new distribution of elements in clusters. What is the change in total square-error?

15. Answer True/False to the following statements. Discuss your answer if necessary.

(a) Running K-means with different initial seeds is likely to produce different results.

(b) Initial cluster centers have to be data points.

(c) Clustering stops when cluster centers are moved to the mean of clusters.

(d) K-means can be less sensitive to outliers if standard deviation is used instead of the average.

(e) K-means can be less sensitive to outliers if median is used instead of the average.

16. Identify the clusters in the Figure below using the center-, contiguity-, and density-based clustering. Assume center-based means K-means, contiguity-based means single link hierarchical and density-based means DBSCAN. Also indicate the number of clusters for each case, and give a brief indication of your reasoning. Note that darkness or the number of dots indicates density.

17. Derive the mathematical relationship between cosine similarity and Euclidean distance when each data object has an L2 (Euclidean) length of 1.

18. Given a similarity measure with values in the interval [0, 1], describe two ways to transform this similarity value into a dissimilarity value in the interval [0, ∞].

19. Distances between samples (A, B, C, D, and E) are given in a graphical form:

Determine single-link and complete-link dendograms for the set of the samples.

20. There is a set S consisting of six points in the plane shown as below, a = (0, 0), b = (8, 0), c = (16, 0), d = (0, 6), e = (8, 6), f = (16, 6). Now we run the k-means algorithm on those points with k = 3. The algorithm uses the Euclidean distance metric (i.e., the straight line distance between two points) to assign each point to its nearest centroid. Also we define the following:

3-starting configuration is a subset of three starting points from S that form the initial centroids, for example, {a, b, c}.

3-partition is a partition of S into k nonempty subsets, for example, {a, b, e}, {c, d}, {f} is a 3-partition.

(a) How many 3-starting configurations are there?

(b) Fill in the last two columns of the following table.3-partitionAn example of a 3-starting configuration that can arrive at the 3-partition after 0 or more iterations of k-meansNumber of unique 3-starting configurations{a,b} {d,e} {c,f}  {a} {d} {b, c, e, f}  {a, b, d} {c} {e, f}  {a, b} {d} {c, e, f}

9.10 REFERENCES FOR FURTHER STUDY

Filippone, M., F. Camastra, F. Masulli, S. Rovetta, A Survey of Kernel and Spectral Methods for Clustering, Pattern Recognition, Vol. 41, 2008, pp. 176–190.

Clustering algorithms are a useful tool to explore data structures and have been employed in many disciplines. The focus of this paper is the partitioning clustering problem with a special interest in two recent approaches: kernel and spectral methods. The aim of this paper is to present a survey of kernel and spectral clustering methods, two approaches that are able to produce nonlinear separating hypersurfaces between clusters. The presented kernel clustering methods are the kernel version of many classical clustering algorithms, for example, K-means, SOM, and neural gas. Spectral clustering arises from concepts in spectral graph theory and the clustering problem is configured as a graph-cut problem where an appropriate objective function has to be optimized.

Han, J., M. Kamber, Data Mining: Concepts and Techniques, 2nd edition, Morgan Kaufmann, San Francisco, CA, 2006.

This book gives a sound understanding of data-mining principles. The primary orientation of the book is for database practitioners and professionals with emphasis on OLAP and data warehousing. In-depth analysis of association rules and clustering algorithms is the additional strength of the book. All algorithms are presented in easily understood pseudo-code and they are suitable for use in real-world, large-scale data-mining projects including advanced applications such as Web mining and text mining.

Hand, D., H. Mannila, P. Smith, Principles of Data Mining, MIT Press, Cambridge, MA, 2001.

The book consists of three sections. The first, foundations, provides a tutorial overview of the principles underlying data-mining algorithms and their applications. The second section, data-mining algorithms, shows how algorithms are constructed to solve specific problems in a principled manner. The third section shows how all of the preceding analyses fit together when applied to real-world data-mining problems.

Jain, A. K., M. N. Murty, P. J. Flynn, Data Clustering: A Review, ACM Computing Surveys, Vol. 31, No. 3, September 1999, pp. 264–323.

Although there are several excellent books on clustering algorithms, this review paper will give the reader enough details about the state-of-the-art techniques in data clustering, with an emphasis on large data sets problems. The paper presents the taxonomy of clustering techniques and identifies crosscutting themes, recent advances, and some important applications. For readers interested in practical implementation of some clustering methods, the paper offers useful advice and a large spectrum of references.

Miyamoto, S., Fuzzy Sets in Information Retrieval and Cluster Analysis, Cluver Academic Publishers, Dodrecht, Germany, 1990.

This book offers an in-depth presentation and analysis of some clustering algorithms and reviews the possibilities of combining these techniques with fuzzy representation of data. Information retrieval, which, with the development of advanced Web-mining techniques, is becoming more important in the data-mining community, is also explained in the book.

10

ASSOCIATION RULES

Chapter Objectives

Explain the local modeling character of association-rule techniques.

Analyze the basic characteristics of large transactional databases.

Describe the Apriori algorithm and explain all its phases