Cluster analysis based on tangles in abstract separations systems

Patent metadata

Field	Value
Publication number	US-11651049-B2
Application number	US-201716092781-A
Country	US
Kind code	B2
Filing date	Apr 13, 2017
Priority date	Apr 13, 2016
Publication date	May 16, 2023
Grant date	May 16, 2023

Abstract

A computer-implemented method to capture and detect clusters in, or determined by, a set V of discrete digital data comprising; computing, from the set V, an abstract separation system ASS that consists of a finite set S, whose elements are called separations; of a predetermined transitive, antisymmetric and reflexive order relation ≤ on S; and of an order-reversing involution *: S→S, that is, a mapping s→s* with the property that, (s*)*=s and that r≤s implies s*<r* for all r, s∈S; predetermining a set of consistency requirements (CRs), that is, a set F of subsets of S; computing, from the ASS (S,≤, *), one or more abstract tangles, that is, any set T⊆S that contains exactly one of each pair {s, s*} for s∈S, and does not contain any of the forbidden configurations F∈F as a subset; or determining that there is no abstract tangle; and determining that any abstract tangle T represents a cluster in, or determined by, the data set V.

First claim

The invention claimed is:

1. A computer-implemented method of automatical image recognition in a set V of pixel values of a digital image, by way of completing the following steps:
computing, from the set V, an abstract separation system (ASS) that consists of a finite set S, whose elements are called separations; of a pre-determined transitive, antisymmetric and reflexive order relation ≤ on S; and of an order-reversing involution *:S→S, that is, a mapping s s* with the property that (s*)*=s and that r≤s implies s*≤r* for all r, s∈S;
determining a set of consistency requirements (CRs), that is, a set, of subsets of S, wherein the consistency requirements are chosen in such a way that for the ASS(S, ≤, *) together with the chosen CRs an abstract tree set A exists such that A distinguishes every pair T, T′ of abstract tangles of S for which there exists a y∈S such that y∈T but y*∈T′; and computing the abstract tree set A;
computing, from the ASS(S,≤, *), one or more abstract tangles of S, that is, one or more sets T⊆S that each contain exactly one of each pair {s, s*} for all s∈S, and do not contain any F∈ as a subset, and outputting T; or determining that S has no abstract tangle and outputting a subset R of S witnessing this;

all in such a way that any recognizable region C in the image determined by V determines, in a pre-specified way, for every s in S either s or s*; and at the same time in such a way that for every such C one of the tangles computed contains precisely the choice of s and s* that C determines, thereby capturing C as a recognizable region in V.

2. The computer-implemented method according to claim 1 , the steps further comprising
computing, with the same order relation ≤, involution *, and consistency requirements , from a second data set V′ consisting of pixel values of a second digital image, a second ASS with a set S′ of separations and an abstract tree set A′ that distinguishes every distinguishable pair of abstract tangles of S′;
determining a degree of structural similarity between the abstract tree sets A and A′, as a measure for the similarity between the images from which the data sets V and V′ were obtained and/or for the similarity of the contents of these images, and
evaluating from the determined degree of structural similarity between the abstract tree sets A and A′ whether the first and the second digital image contain one or more similar objects.

3. A computer-implemented method to compress, in the field of big data, a big data set V of discrete digital data by way of completing the following steps:
computing, from the set V, an abstract separation system (ASS) that consists of a finite set S, whose elements are called separations; of a pre-determined transitive, antisymmetric and reflexive order relation ≤ on S; and of an order-reversing involution *:S→S, that is, a mapping s * with the property that (s*)*=s and that r≤s implies s*≤r* for all r, s∈S;
determining a set of consistency requirements (CRs), that is, a set of subsets of S, wherein the consistency requirements are chosen in such a way that for the ASS(S, ≤, *) together with the chosen CRs an abstract tree set A exists such that A distinguishes every pair T, T′ of abstract tangles of S for which there exists a y∈S such that y∈T but y*∈T′; and computing the abstract tree set A;
computing, from the ASS(S,≤, *), one or more abstract tangles of S, that is, one or more sets T⊆S that each contain exactly one of each pair {s, s*} for all s∈S, and do not contain any F∈ as a subset, and outputting T; or determining that S has no abstract tangle and outputting a subset R of S witnessing this;

