apriori演算法思想

⑴ Apriori演算法是什麼適用於什麼情境

經典的關聯規則挖掘演算法包括Apriori演算法和FP-growth演算法。apriori演算法多次掃描交易資料庫，每次利用候選頻繁集產生頻繁集；而FP-growth則利用樹形結構，無需產生候選頻繁集而是直接得到頻繁集，大大減少掃描交易資料庫的次數，從而提高了演算法的效率。但是apriori的演算法擴展性較好，可以用於並行計算等領域。

Apriori algorithm是關聯規則里一項基本演算法。是由Rakesh Agrawal和Ramakrishnan Srikant兩位博士在1994年提出的關聯規則挖掘演算法。關聯規則的目的就是在一個數據集中找出項與項之間的關系，也被稱為購物藍分析 (Market Basket analysis)，因為「購物藍分析」很貼切的表達了適用該演算法情景中的一個子集。

⑵ Apriori演算法的核心是

• 連接和剪枝。

• 簡言之就是對一個已知的交易資料庫D，有一個最小支持閾值min_support，即為該演算法的輸入；演算法的輸出為滿足最小支持閾值的頻繁項集L。

• 具體為：掃描D，對每個交易商品（T1，...，Tk---1項候選項集）計數，找出滿足計數大於min_support的項集，即為1項頻繁集L1；

• 關鍵的來了：如何由1項頻繁集L1產生2項候選項集C2，此步稱為連接。

• 如何由C2得到L2，此步即為剪枝。從C2中找出計數大於min_support的項集，即為L2。

• 重復以上過程，增大頻繁項集的長度，直至沒有更長的頻繁項集。
  

⑶ apriori演算法使用了什麼性質

Apriori性質：一個頻繁項集的任一子集也應該是頻繁項集。證明根據定義，若一個項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即P（I）<min_sup。若增加一個項A到項集I中，則結果新項集（I∪A）也不是頻繁的，在整個事務資料庫中所出現的次數也不可能多於原項集I出現的次數，因此P（I∪A）<min_sup，即（I∪A）也不是頻繁的。這樣就可以根據逆反公理很容易地確定Apriori性質成立。
http://ke..com/link?url=8F29ZS1ufQ4gtAsaXsyZr__Eut632ia

⑷ 如何實現apriori演算法

