The paper introduces a descriptive data mining method to discover knowledge for the task of automatic categorization in document image analysis. We argue that a document image is a multi-modal unit of analysis whose semantics is deduced from a combination of textual content, layout structure and logical structure. So, the method considers simultaneously different modalities of document representation, and, therefore different types of information: spatial information derived from a complex document image analysis process (layout analysis), information extracted from the logical structure of the document (by means of document image classi cation and understanding) and the textual information extracted by means of an OCR. The proposed method is based on a relational data mining approach to discover association rules, where the relational setting is justi ed, given its appropriateness to analyze data available in more than one modality. Experimental results on a real world dataset are reported.
Document image analysis is the sub eld of digital image processing that aims to
convert document images to symbolic form for modi cation, storage, retrieval,
reuse, and transmission. However, technologies and systems demand a large
amount of domain-speci c knowledge, in order to properly process document
images, as well as to automatically catalog and organize them [
Text mining and document image analysis have always been considered two complementary technologies: the former is appropriate for documents that are generated according to some textual format, while the latter is applicable to documents available on paper media. Document image mining aims to identify high-level spatial objects and relationships, while text mining is more concerned with patterns involving words, sentences and concepts. The possible interactions between spatial information extracted from document images and textual information, related to the content of some layout components, have never been considered in the data mining literature.
In this paper, we propose to extract the required knowledge in the form
of association rules, which have been successfully applied both in the business
and scienti c realms. Some examples of applications to images have also been
reported in the literature. In particular, Ordonez and Omiecinski [
In a generic library or archive, this kind of pattern can be used in a number
of ways. First, discovered association rules can be used as constraints de ning
domain templates of documents both for classi cation tasks, such as in
associative classi cation approaches [
The paper is organized as follows. In the next Section, background and motivations of this work are presented. The proposed solution is presented in Section 3. Finally, experiments are presented in Section 4. 2
In tasks where the goal is to uncover structure in the data and where there is no
target concept, the discovery of relatively simple but frequently occurring
patterns is promising. Association rules are a basic example of this kind of setting.
The problem of mining association rules was originally introduced in the work
[
X ! Y;
where X and Y are sets of items called antecedent and consequent respectively
(X \ Y = ∅). The meaning of such rules is quite intuitive: Given a database D of
transactions, where each transaction T 2 D is a set of items, X ! Y expresses
that whenever a transaction T contains X, then T probably also contains Y . The
conjunction X ^ Y is called a pattern. Two parameters are usually reported for
association rules, namely the support, which estimates the probability p(X T ^
Y T ), and the con dence, which estimates the probability p(Y T jX T ).
The goal of association rule mining is to nd all the rules with support and
con dence exceeding user speci ed thresholds, henceforth called minsup and
minconf respectively. A pattern X ! Y is large (or frequent) if its support
is greater than or equal to minsup. An association rule X ! Y is strong if it
has a large support (i.e., X ! Y is large) and high con dence. However, it is
becoming clear that these rules can be successfully applied to a wide range of
domains, such as web access pattern discovery [
Nevertheless, mining patterns from document images raises many different issues regarding document structure, storage, access and processing. Firstly, documents are typically unstructured or, at most, semi-structured data. In the case of structured data, the associated semantics or meaning is unambiguously and implicitly de ned and encapsulated in the structure of data (i.e., relational databases), whereas unstructured information meaning is only loosely implied by its form and requires several interpretation steps in order to extract the intended meaning. Endowing documents with a structure that properly encodes their semantics adds a degree of complexity in the application of the mining process. This makes the data pre-processing step really crucial.
Secondly, documents are message conveyors whose meaning is deduced from
the combination of the written text, the presentation style, the context, the
reported pictures and the logical structure, at least. For instance, when the
logical structure and the presentation style are quite well-de ned (typically when
some parts are pre-printed or documents are generated by following a
predened formatting style), the reader may easily identify the document type and
locate information of interest even before reading the descriptive text (e.g., the
title of a paper in the case of scienti c papers or newspapers, the sender in the
case of faxes, the supplier or the amount in the case of invoices, etc.). Moreover,
in many contexts, illustrative images fully complement the textual information,
such as diagrams in socio-economic or marketing reports. By considering
typeface information, it is also possible to immediately and clearly capture the notion
the historical origin of documents (e.g., medieval), as well as the cultural origin
(e.g., Arabic). The presence of spurious objects may inherently de ne classes of
documents, such as revenue stamps in the case of legal documents. The idea of
considering the multi-modal nature of documents falls into the novel research
trend of the document understanding eld, that encourages the development of
hybrid strategies for knowledge capture, in order to exploit the different sources
of knowledge (e.g., text, images, layout, type style, tabular and format
information) that simultaneously de ne the semantics of a document [
However, data mining has evolved following a unimodal scheme instantiated
according to the type of the underlying data (text, images, etc). Applications of
data mining involving hybrid knowledge representation models are still to be
explored. Indeed, several works have been proposed to mine association rules from
the textual dimension [
Thirdly, documents are a kind of data that do not match the classical attributevalue format. In the tabular model, data are represented as xed-length vectors of variable values describing properties, where each variable can have only a single, primitive value. Conversely, the entities (e.g., the objects composing a document image) that are observed and about which information is collected may have different properties, which can be properly modeled by as many data tables (relational data model) as the number of object types. Moreover, relationships (e.g., topological or distance relationships that are implicitly de ned by the location of objects spatially distributed in a document image or words distributed in a text) among observed objects forming the same semantic unit can also be explicitly modeled in a relational database by means of tables describing the relationship. Hence, the classical attribute-value representation seems too restrictive and advanced approaches are necessary to both represent and reason in the presence of multiple relations among data.
Lastly, the data mining method should take into account external information, also called expert or domain knowledge, that can add semantics to the whole process and then obtain high-level decision support and user con dence. All these peculiarities make documents a kind of complex data that require methodological evolutions of data mining technologies, as well as the involvement of several document processing techniques. In our context, the extraction of spatio-textual association rules requires the consideration of all these sources of complexity deriving from the inherent nature of processed documents. 3
In our proposal, the system used for processing documents is WISDOM++[
Document image understanding (or interpretation) creates a mapping of the
layout structure into the logical structure, which associates the content with a
hierarchy of logical components, such as title/authors of a scienti c article, or
the name of the censor in a censorship document. As previously pointed out, the
logical and the layout structures are strongly related. For instance, the title of
an article is usually located at the top of the rst page of a document and it is
written with the largest character set used in the document. Document image
understanding also uses rst-order rules [
The task of mining relational association rules is, in this work, solved by the
SPADA system[
In the logic framework adopted by SPADA, a relational database is boiled down into a deductive database. Properties of both reference and task-relevant objects are represented in the extensional part DE , while the domain knowledge is expressed as a normal logic program which de nes the intensional part DI . As an example, we report a fragment of the extensional part of a deductive database D, which describes multi-modal information which can be extracted from any document image: block(b1). block(b2). : : : height(b2,[11..54]). width(b1,[7..82]). : : : on top(b2,b1). : : : on top(b2,b3). : : : part of(b1,p1). part of(b2,p1). page rst(p1). : : : abstract(b1). title(b2). : : : text in abstract(b1,'base'). text in title(b2,'model').... In this example, b1 and b2 are two constants which denote many distinct layout components (reference objects) , while p1 denotes a document page (taskrelevant object). Predicate block de nes a layout component, part of associates a block to a document page, height and width describe geometrical properties of layout components, on top expresses a topological relationship between layout components, page f irst(p1) refers to the position of the page in the document, abstract and title associates b1 and b2 with a logical label, text in abstract and text in title describe the textual content of the logical components.
The complete list of predicates is reported in Table 1. The a-spatial feature type of speci es the content type of a layout component (e.g. image, text, horizontal line). Logical features are used to associate a logical label to a layout object and depend on the speci c domain. In the case of scienti c papers (considered in this work), possible logical labels are: affiliation, page number, gure, caption, index term, running head, author, title, abstract, formulae, subsection title, section title, biography, references, paragraph, table.
Textual content is represented by means of another class of predicates, which are true when the term reported as the second argument occurs in the layout component denoted by the rst argument. Terms are automatically extracted by means of a text-processing module. All terms in the textual components are tokenized and the set of obtained tokens is ltered out, in order to remove punctuation marks, numbers and tokens of less than three characters. Standard Layout structure Logical structure Text text preprocessing methods are used to: i) remove stop-words, such as articles, adverbs, prepositions and other frequent words; ii) determine equivalent stems (stemming), such as `topolog' in the words `topology' and `topological, by means of the well-known Porter's algorithm for English texts .
Only relevant tokens are used in textual predicates. They are selected by
maximizing the product maxT F DF 2 ICF [
Then, the score vi associated to the term wi belonging to at least one of the logical components labeled with c is: vi = T Fc(wi)
DFc2(wi) 1=CFc(wi) (1)
According to this function, it is possible to identify a ranked list of \discriminative" terms for each of the possible labels. From this list, we select the best ndict terms in Dictc, where ndict is a user-de ned parameter. The textual dimension of each logical component d labeled as c is represented in the document description as a set of ground facts that express the presence of a term w 2 Dictc in the speci ed logical component. 3.2
In the setting introduced so far, the problem of mining multi-modal association rules can be formalized as follows:
Given { a set S of reference objects (layout components); { some sets Rk, 1 k m of task-relevant objects (layout components related to those of the reference objects); { a background knowledge BK which includes hierarchies Hk on objects in Rk, granularity levels M in the descriptions (1 is the highest, while M is the lowest) and a set of granularity assignments k which associate each object in Hk with a granularity level (the hierarchical organization of the layout components included in the task-relevant objects); { a couple of thresholds minsup[l] and minconf [l] for each granularity level; { a language bias LB that constrains the search space.
Find strong multi-level association rules, i.e., association rules involving objects at different granularity levels.
Hierarchies Hk de ne is-a (i.e., taxonomic) relations on task-relevant objects. Both the frequency of patterns and the strength of association rules depend on the granularity level l at which patterns/rules describe data. Therefore, a pattern P with support s at level l is frequent if s minsup[l] and all ancestors of P with respect to Hk are frequent at their corresponding levels. An association rule Q ! R with support s and con dence c at level l is strong if the pattern Q [ R is frequent and c minconf [l].
The expressive power of rst-order logic is exploited to specify both the background knowledge BK, such as hierarchies and domain speci c knowledge, and the language bias LB. The LB is important to allow the user to specify his/her bias for interesting solutions and then to exploit this bias to improve both the efficiency of the mining process and the quality of the discovered rules. In SPADA, the language bias is expressed as a set of constraint speci cations for either patterns or association rules. article + j + j j + j + j + j + j j + j + j + j + j + + heading identi cation
(title, author, affiliation) synopsis + (abstract, index term) content nal components
(biography, references) body + (section title, subsect title, paragraph, caption, gure, formulae, table) page component running head page number unde ned
Fig. 1. Hierarchy of logical components.
We investigate the applicability of the proposed solution to real-world document images. In particular, we have considered a dataset composed of 3,603 logical components extracted from twenty-four multi-page documents, which are scienti c papers published as either regular or short in the IEEE Transactions on Pattern Analysis and Machine Intelligence in the January and February 1996 issues. Each paper is a multi-page document and has a variable number of pages and layout components for page. A user labels some layout components of this set of documents according to their logical meaning. Those layout components with no clear logical meaning are labelled as unde ned. All logical labels belong to the lowest level of the hierarchy reported in the previous section. We processed 217 document images in all. The number of features to describe the twenty-four documents presented to SPADA is 38,948, about 179 features for each document page. The total number of logical components is partitioned as follows: 23 for affiliation, 191 for page number, 357 for gure, 202 for caption, 26 for index term, 231 for running head, 28 for author, 26 for title, 25 for abstract, 333 for formulae, 65 for section title, 21 for biography, 45 for references, 968 for paragraph, 48 for table and 1014 for unde ned. About 150 descriptors for each document page have been extracted. To generate textual predicates we set ndict = 50 and we considered the following logical components: title, abstract, index term, references and running head. Hence, the following textual predicates have been included in the document descriptions: text in title, text in abstract, text in index term, text in references,text in running head. The total number of extracted textual features is 1,681. The text was read with a commercial OCR.
In Table 2 we report a comprehensive view of the association rules mined for each logical component at different granularity levels. SPADA nds associations for all logical components. In particular, many spatial patterns involve logical components in the rst page of an article, such as affiliation, title, author, abstract and index term. Indeed, the rst page generally presents a more regular layout structure and contains several distinct logical components. The situation is different for references where most of the rules involve textual predicates, because of the high frequency of discriminating terms (e.g., 'vol', `ieee').
An example of an association rule discovered by SPADA at the second granularity level (L=2) is: is a block(A) ! specialize(A; B); is a(B; heading); on top(B; C); C ̸= B; is a(C; heading) text in component(C; paper): [supp: 38.46% conf: 38.46%],
This rule considers both spatial and textual properties. It is interpreted as follows: a portion equal to 38.46% of the heading blocks is above another heading block which contains the term `paper'. Usually, this term occurs in the abstract (a typical sentence is \In this paper ..."), which means that the heading block C is an abstract, while B is another logical component that usually is above the abstract (e.g., author component or title component). The percentage value of 38.46% indicates that 10 out of 26 layout components of type heading (Figure 1), in the overall initial set of 3,603 layout components, match the association rule reported above. Indeed, at a lower granularity level (L=4), SPADA discovers the following rule: is a block(A) ! specialize(A; B); is a(B; title); on top(B; C); C ̸= B; is a(C; abstract); text in component(C; paper): [supp: 38.46% conf: 38.46%], The rule has the same con dence and support reported for the rule inferred at the rst granularity level. This means that all heading components represented by B in the former rule (L=2) are titles. Another example of a discovered rule is: is a block(A) ! specialize(A; B); is a(B; references); type text(B); at page last(B): [supp: 46.66% conf: 46.66%], which shows the use of the predicate at page last(B) introduced in the BK. This is an example of a pure spatial association rule. The rules reported above have only one predicate on the antecedent side. An example of rules with several predicates on the antecedent side is:
is a block(A); specialize(A; B); is a(B; heading) ! specialize(A; C); is a(C; heading); at page first(B): [supp: 100.0% conf: 100.0%], which has been discovered at the granularity level L=2. It is characterized by the highest value of support (since it matches 23 out 23 affiliation components) and the highest value of con dence, which indicates a very strong implication between the set of predicates on the antecedent and the set of predicates on the consequent. This rule reports that whenever there is a heading block B (antecedent), then there is another heading block C and block B is collocated on the rst page. The information associated to this rule is probably too general, since different types of components could satisfy it. To obtain more speci c indications, we can explore the lower levels of granularity and use specialized patterns. The rule reported above is re ned at the level L=4 with the following is a block(A); specialize(A; B); is a(B; affiliation) ! specialize(A; C); is a(C; affiliation); at page first(B): [supp: 100.0% conf: 100.0%], which keeps the same statistical parameters and states that whenever there is an affiliation block B, then it is collocated on the rst page and there is another affiliation block C, which could be typically the affiliation details of a co-author. Finally, an example of pure a textual association rule discovered by SPADA is: is a block(A) ! specialize(A; B); is a(B; index term); text in component(B; index): [supp: 92.0% conf: 92.0%], which simply states that a logical component index term contains the term \index". 5
Automated extraction of knowledge patterns from document images can boost the application of document analysis systems in various contexts. In this paper we investigate a particular form of knowledge pattern, namely association rules, which are useful for many knowledge-intensive tasks, such as document classi cation and indexing, document reformatting and document reconstruction. The proposed method is based on a multi-relational approach, in order to consider the inherent multi-modality of documents, which convey layout, logical and textual information. Moreover, knowledge patterns are extracted at various levels of granularity. Experiments prove the viability of the proposed approach.
This work partially ful lls the project "PON020056-33489339 PUGLIA@SERVICE - Internet-based Service Engineering enabling Smart Territory structural development" funded by the Italian Ministry of University and Research (MIUR) and the project "MAESTRA - Learning from Massive, Incompletely annotated and Structured Data" (Grant number ICT-2013-612944) funded by the European Commission.