<?xml version="1.0" encoding="UTF-8"?>
<TEI xml:space="preserve" xmlns="http://www.tei-c.org/ns/1.0" 
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
xsi:schemaLocation="http://www.tei-c.org/ns/1.0 https://raw.githubusercontent.com/kermitt2/grobid/master/grobid-home/schemas/xsd/Grobid.xsd"
 xmlns:xlink="http://www.w3.org/1999/xlink">
	<teiHeader xml:lang="en">
		<fileDesc>
			<titleStmt>
				<title level="a" type="main">Modifying Logic of Discovery for Dealing with Domain Knowledge in Data Mining</title>
			</titleStmt>
			<publicationStmt>
				<publisher/>
				<availability status="unknown"><licence/></availability>
			</publicationStmt>
			<sourceDesc>
				<biblStruct>
					<analytic>
						<author role="corresp">
							<persName><forename type="first">Jan</forename><surname>Rauch</surname></persName>
							<email>rauch@vse.cz</email>
							<affiliation key="aff0">
								<orgName type="department">Faculty of Informatics and Statistics</orgName>
								<orgName type="institution">University of Economics</orgName>
								<address>
									<addrLine>Prague ⋆ nám W. Churchilla 4</addrLine>
									<postCode>130 67</postCode>
									<settlement>Prague</settlement>
									<country key="CZ">Czech Republic</country>
								</address>
							</affiliation>
							<affiliation key="aff1">
								<orgName type="department">Faculty of Informatics</orgName>
								<orgName type="institution" key="instit1">Statistics</orgName>
								<orgName type="institution" key="instit2">University of Economics</orgName>
								<address>
									<settlement>Prague</settlement>
								</address>
							</affiliation>
						</author>
						<title level="a" type="main">Modifying Logic of Discovery for Dealing with Domain Knowledge in Data Mining</title>
					</analytic>
					<monogr>
						<imprint>
							<date/>
						</imprint>
					</monogr>
					<idno type="MD5">A5911CF255EF886FD0ADB06E74CB37FB</idno>
				</biblStruct>
			</sourceDesc>
		</fileDesc>
		<encodingDesc>
			<appInfo>
				<application version="0.7.2" ident="GROBID" when="2023-03-24T07:11+0000">
					<desc>GROBID - A machine learning software for extracting information from scholarly documents</desc>
					<ref target="https://github.com/kermitt2/grobid"/>
				</application>
			</appInfo>
		</encodingDesc>
		<profileDesc>
			<abstract>
