This paper describes an approach aimed at structuring of the generated transaction database in the process of forming a market basket using the rough set theory. The analysis of the recent publications and achievements showed that the structuring, categorization and classification at the stage of preliminary transaction analysis, before rules discovery, remain underdeveloped. The paper describes cases for a target set of the elements of the universe, that are classified into categories based on the equivalence relation. Approximations are proposed for the formal representation of such a set based on the rough set theory. A detailed example of the analysis and classification of transactions with various sets of objects is given.
The modern affinity analysis is one of the common techniques of data mining that discovers relationships between co-occurring activities.
Affinity analysis is mainly used for market basket analysis, the purpose of which is to detect associations between different events for the quantitative description of the connection between two or more events, which are called association rules. Such rules have two basic concepts: a transaction – a certain set of events co-occurring together (for example, a customer purchasing goods at a supermarket) and an itemset – a nonempty set of goods that have been bought in a single transaction.
Nowadays supermarkets collect information about purchases and store it in a database to be used later for association rules discovery.
However, the data gathered this way is not structured, since the transactions are written to the database one after another and their attributes, such as the frequency of transactions, the size of the itemset, its cost indicators etc., are not taken into account.
Thus, the database is loaded with the unstructured data where each storage unit can be represented by a finite number of attributes. This leads to a task of categorization and classification of unstructured data as well as the reducing of the amount of data by removing superfluous transactions.
The aim of this paper is to develop a methodology for structuring a transaction database at the preliminary stage of their analysis using the rough set theory. 3
A series of recent publications [1, 2, 5-11, etc.] discusses the development of methods, techniques and algorithms for the analysis of transactions and the binary association rules discovery in them. So, in the work [1], a rather in-depth review of the existing approaches to the search for numerical, generalized, temporal and fuzzy associations was performed.
In [2], the problem of constructing bases of numerical associative rules is solved: a method for synthesizing bases of associative rules is developed, in which the transaction database is fuzzified, threshold support values are calculated, criteria are used to evaluate indirect associations, which reduces the degree of user or expert participation [3, 4] in the process of searching for associative rules, and also allows you to retrieve not only frequently found sets, but rarely arising interesting associative rules.
The work [5] is devoted to a comparative analysis of the tools for association rules discovery (Apriori, DHP, Partition, DIC, etc.). In the work [6], the combined use of associative analysis and the decision tree method for solving economic problems is considered.
It should be noted that the existing publications generally propose the tools for the direct search for binary association rules in transactions. At the same time, the task of structuring and classification at the stage of preliminary transaction analysis, before rules discovery, remains underdeveloped. The theory of rough sets of Z. Pawlak [12] can be used to perform this task. This theory was further developed in [13-21]. It operates with the arrays of disordered (rough) data and, through their categorization, gives them a structured form.
In [13-17], authors outline some selected past and present research directions of rough sets. In particular, has emphasize the importance of searching strategies for relevant approximation spaces as the basic tools in achieving computational building blocks (granules or patterns) required for approximation of complex vague concepts. In [18], proposes a hybrid multi-granulation rough sets based on variable precision tolerance relations. Basic properties of hybrid multi-granularity rough set of variable precision are discussed, which provides a new approach to deal with the incomplete information system. A new generalization of coarse fuzzy sets in the generalized approximation space is proposed in [19-21]. The equivalence relations are viewed as a special type of a binary relations of a universe. Then, the rough fuzzy sets in generalized approximation space is defined.
This theory defines a knowledge base as K=(U, R), where U – is a finite set of objects (the universe), R – is an equivalence relation on U. For any R there is an associated equivalence relation IND(R). The relation IND(R) is called R-indiscernibility relation. Each partition includes elements that have the same values of classification features (attributes). Within each partition, elements are considered indiscernible.
Let X∈ U be a target set while the objects of U are categorized based on the attribute R, then the following situations are to be considered: 1. A set X is called crisp (exact) with respect to R if and only if the boundary region of X is empty. The boundary region consists of those objects that can neither be ruled in nor ruled out as members of the target set X. 2. A set X is called rough (inexact) with respect to R if and only if the boundary region of X is nonempty.
In order to characterize the set X with respect to R, additional notation and basic concepts of rough set theory are presented below: 1. R-lower approximation of a rough set X is a subset of all objects which can be with certainty classified as members of X with respect to IND(R): 2. R-upper approximation of a rough set X is a set of all objects which can be only classified as possible members of X with respect to IND(R):
The R-negative region of X is a subset of the objects of the universe that can be definitely ruled out as members of a target set X:
The boundary region of a set X is a subset of all the objects that belong to the Rupper approximation of X:
RX {Y IND(R)}:Y X RX {Y IND(R)}:Y X Ø
POSR(X) RX X:NEGR(X) U RX
BN R ( X ) RX RX
The R-lower approximation of X is called R-positive region of X:
(
Let us consider a knowledge base K=(U, R), where U={x1,x2,…,x10} – is the universe, R – is an equivalence relation [13]. The selected equivalence classes are:
U/IND(R) {{x1,x2 },{x3,x7,x10 },{x4 },{x5 },{x6 },{x8 },{x9 }}.
The two target sets are: X1 {x1,x2 ,x4 ,x5 } , X 2 {x1,x2,x3,x4 } .
The approximations, negative and boundary regions of the sets were obtained as follows:
RX1 {x1,x2,x4 ,x5 } , RX1 Ø ; BN R ( X1) Ø .
RX 2 {x1,x2,x4 } , NEG R(X1 ) {x3 , x6 , x7 , x8 , x9 , x10} , RX 2 {x1, x2 , x3, x4 , x7 , x10} ; NEG R(X 2 ) {x5 , x6 , x8 , x9} , BN R ( X 2 ) {x3 , x7 , x10} .
In order to evaluate the accuracy of the rough set representation of the set X, the following estimates were introduced: 1. R ( X )
, X Ø . card RX card RX
The accuracy of the rough set representation of X displays the degree of completeness of existing knowledge and is in the range R ( X ) [0,1] . If the boundary region of X is empty, i.e. RX RX , then R ( X ) 1 and X is crisp (precise) with respect to R. And otherwise, if card RX card RX , then R ( X ) 1 and X is rough (vague) with respect to R. 2. The value of roughness of X R ( X ) 1 R ( X ) was introduced as an alternative for the accuracy R (X ) . The value characterizes the degree of incompleteness of existing knowledge.
In general, the procedure of transaction classification using the rough set theory can be carried out in the following way: ─ if the new transaction belongs to the lower approximation of a certain class, then it belongs to this class; ─ if a new transaction belongs to the negative region of a particular class of transactions, then it can be with certainty identified as one that does not belong to this class; ─ if a new transaction belongs to the boundary region of a particular class, then it is undecided whether it belongs to this class. 6
Let us consider a detailed example of the analysis and classification of transactions (n=15) with various itemsets (Xi). The universe of transactions, their itemsets, and attributes are presented in table 1. a5 – baked goods; a6 – confectionery products; a7 – drinks. The listed attributes are evaluated on a verbal-numeric scale: “the attribute is present in the transaction” – “1”, “the attribute is not present in the transaction” – “0”. Additionally, a8 is included in the list of attributes – the size of the itemset with gradations: “small” – “0”; “average” – “1”; “large” – “2”, as well as a9 – the cost of the itemset with gradations: “low” – “0”; “medium” – “1” and “high” – “2”.
Using the equivalence relation, let us divide the universe U of the table 1 into partitions:
U / IND(R1) {X1}; U / IND ( R2 ) { X 2 , X 4 , X 8}; U / IND ( R3 ) {X 3 , X 10}; U / IND ( R4 ) { X 5 , X 9}; U / IND ( R5 ) {X 6 , X11}; U / IND ( R6 ) {X 7}; U / IND ( R7 ) {X 12}; U / IND ( R8 ) {X 13 , X15}; U / IND ( R9 ) {X14} .
The base of transactions for the universe is defined by:
BTr (U,E1, E2 , E3 , E4 , E5 , E6 , E7 , E8 , E9 ) , where E1 {X1}; E2 { X 2 , X 4 , X 8}; E3 {X 3 , X 10 }; E4 {X 5 , X 9}; E5 {X 6 , X 11}; E6 {X 7}; E7 { X12 }; E8 {X13 , X15}; E9 { X 14 } – are the families of equivalence classes of U; the elements that belong to each of such classes are indiscernible.
The new transactions with the following itemsets were formed:
X(
Let us estimate the representation accuracy of the sets X (
The set X (
The set X (
The set X (
X (
The set X (
Using (
RX (
8
R (X (
RX (
12
R (X (
RX (
The obtained results indicate that the target sets X (
In such a situation, the mathematical apparatus of the rough set theory offers three strict rules for the classification of target sets that characterize transactions and their itemsets:
X i E j , if X i POS R(E j ) ; X i E j , if X i NEG R(E j ) ; X i E j or X i E j , if X i BN R(E j ) .
It implies that for a reliable classification of transactions, only first and fourth decision rules can be used.
The presented approach is aimed at structuring of the generated transaction database in the process of forming a market basket using the rough set theory. The basis of this theory is the procedure for equivalence relations formation that is used to distinguish categories (classes) of transactions that are considered indiscernible within each category. When the transactions cannot be completely described by the obtained classes, specific approximations and estimates of their accuracy are introduced, which assess the degree of belonging or completeness of non-membership of such transactions in these classes.
Ultimately, a classified transaction database will increase the selectivity of the search for binary association rules. 11. Kovalenko, I., Davydenko, Y., Shved, A.: Searching for Pareto-optimal solutions. Advances in Intelligent Systems and Computing IV, Springer International Publishing, vol. 1080, pp. 121-138 (2020). doi: 10.1007/978-3-030-33695-0_10 12. Pawlak, Z.: Rough sets theoretical aspects of reasoning about data. Kluwer Academic Publishers, Boston; London (1991). 13. Uzga-Rebrovs, O.: Knowledge representing features in rough sets [in Russian]. In: 7th International Scientific and Practical Conference: Environment. Technology. Resources, vol. 2, pp. 169-175 (2009). 14. Skowron, A., Dutta, S.: Rough sets: past, present, and future. Natural Computing, 17, 4, pp. 855–876 (2018). doi: 10.1007/s11047-018-9700-3 15. Tripathy, H. K., Tripathy, B. K., Das, P. K.: An intelligent approach of rough set in knowledge discovery databases. International Journal of Computer, Electrical, Automation, Control and Information Engineering, vol. 1(11), pp. 3437-3440 (2007). 16. Weihua, X., Xiaoyan, Z.: Fuzziness in Covering Generalized Rough Sets. In: Chinese
Control Conference, Hunan, pp. 386-390 (2007). doi: 10.1109/CHICC.2006.4347200 17. Wang, J., Peng, L.: Research on Expression of Rough Equality Sets. In: IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, Wuhan, pp. 337-341 (2008). doi: 10.1109/PACIIA.2008.289 18. Lin, H., Wang, Q., Lu, X., Li, H.: Hybrid multi-granulation rough sets of variable precision based on tolerance. In: 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), Zhangjiajie, pp. 231-235 (2015). doi: 10.1109/FSKD.2015.7381945 19. Sun, B., Gong, Z.: Rough Fuzzy Sets in Generalized Approximation Space. In: 5th International Conference on Fuzzy Systems and Knowledge Discovery, Shandong, pp. 416-420 (2008). doi: 10.1109/FSKD.2008.178 20. Wei-feng, D., Hai-ming, L., Yan, G., Dan, M.: Another kind of fuzzy rough sets. In: IEEE International Conference on Granular Computing, Beijing, vol. 1, pp. 145-148 (2005). doi: 10.1109/GRC.2005.1547254 21. Dai, J., Chen, W., Pan, Y., Sequent calculus system for rough sets based on rough Stone algebras. In: IEEE International Conference on Granular Computing, Beijing, vol. 2, pp. 423-426 (2005). doi: 10.1109/GRC.2005.1547326