The Representation of FPA-Solutions as Pseudoline-Arrangements Mathematical Basis of the Feature Pattern Analysis (FPA)-Part I

Article excerpt

Summary

In this chapter the mathematical foundations of the Feature Pattern Analysis (FPA) introduced by Feger (1988) are presented, in particular for the two-dimensional case.

The FPA is a method to investigate and describe the structure of co-occurrence data by analyzing the contingencies of the minimal order which still contain the essential information of the data.

A new mathematically supported approach proposed in this paper permits to analyse structures in a given set of observed data in several logically equivalent and coherent alternative forms of representation. In particular it coordinates the three different approaches of representation:

1. Geometrical configurations (pseudoline-arrangements)

2. Sets of third order contingencies

3. Sets of prediction rules (zero cells).

The main effort of this paper is to ensure the mathematical conditions of existence, uniqueness, and construction of the geometrical representation of a given data set of vectors of dichotomous items in form of pseudoline-arrangements representing FPA-solutions as proposed by Feger and discussed in a previous chapter of this volume.

The relations between the geometric representations as pseudoline-arrangements or as planar Hassediagram and the combinatorial representation of a set of patterns or of the set of third order contingencies derived from the data set are investigated.

It is shown that FPA-solutions as mathematical objects can be regarded as oriented matroids with additional properties. The FPA approach yields a meaningful interpretation compatible with the Representation and the uniqueness problem of Measurement Theory ( see Suppes et al 1989, Wille 1996).

After introducing the type of data under consideration, their third order contingencies and an intuitive description of the three possible types of FPA-models, the mathematical notion of simple signed pseudohyperplane-arrangements is introduced as a mathematically appropriate object to represent FPA-solutions geometrically. The necessity of introducing pseudohyperplane-arrangements for modelling FPA-solution instead of Feger's first attempt to consider geometric arrangements restricted to the use of straight lines (for minimal representation dimension k = 2), respectively (k-1) dimensional planes (for minimal representation k > 2) is discussed.

We show in section 5 how a two-dimensional Type I or Type II FPA-solution can be mathematically represented by a planar Hasse-diagram, which appears to be an appropriate tool to analyse and to construct FPA- solutions.

In section 4 it is proved that the pseudoline-arrangement representing the FPA is uniquely determined by its associated third order contingencies. Here the role of the "zero cell condition" introduced by Feger obtains its full mathematical and psychological meaning.

The description of FPA-solutions by a Hasse-diagram as a dual representation of a pseudolinearrangement viewed as a planar graph opens a new psychological dimension of the data, because in the dual image of the pseudoline-arrangement the relation between data ordered and aligned in level sets becomes more transparent as well as providing technical tools for the mathematical proofs.

Key words: mathematical foundation of Feature Pattern Analysis, Hasse-Diagram, structure of cooccurrence data, pseudoline-arrangements

1. Description of the data and notations IMAGE FORMULA8

2. The general FPA-model

An FPA-solution is a geometric representation of the set of observed patterns F (vectors of attributes) in terms of regions, called cells, in a space of minimal dimension k. These regions are separated by pseudohyperplanes, dividing the space in two half spaces coresponding to the opposite categories of a single item of the pattern.

A formal definition of oriented pseudohyperplane-arrangements in general can be found in the mathematical literature on oriented matroids. …