java">importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.Iterator;
importjava.util.Map;
importjava.util.Set;
importjava.util.TreeMap;
/**
*<B>關聯規則挖掘：Apriori演算法</B>
*
*<P>按照Apriori演算法的基本思想來實現
*
*@authorking
*@since2013/06/27
*
*/
publicclassApriori{
	privateMap<Integer,Set<String>>txDatabase;//事務資料庫
	privateFloatminSup;//最小支持度
	privateFloatminConf;//最小置信度
	privateIntegertxDatabaseCount;//事務資料庫中的事務數
	
	privateMap<Integer,Set<Set<String>>>freqItemSet;//頻繁項集集合
	privateMap<Set<String>,Set<Set<String>>>assiciationRules;//頻繁關聯規則集合
	
	publicApriori(
	Map<Integer,Set<String>>txDatabase,
	FloatminSup,
	FloatminConf){
	this.txDatabase=txDatabase;
	this.minSup=minSup;
	this.minConf=minConf;
	this.txDatabaseCount=this.txDatabase.size();
	freqItemSet=newTreeMap<Integer,Set<Set<String>>>();
	assiciationRules=newHashMap<Set<String>,Set<Set<String>>>();
	}
	
	/**
	*掃描事務資料庫，計算頻繁1-項集
	*@return
	*/
	publicMap<Set<String>,Float>getFreq1ItemSet(){
	Map<Set<String>,Float>freq1ItemSetMap=newHashMap<Set<String>,Float>();
	Map<Set<String>,Integer>candFreq1ItemSet=this.getCandFreq1ItemSet();
	Iterator<Map.Entry<Set<String>,Integer>>it=candFreq1ItemSet.entrySet().iterator();
	while(it.hasNext()){
	Map.Entry<Set<String>,Integer>entry=it.next();
	//計算支持度
	Floatsupported=newFloat(entry.getValue().toString())/newFloat(txDatabaseCount);
	if(supported>=minSup){
	freq1ItemSetMap.put(entry.getKey(),supported);
	}
	}
	returnfreq1ItemSetMap;
	}
	
	/**
	*計算候選頻繁1-項集
	*@return
	*/
	publicMap<Set<String>,Integer>getCandFreq1ItemSet(){
	Map<Set<String>,Integer>candFreq1ItemSetMap=newHashMap<Set<String>,Integer>();
	Iterator<Map.Entry<Integer,Set<String>>>it=txDatabase.entrySet().iterator();
	//統計支持數，生成候選頻繁1-項集
	while(it.hasNext()){
	Map.Entry<Integer,Set<String>>entry=it.next();
	Set<String>itemSet=entry.getValue();
	for(Stringitem:itemSet){
	Set<String>key=newHashSet<String>();
	key.add(item.trim());
	if(!candFreq1ItemSetMap.containsKey(key)){
	Integervalue=1;
	candFreq1ItemSetMap.put(key,value);
	}
	else{
	Integervalue=1+candFreq1ItemSetMap.get(key);
	candFreq1ItemSetMap.put(key,value);
	}
	}
	}
	returncandFreq1ItemSetMap;
	}
	
	/**
	*根據頻繁(k-1)-項集計算候選頻繁k-項集
	*
	*@paramm其中m=k-1
	*@paramfreqMItemSet頻繁(k-1)-項集
	*@return
	*/
	publicSet<Set<String>>aprioriGen(intm,Set<Set<String>>freqMItemSet){
	Set<Set<String>>candFreqKItemSet=newHashSet<Set<String>>();
	Iterator<Set<String>>it=freqMItemSet.iterator();
	Set<String>originalItemSet=null;
	while(it.hasNext()){
	originalItemSet=it.next();
	Iterator<Set<String>>itr=this.getIterator(originalItemSet,freqMItemSet);
	while(itr.hasNext()){
	Set<String>identicalSet=newHashSet<String>();//兩個項集相同元素的集合(集合的交運算)
	identicalSet.addAll(originalItemSet);
	Set<String>set=itr.next();
	identicalSet.retainAll(set);//identicalSet中剩下的元素是identicalSet與set集合中公有的元素
	if(identicalSet.size()==m-1){//(k-1)-項集中k-2個相同
	Set<String>differentSet=newHashSet<String>();//兩個項集不同元素的集合(集合的差運算)
	differentSet.addAll(originalItemSet);
	differentSet.removeAll(set);//因為有k-2個相同，則differentSet中一定剩下一個元素，即differentSet大小為1
	differentSet.addAll(set);//構造候選k-項集的一個元素(set大小為k-1,differentSet大小為k)
	if(!this.has_infrequent_subset(differentSet,freqMItemSet))
	candFreqKItemSet.add(differentSet);//加入候選k-項集集合
	}
	}
	}
	returncandFreqKItemSet;
	}
	
	/**
	*使用先驗知識，剪枝。若候選k項集中存在k-1項子集不是頻繁k-1項集，則刪除該候選k項集
	*@paramcandKItemSet
	*@paramfreqMItemSet
	*@return
	*/
	privatebooleanhas_infrequent_subset(Set<String>candKItemSet,Set<Set<String>>freqMItemSet){
		Set<String>tempSet=newHashSet<String>();
		tempSet.addAll(candKItemSet);
		Iterator<String>itItem=candKItemSet.iterator();
		while(itItem.hasNext()){
			Stringitem=itItem.next();
			tempSet.remove(item);//該候選去掉一項後變為k-1項集
			if(!freqMItemSet.contains(tempSet))//判斷k-1項集是否是頻繁項集
				returntrue;
			tempSet.add(item);//恢復
		}
		returnfalse;
	}
	
	/**
	*根據一個頻繁k-項集的元素(集合)，獲取到頻繁k-項集的從該元素開始的迭代器實例
	*@paramitemSet
	*@paramfreqKItemSet頻繁k-項集
	*@return
	*/
	privateIterator<Set<String>>getIterator(Set<String>itemSet,Set<Set<String>>freqKItemSet){
	Iterator<Set<String>>it=freqKItemSet.iterator();
	while(it.hasNext()){
	if(itemSet.equals(it.next())){
	break;
	}
	}
	returnit;
	}
	
	/**
	*根據頻繁(k-1)-項集，調用aprioriGen方法，計算頻繁k-項集
	*
	*@paramk
	*@paramfreqMItemSet頻繁(k-1)-項集
	*@return
	*/
	publicMap<Set<String>,Float>getFreqKItemSet(intk,Set<Set<String>>freqMItemSet){
	Map<Set<String>,Integer>candFreqKItemSetMap=newHashMap<Set<String>,Integer>();
	//調用aprioriGen方法，得到候選頻繁k-項集
	Set<Set<String>>candFreqKItemSet=this.aprioriGen(k-1,freqMItemSet);
	
	//掃描事務資料庫
	Iterator<Map.Entry<Integer,Set<String>>>it=txDatabase.entrySet().iterator();
	//統計支持數
	while(it.hasNext()){
	Map.Entry<Integer,Set<String>>entry=it.next();
	Iterator<Set<String>>kit=candFreqKItemSet.iterator();
	while(kit.hasNext()){
	Set<String>kSet=kit.next();
	Set<String>set=newHashSet<String>();
	set.addAll(kSet);
	set.removeAll(entry.getValue());//候選頻繁k-項集與事務資料庫中元素做差運算
	if(set.isEmpty()){//如果拷貝set為空，支持數加1
	if(candFreqKItemSetMap.get(kSet)==null){
	Integervalue=1;
	candFreqKItemSetMap.put(kSet,value);
	}
	else{
	Integervalue=1+candFreqKItemSetMap.get(kSet);
	candFreqKItemSetMap.put(kSet,value);
	}
	}
	}
	}
	

⑸ 數據挖掘十大經典演算法及各自優勢

數據挖掘十大經典演算法及各自優勢

不僅僅是選中的十大演算法，其實參加評選的18種演算法，實際上隨便拿出一種來都可以稱得上是經典演算法，它們在數據挖掘領域都產生了極為深遠的影響。
1. C4.5
C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法. C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；2) 在樹構造過程中進行剪枝；3) 能夠完成對連續屬性的離散化處理；4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。
2. The k-means algorithm 即K-Means演算法
k-means algorithm演算法是一個聚類演算法，把n的對象根據他們的屬性分為k個分割，k < n。它與處理混合正態分布的最大期望演算法很相似，因為他們都試圖找到數據中自然聚類的中心。它假設對象屬性來自於空間向量，並且目標是使各個群組內部的均 方誤差總和最小。
3. Support vector machines
支持向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一種監督式學習的方法，它廣泛的應用於統計分類以及回歸分析中。支持向量機將向量映射到一個更 高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假 定平行超平面間的距離或差距越大，分類器的總誤差越小。一個極好的指南是C.J.C Burges的《模式識別支持向量機指南》。van der Walt 和 Barnard 將支持向量機和其他分類器進行了比較。
4. The Apriori algorithm
Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這里，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。
5. 最大期望(EM)演算法
在統計計算中，最大期望（EM，Expectation–Maximization）演算法是在概率（probabilistic）模型中尋找參數最大似然 估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variabl）。最大期望經常用在機器學習和計算機視覺的數據集聚（Data Clustering）領域。
6. PageRank
PageRank是Google演算法的重要內容。2001年9月被授予美國專利，專利人是Google創始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指網頁，而是指佩奇，即這個等級方法是以佩奇來命名的。
PageRank根據網站的外部鏈接和內部鏈接的數量和質量倆衡量網站的價值。PageRank背後的概念是，每個到頁面的鏈接都是對該頁面的一次投票， 被鏈接的越多，就意味著被其他網站投票越多。這個就是所謂的「鏈接流行度」——衡量多少人願意將他們的網站和你的網站掛鉤。PageRank這個概念引自 學術中一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。
7. AdaBoost
Adaboost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器 (強分類器)。其演算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的准確率，來確定每個樣本的權 值。將修改過權值的新數據集送給下層分類器進行訓練，最後將每次訓練得到的分類器最後融合起來，作為最後的決策分類器。
8. kNN: k-nearest neighbor classification
K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
9. Naive Bayes
在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。 樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以 及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。 但是實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬 性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。10. CART: 分類與回歸樹
CART, Classification and Regression Trees。 在分類樹下面有兩個關鍵的思想。第一個是關於遞歸地劃分自變數空間的想法；第二個想法是用驗證數據進行剪枝。

