Speaker: Simon Andrews, Reader in Computer Science, SHU

Simon Andrews is a Reader in Computer Science at Sheffield Hallam University. He is the Technical Lead of CENTRIC (Centre of excellence in Terrorism, Resilience, Intelligence and Organised Crime Research), where his main roles are to provide technical visions for new project ideas, and manage the technical work in current projects, such as the European ePOOLICE project (environmental scanning for organised crime detection) and the European ATHENA project (crisis management through the use of social media). He was also a Principle Investigator for the European CUBIST project (Combining and Uniting Business Intelligence with Semantic Technologies).

Simon is an international expert on Formal Concept Analysis (FCA) and is co-Editor in Chief of the International Journal of Conceptual Structures and Smart Applications (IJCSSA). He was Programme Chair of the 19th International Conference on Conceptual Structures and has presented his work on fast concept-mining algorithms world-wide, including at events in Moscow and Japan.

Title: Fast Computation of Formal Concepts: A partial-closure canonicity test to increase the efficiency of Close-by-One-type algorithms

In Formal Concept Analysis (FCA) a formal concept is a set of objects that have the same attributes. Within a given formal context, a formal concept captures all the objects that share the attributes and all the attributes that are shared, and is thus a maximal set.  When FCA is applied to data, it becomes a kind of data mining technique, finding clusters of instances (rows in a data table) that share a number of data values (fields in the data table). This technique has uses in applications such as shopping basket analysis, gene co-expression analysis and component failure prediction and also as a technique for solving classification problems.  However, the application of FCA to real data has issues in the scale and complexity of its computation, a major problem being the repeated computation of the same concept and thus the need to quickly determine such a repeat. The discovery of a quick test for a concept's newness (the so-called canonicity test) has opened the way for FCA of real data but there is still the need for more efficient methods of computation. 

This seminar examines the canonicity test and presents an improvement on it, called the partial-closure canonicity test. We demonstrate the increased efficiency by presenting a performance comparison showing that using the partial-closure test roughly doubles the speed of the computation, with our SHU student data set taking 9.38 seconds to compute its 22,276,243 concepts, compared to 17.20 seconds using the old test.