AQn

Name AQn
Description

The family of AQ-Algorithms provides methods for concept learning and conceptual clustering. This section just introduces some base functionality. For more information, please follow the links.

  1. AQ applied to Concept Learning

    AQ learns concepts from a set P of positive examples and from a set N of negative examples by the following loop: Choose a single p ∈ P, generalize it as much as possible, so that no n ∈ N is covered and remove all covered positive examples from P. This is done until the disjunction of the generalized examples covers every p ∈ P.

    Algorithm:

    • Set K := ∅.
    • The set P consists of all positive examples.
    • Repeat, until P is empty:
      • Choose an example p ∈ P.
      • Generate STAR({p}|N), a list of maximally general conjunctive descriptions, separating p from all elements of N.
      • Choose a best element b of STAR({p}|N). The quality is measured by a "Lexical Evaluation Function".
      • Set K := K ∪ {b}.
      • Delete all p from P, that are covered by b.
    • Output the disjunction of all elements of K.

  2. AQ applied to Conceptual Clustering

    Following the star-method, one possibile way to build clusters is to (e.g. randomly) choose a subset of all given observations, and to distinguish each of its elements from all of the other elements of the subset.

    Algorithm:

    Given a set of observations E.

    • Choose a subset K ⊆ E.
    • For each e ∈ K generate STAR({e}|K\{e}) to distinguish e from all other elements of K.
    • Choose and specialize the best concept definitions given by the stars, such that every possible observation is covered by at most one concept. This process is guided by a "Lexical Evaluation Function" (LEF), measuring the quality of concepts.
    • If the generated concepts do not fit the given requirements, another run with a different subset of E may be necessary.
    • If a partition is suitable according to the LEF, concepts may be refined. This is done by splitting the set of all observations, covered by a single concept, by another run of the clustering algorithm, in order to induce a hierarchy of concepts.
Generalization Star
Example Languages Attribute-Value
Numerical Values
Method Type Algorithm