Lattice

From Nordan Symposia
Revision as of 17:36, 27 April 2009 by Rdavis (talk | contribs)
Jump to navigationJump to search

Lighterstill.jpg

Star-Lattice 2.jpg

Lattice work is an ornamental, lattice framework consisting of a criss-crossed pattern of strips of building material, usually wood or metal, but it can be made of any building material. The design is created by crossing the strips to form a decorative network. Latticework can also be used to support a structure, such as lattice girder bridge supports.

  • Lattice is defined as "a structure of crossed strips arranged to form a regular pattern of open spaces".
  • In India the house of a rich or noble person may be built with a baramdah or verandah surrounding every level leading to the living area. The upper floors often have balconies overlooking the street that are shielded by screens jaalis carved in stone latticework, allowing privacy and coolness.

Mathematics

The name "lattice" is suggested by the form of the "Hasse diagram" depicting it.



In mathematics, a lattice is a partially ordered set (also called a poset) in which subsets of any two elements have a unique supremum (the elements' least upper bound; called their |join) and an infimum (greatest lower bound; called their meet). Lattices can also be characterized as algebraic structures satisfying certain axiomatic |identities. Since the two definitions are equivalent, lattice theory draws on both order theory and universal algebra. Semilattices include lattices, which in turn include Heyting and Boolean algebras. These "lattice-like" structures all admit order-theoretic as well as algebraic descriptions.[1]




Concept lattice

Concept lattice or formal concept analysis is a principled way of automatically deriving an ontology from a collection of objects and their properties. The term was introduced by Rudolf Wille in 1984, and builds on applied lattice and order theory that was developed by Birkhoff and others in the 1930's.

Intuitive description

Formal concept analysis refers to both an unsupervised machine learning technique and, more broadly, a method of data analysis. The approach takes as input a matrix specifying a set of objects and the properties thereof, called attributes, and finds both all the "natural" clusters of attributes and all the "natural" clusters of objects in the input data, where

  • a "natural" object cluster is the set of all objects that share a common subset of attributes, and
  • a "natural" property cluster is the set of all attributes shared by one of the natural object clusters.

Natural property clusters correspond one-for-one with natural object clusters, and a concept is a pair containing both a natural property cluster and its corresponding natural object cluster. The family of these concepts obeys the mathematical axioms defining a lattice, and is called a concept lattice (in French this is called a Treillis de Galois because the relation between the sets of concepts and attributes is a Galois connection).

Note the strong parallel between "natural" property clusters and definitions in terms of individually necessary and jointly sufficient conditions, on one hand, and between "natural" object clusters and the extensions of such definitions, on the other. Provided the input objects and input concepts provide a complete description of the world (never true in practice, but perhaps a reasonable approximation), then the set of attributes in each concept can be interpreted as a set of singly necessary and jointly sufficient conditions for defining the set of objects in the concept. Conversely, if a set of attributes is not identified as a concept in this framework, then those attributes are not singly necessary and jointly sufficient for defining any non-empty subset of objects in the world.

Example

A concept lattice for objects consisting of the integers from 1 to 10, and attributes composite (c), square (s), even (e) odd (o) and prime (p).
The lattice is drawn as a Hasse diagram


Consider O = {1,2,3,4,5,6,7,8,9,10}, and A = {composite, even number, odd number, prime number, square number. The smallest concept including the number 3 is the one with objects {3,5,7}, and attributes odd number, prime number, for 3 has both of those attributes and {3,5,7} is the set of objects having that set of attributes. The largest concept involving the attribute of being square is the one with objects {1,4,9} and attributes {square}, for 1, 4 and 9 are all the square numbers and all three of them have that set of attributes. It can readily be seen that both of these example concepts satisfy the formal definitions below

The full set of concepts for these objects and attributes is shown in the illustration. It includes a concept for each of the original attributes: the composite numbers, square numbers, even numbers, odd numbers, and prime numbers. Additionally it includes concepts for the even composite numbers, composite square numbers (that is, all square numbers except 1), even composite squares, odd squares, odd composite squares, even primes, and odd primes.[2]