matlab implement apriori algorithm source code I. Experiment purpose Through the experiment, deepen the understanding of an important method in data mining - association analysis, its classic algorithm for apriori algorithm, understand the factors affecting the performance of the apriori algorithm, and master the based on apriori algorithm Theory of correlation analysis based on the apriori algorithm principles and methods. Experimental content: To do association analysis on a dataset with apriori algorithm, and realize it with matlab. A typical example of association rule mining is shopping basket analysis. A market analyst has to discover from a large amount of data the relationship between different items that a customer puts in his shopping basket. If a customer buys milk, how likely is it that he also buys bread? What product groups or collections are customers more likely to buy both in a single shopping trip? For example, 80% of customers who buy milk also buy bread at the same time, or 70% of customers who buy hammers also buy nails - these are association rules extracted from shopping basket data. The results of the analysis can help managers design different store layouts. One strategy is to place items that are often purchased together closer together in order to further stimulate the sale of these items together, e.g. if a customer buys a computer and tends to buy financial software at the same time, placing the hardware closer to the software display may help to increase sales of both. Another strategy: placing hardware and software at opposite ends of the store may induce customers who buy these items to pick up other items along the way. Association rules are rules that describe potential relationships that exist between data items in a database,of the form 1212 ..... .mnAAABBB, where (1,2... ,)iAim?,(1,2... ,)jAjn? are data items in the database. The association rules between the data items that according to the occurrence of some items in a transaction, can be deduced that some other items also appear in the same transaction. Apriori algorithm 1.Description of the algorithm The first step of the Apriori algorithm is to simply count the frequency of occurrence of all the items containing an element to determine the largest one-dimensional itemset. In the kth step, in two stages, first use a function sc_candidate(candidate), through the (k-1) step in the generation of the largest itemset Lk-1 to generate the marquee itemset Ck. then search the database to calculate the support of the marquee itemset Ck. In order to calculate the support of the items in Ck more quickly, the function count_support is used to calculate the support. The Apriori algorithm is described as follows: (1) C1={candidate1-itemsets}; (2) L1={c∈C1|c.count≥minsupport}; (3) for(k=2,Lk-1≠Φ,k++) //until the maximum itemset can no longer be generated (4) Ck=sc_candidate (Lk-1); //generate the marquee itemset containing k elements (5) for all transactions t∈D //processing (6) Ct=count_support(Ck,t); //include the marquee itemset in transaction t (7) for all candidates c∈Ct (8) c.count=c. count+1; (9) next (10) Lk={c∈Ck|c.count≥minsupport}; (11) next (12) resultset=resultset∪Lk where, D denotes the database; minsupport denotes the given minimum support; resultset denotes the set of all maximal item set. National Registered Architect, Builder Exam Preparation Materials Past Exam Questions Exam Tips Practice Tests Sc_candidate Function The function's parameter is Lk-1, i.e.: all the largest k-1 dimensional itemset, the result returns the marquee itemset Ck containing k items. In fact, Ck is a superset of the largest k-dimensional itemset, and the support of the items is calculated through the function count_support, and then Lk is generated. degree, and then generate Lk. The function is how to complete these functions, described in detail as follows: First, through the Lk-1 self-connecting operation to generate Ck, called join (join) step, the step can be expressed as follows: insert into Ck select P.item1, P.item2, ... ,P.itemk-1,Q.itemk-1 from Lk-1P,Lk-1Q where P.item1=Q.item1,... ,P.itemk-2=Q.itemk-2,P.itemk-1<Q.itemk-1 if expressed in terms of sets:Ck={X∪X'|X,X'∈Lk-1,|X∩X'|=k-2} Then, there is a prune step, i.e., for any c,c∈Ck, delete all those (k-1)-dimensional subsets of Ck that are not in Lk-1 to get the marquee itemset Ck. expressed as: for all itemset c∈Ck for all (k-1)-dimensional subsets s of c if(s does not belong to Lk-1) then delete c from Ck; expressed in terms of a set:Ck={X∈Ck|All k-1dimensional subsets of X in Lk-1} 2. Example Example to illustrate the process of Apriori algorithm operation, there is a database D, which has four transaction records, denoted as TID Items T1 I1,I3,I4 T2 I2,I3,I5 T3 I1,I2,I3,I5 T4 I2,I5 At each step of the Apriori algorithm the marquee set for that step is created. The support of each candidate item set is counted and compared with the predefined minimum support to determine the maximum item set for that step. The first one-dimensional itemset is C1, where the predefined minimum support is minsupport=2, and the itemsets in the marquee itemset that satisfy the minimum support requirement are combined to form the largest 1-itemsets. in order to generate the largest 2-itemsets, we use the join step in the sc_candidate function, i.e. L1joinL1, and delete those C2-itemsets in the prune step. prune step to remove those itemsets of C2 whose subsets are not in L1. The marquee itemset C2 is generated. 4 transactions in D are searched, and the support of each marquee itemset in C2 is counted. Then compare it with the minimum support and generate L2. The marquee itemset C3 is generated from L2. It is required that the first item in the two largest 2-itemsets that are self-joined is the same, and the two sets that satisfy this condition in L2 are {I2,I3},{I2,I5}. These two sets are joined to produce the set {I2, I3, I5}. In the prune step, test whether the subsets {I3,I5},{I2,I3},{I2,I5} of {I2,I3,I5} are in L2, and from L2, we know that {I3,I5},{I2,I3},{I2,I5} are themselves maximal 2-itemsets. i.e., the subsets of {I2,I3,I5} are all maximal itemsets. Then {I2,I3,I5} is the marquee 3-itemset.Then search all the transaction records in the database to generate the largest 3-tiemsets L3.At this point, no more marquee 4-itemset can be generated from L3 .Apriori algorithm ends. Illustration of the algorithm V. Experimental results The format and content of test.txt are as follows: Experimental results are as follows: VI. Experimental summary Apriori algorithm can be very effective to find out the existence of the association rules in the dataset and can find out the association rules of the largest item, but from the above algorithm execution process can be seen in the shortcomings of the Apriori algorithm: Firstly, in each step of the generation of marquee itemsets cycle generated too many combinations, did not eliminate the combination of the largest item, and the largest item is not generated by the largest item. Firstly, at each step of generating the marquee itemset, the loop generates too many combinations, and does not exclude the elements that should not be involved in the combinations; secondly, each time the support of the itemset is calculated, all the records in the database D are scanned and compared, and this scanning and comparison will greatly increase the I/O overhead of the computer system, if it is a large database. This cost increases geometrically as the number of records in the database increases. Therefore, people are looking for a faster algorithm that can reduce the 1 / O overhead of the system. VII.EXPERIMENTAL PROCEDURES function my_apriori(X,minsup) clc; %%%% main function, input X dataset, determine the association rule that produces greater than the minimum support of minsup %%%%%%%%%%%%%%%%%%%%%%%%%% open test.txt file file = textread(' test.txt','%s','delimiter','\n','whitespace',''); [m,n]=size(file); for i=1:m words=strread(file{i},'%s','delimiter',' '); words=words'. X{i}=words; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% minsup=0.3; % predefine support [m,N]=size(X); % find the dimension of X temp=X{1}; % store all distinct itemsets with staged variables for i=2:N temp=union( temp,X{i}); %find all distinct items (types) end %%%%%%%%%%%%%%%%%%%% find k-frequent items L=Sc_candidate(temp); %find 2-item candidate itemsets sum=1; %count the most frequent itemsets that satisfy the condition while(~isempty(L{1})) %loop termination condition for kth frequent itemset to be empty sum=sum+1; C=count_support(L,X,minsup); %pick out k-frequent items that satisfy minimum support %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% sprintf('%s%d%s','satisfied',sum,'time frequent term set in order') % show for i=1:size(C,1) % show disp(C{i,1}); % part end % split %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% L=gen_rule(C); % generate k-frequent terms in order (based on apriori algorithm rules) End %%%%%%%%%%%%%%%%%%%%%%%% each subroutine is as follows function y=cell_union(X,Y) %implement two cell meta-group merge function, from k-1 itemset to k itemset function [m,n]=size(X); if(~iscellstr(X)) %determine whether X is meta-group L{1}=X ; L{1,2}=Y; else L=X; L{1,n+1}=Y; end y=L; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function y=count_support(L,X,minsup) %find the candidate set that meets the support greater than sup,L is the candidate set and X is the total dataset X=X';% transpose %%%%%%%%%%%%%%%%% count frequent items [m,n]=size(L); [M,N]=size(X); count=zeros(m,1); for i=1:m for j=1:M if(ismember(L{i},X{j})) count(i)= count(i)+1; end end end %%%%%%%%%%% delete infrequent items in data table p=1; C=cell(1); for i=1:m if(count(i)>minsup*M) % Items less than support are infrequent and will be deleted, those greater than that will be kept C{p}=L{i}; p=p+1; end end end y=C'; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function y=gen_rule(C) %apriori algorithm rule to determine whether to generate k-candidate itemset if(~isempty(C{1})) %determine whether C is empty [M,N]=size(C); [m,n] =size(C{1}); temp1=C; L=cell(1); for i=1:M temp2{i}=temp1{i}{n}; temp1{i}{n}=[]; end p=1; for i=1:M for j=i+1:M if(isequal(temp1{i},temp1{j})) % Determine if the first k-1 candidate sets are equal L{p}=cell_union(C{i},temp2{j}); %If equal, add to the k-item set p=p+1; end end end end end y=L'; else y=cell(1);%otherwise y returns null end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function y=Sc_candidate(C) %generate 2-term candidate set function C=C'; %transpose [m,n]=size(C); bcount=zeros(m*(m-1)/2,1); L=cell(m*(m- 1)/2,1); p=1; for i=1:m-1 %Note for j=i+1:m L{p}=cell_union(C{i},C{j}); %Generate a 2-term candidate set p=p+1; end end y=L; function y=count_support(L,X,minsup) %Find a candidate set that matches a support level greater than support sup,L is the candidate set and X is the total data set

.