Data Mining Methodologies for Supporting Engineers during System Identification

After four years of work, I am now close to finishing my PhD. Below is the abstract of my thesis which is about data mining for system identification support:

Data alone are worth almost nothing. While data collection is increasing exponentially worldwide, a clear distinction between retrieving data and obtaining knowledge has to be made. Data are retrieved while measuring phenomena or gathering facts. Knowledge refers to data patterns and trends that are useful for decision making. Data interpretation creates a challenge that is particularly present in system identification, where thousands of models explain a given set of measurements. Manually interpreting such data is not reliable by hand. One solution is to use data mining. This thesis thus proposes an integration of techniques from data mining, a field of research where the aim is to find knowledge from data, into an existing multiple-model system identification methodology.

It is shown that, within a framework for decision support, data mining techniques constitute a valuable tool for engineers performing system identification. For example, clustering techniques group similar models together in order to guide subsequent decisions since they might indicate different possible states of a structure. A main issue concerns the number of clusters, which, usually, is unknown.

For determining the correct number of clusters in data and estimating the quality of a clustering algorithm, a score function is proposed. The score function is a reliable index for estimating the number of clusters in a given data set, thus increasing clustering results understanding for engineers. Furthermore, useful information for engineers performing system identification is achieved through the use of feature selection techniques. They allow selection of relevant parameters that explain candidate models. The core algorithm is a feature selection strategy based on global search.

In addition to providing information about the candidate model space, data mining is found to be a valuable tool for supporting decisions related to subsequent sensor placement. When integrated in a methodology for iterative sensor placement, clustering is found to provide useful support through providing a rational basis for subsequent sensor placement on existing structures. Regarding initial sensor placement, greedy and global search strategies should be selected according to the context. Experiments show that whereas global search is more efficient for initial sensor placement, a greedy strategy is more suitable for iterative sensor placement.

Continue reading... Sphere: Related Content

MLDM 2007: Anil K. Jain's presentation on clustering

As written in the previous post, Anil K. Jain was the invited speaker of MLDM 2007. He gave an interesting presentation about clustering, focusing on the user's dilemma. He started with a comprehensive introduction on clustering and then showed some of the future work he is involved in: semi-supervised clustering and clustering with co-association. Below is the abstract of his presentation:

Data clustering is a long standing research problem in pattern recognition, computer vision, machine learning, and data mining with applications in a number of diverse disciplines. The goal is to partition a set of n d-dimensional points into k clusters, where k may or may not be known. Most clustering techniques require the definition of a similarity measure between patterns, which is not easy to specify in the absence of any prior knowledge about cluster shapes. While a large number of clustering algorithms exist, there is no optimal algorithm. Each clustering algorithm imposes a specific structure on the data and has its own approach for estimating the number of clusters. No single algorithm can adequately handle various cluster shapes and structures that are encountered in practice. Instead of spending our effort in devising yet another clustering algorithm, there is a need to build upon the existing published techniques. In this talk we will address the following problems: (i) clustering via evidence accumulation, (ii) simultaneous clustering and dimensionality reduction, (iii) clustering under pair-wise constraints, and (iv) clustering with relevance feedback. Experimental results show that these approaches are promising in identifying arbitrary shaped clusters in multidimensional data.

He made some interesting remarks during his talk. I have noted three of them:

• K-means has been invented in 1955, 1957, 1965 and 1967 (!)
  
• In a good feature space, any simple clustering algorithm will work
  
• A clustering method is not the same as a clustering algorithm (an algorithm is an implementation of a particular method)

If interested, you can find more information related to his work.

Continue reading... Sphere: Related Content

MLDM 2007: Clustering in Leipzig

I recently came back from the Machine Learning and Data Mining (MLDM) conference in Leipzig, Germany. This was an interesting meeting with various subjects. Out of the usual subjects such as classification (SVM, etc.), feature selection and clustering, a lot of papers were dedicated to applications of data mining.

Examples of application domains are:

• Intrusion detection
  
• Marketing data
  
• Image mining
  
