One of the formal technique in Data mining is Formal Concept Analysis (FCA). During preprocessing of a many-valued context many applications of FCA require the partitioning of numerical data attributes into some smaller intervals. Designation of such numerical intervals with linguistic terms without domain experts will help researchers to understand attributes and their dependencies better. To solve this task we propose the notion of a special ACL-scale, which can be considered as a linguistic variable with ordered linguistic terms, modeled by fuzzy sets. The notion of ACL-scale, algorithms of its creation and application are presented. The example how many-valued context can be transformed into formal context using ACL-scale is shown in the paper. The main contribution is a new uniform tool for preprocessing of numerical attributes of given tables which simplify their transformation into a formal context with linguistic attributes.
One of the formal techniques in Data Mining and Knowledge Discovery in Databases
(DM&KDD) process for extraction and representation of useful information, of
objects (attributes) and of data dependencies is the Formal Concept Analysis (FCA)
[
In this paper we propose the approach for transforming numerical attributes of a many-valued context into linguistic variables. This transformation is considered as preprocessing based on the fuzzy scaling theory, where the membership functions are used to derive linguistic values of the partitions of numerical attributes only. The advantage of this approach is a linguistic granulation of numerical attributes in a many-valued context. This linguistic granulation can be useful in segmentation of objects with similar features. Mining the dependencies among several objects expressed in linguistic terms is another application of that linguistic granulation. To solve this task we propose the notion of a special Absolute & Comparative scale (ACL-scale). Using ACL-scale the partitions of numerical data and their linguistic descriptions can be derived. Therefore, the formal context can be presented in a traditional form, and well-known algorithms for FCA can be applied without computing of membership functions. 2
Here we recall the definition of many-valued context [
Definition 1. A many-valued context = (, , , ) is a set of objects , a set of attributes , a set of possible values W, and a ternary relation ⊆ × × , with (, , ) ∈ , (, , ) ∈ ⇒ = , where (, , ) ∈ indicates that object has the attribute m with value w. In this case, we also write () = , regarding the attribute m as a partial function from to .
Definition 2. A formal context is a triple = ⟨, , ⟩ where is a set of objects, is a set of attributes and ⊆ × is a binary relation between and . For ⟨, ⟩ ∈ it is said “The object has the attribute ”.
The task is to transform given many-valued context into a formal context. We denote this transformation as ⇒ .
Each value ∈ is a linguistic value (some linguistic description of a numerical value ), derived by scaling. This means that for each attribute ∈ on the set of its possible numerical values a special scale has to be defined and then applied to transform a given numerical value into a linguistic value . Therefore we consider a task of a scale construction for each attribute ∈ on the set of its possible numerical values . The main demands for this scale construction are simple adaptation to a set of numerical values and minimizing of an expert participation. To solve this task the scale must be formed in automatic way using uniform quantity of parameters and of operations. Beside that the scale must be considered as a linguistic variable to associate its linguistic terms to the scaling values.
So, the problem is to denote the notion of a special scale, which satisfies the mentioned above demands, and algorithms of its construction and its application. Application of this special scale will allow to decrease preprocessing time of a transformation of a given many-valued context into a formal context using uniform formal tool. 3
In this section we propose a special scale, named an ACL-scale (Absolute & Comparative scale) to do the transformation of given many-valued context into a formal context.
Let {! ∈ , ⊆ ℝ, = 1,2, … , } be the set of possible ordered values of a numerical attribute m in respect to definition 1.
We assume that the binary relation ≤ is defined possessing the following properties: • reflexivity: ≤ , ∀ ∈ . • transitivity: if ≤ and ≤ , then ≤ , ∀ , , ∈ . • anti-symmetry: if ≤ and ≤ , then = , ∀ , ∈ .
Let suppose several partially ordered intervals of equal length cover a set and they are used for building a linguistic variable with fuzzy terms ! = !, !! ! , ! ∈ , ! ∈ , = 1,2, … , , = 1,2, … , , < . Here !! ! , = 1,2, … , denotes the membership function of a fuzzy term with a linguistic value !. Therefore it can be said that a set of linguistic values covers a set . Each linguistic value ! ∈ can be considered as an ordered gradation of a scale and as linguistic estimation of every numerical value with some truth value.
Definition 3. ACL-scale for an attribute m with possible numerical values from the set W is an algebraic system
= {, , Ω }, where the set = , denotes possible numerical values and possible fuzzy terms for an attribute m; = {, , , } is a set of parameters of an ACLscale; Ω = {, } is a set of operations, defined on a set . Below the components and Ω of an ACL-scale will be considered in details. 3.1
Parameterization of an ACL-scale is useful as a tool for domain specific adaptation. To adopt an ACL-scale to real values of a set W we consider two alternatives. The first one corresponds to the case when experts evaluate quantaty, parameters and shape of membership functions of linguistic variables . Unfortunately this case is difficult to realize in practice. In the second alternative the goal is to minimize the work of expert and some algorithm is used to adopt an ACL-scale to real values of a set W. We apply the second alternative and consider four parameters of an ACL-scale adaptation:
= {, , , },
where = (), = (); MF is the uniform shape of the
membership functions of fuzzy terms (for example in a triangular form) [
Notice, that these intervals are the result of partitioning of the set W and any numerical value ∈ − , is considered according to an ACL-scale as identical, with the same linguistic value, but having different truth degree. According to (2) the length of numerical intervals d depends on quantity of fuzzy terms.
In this case researcher must define the shape and the quantity of fuzzy terms r . Parameter r determines a quantity of numerical intervals and their length d. It means that parameter r determines a level of linguistic granulation: smaller value of parameter r corresponds to larger linguistic granulation and vice versa. Therefore the quantity of fuzzy terms r depends on research goals and required level of granulation. Taking into account human perception the recommendation for choosing the value of parameter r are: 3 < < 10.
The example of ACL-scale for a numerical attribute m with possible values defined in = [−26, 66] is shown on the Figure 1. Here partitioning into six ordered intervals was done, on which five triangular fuzzy terms (r=5) were constructed with linguistic values = {!!!, !, !, !, !!!}. (1) (2) We assume that the following is fulfilled for an ACL-scale: 1. The numerical values w of attributes m corresponding to real or ideal objects are estimated. 2. Numerical and linguistic estimates are various, but they are equally essential aspects at the different levels of granularity. 3. Linguistic values of numerical attributes can be estimated by expert or a modeling estimation procedure.
The usage of parameters of an ACL-scale for linguistic description of numerical attributes allows to determine linguistic values practically in an automatic way, better understood by researchers. 3.2
The set of operations, defined on a set Η, can be based on fuzzified/defuzzified functions. The operation for linguistic description of each numerical value is defined as the following function: ! = !, ! ! ≥ ! ! , ∈ 1, 2, . . . , , ∀ = 1, 2, . . . , r.
(3) In respect to (3) for every ! ∈ W there will be only one linguistic value ! ∈ with the maximum value among all of membership functions, s – is a number of that membership function.
We denote the operation for numerical estimation of linguistic value as function !! = ! , ! ∈ , ! ∈ , for example, as centroid of area: !! = !!""##!$ !∙!(!)!".
!!""##!$ !(!)!" !! = !! − ! , It is obvious, that function calculates approximate value with some error of estimation, and the latter can be computed in different ways, for example in a form: where the approximate value is !! = ! ; ! is the actual numerical value of some attribute.
The usage of uniform scaling by an ACL-scale will allow to transform given manyvalued context into a formal context in automatic way and to explore the concepts having linguistic values which are better understood by researchers. 4
The transformation of a numerical value ! ∈ , = 1,2, … , into a linguistic value ! ∈ with an ACL-scale means, that it is possible to define several fuzzy terms ! ! , = 1, 2, . . . , r with different truth degree for ∀!.
Let ⊆ ℝ be a set of possible numerical values of an attribute.
First of all, it is required to construct an ACL-scale on the set W, containing the ordered fuzzy terms with linguistic values ! ∈ , = 1,2, … , .
Below we propose the Algorithm 1 for an ACL-scale creation by the determining its parameters on the set of possible numerical values W of a many-valued context.
Step 1. Define the parameter r (the number of fuzzy terms) of ACL-scale. Step 2. Compute the parameter nmin as the minimum value on a set of W. Step 3. Compute the parameter nmax as the maximum value on a set of W. Step 4. Order the possible values on . Partition the ordered set of possible values ⊆ ℝ, into r+1 intervals in respect to (2).
Step 5. Define the shape of the membership functions MF of fuzzy terms. Determine the linguistic values of fuzzy terms ! ∈ , = 1,2, … , .
To output the linguistic values for the numerical values of the set W, using an ACLscale, Algorithm 2 is proposed.
For each numerical value ! ∈ , = 1,2, … , do the following:
Step 1. Using operation (3) and well-known notion of fuzzy terms of chosen
shape (for details you can see [
Step 2. Determine the fuzzy term ! ! with the maximum value of membership function according to (3).
Step 3. Assign the output linguistic value as ! = ! for input ! Here s is the number of linguistic value on the set , corresponding to an ACL-scale for the set of numerical values W. 5
To illustrate how the ACL-scale can be applied to transform a many-valued context into a formal context we use the input data, which characterize hardware by two attributes ="Load of the central processor - CPU" and ="Load of the memory - RAM" (see Table 1).
We created one ACL-scale using the Algorithm 1 for both attributes, as their numerical values are contained in the same set of possible numerical values [0,100] presented in percentage. For this domain we defined = 0%, = 100%. Then seven fuzzy terms ( = 7) with linguistic values ”very low”, “low”, “below an average”, “average”, ”above an average”, ”high”, ”very high” were defined.
Table 1. Input many-valued data id_obiect , %
, % 1 2 3 4 5 6 7 8 9 84,31 50,67 66,89 97,06 92,04 97,33 97,44 88,30 66,64 82,94 58,93 68,18 77,56 33,58 93,42 94,78 80,05 48,49 The shape of membership function was chosen as triangular with parameters shown in Table 2 (a - left, c - right, b - middle of numerical interval on which membership function is build). After an ACL-scale has been created, it was used to output the linguistic value for every numerical value of the hardware attributes, applying the Algorithm 2. Table 3 illustrates the results of transformation of input data (see Table 1) into linguistic values. The results in Table 4 show the transformation of the numerical attributes of a manyvalued context (see Table 1) into linguistic variables for more understandable description of these attributes, which can be used for mining dependencies or for clustering. For further analysis the additional characteristics of a linguistic value of attributes are useful: the truth degree and the membership function.
av x aa x x hi x x x x x x x av x aa x x hi x x x vh x x
During the past years preprocessing became an important step of data mining. For better understanding and analyzing numerical data, it is useful to have their linguistic description. To derive the latter description the transformation tecniques based on scaling are used usually.
In this paper the notion of an ACL-scale as the tool for transformation a many-valued context with a numerical attributes into a formal context with linguistic attributes is proposed. The algorithm of an ACL-scale creation by adaptation of its parameters on a set of numerical values is described. Application of an ACL-scale provides the linguistic granulation which can be useful in segmentation and investigation of objects with similar features. Mining the dependencies among attributes and among several objects expressed in linguistic terms is another application of that linguistic granulation. In these tasks time reduction on preprocessing stage will be obtained due to usage of the proposed uniform scaling algorithm for different numerical attributes. The given example shows applicability and suitability of an ACL-scale for the preprocessing of a many-valued context with numerical attributes and deriving formal context with linguistic values. 7
The authors acknowledge that this paper was partially supported by the project no. 2014/232 of the Ministry of Education and Science of Russian Federation "Development of New Approach to the Intellectual Analysis of Information Resources" and by the project no. 16-07-00535 "Development and research of data mining algorithms for organizational and technical systems based on fuzzy models" of the Russian Foundation of Basic Research.