apriori.cs

一个经典的apriori算法（c#实现）

				{			
					//find the frequent itemsets for this candidate itemset
					//ItemsetCandidate frequentItemset = this.GenerateFrequentItemsets(candidateItemset, minimum_support);	

					this.AprioriGenerator(candidateItemset, TransactionsData, minimum_support);
				}
			

			
				string done = "Finished Generating Candidate Itemsets ";
			
				e = new ProgressMonitorEventArgs(1,100,70,"Apriori.AprioriGenerator()",done );

				this.OnProgressMonitorEvent(e);
			
			}
		

			/// <summary>
			/// Generates frequent itemsets. 
			/// </summary>
			/// <param name="candidateItemset">
			/// The candidate itemset to generate frequent itemsets from.
			/// </param>
			/// <param name="minimum_support">
			/// The minimum support count needed for frequent itemsets.
			/// </param>
			/// <returns>
			/// Returns a frequent itemset.
			/// </returns>
			protected ItemsetCandidate GenerateFrequentItemsets(ItemsetCandidate candidateItemset, int minimum_support)
			{

				ItemsetCandidate itemsetFrequent = new ItemsetCandidate();

			
				foreach(ItemsetArrayList itemsFrequent in candidateItemset.Items)
				{
					if (itemsFrequent.SupportCount >= minimum_support)
					{

						itemsetFrequent.Items.Add(itemsFrequent);
					}
				}

				itemsetFrequent.Items.Capacity = itemsetFrequent.Items.Count;

				return itemsetFrequent;	
		
			}
		
		
			/// <summary>
			/// Checks if an item has a frequent subset.
			/// </summary>
			[ReservedAttribute(true,"December 25, 2002")]
			protected bool HasInfrequentSubSet()
			{
				throw new Exception("This is a reserved attribute! Do not use it");
			}	

		
			/// <summary>
			/// Collection of Frequent Itemsets.
			/// </summary>
			[ObsoleteAttribute("Retrieve the collection from the database",false)]
			[ReservedAttribute(true,"December 25, 2002")]
			public ItemsetArrayList ItemsetsFrequentCollection
			{
				get
				{
					return itemsetsFrequentCollection;
				}

				set
				{
					itemsetsFrequentCollection.Add(value);
				}
			}
			
		
			/// <summary>
			/// Collection of Candidate Itemsets.
			/// </summary>
			[ObsoleteAttribute("Retrieve the collection from the database",false)]
			[ReservedAttribute(true,"December 25, 2002")]
			public ItemsetArrayList ItemsetsCandidateCollection
			{
				get
				{
					return itemsetsCandidateCollection;
				}

				set
				{
					itemsetsCandidateCollection.Add(value);
				}
			}
		

			/// <summary>
			/// Creates an Itemset by joining a candidate itemset to itself.
			/// </summary>
			/// <param name="candidate_itemset">
			///  A candidate itemset to join.
			/// </param>
			/// <param name="minimumSupport">
			/// The minimum number transactions that must contain a set of items in the database.
			/// </param>
			/// <param name="transactionsData">
			/// The database of transactions data to be analyzed.
			/// </param>
			/// <returns>
			/// A candidate itemset object.
			/// </returns>
			public ItemsetCandidate JoinCandidateItemsets(ItemsetCandidate candidate_itemset, Database transactionsData, int																minimumSupport)
			{
			
				//Exit this function if the number of items is zero
				if (candidate_itemset.Items.Count == 0)
				{
					throw new Exception("cannot join items : no items are present!");
				}

				else
				{
					ItemsetArrayList copy_candidate_itemset = candidate_itemset.Items;

					ItemsetCandidate new_candidate_itemset = new ItemsetCandidate();

			
					new_candidate_itemset.Level = candidate_itemset.Level + 1;

				
					//members of an itemset of k items are joinable if their first (k-2) members are joinable
					int count_common_items = (new_candidate_itemset.Level - 2);
			

					foreach (ItemsetArrayList itemset in candidate_itemset.Items)
					{				
						int count_members = 0;
				
						foreach(ItemsetArrayList copy_itemset in copy_candidate_itemset)
						{
							bool join_items = true;

							for(count_members = 0; count_members < count_common_items; count_members++)
							{
								if(itemset[count_members] != copy_itemset[count_members])
								{
									join_items = false;

									break;
								}
							}

						
							//OLD VALUE :
							//if (itemset[count_common_items].ToString().CompareTo(copy_itemset[count_common_items])!= -1) 
							//January 4, 2002, 4:15 pm
							if (itemset[count_common_items].ToString().CompareTo(copy_itemset[count_common_items].ToString())!= -1) 
							{
								join_items = false;
							}
					

							if (join_items == true)
							{
								ItemsetArrayList new_itemset = new ItemsetArrayList(1);
			
								for(count_members = 0; count_members <= count_common_items; count_members++)
								{							
									if(itemset[count_members] == copy_itemset[count_members])
									{
										new_itemset.Add(itemset[count_members]);
									}
									else
									{
										new_itemset.Add(itemset[count_members]);

										new_itemset.Add(copy_itemset[count_members]);
									}

								}

								new_itemset.Capacity = new_itemset.Count;

							
								//get the support count for each item set
								new_itemset.SupportCount = this.SupportCount(new_itemset,transactionsData);

								new_itemset.Level = new_candidate_itemset.Level;

								itemset.Capacity = itemset.Count;
				

								//Add the itemset to the itemset table
								transactionsData.AddItemset(new_itemset,",");

								//Do not add itemsets that do not have a minimum support count
								if(new_itemset.SupportCount >= minimumSupport)
								{
									new_candidate_itemset.Items.Add(new_itemset);
								}

							}
						}
					}

					new_candidate_itemset.Items.Capacity = new_candidate_itemset.Items.Count;
			
					return new_candidate_itemset;

				}

			}
		
		
			/// <summary>
			/// Creates market based analysis association rules between a pair of items.
			/// </summary>
			/// <param name="parentRuleset">
			/// The parent set of frequent items.
			/// </param>
			/// <param name="leftRuleset">
			/// The set of items on the left side of a market based analysis association rule.
			/// </param>
			/// <param name="rightRuleset">
			/// The set of items on the right side of a market based analysis association rule
			/// </param>
			/// <param name="transactionsData">
			/// The database data access component containing transactions to be analyzed.
			/// </param>
			public void CreateItemsetRuleset(ItemsetArrayList parentRuleset, ItemsetArrayList leftRuleset, ItemsetArrayList												rightRuleset, Database transactionsData)
			{						
				//Create and add an association rule to the database
				transactionsData.AddRuleset(parentRuleset, leftRuleset, rightRuleset);			
			}
		
		
			/// <summary>
			/// Recursively creates all the subsets belonging to an itemset and saves them to the database.
			/// </summary>
			/// <param name="Level">
			/// The minimum number of elements for an itemset. 
			/// </param>
			/// <param name="itemSubset">
			/// An ItemsetArrayList collection of items.
			/// </param>
			/// <param name="parentItemset">
			/// The parent itemset used to generate subsets and create market based analysis association rules.
			/// </param>
			/// <param name="transactionsData">
			/// The database of transactions data.
			/// </param>
			public void CreateItemsetSubsets(int Level, ItemsetArrayList itemSubset, ItemsetArrayList parentItemset,													Database transactionsData)
			{			
				int length = 0;

				ItemsetArrayList childSubset = new ItemsetArrayList(1);	
		
				ItemsetArrayList rulesItemset;

			
				if(itemSubset.Count > Level)
				{
					foreach(ItemsetArrayList item in itemSubset)
					{
						ItemsetArrayList [] subsets = this.CreateItemsetSubsets(item);

					
						//Only one parentItemset will be used to generate association rules 
						if(parentItemset == null)
						{
							parentItemset = item;						
						}


						if (subsets != null)
						{
							length = subsets.Length;
						}

						else
						{
							break;
						}

						for(int count = 0; count < length; count++)
						{
							//Add the itemset and the subset to the subsets table
							transactionsData.AddSubset(item,subsets[count]);

							childSubset.Add(subsets[count]);

							//Only add unique values to the ItemsetArrayList class
 
							//Create an itemset containing support, confidence and association rules by
							//generating the rule [childSubset is associated with [parentItemset - childSubset]
							rulesItemset = (parentItemset-subsets[count]);

							this.CreateItemsetRuleset(parentItemset, subsets[count], rulesItemset,transactionsData);
						
						}
					}
				
					//Recursively generate subsets for the itemset
					childSubset.TrimToSize();

					this.CreateItemsetSubsets(0, childSubset, parentItemset, transactionsData);
				}
			
			}


			/// <summary>
			/// Creates the subsets of an itemset.
			/// </summary>
			/// <param name="itemSubset">
			/// The ItemsetArrayList containing the items to generate subsets for.
			/// </param>
			/// <returns>
			/// Returns an array of ItemsetArrayList object.
			/// </returns>
			public ItemsetArrayList [] CreateItemsetSubsets(ItemsetArrayList itemSubset)
			{
				int length = itemSubset.Count;

			
				ItemsetArrayList [] subset = new ItemsetArrayList[length];

			
				//There are zero subsets for an itemset with one element
				switch (length)
				{

					case 0:
					{
						subset = null;

						break;
					}

					case 1:
					{
						subset = null;

						break;
					}

					default:
					{
						//Add the first length - 1 elements
					
						subset[0] = new ItemsetArrayList(1);

						for(int count = 0; count < (length - 1); count++)
						{
							subset[0].Add(itemSubset[count]);
						}

						subset[0].TrimToSize();
					
						//Add the last length - 1 elements
						subset[1] = new ItemsetArrayList(1);

						for(int count = 1; count < (length); count++)
						{
							subset[1].Add(itemSubset[count]); 
						}

						subset[1].TrimToSize();

						//Add the last length - 1 elements
						for(int count = 1; count < (length-1); count++)
						{
							int position = 0;

							subset[(count + 1)] = new ItemsetArrayList(1);

							subset[(count + 1)].Add(itemSubset[position]);


							for(position = 1; position < length; position++)
							{
								if(position != count)
								{
									subset[(count + 1)].Add(itemSubset[position]); 
								}
							}

							subset[(count + 1)].TrimToSize();						
						}

						break;
					}

				}
					
				return subset;

			}
		
		}

	}

}