以上是小編為大家分享的關於數據挖掘十大經典演算法及各自優勢的相關內容，更多信息可以關注環球青藤分享更多干貨

⑹ 試解釋Apriori演算法核心思想,演算法的不足,及演算法改進的途徑

自己去找論文下載看看，萬方都有的，你直接搜「Apriori演算法」即可，一大堆，自己看著挑吧

⑺ 利用Apriori演算法產生頻繁項集,(min sup=0.6),給出具體計算過程

Apriori演算法是一種發現頻繁項集的基本演算法。演算法使用頻繁項集性質的先驗知識。Apriori演算法使用一種稱為逐層搜索的迭代方法，其中K項集用於探索(k+1)項集。首先，通過掃描資料庫，累計每個項的計數，並收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記為L1.然後，使用L1找出頻繁2項集的集合L2，使用L2找到L3，如此下去，直到不能再找到頻繁k項集。Apriori演算法的主要步驟如下：(1)掃描事務資料庫中的每個事務，產生候選1．項集的集合Cl；(2)根據最小支持度min_sup，由候選l-項集的集合Cl產生頻繁1一項集的集合Ll；(3)對k=l；(4)由Lk執行連接和剪枝操作，產生候選(k+1)．項集的集合Ck+l-(5)根據最小支持度min_sup，由候選(k+1)一項集的集合Ck+l產生頻繁(k+1)-項集的集合Lk+1．(6)若L?≠①，則k．k+1，跳往步驟(4)；否則，跳往步驟(7)；(7)根據最小置信度min_conf,由頻繁項集產生強關聯規則，結束。

