Data Mining using APriori Algorithm in XI – Part II

[Former Member]

In my previous blog of this DataMining blog series ( jeyakumar.muthu2/blog/2005/11/23/data-mining-using-apriori-algorithm-in-xi-150-part-i ), I had explained the theoretical implementation steps of APriori algorithm. In that, the first step is Candidate Generation process. Before going to this process, the input flat file should be converted into a XML file using File Content Conversion.

What is Candidate Generation process?

Well, this process can be defined in two sections. These sections can be differentiated by the structure of the input file. Because this process has two different input files. You can see this in my previous blog’s diagram.

In the first section, it will get the input XML file, which is generated by the File Content Conversion technique. This section will read this input file and generate the output file, which should have unique candidates only. Unique candidate means only one entry for each candidate, no duplication of the candidates is allowed. The output file is called as First Candidate Itemset.

Now we will see the file structures of this section.

Input File

Output File

Message Mapping

In this message mapping, you have to do two important things. First one is Context Change, which is pointed out in the previous diagram. Next one is the properties of the node function “sort”. This is mentioned below.

Normally, in this algorithm all the candidates should be processed in the lexicographical order only. So that, we are choosing the Comparison type as “Lexicographical” in the sort node’s properties.

Java Function

Now the business logic comes into the picture. This should return the unique candidates.

Code Area

Vector vectorItem = new Vector(10, 10);Vector vectorItemName = new Vector(10, 10);Vector vectorCounts = new Vector(10, 10);int intLastCount = 1;boolean flag = true;for (int intCounter1 = 0; intCounter1 < arrayItem.length; intCounter1++) vectorItem.add(arrayItem[intCounter1]);vectorItem.trimToSize();vectorItemName.add(0,"test");vectorCounts.add(0,new Integer(1));vectorItemName.trimToSize();  for (int intCounter1 = 0; intCounter1 < vectorItem.size();intCounter1++){ for (int intCounter2 = 0; intCounter2 < vectorItemName.size(); intCounter2++){  if ( vectorItem.elementAt(intCounter1).equals(vectorItemName.elementAt(intCounter2))) {   flag = false;  } } if(flag == true){  vectorItemName.add(intLastCount, vectorItem.elementAt(intCounter1));  intLastCount++; } else  flag = true;}  for (int intCounter1 = 1; intCounter1 < intLastCount; intCounter1++) result.addValue( (String) vectorItemName.get(intCounter1) );   

Next, create the interface mapping using the abstract interfaces to use in the Integration Process.

In the second section, it will get the input file from Candidate Pruning process. This part also will produce unique candidates. But the difference is it will produce the combinations from the given input candidates. In the DataMining world, they will call as N-th Candidate Itemset according to their level.

Now, we will see the file structures of this section.

Output File

Message Mapping

In this mapping also change the “sort” node properties as I mentioned before.

Java Function

Here is the business logic… this will produce the unique candidate combinations from the input N-th Candidate Itemset.

Code Area

String strResult= new String();Vector[] vectorItem = new Vector[arrayItem.length];Vector vectorResult = new Vector();boolean flag=true;  for(int intCounter1 =0; intCounter1 < arrayItem.length; intCounter1++){ StringTokenizer st = new StringTokenizer(arrayItem[intCounter1],","); vectorItem[intCounter1] = new Vector(20);    while (st.hasMoreTokens())   vectorItem[intCounter1].addElement(st.nextToken()); vectorItem[intCounter1].trimToSize();}  for(int intCounter2 =0; intCounter2 < vectorItem.length; intCounter2++){ for(int intCounter3 =intCounter2; intCounter3 < vectorItem.length-1; intCounter3++){  for(int intCounter4=0, intCounter5=0; intCounter4 < vectorItem[intCounter2].size() && intCounter5 < vectorItem[intCounter2+1].size();){   String str1 = (String) vectorItem[intCounter2].get(intCounter4);   String str2 = (String) vectorItem[intCounter3+1].get(intCounter5);   if(str1.equals(str2)){    intCounter5++;    intCounter4=0;    if(intCounter5 == vectorItem[intCounter2+1].size()){     intCounter5=0;     intCounter3++;    }        }   else{    intCounter4++;    if(intCounter4==vectorItem[intCounter2].size()){     strResult = (String) vectorItem[intCounter2].get(0);     for(int intCounter6 =1; intCounter6 < vectorItem[intCounter2].size(); intCounter6++)      strResult = strResult +","+ (String) vectorItem[intCounter2].get(intCounter6);     strResult = strResult +","+ str2;     vectorResult.add(strResult);     if(intCounter3 <= vectorItem[intCounter2].size()){      intCounter4--;      intCounter5++;     }                 }   }  } }}   for(int intCounter1 = 0; intCounter1 < vectorResult.size(); intCounter1++) for(int intCounter2 = intCounter1+1; intCounter2 < vectorResult.size(); intCounter2++)  if(vectorResult.get(intCounter1).equals(vectorResult.get(intCounter2))){   vectorResult.remove(intCounter2);  }for(int intCounter1 = 0; intCounter1 < vectorResult.size(); intCounter1++) result.addValue( (String) vectorResult.get(intCounter1));

Then, create the interface mapping using the abstract interfaces to use in the Integration Process.

Now, we will see the Integration Process.

Integration Process

As explained earlier, this Candidate Generation process has to be carried out in two different ways depending on the input file structure.

So the Integration Process has got two seperate branches to process the input file. A Fork step is used for this purpose. Both the branches of the fork step have got a receive step corresponding to a particular structure of input file ( input interface ).So depending on the input file that arrives, the corresponding receive step ( i.e. the entire Branch ) is activated and subsequent transformation is performed. At any point of time, only one Branch of the fork is activated and the other never gets triggered. So, a container operation is performed after the transformation step and this operation is used to terminate the fork step.

Input file for the First section

Output file for the First section

Input file for the Second section

Output file for the Second section

In my next blog of this DataMinig blog series, we will see the practical implementation of the Support Calculation process and the Candidate Pruning process.