• Medical and biological data mining
  
• Text and document mining
  
• Spam, Newsgroup, blog

A unique session was organized during three days. In comparison to huge conferences with parallel sessions, here the advantage is that more people are attending your presentation. I was personally there to present my work on cluster validity. The most interesting presentation, in my opinion, was the invited talk given by Anil K. Jain about data clustering (certainly because I'm myself involved in clustering). In the next post, I will point out some of his conclusions and recommendations for clustering.

Continue reading... Sphere: Related Content

Machine Learning and Data Mining (MLDM'2007)

Every two years, since 1999, the IBAI institute in Germany, is organizing the International Conference on Machine Learning and Data Mining (MLDM 2007). Well, even in Europe we have data mining related conferences :-) A lot of subjects are covered and applications papers are also encouraged in fields such as multimedia, biomedical and webmining.


I will go to MLDM this year to present an article about cluster validity. I hope to see some of you there. One of the keynote speaker is Anil K. Jain, a pioneer in the field of clustering. He is giving a presentation entitled "Data Clustering: User’s Dilemma". I'm sure this will be very interesting and I will give you some feedback after the conference.

Continue reading... Sphere: Related Content

K-means: random starting centroids

One of the most common technique for clustering is K-means (1). I have already written a few words about clustering algorithms on this blog.

The main drawbacks of K-means are certainly the numeric consideration of the parameters, the unknown number of clusters K and the random starting centroid locations. The paper by Huang (2) is a possible solution to the first. For the second, cluster validation techniques can be used to find a reliable value for K.

In this post, I want to discuss about the third one. In K-means, the K initial centroids are chosen randomly. Therefore, running P times can result in P different clustering of the same data. A possible strategy for avoiding such a problem is multiple runs. The K-means procedure is done P times on the data and evaluated using a cluster validity index. Then, the run with the maximum (or minimum depending on the validity index) value is chosen as the clustering result.

(1) Jain, A. and Dubes, R.: 1988, Algorithms for Clustering Data, Prentice Hall.
(2) Huang, Z.: 1998, Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values, Data Mining and Knowledge Discovery 2(3), 283.

Continue reading... Sphere: Related Content

Clustering with Gaussian mixtures

In a previous post on clustering and cluster validity (i.e. determining the number of clusters), I was writing about the different types of algorithms. Another way of doing clustering is through Gaussian mixtures.

Andrew W. Moore has made a nice presentation on this topic. After a short introduction on unsupervised learning, he then presents GMM (Gaussian Mixtures Models) principles. He continues with the EM (Expectation Maximization) algorithm for maximum likelihood. He also gives real-life examples. Finally the Duda et al. book is suggested as reference.

Using Gaussian mixtures for clustering is clean and provides a strong mathematical background. Moreover, using cross-validation, the number of clusters within data can be inferred. However, the algorithm (with cross-validation) is time consuming and perhaps not practical for some real-life data sets.

Continue reading... Sphere: Related Content

Unique cluster

Estimating the correct, or most reliable number of clusters, namely cluster validity, is of importance in clustering. For more details about clustering and cluster validity, you can read these three posts: part1, part2 and part3.

In the recent literature, a lot of work has been done on clustering and on developing indices that are able to give you an approximate of the number of groups in a set of points. It is interesting to see that most of these indices estimate the number of clusters from two to K_max. The one cluster case seems to be of no interest. It is surprising since this subject has already been studied in 1970 or so.

The importance of the one cluster case has been noticed by Gordon (1). The book chapter by Gordon is full of information regarding concepts behind clustering. For example pointers to holder papers giving definitions for a cluster are given. However, I have found no recent work dealing with cluster validity and unique cluster. Does this mean that clusters always exist at least by pairs?

(1) Gordon, A.D. Data science, classification and related methods (eds. Hayashi, C., Yajima, K., Bock H.H., Ohsumi, N., Tanaka, Y. and Baba, Y.), chapter Cluster validation, pages 22-39. Springer, 1996.

Continue reading... Sphere: Related Content

Cluster validity: Existing indices

The third - and final - post on cluster validity is about existing validity indices. As written in (1), the two fundamentals issues in cluster validity are 1) the number of clusters present in the data and 2) how good is the clustering itself.