⑻ Arnoldi演算法的優缺點

1.優點：適合稀疏數據集。演算法原理簡單，易實現。適合事務資料庫的關聯規則挖掘。2.缺點：可能產生龐大的候選集。演算法需多次遍歷數據集，演算法效率低，耗時。
Apriori演算法是第一個關聯規則挖掘演算法，也是最經典的演算法。它利用逐層搜索的迭代方法找出資料庫中項集的關系，以形成規則，其過程由連接（類矩陣運算）與剪枝（去掉那些沒必要的中間結果）組成。該演算法中項集的概念即為項的集合。包含K個項的集合為k項集。項集出現的頻率是包含項集的事務數，稱為項集的頻率。如果某項集滿足最小支持度，則稱它為頻繁項集。

⑼ 關聯規則演算法(The Apriori algorithm)

        關聯規則的目的在於在一個數據集中找出項之間的關系，也稱之為購物籃分析 (market basket analysis)。例如，購買鞋的顧客，有10%的可能也會買襪子，60%的買麵包的顧客，也會買牛奶。這其中最有名的例子就是"尿布和啤酒"的故事了。

        本篇的Apriori演算法主要是基於頻繁集的關聯分析。其主要目的就是為了尋找強關聯規則。

        要理解頻繁集、強關聯規則，要先藉助下面的一個情境，來介紹幾個重要概念。

        下表是一些購買記錄：

將購買記錄整理，可得到下表，橫欄和縱欄的數字表示同時購買這兩種商品的交易條數。如購買有Orange的交易數為4，而同時購買Orange和Coke的交易數為2。

        置信度，表示這條規則有多大程度上值得可信。

        設條件的項的集合為A,結果的集合為B。置信度計算在A中，同時也含有B的概率。即Confidence(A->B)=P(B|A)。例 如計算"如果Orange則Coke"的置信度。由於在含有Orange的4條交易中，僅有2條交易含有Coke。其置信度為0.5。

        支持度，計算在所有的交易集中，既有A又有B的概率。

        例如在5條記錄中，既有Orange又有Coke的記錄有2條。則此條規則的支持度為2/5=0.4。現在這條規則可表述為，如果一個顧客購買了Orange,則有50%的可能購買Coke。而這樣的情況（即買了Orange會再買Coke）會有40%的可能發生。

