Unsupervised, Nominal methods

Finally I want to discuss unsupervised methods which only require nominal data without a distance measure. Often we are trapped into thinking about the continuous, ordered cases where we can visualize relationships in 2 or 3-dimensional cartesian graphs. The previous methods should have illustrated this assumption.

With nominal data the idea of a decision surface doesn't make sense (section 3.1). Though aggregation of values is possible via hierarchies (perhaps induced by a fuzzy similarity measure) different values are otherwise unrelated and can therefore only be handled as single points or sets of values.

Different variables can only be aggregated by logic operations. If variable x₁ has a value out of a given subset $S_i \subset dom(x_i)$ and variable x_j a value in $S_j \subset dom(x_j)$ then a third variable x_khas with some probability p a value in $S_k \subset dom(x_k)$. This process is known as rule inference and is discussed in section 3.3.5.

In the nominal case we have only count tables which can be visualized in histograms (though even this could be misleading as continuous probability distributions are often represented in this way). These count tables then can be used for deriving probability or other evidence distributions. As aggregation of values and variables in the sense of adding and multiplying is very restricted, the use of the first 3 basic techniques, mentioned in section 2.3, on an induced probability distribution are the main structure-finding approaches. With the following method introductions I also hope to make the point that the introduced techniques are from their theoretical viewpoint a sufficient description for investigating nominal data.

Before I start with the method descriptions I want to present the Market Basket problem as a good example for the nominal, unsupervised problem domain (though it has a little different data structure than discussed). In Market Basket research we want to investigate patterns in the shopping behavior of customers. A set of nominal items is given. Subsets of these items are bought by customers in so-called ``transactions''. The purpose is to identify rules of the type ``A customer purchasing items A,B, and C often also purchases item D'' (section 3.3.5). For specific questions like effects of advertising we also might want to specify some of the items A, or D a priori. For example, if a customer buys milk what else is he likely to buy?

The usefulness of hierarchies also becomes apparent in this example. If all different items in a shop are distinguished (milk from different producers, skim, 1%,2%, and whole milk) then hardly any general rules can be found. A hierarchy of values (just any type of milk, any kind of bread, etc.) can help inferring general as well as more specialized patterns. Clearly rule-inference is also an unsupervised method as we don't use any data for supervised classification training.