<div xmlns="http://www.tei-c.org/ns/1.0"><p>Logic of discovery was developed in 1970's as an answer to questions "Can computers formulate and justify scientific hypotheses?" and "Can they comprehend empirical data and process it rationally, using the apparatus of modern mathematical logic and statistics to try to produce a rational image of the observed empirical world?". Logic of discovery is based on observational and theoretical languages and on inductive inference corresponding to statistical approaches. Formulas of observational language concern analyzed observational data and formulas of theoretical language concern suitable state dependent structures. The goal of the paper is to discuss a possibility to adapt the logic of discovery to data mining.</p><p>⋆ This paper was prepared with the support of Institutional funds for support of a long-term development of science and research at the</p></div>
			</abstract>
		</profileDesc>
	</teiHeader>
	<text xml:lang="en">
		<body>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>Logic of discovery is developed in the book <ref type="bibr" target="#b1">[2]</ref> which starts with questions:(Q 1 ) -Can computers formulate and justify scientific hypotheses? (Q 2 ) -Can they comprehend empirical data and process it rationally, using the apparatus of modern mathematical logic and statistics to try to produce a rational image of the observed empirical world? Answers are based on a scheme of inductive inference: theoretical assumptions, observational statement (s) theoretical statement .</p><p>This schema means that having accepted theoretical assumptions and having verified observational statements concerning analyzed data, we accept a theoretical statement. The schema leads to additional questions L0 -L4: (L0) In what languages does one formulate observational and theoretical statements? (L1) What are rational inductive inference rules bridging the gap between observational and theoretical sentences? (L2) Are there rational methods for deciding whether a theoretical statement is justified? (L3) What are the conditions for a theoretical statement or a set of theoretical statements to be of interest with respect to the task of scientific cognition? (L4) Are there methods for suggesting such a set of statements, which is as interesting (important) as possible?</p><p>Answering questions (LO) -(L2) leads to logic of induction, answers to questions (L3) and (L4) lead to logic of suggestions. Answers to questions (LO) -(L4) constitute a logic of discovery. Very detailed answers to questions L0 -L4 are given in the book <ref type="bibr" target="#b1">[2]</ref> and the logic of discovery is developed. Observational and theoretical calculi are developed as languages for observational and theoretical statements respectively. Principles of logic of discovery are briefly outlined in section 2.</p><p>Various observational calculi are defined in <ref type="bibr" target="#b1">[2]</ref>. The most studied calculi are monadic observational predicate calculi. They can be understood as a modification of classical predicate calculi -only finite models are allowed and generalized quantifiers are added. Finite models correspond to observational data we analyze and generalized quantifiers make possible to express important statements on observational data. Monadic observational predicate calculi were modified and significantly simplified in <ref type="bibr" target="#b4">[5]</ref> such that they can be understood as a logic of association rules. Association rules -formulas of these calculi are more general than association rules defined in <ref type="bibr" target="#b0">[1]</ref>. These generalized association rules are produced by the procedure 4ft-Miner <ref type="bibr" target="#b6">[7]</ref>.</p><p>Application of domain knowledge in data mining is introduced among 10 challenging problems of data mining <ref type="bibr" target="#b3">[4]</ref>, see also http://www.cs.uvm.edu/ ~icdm/. Domain knowledge is also referred as background knowledge, world knowledge, or business knowledge. Results presented in <ref type="bibr" target="#b4">[5]</ref> make possible to deal with domain knowledge in the process of data mining. A way of filtering out consequences of domain knowledge from results of the 4ft-Miner procedure is outlined in <ref type="bibr" target="#b5">[6]</ref>. It is based on application of logic of association rules <ref type="bibr" target="#b4">[5]</ref>. The goal of this paper is to present (in a given scope) a theoretical elaboration of this approach.</p><p>We are going to modify logic of discovery developed in <ref type="bibr" target="#b1">[2]</ref>. A modified theoretical language is intended to express items of domain knowledge intuitively understandable to domain experts without experience in data mining. Formulas of observational language correspond to patterns produced by data mining procedures. There is a new way of a correspondence between theoretical and observational languages.</p><p>A set of atomic consequences is assigned to each item of domain knowledge (i.e. to a formula of the theoretical language). The atomic consequences are simple formulas of observational calculus such that the assignment can be done by a domain expert. Deduction rules among observational formulas are then used to spread the consequences of items of domain knowledge among additional formulas of observational calculus.</p><p>Let us emphasize that the theoretical language expressing domain knowledge totally differs from the observational language of patterns produced by data mining procedures. The correspondence between these languages is ensured by the atomic consequences defined by the domain expert and by deduction rules in the observational calculus. First we outline general features of this approach and then we elaborate it for association rules. We call resulting modification of logic of discovery as logic of mining of association rules. No analogous approach concerning association rules is known to the author. Logic of discovery is sketched in section 2. Principles of its modification are discussed in section 3. Modified observational and theoretical languages are introduced in sections 4 and 5. System 4ft-Discoverer integrating both introduced theoretical principles and software procedures for dealing with domain knowledge is discussed in section 6.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Logic of Discovery</head><p>Semantic system S = Sent, M, V, V al is determined by a non-empty set Sent of sentences, a non-empty set M of models, a non-empty set V of abstract values and an evaluating function</p><formula xml:id="formula_0">V al : (Sent × M) → V [2]. If ϕ ∈ Sent and M ∈ M then V al(ϕ, M ) is the value of ϕ in M . Semantic system S = Sent, M, V, V al is observational if Sent, M, V are recursive sets and V al is a partial recursive function [2]. Observational semantic system S O = Sent O , M O , V O , V al O corresponding</formula><p>to analyzed data and theoretical semantic system S T = Sent T , U T , V T , V al T corresponding to the whole set of objects, we are interested in are developed in <ref type="bibr" target="#b1">[2]</ref>.</p><p>Observational predicate calculus is a result of modifications of predicate calculi -only finite models are allowed and generalized quantifiers are added <ref type="bibr" target="#b1">[2]</ref>, see introduction. System of closed formulas of such calculus is an observational semantic system. Observational predicate calculus with formulas corresponding to association rules was developed in <ref type="bibr" target="#b1">[2]</ref>. Question of rationality of inductive inference rule is very important. It is studied in <ref type="bibr" target="#b1">[2]</ref> using statistical approaches. It leads to observational predicate calculi with generalized quantifiers corresponding to statistical hypothesis tests and to theoretical semantic system S T = Sent T , U T , V T , V al T with state dependent structures. However, the more detailed description is out of the scope of this paper.</p><p>Using induction rules based on statistical methods usually means there is 1:1 correspondence between observational and theoretical statements. Thus a task of a suggestion of interesting theoretical statements can be converted to a task of a suggestion of interesting observational statements. The GUHA method is defined in <ref type="bibr" target="#b1">[2]</ref> to solve this task. The method is carried out using GUHA procedures. A GUHA procedure is a computer program the input of which consists of analyzed data and a set of parameters defining the large set of relevant observational patterns. Its output is a set of all prime patterns. A pattern is prime if it is true in the analyzed data, and if it does not logically follow from another output simples pattern.</p><p>The most used GUHA procedure is the ASSOC procedure. It deals with enhanced association rules. It was several times implemented and many times applied, see e.g. <ref type="bibr" target="#b2">[3]</ref>. One of its implementations is the procedure 4ft-Miner, see introduction and section 6.1. Implementations of the ASSOC procedure use theoretical results (namely deduction rules) concerning observational predicate calculi <ref type="bibr" target="#b1">[2]</ref>. Logic of association rules involves additional both theoretically interesting and practically important results <ref type="bibr" target="#b4">[5,</ref><ref type="bibr" target="#b5">6]</ref>. Meaning of the GUHA method and thus also meaning of logic of discovery for data mining is summarized in <ref type="bibr" target="#b2">[3]</ref>.</p><p>3 Modifying Logic of Discovery</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Starting points</head><p>Our starting points are: (1) Data we are dealing with do not satisfy requirements for application of statistical approaches. An example of such data is data about patients of a particular hospital. (2) Objects described by our data belong to a broader set of objects. An example of such a broader set is a set of residents in a region to which the hospital belongs. <ref type="bibr" target="#b2">(3)</ref> We have various items of knowledge related to a particular data set. An example is identification of a particular device used to measure each of the observed patients. ( <ref type="formula">4</ref>) We have various items of knowledge related to the broader set of objects that are not directly recorded for each object. An example is information on specific vaccination applied in a region in question. <ref type="bibr" target="#b4">(5)</ref> We have various items of general knowledge about attributes of objects described in our data. An example is a commonly accepted fact that if weight increases, then blood pressure increases too. <ref type="bibr" target="#b5">(6)</ref> We have data mining procedures, which are able to produce a lot of strong patterns valid in given data. Examples are the apriori algorithm <ref type="bibr" target="#b0">[1]</ref> and the procedure 4ft-Miner, see section 6.1. Both produce association rules.</p><p>(7) Most of the patterns produced by the data mining procedure are uninteresting because of they are consequences of the above mentioned items of knowledge. <ref type="bibr" target="#b7">(8)</ref> There are groups of patterns hidden in patterns produced by the data mining procedure such that each of the groups can be considered as a consequence of a yet not known item of knowledge.</p><p>Our goal is to modify logic of discovery such that we will be able to: (I) use items of knowledge mentioned in points 3 -5; (II) filter out consequences of the above introduced items of knowledge from results of mining procedures, see point 7; (III) recognize a group of patterns, which can be considered as a consequence of a (yet not known) item of knowledge, see point 8.</p><p>We assume to use GUHA procedures as data mining procedures together with results on a related observational logical semantic system. To achieve requirements (I)-(III) we are going to: (A) Enhance observational semantic system by features making possible to capture items of knowledge related to particular data sets, see (3) above. (B) Enhance theoretical semantic system by features making possible to capture both items of general knowledge and items of knowledge related to the broader set, see ( <ref type="formula">4</ref>) and ( <ref type="formula">5</ref>) above. (C) Enhance theoretical semantic system by function Cons assigning to each item I of knowledge according to (B) sets of formulas Cons(I) of a corresponding observational system (i.e. a set of patterns produced by a GUHA data mining procedure). Set Cons(I) is assumed to be a set of atomic consequences of I. (D) To develop a new analytical procedure G-FILTER for each GUHA procedure. G-FILTER will filter out all consequences of given items of knowledge from output of the GUHA procedure. This way requirement II) will be achieved. (E) To develop a new analytical procedure G-SYNT for each GUHA procedure. G-SYNT will recognize groups of patterns, which can be considered as a consequence of a (yet not known) items of knowledge. This way requirement III) will be achieved.</p><p>We present principles of modification of logic of discovery using results related to logic of association rules <ref type="bibr" target="#b4">[5]</ref>. We deal with data matrices introduced in section 3.2. The principles of modification of observational and theoretical systems are outlined in sections 3.3 and 3.4. The procedures G-FILTER and G-SYNT are presented by description of procedures 4ft-Filter and 4ft-Synt, which are related to the procedure 4ft-Miner, see section 6.2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Data Matrices</head><p>We consider data matrices with values -natural numbers only. Data matrix -informal view Data matrix M = M, f1, . . . , fK</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Fig. 1. Data matrix</head><p>There is only the finite number of categories for each attribute. Let us assume that the number of categories in a column is t and that the categories are natural numbers 1, . . . , t. All values in the data matrix are then described by the numbers of categories for each column. The whole information on the number of columns and categories in the data matrix is then given by type of data matrix: A type of data matrix is a K-tuple T = t 1 , . . . , t K where t i ≥ 2 are natural numbers for i = 1, . . . , K.</p><p>We use a more formal definition of a data matrix with the number of columns and the numbers of possible values in particular columns given by the type T = t 1 , . . . , t K : A data matrix of the type</p><formula xml:id="formula_1">T is a K + 1-tuple M = M, f 1 , . . . , f K ,</formula><p>where M is a non-empty finite set and f i is the unary function from M to {1, . . . , t i } for i = 1, . . . , K. Set M is a set of rows of data matrix M. Set M is called a domain of data matrix M. We write M = Dom(M). An example of data matrix M = M, f 1 , . . . , f K is in the right part of figure <ref type="figure">1</ref>. We assume that M = {o 1 , . . . , o n }.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3">Modifying Observational Semantic System</head><p>Observational semantic system L C is a language of a logical calculus formulas of which correspond to patterns produced by a data mining procedure (i.e. GUHA procedure in our case). There is an evaluation function</p><formula xml:id="formula_2">S T = M T , L C , V al C , L M T , V al M T is used instead of S O = Sent O , M O , V O , V al O introduced in section 2. Set M T of</formula><formula xml:id="formula_3">V al C : (L C × M T ) → {0, 1}. If ϕ ∈ L C and M ∈ M T then V al C (ϕ, M) is the value of ϕ in M. If it is V al C (ϕ, M) = 1 then ϕ is true in M, otherwise ϕ is false in M.</formula><p>L M T is a language intended to express items of knowledge related to particular data matrices, see point (3) in section 3.1. It is a set Θ = {θ 1 , . . . θ R } of formulas corresponding to features of M, each of them can be true or false. There is an evaluation function V al</p><formula xml:id="formula_4">M T : (Θ × M T ) → {0, 1}. If it is θ ∈ Θ and M ∈ M T then V al M T (θ, M) is the value of feature θ for M. If it is V al M T (θ, M) = 1 then M has feature θ, otherwise M has not feature θ.</formula></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.4">Modifying Theoretical Semantic System</head><formula xml:id="formula_5">Theoretical semantic system U T = M , L T M , Cons is used instead of S T = Sent T , U V t , V T , V al T introduced in section 2.</formula><p>We assume that theoretical system</p><formula xml:id="formula_6">U T = M , L T M , Cons is related to observational semantic system S T = M T , L C , V al C , L M T , V al M T introduced above. M = {Dom(M) | M ∈ M T } is a union of domains of all data matrices M ∈ M T . Language L T</formula><p>M is intended to express items of knowledge introduced in points ( <ref type="formula">4</ref>) and ( <ref type="formula">5</ref>) in section 3.1. There are lot of such items of knowledge <ref type="bibr" target="#b5">[6,</ref><ref type="bibr" target="#b7">8]</ref>, several examples are in section 5.</p><p>We use function Cons : (L T M × M T ) → P(L C ). This function assigns to each couple I, M a set Cons(I, M) of formulas of language L C . Here I ∈ L T M is an item of knowledge (i.e. a formula of language L T M ) and M ∈ M T is a data matrix of type T of related observational semantic system S T . The set Cons(I, M) is considered as a set of all atomic consequences of item I of knowledge in data matrix M, see point (C) in section 3.1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Observational Semantic System of Association Rules</head><p>Observational semantic system S T AR = M T , L T AR , V al T AR , L M T , V al M T of type T = t 1 , . . . , t K concerning association rules is outlined in this section. Association rules of type T are couples of Boolean attributes created from columns of data matrices M ∈ M T . Language L T AR of association rules is introduced in section 4.1, evaluation function V al T AR in section 4.2. Language L T AR , set M T of data matrices and evaluation function V al T AR constitute a logical calculus with important deduction rules, see section 4.3. All definitions are given informally.</p><p>We will not discuss here details of language L M T and related evaluation function V al T M . They are intended to express characteristics of particular data matrices. Examples: data matrix M 1 concerns only pathological patients, data matrix M 2 concerns patients from mountain region, etc. More detailed description is out of scope of this paper, additional research is assumed.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1">Language L T</head><p>AR of Association Rules An association rule is expression ϕ ≈ ψ where ϕ and ψ are Boolean attributes derived from columns of the analyzed data matrix and ≈ is a 4ft-quantifier <ref type="bibr" target="#b4">[5]</ref>. Boolean attribute ϕ is called antecedent and ψ is called succedent. 4ft-quantifier defines relation of ϕ and ψ by associated function F ≈ of ≈, see below.</p><p>Basic Boolean attributes are created first. The basic Boolean attribute is an expression A(α) where α ⊂ {a 1 , . . . a t } and {a 1 , . . . a t } is the set of all categories of the attribute A. Here α is a coefficient of A(α). The basic Boolean attribute </p><formula xml:id="formula_7">A(α) is true in row o of M if it is A(o) ∈ α where A(o)</formula></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>An example of association rule is expression</head><formula xml:id="formula_8">A 1 (1) ∧ A 2 (4, 5) ≈ A K (2, 6</formula><p>). Note that ϕ and ψ in ϕ ≈ ψ have no common attributes.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2">Evaluation Function V al T AR</head><p>Association rule ϕ ≈ ψ can be true or false in a given data matrix M ∈ M T . Rule ϕ ≈ ψ is verified on the basis of a four-fold table 4f t(ϕ,ψ, M) of ϕ and ψ in M, see figure <ref type="figure">2</ref>. Here a is the number of the objects (i.e. the rows of M) satisfying both ϕ and ψ, b is the number of the objects satisfying ϕ and not satisfying ψ, and similarly for c and d, see figure <ref type="figure">2</ref>. Four-fold table 4f t(ϕ,ψ, M) is written as a, b, c, d and called 4ft-table <ref type="table">.</ref> Evaluation function V al T AR assigns a value 0 or 1 to each couple ϕ ≈ ψ, M where ϕ ≈ ψ is the association rule and <ref type="figure">b, c, d</ref>) where a, b, c, d = 4f t(ϕ, ψ, M). Examples of 4ft-quantifiers and their associated functions are in table 1 where 0 &lt; p ≤ 1 and 0 &lt; α &lt; 0.5 are real numbers, B &gt; 0 is an integer number. </p><formula xml:id="formula_9">M ∈ M T . If V al T AR (ϕ ≈ ψ, M) = 1 then we say that rule ϕ ≈ ψ is true in M and if V al T AR (ϕ ≈ ψ, M) = 0 then we say that rule ϕ ≈ ψ is false in M. V al T AR (ϕ ≈ ψ, M) is defined using 4ft-table 4ft(ϕ, ψ, M) of ϕ and ψ in M and associated function F ≈ of ≈. Associated function F ≈ of 4ft quantifier ≈ is a {0, 1} -valued function de- fined for all quadruples a, b, c, d of natural numbers. Value V al(ϕ ≈ ψ, M) of association rule ϕ ≈ ψ in data matrix M ∈ M T is defined such that V al(ϕ ≈ ψ, M) = F ≈ (a,</formula><formula xml:id="formula_10">( k i )( n−k r−i ) ( r n ) ≤ α ∧ a ≥ B Above average dependence ∼ + q,B a a+b ≥ (1 + q) a+c a+b+c+d ∧ a ≥ B Table 1. Examples of 4ft-quantifiers</formula></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.3">Deduction Rules in Logical Calculus of Association Rules</head><p>Language L T AR , set of data matrices M T and evaluation function V al T AR constitute a logical calculus of association rules <ref type="bibr" target="#b4">[5]</ref>. There are both theoretically interesting and practically useful results concerning logical calculi of association rules. Most of them are related to classes of 4ft-quantifiers <ref type="bibr" target="#b4">[5]</ref>. An example of a class of 4ft-quantifiers is the class of implicational 4ft-quantifiers. It is defined such that 4ft-quantifier ≈ is implicational if it satisfies the condition:</p><p>if <ref type="table">1</ref>) are implicational. Criteria of soundness of deduction rules ϕ≈ψ ϕ ′ ≈ψ ′ where both ϕ ≈ ψ and ϕ ′ ≈ ψ ′ are association rules were found <ref type="bibr" target="#b4">[5]</ref>. Criteria are related to important classes of association rules. We outline such criterion for the class of interesting implicational quantifiers. All practically important implicational 4ft-quantifiers are interesting implicational quantifiers.</p><formula xml:id="formula_11">F ≈ (a, b, c, d) = 1 ∧ a ′ ≥ a ∧ b ′ ≤ b then also F ≈ (a ′ , b ′ , c ′ , d ′ ) = 1. Both 4ft- quantifiers ⇒ p,B and ⇒ ! p,α,B (see Table</formula><p>If ⇒ * is an interesting implicational quantifier then there are formulas ω 1A , ω 1B , ω 2 of propositional calculus created from ϕ, ψ, ϕ ′ , ψ ′ so that the deduction rule ϕ⇒ * ψ ϕ ′ ⇒ * ψ ′ is sound if and only if at least one of the following conditions (1), (2) are satisfied: (1) -both ω 1A and ω 1B are tautologies, (2) -ω 2 is a tautology.</p><p>Similar theorems are proved for additional important classes of 4ft-quantifiers <ref type="bibr" target="#b4">[5]</ref>. These results are crucial, see section 6.2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Theoretical Semantic System of Association Rules</head><formula xml:id="formula_12">Theoretical semantic system U AR = M , L T M , Cons T AR related to observational semantic system S T AR = M T , L T AR , V al T AR , L M T , V al M T of type T = t 1 , .</formula><p>. . , t K concerning generalized association rules is sketched in this section.</p><p>Set M and language L T M are introduced in section 3.4. Language L T M is intended to express items of knowledge introduced in points ( <ref type="formula">4</ref>) and ( <ref type="formula">5</ref>) in section 3.1. We give four important examples of formulas of language L T M . Then we outline how function Cons T AR is constructed for one of these examples. The examples are: A ↑↑ B, A ↑↓ B, A → + ω, and ω 1 → + ω 2 . Here A is one of attributes A 1 , . . . , A K of language L T AR , the same is true for B. In addition, ω, ω 1 , ω 2 are Boolean attributes of L T AR and ω does not contain attribute A. Intuitive meaning of particular formulas:</p><formula xml:id="formula_13">-A ↑↑ B means if A increases then B increases too -A ↑↓ B means if A increases then B decreases -A → + ω means if A increases then relative frequency of ω increases -ω 1 → + ω 2 means if ω 1 is satisfied then relative frequency of ω 2 increases.</formula><p>We show how function Cons T AR creates a set Cons T AR (A ↑↑ B, M) of association rules -formulas of language L T AR which can be considered as a set of all atomic consequences of A ↑↑ B in data matrix M. Function Cons T AR can be seen as a family of functions Cons T ≈ where ≈ is a 4ft-quantifier of language L T AR . Function Cons T ≈ creates a set Cons T ≈ (A ↑↑ B, M) of association rulesformulas of language L T AR such that this set can be considered as a set of all atomic consequences of A ↑↑ B of the form ρ ≈ σ in data matrix M. Then it is</p><formula xml:id="formula_14">Cons T AR (A ↑↑ B, M) = {Cons T ≈ (A ↑↑ B, M) | ≈ belongs to L T AR } .</formula><p>We outline function Cons T ⇒p,B for 4ft-quantifier ⇒ p,B of founded implication (see Table <ref type="table">1</ref>) and item A ↑↑ B of domain knowledge. Functions Cons T ≈ for additional 4ft-quantifiers and formulas of L T M are defined similarly <ref type="bibr" target="#b5">[6]</ref>. We assume that attribute A has categories 1, . . . , u and attribute B has categories 1, . . . , v. Our task is to define a set of rules ρ ⇒ p,B σ which can be naturally considered as a set of all the consequences of item A ↑↑ B and which are as simple as possible. In this case, we consider the simplest rules to be in the form A(α) ⇒ p,B B(β) where α ⊂ {1, . . . , u} and β ⊂ {1, . . . , v}.</p><p>Rule A(low) ⇒ p,B B(low) stating that "if A is low then B is low" can be understood as a natural consequence of A ↑↑ B. The only problem is to define the coefficients α and β that can be understood as "low". This can be done so that we choose natural A low , 1 &lt; A low &lt; u and natural B low , 1 &lt; B low &lt; v and then we consider α as "low" iff α ⊂ {1, . . . , A low } and β as "low" iff β ⊂ {1, . . . , B low }, see also section 6.1.</p><p>Also rule A(high) ⇒ p,B B(high) stating that "if A is high then B is high" can be understood as a natural consequence of A ↑↑ B. The coefficients α and β can be defined as "high" in the following way. We choose natural A high , 1 &lt; A low &lt; A high &lt; u and natural B high , 1 &lt; B low &lt; B high &lt; v and then we consider α as "high" iff α ⊂ {A high , . . . , v} and β as "high" iff β ⊂ {B high , . . . , v}.</p><p>It remains to define values of parameters p and B of ⇒ p,B . A possibility is to allow each p ≥ 0.9 and B ≥ n 20 where n is the number of rows of data matrix M. However, boundaries of p and B as well as values A low , A high , B low , B high should be determined by a domain expert. The set of rules A(low) ⇒ p,B B(low) and A(high) ⇒ p,B B(high) satisfying the above given conditions can be considered as Cons T ⇒p,B (A ↑↑ B, M) -a set of atomic consequences of A ↑↑ B of the form ρ ⇒ p,B σ in M.</p><p>Set Cons T ⇒p,B (A ↑↑ B, M) can be defined in a more precise way by adding rules A(medium) ⇒ p,B B(medium) with a suitable definition of "medium". Rules A(low, medium) ⇒ p,B B(medium), A(low, medium) ⇒ p,B B(medium, high), and A(medium) ⇒ p,B B(medium, high) can also be added.</p><p>Note: there is a natural requirement on the reasonable consistency of set Cons T AR (A ↑↑ B, M) of atomic consequences of the A ↑↑ B i.e. there cannot be two atomic consequences ρ 1 ≈ σ 1 and ρ 2 ≈ σ 2 that contradict each other. A detailed discussion of this topic is, however, without the scope of this paper.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6">4ft-Discoverer</head><p>We have defined observational system S T AR = M T , L T AR , V al T AR , L M T , V al M T and related theoretical system U T AR = M , L T M , Cons T AR . The goal of this section is to discuss possibilities of implementation of a theoretical framework for dealing with domain knowledge involved in these systems.</p><p>We use the GUHA procedure 4ft-Miner mining for association rules -couples of Boolean attributes created from columns of data matrices M ∈ M T <ref type="bibr" target="#b6">[7]</ref>. The 4ft-Miner procedure has very fine tools to define a set of association rules to be generated and verified. It deals, among other, with basic Boolean attributes A(α), B(β), A(low), B(low) etc. Main features of 4ft-Miner procedure are outlined in section 6.1.</p><p>Intention to develop two additional analytical procedures G-FILTER and G-SYNT related to each GUHA procedure is announced in points (D) and (E) in section 3.1. We present principles of procedures 4ft-Filter and 4ft-Synt related to 4ft-Miner procedure. The 4ft-Filter procedure is intended to filter out consequences of a given item of domain knowledge from the output of 4ft-Miner. Item of domain knowledge is expressed by a formula of L M T . The 4ft-Synt procedure is intended to recognize groups of patterns which can be considered as a consequence of a yet not known item of knowledge. Principles of both procedures are introduced in section 6.2.</p><p>Semantic systems S T AR and U T AR together with the procedures 4ft-Miner, 4ft-Filter, and 4ft-Synt constitute a framework for a process of data mining for association rules based on domain knowledge. We call this framework 4ft-Discoverer, i.e. 4f tD. It is 4f tD = S T AR , U T AR , 4ft-Miner, 4ft-Filter, 4ft-Synt .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.1">4ft-Miner</head><p>The 4ft-Miner procedure mines for association rules ϕ ≈ ψ, see section 4. Input parameters define 4ft-quantifier ≈, set of relevant antecedents Φ and set of relevant succedents Ψ ; we assume ϕ ∈ Φ and ψ ∈ Ψ . Each antecedent is a conjunction τ 1 ∧. . .∧τ m of partial antecedents τ 1 , . . . , τ m . Each partial antecedent is either a conjunction λ 1 ∧ . . . ∧ λ q or a disjunction λ 1 ∨ . . . ∨ λ q of literals λ 1 , . . . , λ q . Each literal is a basic Boolean attribute A(α) or its negation ¬A(α). Definition of a set of relevant antecedents Φ consists of definitions of relevant partial antecedents Φ</p><formula xml:id="formula_15">1 , . . . , Φ m . Conjunction τ 1 ∧ . . . ∧ τ m is a relevant antecedent if τ 1 ∈ Φ 1 , . . . , τ m ∈ Φ m .</formula><p>Definition of a relevant partial antecedent is given by a list A ′ 1 , . . . , A ′ u of attributes, by a minimal and maximal number of literals in particular partial antecedents and by a type of partial antecedent, i.e. conjunctions or disjunctions. In addition, for each attribute A ′ a set of relevant basic Boolean attributes which are automatically generated is defined. There are various detailed possibilities how to define all relevant basic Boolean attributes A ′ (α) <ref type="bibr" target="#b6">[7]</ref>. We outline only one of them. We use attribute A with categories 1, 2, 3, 4, 5. Option intervals of length 2-3 gives basic Boolean attributes A(1, 2), A(2, 3), A(3, 4), A(4, 5), A(1, 2, 3), A(2, 3, 4), A <ref type="bibr" target="#b2">(3,</ref><ref type="bibr" target="#b3">4,</ref><ref type="bibr" target="#b4">5)</ref>. This way we can get basic Boolean attributes A(low), A(high), B(low), B(high), see section 5.</p><p>Set Ψ of relevant succedents is defined analogously. The 4ft-Miner procedure does not use well known a-priori algorithm <ref type="bibr" target="#b0">[1]</ref>. Its implementation is based on representation of analyzed data by suitable strings of bits <ref type="bibr" target="#b6">[7]</ref>. Its performance is good enough to solve a lot of practically important tasks. A detailed study of its time and space complexity is in <ref type="bibr" target="#b6">[7]</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.2">4ft-Filter and 4ft-Synt</head><p>The 4ft-Filter procedure is intended to filter out consequences of a given item of domain knowledge from association rules produced by the 4ft-Miner procedure. Item of domain knowledge is represented by a formula I ∈ L T M , see section 3.4. Function Is4f tConsequence(I, ϕ ≈ ψ, M) defined for all formulas I ∈ L T M , association rules ϕ ≈ ψ ∈ L T AR and data matrices M ∈ M T can be used to realize the 4ft-Filter procedure. It is Is4f tConsequence(I, ϕ ≈ ψ, M) = 1 if the rule ϕ ≈ ψ can be considered as a consequence of I, otherwise it is Is4f tConsequence(I, ϕ ≈ ψ, M) = 0.</p><p>Value Is4f tConsequence(I, ϕ ≈ ψ, M) is computed using function Cons T AR , see section 5 and using deduction rules ϕ≈ψ ϕ ′ ≈ψ ′ , see section 4.3. There are criteria of correctness of rules ϕ≈ψ ϕ ′ ≈ψ ′ for each 4ft-quantifier ≈ of 4ft-Miner procedure <ref type="bibr" target="#b4">[5,</ref><ref type="bibr" target="#b6">7]</ref>. Function Cons T AR is defined for all I ∈ L T M , and M ∈ M T such that Cons T AR (I, M) = Λ and Λ is a set of all association rules ρ ≈ σ which can be considered as atomic consequences of I in M.</p><p>Value Is4f tConsequence(I, ϕ ≈ ψ, M) is computed in two steps. In the first step, we compute set Λ = Cons T AR (I, M). In the second step, we test correctness of ρ≈σ ϕ≈ψ for each ρ ≈ σ ∈ Λ. If there is such a correct rule, then ϕ ≈ ψ is considered as a consequence of I in M and Is4f tConsequence(I, ϕ ≈ ψ, M) = 1. Otherwise Is4f tConsequence(I, ϕ ≈ ψ, M) = 0. Function Is4f tConsequence(I, ϕ ≈ ψ, M) can also be used to realize the procedure 4ft-Synt which recognizes group of rules ϕ ≈ ψ, which can be considered as consequences of (yet unknown) items of knowledge. We assume that each even yet unknown item of knowledge is represented by a formula of language L T M . The procedure 4ft-Synt can be then realized such that we choose formula ω ∈ L T M and using function Is4f tConsequence(ω, ϕ ≈ ψ, M) we pick up all consequences of ω from output of 4ft-Miner procedure. However, we have somehow to limit set of tested formulas ω ∈ L T M . A more detailed study of this problem is out of the scope of this paper.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7">Conclusions</head><p>The goal of this paper was to elaborate theoretically an approach for dealing with domain knowledge in mining association rules. It was done by modifications of logic of discovery developed in <ref type="bibr" target="#b1">[2]</ref>. General requirements for such modifications were discussed in section 3.1.</p><p>Then a framework 4f tD = S T AR , U T AR , 4ft-Miner, 4ft-Filter, 4ft-Synt for dealing with domain knowledge when mining association rules is described. Association rules are understood as interesting couples of Boolean attributes derived from columns of the analyzed data matrix. The Boolean attributes are derived from basic Boolean attributes by connectives ∧, ∨, ¬, see section 4.1. The general form of the basic Boolean attributes is A(α). Here α is automatically generated subset of categories of A. It makes possible to deal with notions like A(low) and B(high). Implemented procedure 4ft-Miner produces such association rules <ref type="bibr" target="#b6">[7]</ref>.</p><p>The presented approach relates these rules to items of domain knowledge like A ↑↑ B concerning non-Boolean attributes, see section 5. The procedures 4ft-Filter and 4ft-Synt are suggestedto deal with such items of domain knowledge when interpreting results of 4ft-Miner. They are being implemented.</p><p>No similar approach concerning association rules is known to the author. However, a comparison of the presented approach with ways of dealing with domain knowledge in additional data mining areas is still a challenge and a subject of further work. It requires both theoretical study and experiments with 4ft-Discoverer after its implementation.</p></div><figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_0"><head></head><label></label><figDesc>all data matrices M of type T is used instead of M O and two languages -L C and L M T are used instead of Sent O . We always use set {0,1} (i.e. {false, true}) as a set of possible values of formulas of our languages instead of V O .</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_1"><head></head><label></label><figDesc>`r i ´i(1 − p) r−i ≤ α ∧ a ≥ B Founded equivalence ≡p,B a+d a+b+c+d ≥ p ∧ a ≥ B Fisher ≈α,B P min(r,k) i=a</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" type="table" xml:id="tab_0"><head></head><label></label><figDesc>The natural numbers represent categories, i.e. possible values of observed attributes A 1 , . . . , A K . Columns of the data matrix correspond to attributes. Rows correspond to observed objects, e.g. patients. An example of the data matrix is in the left part of figure1.</figDesc><table><row><cell cols="4">object A1 . . . AK</cell><cell>object</cell><cell>f1</cell><cell>. . .</cell><cell>fK</cell></row><row><cell>o1</cell><cell cols="3">1 . . . 6</cell><cell>o1</cell><cell cols="2">f1(o1) . . .</cell><cell>fK (o1)</cell></row><row><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell></row><row><cell>on</cell><cell cols="2">1 . . .</cell><cell>1</cell><cell>on</cell><cell>f1(on)</cell><cell>. . .</cell><cell>fK (on)</cell></row></table></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" type="table" xml:id="tab_1"><head></head><label></label><figDesc>is the value of the attribute A in row o. Boolean attributes ϕ and ψ are derived from basic Boolean attributes using connectives ∨, ∧ and ¬ in the usual way. Examples of Boolean attributes are in figure 2.</figDesc><table><row><cell cols="7">M A1 . . . AK A1(1) AK (2, 6) A1(1) ∧ AK (2, 6) o1 1 . . . 6 1 1 1</cell><cell cols="2">M ψ ¬ψ</cell></row><row><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>. . .</cell><cell>ϕ a ¬ϕ a</cell><cell>b b</cell></row><row><cell cols="3">on 1 . . .</cell><cell>1</cell><cell>1</cell><cell>0</cell><cell>0</cell><cell></cell><cell></cell></row><row><cell cols="6">Data matrix and examples of Boolean attributes</cell><cell></cell><cell cols="2">4ft(ϕ, ψ, M)</cell></row></table><note>Fig. 2. Derived Boolean attributes and 4ft-table 4ft(ϕ, ψ, M)</note></figure>
		</body>
		<back>
			<div type="references">

				<listBibl>

