DrGollerResearchWiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Purposes of Clustering =====

==== Clustering for Data Reduction ====

Clustering algorithms scan a set of data and return a set of clusters. The set of data is typically very large in size while the number of clusters is small. Using the circumstance that most clustering algorithms do not store the data that are part of a cluster but a small set of describing features of each cluster, it is possible to use the set of features of a cluster instead of the cluster’s data. In other words, the features that characterise a cluster are a condensed representation of a subset of data. The features of all clusters form a compact representation of all data.

Several typical applications profit of the data reducing effect of clustering. Customer segmentation is only one of them. The aim of customer segmentation is to group the set of all customers of a company into few sets of customers that are represented by characteristic features—e.g. by an “average customer”.

Data reduction is a necessary pre-processing step whenever there is a large set of unique but similar objects that shall be used for data mining. Data mining techniques try to find frequently occurring patterns within the data, Yet, it is impossible to find frequently occurring patterns if each instance is unique because unique items can never be frequent. The usage of clustering can solve this problem. Before being clustered a specific tuple cannot be used for data mining because it is unique but after being clustered the same tuple can be used for data mining when it is treated as a an element of a cluster—there might be many tuples being element of the the same cluster while each tuple is unique. Hence, it is possible to find frequent patterns.

A simple example shall illustrate the necessity of clustering for pre-processing mentioned above:

Suppose a mail order company wants to analyse which costumers buy which kind of products. The company stores sales data and customer data in the two tables “sales” and “customer”, respectively, of a relational database system. If the company performs an association rule analysis on the “sales” table it receives rules of the form “If a customer buys the set of products ‘A’, he/she will probably buy the set of products ‘B’, too”. Yet, it is impossible to tell what kind of products a potential customer that has never bought anything is interested in. The customer must have bought at least a single item to guess what other good he/she might be interested in.

Assuming that two customers that are in a similar living condition—i.e. they have the same sex, similar age and similar educational and cultural background, also share some of their interests concerning specific type of products. Yet, the tuples representing customers in the “customer” table are unique combinations of attribute values in most times—i.e. usually, no two customers have same name, sex, birthday and address. But when clustering the data in the “customer” table, the company receives a set of typical customers, e.g. the female teenager. The resulting clusters can be combined with the result of the association rule analysis. By doing so, the company is now able to predict the set of products a potential customer is interested in. The company might use this knowledge for several purposes such as marketing events customised to the interests of specific customer segments, e.g. enclosing a catalogue with books that are primarily read by female teenagers into a girls’ magazine.

==== Clustering for Hypothesis Generation ====

Some features describing a cluster are suited for being interpreted as a statistical hypothesis. Assume that the application of a partitioning clustering algorithm, see Section  for details, such as $k$-means has returned three clusters with means $\vec{\mu}_1,
\vec{\mu}_2,$ and $\vec{\mu}_3$. $k$-means is a partitioning clustering algorithm that partitions a set of data in $k$ disjoint subsets and returns the mean of each subset—$k$ is a user-given parameter. When the best value of parameter $k$ is unknown, $k$-means is iterated several times to determine the best value of parameter $k$. A potential hypothesis is that there are three independent statistical variables $\vec{X}_1, \vec{X}_2,$ and $\vec{X}_3$ with means $\vec{\mu}_1, \vec{\mu}_2,$ and $\vec{\mu}_3$. Frequent co-occurrences of attribute values can be source of hypothesis, too. For instance, if the mean vector $\vec{\mu}_1$ has the dimensions “income” and “total sales per month”, then a small value of the mean in dimension “income” and a high value of the mean in dimension “total sales per month” means that persons with low own income buy a lot of things.

It is common practise in statistics to generate a hypothesis before testing whether data supports it or not. Otherwise, the hypotheses would be trimmed to fit a specific data set that might cause the so-called overfitting problem. Overfitting occurs when the underlying statistical model of a hypothesis fits almost exactly to the data that has been used to generate that model but only poorly fits to other data having the same schema.

When clustering is used for hypothesis generation, it returns those hypotheses that best fit the given data—which might cause overfitting. Hence, it is necessary to validate the resulting hypotheses by testing each hypothesis with a set of data that has not been used for clustering. For instance, when one has used the data of the past to determine a set of hypotheses, one can use current data in order to try to falsify those hypotheses.
DrGollerResearchWiki

User Tools

Site Tools

Page Tools
