The paper examines the issues of hidden connections and potentially useful information from large data sets. Theoretical knowledge about associative rules is substantiated, their influence on connections in multimodal data sets is investigated. The methods of application of associative rules in practice are analyzed. The following are considered in detail: the basic concepts of associative rules and their connection with the idea of logical regularity; ways to determine the "strength" of these connections; basic algorithms for finding patterns; practical implementation of the search for associative rules. The regularities in the "templates" are analyzed: support and confidence value. The correct choice of these values, which directly affect the results of the search for rules, is experimentally determined. Research in this paper aimed to consider the basic concepts and find the Associative Rules both in traditional ways and in heterogeneous data of semantic networks, which creates specific problems when using existing algorithms. The data of semantic networks are analyzed, which in most cases serve a particular field and are highly specialized. The paper presents a new search method for Associative rules on inhomogeneous data in semantic networks expressed in RDF/(S) and was considered only to a small extent. The results of experiments on accurate SW data showed promising results.
The primary purpose of data mining is to "reveal" the hidden connections and potentially useful
information from large datasets [
The basic concepts of associative rules and their connection with logical regularity. • • • •
Ways to determine the "strength" of these connections.
Basic algorithms for finding frequency.
Practical implementation of searching for associative rules.
For the first time, searching for associative rules arose in the consumer area: it was necessary to identify specific "patterns" of consumer purchases to increase sales of goods due to these data. The Associative rule acquired of the form: "Event X is followed by event Y", as a result of which it is possible to obtain a certain regularity - if the purchase (transaction) has a set of goods (elements) X,
2022 Copyright for this paper by its authors.
then with some probability to assume that the set Y will also appear in it [
The department grouped all products in grocery stores to find what they needed more quickly. It reduces spending time shopping in a store and is also interested in buying something else. Keep in mind that associative rules will not help, in this case, the consumer's personal preferences. Still, with their help, it is possible to find connections between items in each purchase transaction (as opposed to filtering preferences, which considers all purchases of one consumer to recommend to him goods or services in the future). Therefore, the data to search for associative rules are regarded as separate purchases of different consumers by one group.
The purpose of AR [
⊂ and ∩ =⊘(X and Y - set of things) [
Let's say we want to analyze how sales are related to certain goods in the store. In this case, the S contain a list of things X (that is, it is a subset , "covers" the transaction). list will include all goods in the store, and the transaction (purchase) will be a set of things in the buyer's basket. Let's find AR: { , } → { }(where{ , } = , { } = ): transaction ∈ must 2.1.
In the case of a product basket problem, consider the following example of a rule: Bread →
Apples (support value = 20%, confidence value = 45%). The results show that 20% of buyers buy
bread along with apples at the time like 45% of buyers who buy bread, they also buy apples. Support
value and confidence value determine "power" of this rule [
The calculation of the support value rule is to represent transactions ∈ , which are subordinate ∪ , and in some way is the probability (
∪ ), in other words, it is the amount or percentage of
transactions that have a set of specific elements. The support value of the
→ rule will be
calculated by the Formula 1:
( ∪ ),
(1)
where - the number of transactions in the T list (in our database);
number of transactions in T that include X and Y [
ID 0001 0002 0003 0004 0005
Items A, F, B, C
A, C
A, D
D, E, C
F, A, D
where ( )- the number of transactions in T that include X; ( ∪
)the number of transactions in T that include X and Y [
The confidence value determines the "predictability" of a rule. When its value is too small, there is a problem of reliability of definition or prediction of Y and X. Confidence value rule { , } → { } = 1/2 = 50% in our DB (Table 1). (2) (3) 2.3.
There is a problem: what to do when confidence value, for example, of rule { , } → { }, is less
than ({ })? Lift value acts as an indicator of the "predictive power" of the rule compared to a
random event, calculated (Formula 3) [
Support value is useful in cases where it’s too small value indicates that the rule can happen "accidentally". Support value list of things { , , } = 1/5 = 20% in our DB (Table 1). 2.2.
Confidence value rule consist in representing transactions ∈ with values from the list Y, which
include X, and in some way is a conditional probability ( | ). In other words, confidence value
determines how often "things" in list Y appear in transactions with things in list X. Confidence value
rule X → Y will be calculated by the Formula 2 [
Can be represented as ( → ) (if X and Y are independent, the value of lift value will
( )
be equal to 1; if X and Y occur more often than if they were independent, lift value> 1) [
Recently, the amount of data and semantic annotations in the so-called "Semantic Web" (SW) is
constantly growing. This new type of complex and diversified graph-oriented networks creates a
problem for extraction data presented using RDF / (S) and OWL languages. The solution to this
problem may be to use new algorithms that use the axioms of ontologies (Tbox) to obtain the
corresponding transactions, which will later use traditional association rule algorithms to find the
result. This process is guided by the requirements of the analyst, expressed in the form of query
patterns. [
In the last few years, there has been a growing interest in combining two research areas: semantic
networks and data mining (DM). As mentioned above, the number of available semantic annotations
is constantly growing. This is partly due to the active researchers involved in the study of textual data,
commonly referred to as Ontology Learning [
Machine learning algorithms are successfully applied to large data sets to obtain results by
searching for patterns (e.g., associative rules) [
Previous work on SW data extraction has focused mainly on clustering and instance classification. However, the presentation methods required for associative data mining are different from the usual clustering and classification tasks. The rules of the association are based on the concept of transaction, which is an observation of the frequency of occurrence of the current set of elements. This is basically a data representation based on the set, which differs from the vector-numerical representation used in clustering and classification. When working with SW data, the main problem is to determine the necessary transactions and elements of a semi-structured and heterogeneous representation of this data. Thus, it becomes crucial to use as much knowledge as possible provided by ontologies so that transactions can be easily identified and extracted. There is a wide variety of ways to generate elements and transactions from semantic data, which depend on the level of detail and structural semantics. 3.1.
Semantic web technologies aim to provide the necessary presentation languages and tools to bring
semantics to current web content. As a result, the W3C has proposed several presentation formats that
rely on XML. The resource description language (RDF) was the first language proposed by the W3C
to describe semantic metadata. RDF has three types of elements: resources (web objects (entities) that
are identified by URIs), literals (atomic values such as strings, dates, numbers, ...) and properties
(binary relationships between resources and literals, also identified by URI). The main components of
the RDF are triplets: a binary relationship between two resources or between a resource and a literal.
The resulting metadata can be considered as a graph, where nodes are resources and literals, and
edges are the properties that connect them. RDFS extends RDF to allow you to define triplets by
classes and properties. Thus, we can describe a schema that manages our metadata in the same
description frame. An ontology web language (OWL) was later proposed to facilitate the work on the
semantic description [
One of the areas of application may be medicine - here all the time a huge amount of semantic data is generated. In particular, most semi-structured and very heterogeneous data sources (e.g., laboratory test reports, ultrasound scans, images) are subjected to semantic annotation using UMLS, NCI and Galen ontologies. Suppose we have an excerpt from a clinical report presented in Figure 1a, the semantic annotation of which leads to certain axioms (Figure 1 b) and statements (Figure 2). Axioms in Figure 3 provide the semantics of all information concerning the patient (i.e., medical history, reports, laboratory results) by conceptualizing the domain. Figure 4 provides data on triplets that describe the patient (i.e., semantic annotations (Abox); subjects, predicates, and URI-formatted objects that point to relevant data resources).
The generated data also represent complex relationships that are rapidly evolving with the use of
new biomedical research methods. Obviously, traditional analytical tools are not suitable for this type
of data [
a)
Axioms of ontologies (Tbox) allow to define an area from the point of view of atomic concepts (classes in OWL) and roles (properties in OWL). OWL provides for the union ⋃, intersection ⋂ and negation ¬, as well as list classes (one Of), existence ∃, universality ∀ and constraints (≤, ≥, =) of the atomic concept of or the inverse ¬ .
This section presents an overview of the method according to the scheme shown in Figure 3. The user specifies the extraction pattern using the query language syntax. The transaction miner can identify and construct transactions according to a previously defined mining scheme. Finally, the set of received transactions is processed by the traditional pattern mining algorithm, which finds the associative rules according to the minimum values of support value and confidence value defined in the template for the network shown in Figure 4.
Both the ontology and the instances can be represented in the form of subject-predicate-object triplets (Figures 5-6), forming a graph where nodes are resources and literals, and edges are properties that connect. This dynamic graph-based structure contrasts with the well-structured and homogeneous datasets used in conventional associative rule search algorithms.
Therefore, to obtain entities and transactions, users must specify the target concept of the analysis and related functions. The features must be relevant to the target concept, i.e., they will be extracted from the subgraph of each instance belonging to the target concept of the analysis.
In this method, only important instances (i.e., features) are "extracted" and combined from the entire repository and embedded in regular transactions, capturing implicit data at the schema level in the ontology. You can then apply existing associative rules search algorithms.
This type of search rule will become increasingly valuable in future research on both machine learning and SW data. In the future, you can apply generalized query schemes using ontology axioms, as well as automatically detect important instances and search for associative rules. In addition, the method can be used in a variety of scenarios where mining tasks are transaction-oriented.
The problem of the research is the use of data in the ontology to filter and narrow the identified rules, as well as to express the goals of the user. Another important area worth researching is the combination of clustering mining algorithms and associative rules.
Previously, this technique has been implemented through hierarchical clustering based on a set of subjects (FIHC). Basically, the FIHC algorithm generates clusters from frequent sets of elements, which in turn constitute cluster descriptors.
A new approach could be an algorithm based on finding frequent pairs of objects, which provides more homogeneous clusters and better descriptions than those obtained from FIHC.
Also, many studies involve the use of more complex algorithms for data extraction and the formation of transactions from them, the study of their efficiency.
No less interesting is the development of new algorithms for data exchange, which are based on semantically enriched elements of the generated transactions.
This section will take a closer look at both the well-known AR search algorithms and the new AR search algorithm in semantic networks.
AIS algorithm. The first algorithm for finding associative rules, called AIS, was developed by
IBM Almaden Agrawal, Imielinski, and Swami in 1993. From this work began an interest in
associative rules; in the mid-90s of the last century came the peak of research in this area, and since
then every year there are several new algorithms. In the AIS algorithm, candidates for multiple sets
are generated and counted "on the fly" while scanning the database [
SETM algorithm. The creation of this algorithm was motivated by the desire to use the SQL language to calculate frequent sets of goods. Like the AIS algorithm, SETM also generates candidates "on the fly" based on database transformations. To use the standard SQL join operation to form a candidate, SETM separates the candidate formation from their count.
The inconvenience of AIS and SETM algorithms is the excessive generation and calculation of the
Support value of too many candidates, which as a result are not provided often. To improve their
performance, the Apriori algorithm was proposed. [
Apriori algorithm. The work of this algorithm consists of several stages - the formation of candidates and the counting of candidates. Candidate generation is the stage at which the algorithm, by scanning the database, creates many i-th candidates.
At this stage, their Support value is not calculated. Candidate counting is the stage at which the Support value of each i-th candidate is calculated. Candidates whose Support value is less than the minimum value set by the user (min Support value) are also rejected here.
The other i-th sets will be the ones that are often found in the database - that is, if the set {A, B} is
common, then the sets {A}, {B} will also be common. This property is the Support value property
(Formula 4): [
∀ , : ( ⊆ ) ⇒ ( ) ≥ ( ), (4) where X, Y - sets of elements.
Looking at the algorithm of simple search of values, in it there are 2 variants of sets at the given n elements (Figure 7). Suppose we have a set (AB) with a low value Support value - the Apriori algorithm "cuts off" AB and its derivative sets, thereby accelerating (Figure 8).
Let's consider the Apriori algorithm on an example, for this purpose we will change a little and we will expand our Table 1 with data (Table 2):
Set min Support value = 3 (Figure 9).
At the first stage (Figure 9), there is a formation of 1-element candidates. Next, the algorithm calculates the Support value of 1-element sets. Sets with a Support value less than the specified (in our case 3) are cut off. In the example, these are sets E and F, which have Support value = 1. The remaining sets of elements are considered to be common: A, B, C, D.
Next is the formation of 2-element candidates, counting their Support value and cutting off sets from Support value < 3. The remaining 2-element sets AB, AC, BD, participate in the further work of the algorithm.
Continuing the work, the algorithm at the last stage forms 3-element sets of goods: ABC, ABD, BCD, ACD, calculates their Support value and again cuts off sets from Support value < 3. The result a set of ABC products is the most common (Figure 9).
Among the varieties of the Apriori algorithm are the following: • AprioriTID. The peculiarity of this algorithm is that the database of elements is not used to calculate the Support value of the recruitment candidates after the first step. For this purpose, the candidate coding performed in the previous steps is used. In the following steps, the size of the encoded sets can be much smaller than the database itself, thus saving significant resources. • AprioriHybrid. Analysis of the running time of the Apriori and AprioriTID algorithms shows that in earlier steps Apriori achieves better speed than AprioriTID; however, AprioriTID works better than Apriori at later steps. In addition, they form the same procedure for candidate sets. Based on this observation, the AprioriHybrid algorithm is proposed to combine the best properties of the Apriori and AprioriTID algorithms. AprioriHybrid uses the Apriori algorithm in the initial steps and moves to the AprioriTID algorithm when large sets of memory can be used. However, switching from Apriori to AprioriTID requires resources.
Some authors have proposed other algorithms for finding associative rules, which were also improvements to the Apriori algorithm. One of them is the DHP algorithm, also called the hashing algorithm (proposed by J. Park, M. Chen and P. Yu, 1995). Based on its probabilistic calculation of sets of candidates, valid for reducing the count of candidates for the duration of the Apriori algorithm. The reduction is provided by the fact that of the k-element sets of candidates, in addition to the step of reducing the passage of the hashing step. In the algorithm at the k-1 stage during the selection of the candidate, the so-called hash table is created. Each hash table entry is a counter of all reference values of k-element sets that correspond to a row in the hash table. The algorithm uses this information on the k-th to reduce the elements of the candidate sets. After reducing the subset, as in Apriori, the algorithm can delete the candidate set if its value in the hash table is less than the specified Support value.
Also to other advanced algorithms: PARTITION, DIC, the algorithm of "sample analysis". PARTITION algorithm (proposed by A. Savasere, E. Omiecinski and S. Navathe, 1995). This algorithm of partitioning (division) is contained in the database of scanning operations through the section of its section, each of which can fit in RAM. In the first place in each of the sections using the Apriori algorithm displays sets that are common. The second confirms the importance of supporting each such set. Thus, the stages are available on all other common data sets. The DIC algorithm (Dynamic Itemset Counting, proposed by S. Brin R. Motwani, J. Ullman and S. Tsur, 1997) divides the database into several blocks, each of which is marked by so-called "start points", and then cyclically scans the database. 4.2.
Until now, AR search methods have been applied to traditional data in tabular format or on the basis of graphs. This section explores the problem of finding rules in semantic web data and proposes a new approach to finding APs directly from semantic web data. This approach takes into account the complex nature of semantic web data in contrast to traditional data and, in contrast to existing methods, eliminates the need to convert data and involve end-users in the search process. In trying to apply this search to atypical data, we encounter certain problems and differences compared to traditional ones: • • •
Heterogeneous: traditional mining algorithms work with homogeneous data sets in which instances are stored in a well-ordered system, and each instance has predefined attributes. But the semantic data are heterogeneous. This means that specific instances of categories / domains (e.g. people, cars, medicines, etc.) based on the same ontology or individual ontologies may have different characteristics.
There is no clear definition of transactions: in conventional information systems, data is stored in databases using predefined structures, and these structures can be used to recognize transactions and thus extract them from the data set. Then the traditional AR search algorithms process these transactions. For example, in the case of a “buyer basket”, transactions are formed from products that are purchased together, and these products will have the same ID as the transaction ID. Conversely, in a semantic network, different attributes for an instance may be formed at different times, and therefore an instance may have an attribute that does not exist in another instance of the same type.
Multiple relationships between entities: Traditional AR search algorithms to generate large sets of elements take into account only the values of the objects and assume that there is only one type of relationship between the entities (for example, purchased together). But in semantic data, there are many relationships between entities. In fact, predicates are relations between two entities or between one entity and one value.
Because semantic annotations are encoded in RDF / (S) and OWL, you should extend SPARQL with new elements that can specify a search pattern. The syntax is somewhat similar to Microsoft Data
Mining Extension (DMX), which is an SQL extension for working with DM models in Microsoft SQL Server. The extended SPARQL grammar is shown in Figure 10 and Figure 11 shows an example of the SPARQL view for AR search schemes (Formula 5): = ( , , {
The SPARQL query has been expanded by adding a new character called MiningQuery. The body of the query consists of variables that the user targets when searching for data. Next to each variable, we define its type: RESOURCE for variables that contain RDF, and LITERAL for those that have regular data types. In case we want to find patterns with only one variable, we add the keyword MAX-CARD1 to the variable. By default, found templates can contain more than one occurrence of each variable. In addition, we define the "sequence" of this rule by adding the PREDICT keyword (optional). Finally, the TARGET keyword refers to the analyzed resource, which should be an ontology concept. The purpose of the analysis determines the set of rules obtained. In WhereClause, we specify restrictions on previous variables. The advantage is that the user's knowledge of the ontology structure is not required. Therefore, users only need to specify the type (concept of ontology) to which the variables refer.
Let the user choose the patient as the desired "concept" of the analysis. The set of characteristics that will make up the transaction includes diagnosed diseases, prescribed drugs and damage rate. Finally, the transaction will be based on the details of the report, i.e. the transactions will not include the characteristics in all reports in general, but only the characteristics of each doctor's report.
The variable jadi refers to the index of injury to the patient's joint, the user specifies the report and damageIndex as a property of the resource and the type of data from which they can be obtained. UsingClause defines the name and parameters of the algorithm.
Because we do not ask the user to specify the exact relationship, the query model introduces some ambiguity about the elements that perform the transaction. Thus, the same conceptual changes (selected features) can be used under different contexts of ontology. For example, Disease can diagnose the patient's own illness or the illness of a family member. This ambiguity becomes a problem in determining what the intentions of the users really are. In fact, the user can use this ambiguity by specifying in the extended SPARQL query to understand the ontology using the "triplets" WHERE. However, this task can be cumbersome. For the query to be really correct, the user can select the desired context using CONTEXT added to the corresponding concept. In addition, the system will build transactions, taking into account all possible contexts.
Recalling the form of subject-predicate-object triplets (Fig. 2.2.4), they will be useful for the above-mentioned
AR search scheme = ( ,
}). Instances of RHEX1, RHEX1, TREAT1 will belong to the concepts of context Q. The transactions of the elements obtained from these three compositions are shown in Figure 12:
To ensure that the algorithm is correct and relevant, it will be tested on real-world OWL instances of patient observation. These annotations were formed in the context of the Health-e-Child (HeC) project and they correspond to an ontology similar to the example in Figure 1b).
The structure of semantic annotations is very heterogeneous and contains information about 588 patients classified into three different groups according to their disease: juvenile idiopathic arthritis (JIAPatient), heart disease (CardioPatient) and neurological disease (NeuroPatient).
The total number of semantic annotations is 629,000, which is an average of more than 1,000 annotations per patient.
To avoid errors, query schemes were automatically generated for 12 different concept concepts (disease, treatment, medication, ...) and 3 concepts for contexts: patient, visit and report. It is worth noting that the Report concept has 20 sub-concepts that correspond to the various clinical reports of the HeC project.
The current implementation of transaction extraction has been developed on the basis of the ontology indexing system, which also provides a simple mechanism for creating ontological indexes. To confirm the relevance and results of the found transactions, there is a range of different AP search algorithms, among which genetic algorithms (GA) for AP search have recently been proposed.
On the Table 3 shows three selected contexts for experiments, as well as the number of generated transactions and their average length.
The number and nature of transactions received in each context are completely different and will therefore affect the rules created. More general contexts tend to generate longer transactions, which in turn increases the likelihood of obtaining more rules.
Instead, more specific contexts generate smaller transactions, which narrows the scope for detecting rules.
This discrepancy in the nature of transactions necessitates adequate adjustment of the minimum Support value threshold of each set-in order to be able to find the association rules.
In the Table 4 shows the number of created rules together with their average Confidence value, average Lift value and -coefficient for three sets of transactions.
All created rules have a high Confidence value. In addition, the more limited the context, the better the rules are formed. Moreover, the -coefficient shows a strong correlation in all cases.
In the Table 5 shows the effect of applying certain restrictions (i.e. selecting only specific report types) in the search template.
Each line displays received transactions and rules for all reports, canceling the 5 most common reports and discarding the 12 most common reports in the patient context. This table also includes the percentage of rules that contain items from different reports.
Figure 13 analyzes the coverage of the formed rules by different thresholds of support as an indicator of their quality.
The rules obtained from the Patient set achieve good coverage with relatively high thresholds of Support value. However, other received sets of rules are not able to confirm the high percentage of transactions. The fact is that the length of other sets of transactions is shorter, which usually reduces the number of detected AR. In the case of the Report transaction set, the coverage is even less because the transactions are derived from different types of reports. Therefore, good rules may arise, but with very low Support value thresholds. In these cases, it would be advisable to use more sophisticated AR search algorithms that are not based on the concept of Support value.
In Figure 14 shows the average Confidence value of the generated rules with different threshold Support value.
The support value for the three sets of transactions remains high even for low thresholds, which confirms the quality of the rules.
Based on the two previous measures (coverage and average Confidence value) we can select a minimum Support value threshold for each set of transactions and further analyze the quality of the rules obtained. In Figure 15 shows the coating, multiplied by the average Confidence value. For each set of transactions, the Support value threshold is selected, at which both measures are maximally involved.
Finally, the three Figures 16, 17 and 18 show an example of AR obtained in the context of Patient, Visit and Report.
When considering the results, the Support value can also be interpreted as a percentage, for example for the first rule it was 0.260 - this means that sets of diseases in the rule occur in 26% of transactions. In many ARs found in the table above, the Confidence value is close to 1. Considering the first rule in the example, this means that in 100% of transactions a patient with oligoarthritic and lumbar pain has active tissue inflammation in this department. Lift value characterizes how good the prediction is and how interdependent the factors are. The greater the value, the greater the dependence of factors, i.e. how much the presence of one factor affects another. With low Lift values, on the contrary, the lower it is, the greater the negative effect one factor has on another.
This Figure 18 has some really interesting context-based rules Report. At observation at the patient of a fever in most cases it specified on the appearance of erythema, indicating a complex inflammation of the joint or tissues.
Most of the operations before which magnetic resonance imaging is performed with using additional chemical compounds of iron, were just for removal tumors. However, with high Confidence and Lift value, these rules are low Support value, which indicates the small number of occurrences of these sets in transactions.
Summarizing all the above, research in this work was directed to consider the basic concepts and search for AR in both traditional ways and in inhomogeneous data of semantic networks, which creates certain problems when using existing algorithms. It is worth noting that one of the most popular areas of application for AR search still remains consumer and marketing. Semantic network data in most cases serve for a specific field and are highly specialized. Probably that's why direction you can do a lot of interesting research, one of which is the search associations among heterogeneous data.
A new method for finding ARs from inhomogeneous ones was also presented data in semantic networks expressed in RDF / (S) and OWL. Previously, this problem considered only to a small extent. Experiments on real SW data show good results. An interesting problem for future work is data mining in the ontology for filtering and cutting off the detected rules. Yet one important area that can be considered in the future concerns combination of clustering and AR search algorithms for generalization of arrays documents. This technology has previously been implemented to some extent hierarchical clustering of sets (FIHC). Basically, the FIHC algorithm generates clusters of sets of elements, which, in turn, make up the cluster descriptors. A new approach based on hierarchy has also recently been proposed element sets, which provides more homogeneous clusters and better descriptions than those obtained from FIHC. Undoubtedly, each algorithm can be improved and improve, apply better ways of embedding data to generated transactions and study their effectiveness. It is no less interesting development of new data exchange algorithms based on SW data and are accelerated by new ways of processing the generated transactions.