<biblStruct xml:id="b0">
	<analytic>
		<title level="a" type="main">Fast Discovery of Association Rules</title>
		<author>
			<persName><forename type="first">R</forename><surname>Aggraval</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Advances in Knowledge Discovery and Data Mining</title>
				<editor>
			<persName><forename type="first">U</forename><forename type="middle">M</forename><surname>Fayyad</surname></persName>
		</editor>
		<meeting><address><addrLine>Menlo Park</addrLine></address></meeting>
		<imprint>
			<publisher>AAAI Press</publisher>
			<date type="published" when="1996">1996</date>
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b1">
	<monogr>
		<title level="m" type="main">Mechanizing Hypothesis Formation(Mathematical Foundations for a General Theory</title>
		<author>
			<persName><forename type="first">P</forename><surname>Hájek</surname></persName>
		</author>
		<author>
			<persName><forename type="first">T</forename><surname>Havránek</surname></persName>
		</author>
		<imprint>
			<date type="published" when="1978">1978. 1978</date>
			<publisher>Springer-Verlag</publisher>
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b2">
	<analytic>
		<title level="a" type="main">The GUHA method and its meaning for data mining</title>
		<author>
			<persName><forename type="first">P</forename><surname>Hájek</surname></persName>
		</author>
		<author>
			<persName><forename type="first">M</forename><surname>Holeňa</surname></persName>
		</author>
		<author>
			<persName><forename type="first">J</forename><surname>Rauch</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="j">Journal of Computer and System Science</title>
		<imprint>
			<biblScope unit="volume">76</biblScope>
			<biblScope unit="page" from="34" to="48" />
			<date type="published" when="2010">2010</date>
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b3">
	<analytic>
		<title level="a" type="main">10 Challenging Problems in Data Mining Research</title>
		<author>
			<persName><forename type="first">Q</forename><surname>Yang</surname></persName>
		</author>
		<author>
			<persName><forename type="first">X</forename><surname>Wu</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="j">International Journal of Information Technology &amp; Decision Making</title>
		<imprint>
			<biblScope unit="volume">5</biblScope>
			<biblScope unit="issue">4</biblScope>
			<biblScope unit="page" from="597" to="604" />
			<date type="published" when="2006">2006. 2006</date>
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b4">
	<analytic>
		<title level="a" type="main">Logic of Association Rules</title>
		<author>
			<persName><forename type="first">J</forename><surname>Rauch</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="j">Applied Intelligence</title>
		<imprint>
			<biblScope unit="volume">22</biblScope>
			<biblScope unit="page" from="9" to="28" />
			<date type="published" when="2005">2005</date>
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b5">
	<analytic>
		<title level="a" type="main">Considerations on Logical Calculi for Dealing with Knowledge in Data Mining</title>
		<author>
			<persName><forename type="first">J</forename><surname>Rauch</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Advances in Data Management</title>
				<editor>
			<persName><forename type="first">Z</forename><forename type="middle">W</forename><surname>Ras</surname></persName>
		</editor>
		<editor>
			<persName><forename type="first">A</forename><surname>Dardzinska</surname></persName>
		</editor>
		<imprint>
			<publisher>Springer</publisher>
			<date type="published" when="2009">2009. 2009</date>
			<biblScope unit="page" from="177" to="202" />
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b6">
	<analytic>
		<title level="a" type="main">An Alternative Approach to Mining Association Rules</title>
		<author>
			<persName><forename type="first">J</forename><surname>Rauch</surname></persName>
		</author>
		<author>
			<persName><forename type="first">M</forename><surname>Šimůnek</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Data Mining: Foundations, Methods, and Applications</title>
				<editor>
			<persName><forename type="first">T</forename><forename type="middle">Y</forename><surname>Lin</surname></persName>
		</editor>
		<imprint>
			<publisher>Springer-Verlag</publisher>
			<date type="published" when="2005">2005</date>
			<biblScope unit="page" from="219" to="238" />
		</imprint>
	</monogr>
</biblStruct>

<biblStruct xml:id="b7">
	<analytic>
		<title level="a" type="main">Dealing with Background Knowledge in the SEWE-BAR Project</title>
		<author>
			<persName><forename type="first">J</forename><surname>Rauch</surname></persName>
		</author>
		<author>
			<persName><forename type="first">M</forename><surname>Šimůnek</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Knowledge Discovery Enhanced with Semantic and Social Information</title>
				<editor>
			<persName><forename type="first">B</forename><surname>Berendt</surname></persName>
		</editor>
		<meeting><address><addrLine>Berlin</addrLine></address></meeting>
		<imprint>
			<publisher>Springer-Verlag</publisher>
			<date type="published" when="2009">2009. 2009</date>
			<biblScope unit="page" from="89" to="106" />
		</imprint>
	</monogr>
</biblStruct>

				</listBibl>
			</div>
		</back>
	</text>
</TEI>