all in such a way that any cluster C in V determines, in a pre-specified way, for every s in S either s or s*; and at the same time in such a way that for every such C one of the tangles computed contains precisely the choice of s and s* that C determines, thereby capturing C as a cluster in V; and
evaluating relative positions of the computed abstract tangles from the abstract tree set A; and
storing said relative positions as well as a small sample of data points from each abstract tangle,

thereby obtaining a lossily compressed version of the data set V.

4. A computer-implemented method to automatically recognize commonly held views of polled individuals represented in a data set V, by way of completing the following steps:
computing, from the set V, an abstract separation system (ASS) that consists of a finite set S, whose elements are called separations; of a pre-determined transitive, antisymmetric and reflexive order relation ≤ on S; and of an order-reversing involution *:S→S, that is, a mapping s s* with the property that (s*)*=s and that r≤s implies s*≤r* for all r, s∈S;
determining a set of consistency requirements (CRs), that is, a set of subsets of S;
computing, from the ASS(S,≤, *), one or more abstract tangles of S, that is, one or more sets T⊆S that each contain exactly one of each pair {s, s*} for all s∈S, and do not contain any F∈ as a subset, and outputting T; or determining that S has no abstract tangle and outputting a subset R of S witnessing this;

all in such a way that any commonly held view of the polled individuals is represented by a respective cluster C in V, which cluster C determines, in a pre-specified way, for every s in S either s or s*; and at the same time in such a way that for every such C one of the tangles computed contains precisely the choice of s and s* that C determines, thereby capturing C as a cluster in V and thus recognizing the commonly held view represented by C,
wherein the set S of separations consists of pairs (A, B), each separation pair (A, B) and (B, A) corresponding to a question posed to the individuals, such that A is the set of individuals with an affirmative or neutral answer and B is the set of individuals with a negative or neutral answer to the question,
and wherein the way in which a cluster C in V is deemed to determine one of an inverse pair s=(A,B) and s*=(B,A) of separations is that if more of C lies in A than in B then C determines s*, while if more of C lies in B than in A then C determines s; if C has equal parts in A and in B then s will not be oriented by any tangle designed to formalize C.

5. The computer-implemented methodaccording to claim 4 , wherein the consistency requirements are chosen in such a way that for the ASS(S, ≤, *) together with the chosen CRs a set A exists such that A distinguishes every distinguishable pair T, T′ of abstract tangles of S, i.e., every pair T, T′ of abstract tangles of S for which there exists a y∈S such that y∈T but y*∈T′, wherein:
A is an abstract tree set, i.e., a subset of S such that s∈A implies s*∈A for every s∈A, such that r≤s, r≤s*, r*≤s or r*≤s* holds for any two r, s∈A, such that A contains no element r for which there is an s∈S with r<s and also r<s* and such that A contains no element r with r=r*;
and wherein such a set A is computed.

6. The computer-implemented method according to claim 4 , further comprising
pre-determining an order function s |s| on S, such that |s|≥0 for every s∈S and such that |s|=|s*|, that measures how natural a separation s of the data is;
limiting, before the computing of any abstract tangle or any abstract tree set, the set S of separations to the subset S k of those s∈S with |s|<k, wherein k is a chosen threshold value; and
computing characteristics based on the orders of the separations in at least one abstract tangle T representing a cluster, such as the complexity of the cluster, its cohesion or its visibility, wherein:
the complexity of a cluster is the smallest number k such that C induces an abstract tangle of the set S k that is not induced by any cluster C′ that is not part of C or contains C;
the cohes

Assignees

• Univ Hamburg
• Victoria Link Ltd

Inventors

• Diestel Reinhard
• Whittle Geoffrey

Classifications

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06V30/1988

  Graph matching (graphical image representation G06V30/18181) · CPC title

• G06F18/23213 Primary

  with fixed number of clusters, e.g. K-means clustering · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title