Several indices have been proposed in the literature. The main idea with these indices is to plot them with regard to the number of clusters and then analyze this plot. Dunn Index (2) combines dissimilarity between clusters and their diameters to estimate the most reliable number of clusters. Dunn Index is computationally expensive and sensitive to noise. Silhouette index (3) uses average dissimilarity between points to show the structure of the data and consequently its possible clusters. Silhouette index is only suitable for estimating the first choice or best partition. The concepts of dispersion of a cluster and dissimilarity between clusters are used to compute Davies-Bouldin index (4). According to (5), Davies-Bouldin index is among the best indices.

Silhouette, Dunn and Davies-Bouldin indices require the definition of at least two clusters. Finally, I want to point out the fact that several other indices exist in the literature. Some are computationally expensive while other are unable to discover the real number of clusters in certain datasets (5).

(1) U. Maulik and S. Bandyopadhyay. Performance evaluation of some clustering algorithms and validity indices. IEEE Trans. Pattern Anal. Mach. Intell., 24(12):1650-1654, 2002.
(2) J.C. Dunn. Well separated clusters and optimal fuzzy partitions. Journal of Cybernetics, 4:95-104, 1974.
(3) L. Kaufman and P.J. Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, 1990.
(4) D.L. Davies and W. Bouldin. A cluster separation measure. IEEE PAMI, 1:224-227, 1979.
(5) M. Kim and R.S. Ramakrishna. New indices for cluster validity assessment. Pattern Recogn. Lett., 26(15):2353-2363, 2005.

Continue reading... Sphere: Related Content

Cluster validity: Introduction to clustering

In the near future, I will use this blog to write about recent research I'm involved in. I start today (and the following days) by an introduction on the topic I'm interested in: cluster validity.

Clustering is certainly the best known example of unsupervised learning. The goal of clustering is to group data points that are similar according to a given similarity metric (by default Euclidean distance is used). As Jain et al. write in (1), "clustering is a subjective process [...] This subjectivity makes the process of clustering difficult". Clustering techniques have been applied in various domains such as text mining, color image segmentation, sensory time series, information exploration and automatic counting in video sequences. In these domains, the number of clusters is usually not known in advance.

On goal of cluster validity is to estimate the most reliable number of clusters in a dataset. Before going into more details about cluster validity, next post will focus on the clustering techniques.

(1) A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: a review. ACM Computing Surveys, 31(3):264-323, 1999.

Continue reading... Sphere: Related Content

When web mining meets clustering

Google is nowadays the most widely used search engine on the planet. A lot of people use it and are satisfied by its performances. However, Google suffers from several drawbacks. For example, a lot of results are redundant. It sometimes happens that Google gives you too much answers. Assume that you have an information on a .pdf file linked from a specific webpage itself belonging to an overall website. Google will perhaps give you three different links (the main website, the specific webpage and the .pdf file itself). Another drawback of Google (and many other free-text search engine) is the lack of structure among results. Information is given in a raw manner, without themes, hierarchies or categories. So, it often happens to be drowned under the information obtained. A search on the term data mining, for example, results in 52,600,000 hits.

Clusty, a recent search engine (Pittsburgh, 2004), is a good alternative to Google. Clusty is a meta search engine, which means it queries top search engines and combines the results for the user. Clusty use clustering techniques to group results into categories. The results are automatically clustered according to selected key-words. For the example of the term data mining, Clusty proposes 246 results that are part of 36,244,144 hits found. The figure below shows the results obtained.

Click on the picture to enlarge.
Clusty proposes clusters and sub-clusters that can be browsed (left part of the figure). Information is not raw as in Google, but rather organized. Up to now, the only drawback I have noticed regarding Clusty is about ads. They are to close to the results obtained and this sometimes induce confusion to the user.

Continue reading... Sphere: Related Content