There is some evidence that integration benefits of classification and association rule mining together can result in more accurate and efficient classification models than traditional classification algorithms (Ma & Liu, 1998). %%EOF 0000004342 00000 n International Journal of Pattern Recognition and Artificial Intelligence. As the results show, proposed method gained the best position and CBA has the worst one. They concluded that Apriori is a better choice for rule-based mining task in terms of accuracy and computational complexity. If we convert the result of decision tree to classification rules, these rules would be mutually exclusive and exhaustive at the same time. The .gov means its official. sharing sensitive information, make sure youre on a federal 0000006762 00000 n 2009. pp. This parameter defined that how many times each sample must be covered to remove from the samples (Li, Han & Pei, 2001). Apriori algorithm can produce a lot of rules, but much of them are superfluous.

After the conditions are satisfied for the Apriori algorithm, we run this algorithm for each class with different Minsup and Minconf. The ARM is a powerful exploratory technique with a wide range of applications including marketing policies, medical domain (Ilayaraja & Meyyappan, 2013; Shin et al., 2010), financial forecast, credit fraud detection (Sarno et al., 2015) and many other areas. If the new harmony is better than the worst harmony in HM, then include the new harmony in the HM and exclude the worst harmony from the HM. European conference on machine learning; 2000. pp. 0000003123 00000 n Ramak Ghavamizadeh Meibodi authored or reviewed drafts of the paper, approved the final draft. That is, if more than one rule is triggered, need conflict resolution: Size ordering - assign the highest priority to the triggering rules that has the toughest requirement (i.e., with the most attribute test), Class-based ordering - decreasing order of prevalence or misclassification cost per class, Rule-based ordering (decision list) - rules are organized into one long priority list, according to some measure of rule quality or by experts. Rule r1 covers 50 positive examples and 5 negative examples Rule r2 covers 2 positive examples and no negative examples. Principles of Data Mining and Knowledge Discovery. ;VEY Producing concise and accurate classifier by utilizing association rule mining is one of the attractive domain for data mining and machine learning researchers. 0000010467 00000 n Dynamic relocation of mobile base station in wireless sensor networks using a cluster-based harmony search algorithm. 469 0 obj <> endobj .{x39NG=B2Ft4Pg&@yjh|ZX-:t':`yD,#(G6!zJu7#c(]=NOWGZGin=lvsyj}}~/]}3}ZT}b8Lel-|lJh&w8k~)b,wn&S7/{}oerCN7v j$i1q#CRGqI<2mAGtVuc2a+h}^~{]sQg%.Opk{n`L6__^Vv5kX}BA Proceedings of the 1993 ACM SIGMOD international conference on management of data, Washington DC, 25-28 May 1993; New York. The Friedman test is a non-parametric statistical test developed by Milton Friedman (Friedman, 1937; Friedman, 1940). 0000007479 00000 n The code shows that how we build a rule-based classifier and determine the test data output. e*BCK \ewePv3PNns&X`;q02h!jqLJ4jy&A%"xmnNK?ga3Zh,aPKuW aG +w|i,37&IhTY[LZK*? Shin AM, Lee IH, Lee GH, Park HJ, Park HS, Yoon KI, Lee JJ, Kim YN. Thabtah F, Cowling P, Hammoud S. Improving rule sorting, predictive accuracy and training time in associative classification. Classification of imbalanced data: a review. 0000011855 00000 n The pseudo code of the proposed method is shown in Table 1. Careers.

0000033011 00000 n 6Qo:q,_Dk4P41V)gK,4+*/W$/%!cLQ[PLugE KEHTVSiAs(\gm/Yufy!yWs|TPEX0K,Mfu=VJzqB(Yr/#.uH[pp%CiXLMn 0000004762 00000 n International Journal of Computer Applications. Proceedings of the 17th international conference on data engineering, 2001; Piscataway. official website and that any information you provide is encrypted 0000006162 00000 n For example, when a test record is presented to the classifier, it is assigned to the class label of the highest ranked rule it has triggered. Bethesda, MD 20894, Web Policies Consider a dataset for supervised learning which contains observations of a class label variable and a number of predictor variables. 265269. Each record is covered by at least one rule. The third change occurs in the classification phase. Instead of using only support and confidence, we also used lift measure as a metric for evaluating the significance and reliability of association rules. 424435. This is clearly impractical. Instead of using a large number of candidate rules, binary Harmony Search was utilized for selecting the best subset of rules that appropriate for building a classification model. 0000009023 00000 n By using this approach, the selected rules are not the best subset of possible rules. 0000070743 00000 n 0000010227 00000 n Association rules provide information of this type in the form of if-then statements. Unlike the if-then rules of logic, association rules are intrinsically probabilistic and are computed from the data. Classification is one of the most important areas in data mining that has applied in many applications such as bioinformatics, fraud detection, loan risk prediction, medical diagnosis, weather prediction, customer segmentation, target marketing, text classification and engineering fault detection. A new heuristic optimization algorithm: harmony search. Data mining, 2004 ICDM04 fourth IEEE international conference on; Piscataway. Another challenge of existing algorithms is related to rare class. 0000061298 00000 n 0000002249 00000 n I'P9? [. Mazid, Ali & Tickle (2009) compared the performance between the rule-based classification and association rule mining algorithm based on their classification performance and computational complexity. Hesam Hasanpour conceived and designed the experiments, performed the experiments, analyzed the data, contributed reagents/materials/analysis tools, prepared figures and/or tables, performed the computation work, authored or reviewed drafts of the paper, approved the final draft. Therefore we used the implementation of HS that proposed by Afkhami, Ma & Soleimani (2013). Li J, Shen H, Topor R. Mining the optimal class association rule set. rrBmTs8]34NnO#)X-9=8=9w+aWa^r@\WTT4lo\htW^-T[3tx*mIQicd.9E,m_]O`]<:j/:,tXI F)Flj'_#U?u"^E5*m.15rA[0]R]nb A"|?+ 7z{q\y'E%= -ypQ6O6=Mkk1v/HvO{"_onV}~=A\qxo5\O!pQ9l:PW!76>y=q #j The PAR determines the probability of a candidate from the HM to be mutated. 2003. pp. 0000063968 00000 n We used the Friedman test (Friedman, 1940) as an appropriate choice for comparing multiple classification algorithms (Brazdil & Soares, 2000; Demar, 2006). 0000004140 00000 n 0000007488 00000 n Accessibility D~K;!^s5 *{!(lll^Hp -s@. 0000012333 00000 n Another issue that must be considered is related to the type of dataset that is appropriate for applying the Apriori algorithm. Since the number of rules that satisfy Minsup and Minconf conditions is high and considering all subset of rules is not possible, we applied the Harmony Search algorithm for finding the best subset of rules that can be used as a classifier. <<31B4E2F4BAEB66499930C08531A735FC>]>> 0000004093 00000 n Their experimental results showed that Apriori is the most beneficial association rule mining algorithm. Their experiments show that this approach achieves better accuracy than conventional classification algorithms such as C4.5. Harmony Search (HS) is a population-based stochastic search algorithm that inspired by the musical process of searching for a perfect state of harmony (Geem, Kim & Loganathan, 2001). The larger the lift ratio, the more significant the association. This figure shows what steps must be done for implementation of the proposed method. Otherwise, the next rule is identical to previous rule Numerous previous studies have shown that this type of classifier achieves a higher classification accuracy than traditional classification algorithms. 0000007621 00000 n The harmony in music is analogous to the optimization solution vector, and the musicians improvisations are similar to local and global search methods in optimization techniques When a musician is improvising, he has three choices: (1) to execute any pitch from memory; (2) to execute a pitch next to any other in his memory; (3) to execute a random pitch from the range of all possible pitches. Nahar J, Imam T, Tickle KS, Chen Y-PP. At the initial step, we did some preprocessing on each dataset. We combined the Apriori, CBA and Harmony Search algorithms in order to build a rule-based classifier that has a high prediction accuracy. endstream endobj 484 0 obj<>stream bayesian Support and confidence are two measures of rule interestingness that mirror the usefulness and certainty of a rule respectively (Agrawal et al., 1996). Yin X, Han J. CPAR: classification based on predictive association rules. Although rule-based classification algorithms have high classification accuracy, but some of them suffer from a critical limitation. 331335. Hl*yoHxh+#lX>Zr]| }l`O|m>ym^X9/S6nwrYiYGkG ~Y-.Op ApMGgNlk*pM]_/xxy> 6375. It was first introduced by Agrawal and Srikant (Agrawal, Imieliski & Swami, 1993). Let us consider a rule R1, Rule-Based Classifier classify records by using a collection of ifthen rules. The CBA algorithm is not the best in none of the datasets and in all of the datasets our proposed method outperformed the CBA algorithm. Assume $n_n$ is Number of instances covered by rule, $n_c$ is Number of instances covered by rule, $k_k$ is Number of classes, and $p_p$ is Prior probability. 0000014019 00000 n Another challenge is that the resulted rules bias to prevalent classes and classification the rare instances is a major problem. We used Harmony Search, a music-inspired stochastic search algorithm, for selecting the best subset of rules as a classifier. Ma BLWHY, Liu B. Hence, Lift is a value thatgives us information about the increase in the probability of the consequentgiven antecedent part of a rule. First of all, we can apply feature selection before applying Apriori algorithm. Direct Method extract rules directly from data. This approach leads to the generation of more rules. Feature selection can be done before or after of discretization. 82 0 obj <> endobj If none of the rules fired, it is assigned to the default class. Such a dataset can be converted into an appropriate format for association rule mining if both the class label and the predictors are of the categorical type. 0000000016 00000 n Scheffer T. Finding association rules that trade support optimally against confidence. 0000003591 00000 n Advances in Knowledge Discovery and Data Mining. Similar to the parametric repeated measures ANOVA, it is used to detect differences between groups when the dependent variable being measured is ordinal. 0000004187 00000 n The following information was supplied regarding data availability: This work uses standard benchmark datasets that can be downloaded from the following addresses: https://sci2s.ugr.es/keel/datasets.php; https://archive.ics.uci.edu/ml/index.php. 0000002701 00000 n clustering mining 1993. pp. 0000007267 00000 n 0000012066 00000 n To increase reliability, the experiments for each dataset have been repeated 10 times and the average of results were reported. The result of the proposed method is shown in Table 3. 0000009914 00000 n 0000004543 00000 n 369376. 0000001749 00000 n (TaxableIncome < 50K) (Refund = Yes) Evade = No. 0000002658 00000 n Fast discovery of association rules. The authors received no funding for this work. Geem ZW, Kim JH, Loganathan GV. 194199. The Data mining, 2001 ICDM 2001, proceedings IEEE international conference on; Piscataway. FOIA 0000002147 00000 n 0000004091 00000 n 123 0 obj<>stream An official website of the United States government. In the next section, we describe the proposed method. The first change is that we use multiple Minsup than can be useful for imbalanced datasets. 2000. pp.

The main novelty of our study is in the next step. Take Ripper method as example. In binary HS, the size of each solution equals the number of candidates rules. 8600 Rockville Pike Growing decision trees on support-less association rules. <<0C51DAAA53F6BC4896C47AFB30077277>]>> CBA implements the famous Apriori algorithm (Agrawal, Imieliski & Swami, 1993) in order to discover frequent items.

For every solution (subset of selected rules) we applied a modified version of the CBA algorithm on training and validation data and assigned the resulted value to the cost function. Repeat with next smallest class as positive class. Diagnostic analysis of patients with essential hypertension using association rule mining. We select the top K (a predefined parameter) rules from each class that covers the test sample conditions and determined the class label according to the sum of the confidence of selected rules. Why do we remove negative instances? 0000013831 00000 n Chen W-C, Hsu C-C, Hsu J-N. We believe that population-based evolutionary algorithms fit well to the rule selection problem. The algorithm then stops and returns the classifier in the form of an IF-THEN-ELSE rule list. 2013. pp. Thabtah FA, Cowling P, Peng Y. MMAC: a new multi-class, multi-label associative classification approach. endstream endobj 470 0 obj<> endobj 471 0 obj<> endobj 472 0 obj<>/ColorSpace<>/Font<>/ProcSet[/PDF/Text/ImageC/ImageI]/ExtGState<>>> endobj 473 0 obj<> endobj 474 0 obj<> endobj 475 0 obj<> endobj 476 0 obj[/ICCBased 494 0 R] endobj 477 0 obj[/Indexed 476 0 R 255 495 0 R] endobj 478 0 obj[/Indexed 476 0 R 255 496 0 R] endobj 479 0 obj[/Indexed 476 0 R 255 497 0 R] endobj 480 0 obj<> endobj 481 0 obj<> endobj 482 0 obj<> endobj 483 0 obj<>stream Geem ZW, Tseng C-L, Park Y. We compared our proposed method with the CPAR, CBA and C4.5 algorithms that are famous in rule-based classification (Ma & Liu, 1998; Quinlan, 1993; Yin & Han, 2003) The characteristic of the used datasets are shown in Table 2. r@ A!Bip@Z~3|?[2$3eU;!$fbLc%ghUW0^& 0000009703 00000 n Determine Traininput, Trainoutput, Testinput, Testoutput, Valinput and Valoutput, Rulesj= apply Apriori algorithm(traininput, Minsupj,Minconj,class j ), Selected_rules=Apply harmony search algorithm (Finalrules, Traininput, Trtainoutput, Valinput, Valoutput), Testoutput= apply selected_rules on Testinput. IF condition THEN conclusion 0000018666 00000 n -Easy to interpret, Determine the rule consequent by taking majority class of instances covered by the rule, Compare error rate on validation set before and after pruning. 0000001136 00000 n Rule-based classifier makes use of a set of IF-THEN rules for classification. The reported accuracy of other studies may be different in some algorithms from our ones. 469 32 0000020055 00000 n 0000018201 00000 n Pattern recognition, informatics and mobile engineering (PRIME), 2013 international conference on; Piscataway. One of the important section in any meta-heuristic algorithm is the calculation of cost function. Each solution consists of a binary vector of rule incidences, indicating exclusion (0) or inclusion (1) of the rule in the combination. Cano A, Zafra A, Ventura S. An interpretable classification rule mining algorithm. 55.zmXjzv31 ?jLX8quO0UCpjUKzZ2fQQ^PoL)qE)Le^_6T`K=-APA _X5A4{q[[5K?> ZRjB|nzrh Since we need to discover the relationship between input attributes and class label, we need to find all the rules of the form A B that antecedent part of the rule includes of some item and the consequent part can just be the class items. ;#*3fRy3 Before Scheffer T. Finding association rules that trade support optimally against confidence. We applied a discretization algorithm based on a class-attribute contingency coefficient that was proposed by Tsai, Lee & Yang, (2008). Nahar et al. Association rule mining finds interesting relationships among large sets of data items. 0000011614 00000 n 0000017998 00000 n (Condition) Class Label 0000003818 00000 n Selecting a small set of relevant association rules to construct a classifier. In K-fold cross-validation, this approach must be repeated for K times, until all the samples in the dataset are used for the test data. MohdAlia O. Sarno R, Dewandono RD, Ahmad T, Naufal MF, Sinaga F. Hybrid association rule learning and process mining for fraud detection. Brazdil PB, Soares C. A comparison of ranking methods for classification algorithm selection. Simplified rules may no longer be exhaustive either since a record may not trigger any rules. 0000003250 00000 n Yin & Han (2003) propose the CPAR (Classification based on Predictive Association Rules) rule-based classification algorithm CPAR doesnt generate a large number of candidate rules as in conventional associative classification. Rule-based classifiers can play a very important role in applications such as fraud detection, medical diagnosis, etc. We can express a rule in the following from This algorithm will describe with details in the next section. The result of these approaches is that the final selected rules may not be the global best rules. 2001. pp. These rules can be simplified. The algorithm first selects the best rule (rule having the highest confidence), then eliminates all the covered examples. Classifier has exhaustive coverage if it accounts for every possible combination of attribute values. It pursues a greedy algorithm to produce rules directly from training data and uses the best K rules in prediction time. This research has focused on the application of computational intelligence in association rule mining-based classifiers. DNggM)JE+}Y^Dx. 0000004467 00000 n A traditional method is discretization that can be static or based on the distribution of data. As small rules are favorable, we can limit the size of items that appear in a rule and consequently decrease the running time of Apriori algorithm. 452455. Using greedy approaches, the resulted rules bias to prevalent classes and classification the rare instances is a major problem. 0000001958 00000 n For this aim, we apply a modified version of the CBA algorithm on the selected rules and calculate the error rate of applying the resulted rules on the training and validation data. Cross-validation is a standard evaluation measure for calculating error rate on data in machine learning. Lift is the ratio of Confidence to Expected Confidence. Association rules show attribute value conditions that occur frequently together in a given data set. 0 HS has been successfully applied to various discrete optimization problems such as Maximum Clique Problem (Afkhami, Ma & Soleimani, 2013), traveling salesperson problem (Geem, Kim & Loganathan, 2001), tour routing (Geem, Tseng & Park, 2005), water network design (Geem, 2006), dynamic relocation of mobile base stations in wireless sensor networks (Mohd Alia, 2017), and others. 0000020502 00000 n 0000010922 00000 n The steps in the procedure of HS are as follows: Step 1. 0000007937 00000 n 0000009971 00000 n We applied a modified version of the Apriori algorithm with multiple minimum support for extracting useful rules for each class in the dataset. Received 2018 Dec 17; Accepted 2019 Mar 30. The HMCR is defined as the probability of selecting a component from the present HM members. Update the HM. Li W, Han J, Pei J. CMAR: accurate and efficient classification based on multiple class-association rules. HHS Vulnerability Disclosure, Help 0000004377 00000 n We selected datasets with a verity of size in samples, attributes and number of classes. To select appropriate rules from the set of all possible rules, constraints on various measures of interestingness can be used. %PDF-1.4 % considered three rule generation algorithmsApriori, Predictive Apriori and Tertius- for extraction the meaningful factors for particular types of cancer (Nahar et al., 2011) and heart disease (Nahar et al., 2013). The proposed method of rule selection based on HS are depicted in Fig. Time complexity of the Apriori algorithm and association rule mining is a critical challenge that must be considered (Cano, Luna & Ventura, 2013; Cano, Zafra & Ventura, 2014; Luna et al., 2016; Thabtah, Cowling & Hammoud, 2006). 0000013324 00000 n startxref 500 0 obj<>stream There are a number of famous association rule mining algorithms that are accessible to researchers (Agrawal, Imieliski & Swami, 1993; Burdick, Calimlim & Gehrke, 2001; Scheffer, 2001a). 0000004685 00000 n After discretization, we convert each dataset to the appropriate format such that the value of each feature can be True (1) or False (0). We applied the proposed method on a seventeen benchmark dataset and compared its result with traditional association rule classification algorithms. General-to-Specific Strategy (Ripper Algorithm). will also be available for a limited time. 443452. From association to classification: inference using weight of evidence. Adjusting and generalizing CBA algorithm to handling class imbalance. 0000000016 00000 n A lift ratio larger than 1.0 implies that the relationship between the antecedent and the consequent is more significant than would be expected and make those rules potentially useful for predicting the consequent in unseen instances. discovering all the association rules inherent in a database. The new PMC design is here! Jovanoski V, Lavra N. Classification rule learning with APRIORI-C. Portuguese conference on artificial intelligence; 2001. pp. The standard Harmony Search (HS) is not suitable for binary representations. u-[ "|p3 0000002421 00000 n 0000020681 00000 n However, identifying the most effective rule at classifying a new case is a big challenge. It must be noted that classification algorithms are ranked on each of the datasets and then the Friedman test is applied. An advantage of associative classifiers is that they are rule-based and thus lend themselves to be more easily understood by humans. Classifier contains mutually exclusive rules if the rules are independent of each other. (a&0!b9 1c0}-y>{~{W 6 5 A@v@K Plq1TaEixJYfX,q+V[.,b_JU h*2 _I4t>nNUoW1ti"mY(Yj}u/&M: Jb9~tcw>e5-o"l=1X6,6^^E[Az:t e9pt.|_1_N,SjLr"? 0000015328 00000 n The second thing that we can do is related to the size of the rules. Add conjuncts that maximizes FOILs information gain measure: Gain(R0,R1)=t(logp1p1+n1logp0p0+n0)Gain(R0,R1)=t(logp1p1+n1logp0p0+n0), R1R1: {A} class (rule after adding conjunct), tt: number of positive instances covered by both R0R0 and R1R1, p0p0: number of positive instances covered by R0R0, n0n0: number of negative instances covered by R0R0, p1p1: number of positive instances covered by R1R1, n1n1: number of negative instances covered by R1R1, Specific-to-General Strategy (CN2 Algorithm), Why do we need to eliminate instances? This is due to the pitch adjusting operator not being able to perform the local search in the binary space. HtM-'w5~R6,#,(bCu_g..,t`9ma7Aolz8nOVL{c/4{\oF?9;Z):~Gp|Ls;C'=XJl/'"W7:QBe.#76s;j.?tGp l#YJ\i9De PMC legacy view Using different discretization approaches can result in different outputs. Consider a training set that contains 60 positive examples and 100 negative examples. Once the discovery of frequent items finished, CBA proceeds by converting any frequent item that passes the Minconf into a rule in the classifier. International conference on natural computation; 2005. pp. This subset of rules is called class association rules (CARs). 0000018468 00000 n However, they still suffer from a fundamental limitation. Accuracy of r2=2/2=100%. Solution to make the rule set mutually exclusive: Solution to make the rule set exhaustive: An ordered rule set is known as a decision list. The initial HM consists of a given number of randomly generated solutions to the optimization problems under consideration. One challenge with this approach is that selecting the best rules may be not the best subset of rules. As its time complexity is exponential, we can do some preprocessing activity to decrease the running time. 4451. We used Apriori algorithm with multiple Minsup for rule generation. Association Rule Mining (ARM) is another popular and substantial technique in machine learning and data mining that introduced by Agrawal, Imieliski & Swami (1993), and since that remained one of the most active research areas in machine learning and knowledge discovery. Example 1: We used the Apriori algorithm for rule generation and Harmony Search for selecting the best subset of rules that can build a classifier. Proceedings of the sixth ACM SIGKDD international conference on knowledge discovery and data mining; New York. Rules are rank ordered according to their priority.

As previously was mentioned, the Apriori algorithm produces many rules and CBA algorithm uses a greedy algorithm for selecting a subset of produced rules for building a classifier. Friedman M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Harmony search for generalized orienteering problem: best touring in China. We merged the Apriori algorithm, Harmony Search, and classification-based association rules (CBA) algorithm in order to build a rule-based classifier. Ilayaraja M, Meyyappan T. Mining medical data to identify frequent diseases using Apriori algorithm. Harmony Search (HS) is a relatively simple yet very efficient evolutionary algorithm. The second change is that in the original CBA algorithm once each sample is covered by a rule, it is removed from the samples; we defined a parameter called Delta. At each run, we split each dataset to five parts, three part for training, one part for validation and one part for testing.

In the first stage, the learning target is to discover the association patterns inherent in a database (also referred to as knowledge discovery). As previously stated, a classification system is built in two phase. Using measures such as precision and recall better reflects the benefits of the proposed method.