支持度大於預先定好的最小支持度的項集。

       關聯規則：令項集I={i1,i2,...in}，且有一個數據集合D，它其中的每一條記錄T，都是I的子集。那麼關聯規則是形如A->B的表達式，A、B均為I的子集，且A與B的交集為空。這條關聯規則的支持度：support = P(A並B)。這條關聯規則的置信度：confidence = support(A並B）/suport(A)。

       強關聯規則：如果存在一條關聯規則，它的支持度和置信度都大於預先定義好的最小支持度與置信度，我們就稱它為強關聯規則。

下面用一個例子說明演算法的過程：

項目集合 I={1，2，3，4，5};

事務集 T：

設定最小支持度（minsup）=3/7，最小置信度（misconf）=5/7。

假設：n-頻繁項目集為包含n個元素的項目集，例如1-頻繁項目集為包含1個元素的項目集

則這里，1-頻繁項目集有：{1}，{2}，{3}，{4}，{5}

生成2-頻繁項目集的過程如下：

        首先列出所有可能的2-項目集，如下：

        {1，2}，{1，3}，{1，4}，{1，5}

        {2，3}，{2，4}，{2，5}

        {3，4}，{3，5}

        {4，5}

        計算它們的支持度，發現只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度    滿足要求，因此求得2-頻繁項目集：

        {1，2}，{1，3}，{1，4}，{2，3}，{2，4}

生成3-頻繁項目集：

對於現有的2-頻繁項目集，兩兩取並集，並確保第三個二元組也在2-頻繁項目集內，把得到的所有3-項目集分別計算支持度，剔除不滿足最小支持度的項目集；

例如，

{1，2}，{1，3}的並集得到{1，2，3}；

{1，2}，{1，4}的並集得到{1，2，4}；

{1，3}，{1，4}的並集得到{1，3，4}；

{2，3}，{2，4}的並集得到{2，3，4}；

但是由於{1，3，4}的子集{3，4}不在2-頻繁項目集中，所以需要把{1，3，4}剔除掉。{2，3，4} 同理剔除。

然後再來計算{1，2，3}和{1，2，4}的支持度，發現{1，2，3}的支持度為3/7 ，{1，2，4}的支持度為2/7，所以需要把{1，2，4}剔除。因此得到3-頻繁項目集：{1，2，3}。

重復上面步驟繼續尋找n-頻繁項目集，直到不能發現更大的頻繁項目集。所以，到此，頻繁項目集生成過程結束。

這里只說明3-頻繁項目集生成關聯規則的過程，即以集合{1，2，3}為例：

回顧事物集，先生成1-後件的關聯規則：

（1，2）—>3，置信度=3/4（出現（1，2）的記錄共4條，其中有3條包含3，所以3/4）；

（1，3）—>2，置信度=3/5；

（2，3）—>1，置信度=3/3；

第二條置信度<5/7，未達到最小置信度，所以剔除掉。所以對於3-頻繁項目集生成的強關聯規則為：（1，2）—>3和（2，3）—>1。

這表示，如果1、2出現了，則極有可能出現3；2、3出現，則極有可能有1。

http://www.cnblogs.com/junyuhuang/p/5572364.html

⑽ apriori演算法是什麼

經典的關聯規則挖掘演算法包括Apriori演算法和FP-growth演算法。

apriori演算法多次掃描交易資料庫，每次利用候選頻繁集產生頻繁集；而FP-growth則利用樹形結構，無需產生候選頻繁集而是直接得到頻繁集，大大減少掃描交易資料庫的次數，從而提高了演算法的效率，但是apriori的演算法擴展性較好，可以用於並行計算等領域。

基本演算法：

Apriori algorithm是關聯規則里一項基本演算法

Apriori演算法將發現關聯規則的過程分：

第一通過迭代，檢索出事務資料庫1中的所有頻繁項集，即支持度不低於用戶設定的閾值的項集；

第二利用頻繁項集構造出滿足用戶最小信任度的規則。其中，挖掘或識別出所有頻繁項集是該演算法的核心，占整個計算量的大部分。