apriori演算法r語言
㈠ r apriori演算法結果怎麼看
演算法:Apriori
輸入:D - 事務資料庫;min_sup - 最小支持度計數閾值
輸出:L - D中的頻繁項集
方法:
L1=find_frequent_1-itemsets(D); // 找出所有頻繁1項集
For(k=2;Lk-1!=null;k++){
Ck=apriori_gen(Lk-1); // 產生候選,並剪枝
For each 事務t in D{ // 掃描D進行候選計數
Ct =subset(Ck,t); // 得到t的子集
For each 候選c 屬於 Ct
c.count++;
}
Lk={c屬於Ck | c.count>=min_sup}
}
Return L=所有的頻繁集;
Procere apriori_gen(Lk-1:frequent(k-1)-itemsets)
For each項集l1屬於Lk-1
For each項集 l2屬於Lk-1
If((l1[1]=l2[1])( l1[2]=l2[2])……..
(l1[k-2]=l2[k-2])(l1[k-1]<l2[k-1])) then{
c=l1連接l2 //連接步:產生候選
if has_infrequent_subset(c,Lk-1) then
delete c; //剪枝步:刪除非頻繁候選
else add c to Ck;
}
Return Ck;
Procere has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets)
For each(k-1)-subset s of c
If s不屬於Lk-1 then
Return true;
Return false;
㈡ Apriori演算法是什麼適用於什麼情境
經典的關聯規則挖掘演算法包括Apriori演算法和FP-growth演算法。apriori演算法多次掃描交易資料庫,每次利用候選頻繁集產生頻繁集;而FP-growth則利用樹形結構,無需產生候選頻繁集而是直接得到頻繁集,大大減少掃描交易資料庫的次數,從而提高了演算法的效率。但是apriori的演算法擴展性較好,可以用於並行計算等領域。
Apriori algorithm是關聯規則里一項基本演算法。是由Rakesh Agrawal和Ramakrishnan Srikant兩位博士在1994年提出的關聯規則挖掘演算法。關聯規則的目的就是在一個數據集中找出項與項之間的關系,也被稱為購物藍分析 (Market Basket analysis),因為「購物藍分析」很貼切的表達了適用該演算法情景中的一個子集。
㈢ 用R語言進行關聯分析
用R語言進行關聯分析
關聯是兩個或多個變數取值之間存在的一類重要的可被發現的某種規律性。關聯分析目的是尋找給定數據記錄集中數據項之間隱藏的關聯關系,描述數據之間的密切度。
幾個基本概念
1. 項集
這是一個集合的概念,在一籃子商品中的一件消費品即為一項(Item),則若干項的集合為項集,如{啤酒,尿布}構成一個二元項集。
2. 關聯規則
一般記為的形式,X為先決條件,Y為相應的關聯結果,用於表示數據內隱含的關聯性。如:,表示購買了尿布的消費者往往也會購買啤酒。
關聯性強度如何,由三個概念——支持度、置信度、提升度來控制和評價。
例:有10000個消費者購買了商品,其中購買尿布1000個,購買啤酒2000個,購買麵包500個,同時購買尿布和麵包800個,同時購買尿布和麵包100個。
3. 支持度(Support)
支持度是指在所有項集中{X, Y}出現的可能性,即項集中同時含有X和Y的概率:
該指標作為建立強關聯規則的第一個門檻,衡量了所考察關聯規則在「量」上的多少。通過設定最小閾值(minsup),剔除「出鏡率」較低的無意義規則,保留出現較為頻繁的項集所隱含的規則。
設定最小閾值為5%,由於{尿布,啤酒}的支持度為800/10000=8%,滿足基本輸了要求,成為頻繁項集,保留規則;而{尿布,麵包}的支持度為100/10000=1%,被剔除。
4. 置信度(Confidence)
置信度表示在先決條件X發生的條件下,關聯結果Y發生的概率:
這是生成強關聯規則的第二個門檻,衡量了所考察的關聯規則在「質」上的可靠性。相似的,我們需要對置信度設定最小閾值(mincon)來實現進一步篩選。
具體的,當設定置信度的最小閾值為70%時,置信度為800/1000=80%,而的置信度為800/2000=40%,被剔除。
5. 提升度(lift)
提升度表示在含有X的條件下同時含有Y的可能性與沒有X這個條件下項集中含有Y的可能性之比:
該指標與置信度同樣衡量規則的可靠性,可以看作是置信度的一種互補指標。
R中Apriori演算法
演算法步驟:
1. 選出滿足支持度最小閾值的所有項集,即頻繁項集;
2. 從頻繁項集中找出滿足最小置信度的所有規則。
> library(arules) #載入arules包
> click_detail =read.transactions("click_detail.txt",format="basket",sep=",",cols=c(1)) #讀取txt文檔(文檔編碼為ANSI)
> rules <- apriori(click_detail, parameter =list(supp=0.01,conf=0.5,target="rules")) #調用apriori演算法
> rules
set of419 rules
> inspect(rules[1:10]) #查看前十條規則
解釋
1) library(arules):載入程序包arules,當然如果你前面沒有下載過這個包,就要先install.packages(arules)
2) click_detail =read.transactions("click_detail.txt",format="basket",sep=",",cols=c(1)):讀入數據
read.transactions(file, format =c("basket", "single"), sep = NULL,
cols = NULL, rm.plicates =FALSE, encoding = "unknown")
file:文件名,對應click_detail中的「click_detail.txt」
format:文件格式,可以有兩種,分別為「basket」,「single」,click_detail.txt中用的是basket。
basket: basket就是籃子,一個顧客買的東西都放到同一個籃子,所有顧客的transactions就是一個個籃子的組合結果。如下形式,每條交易都是獨立的。
文件形式:
item1,item2
item1
item2,item3
讀入後:
items
1 {item1,
item2}
2 {item1}
3 {item2,
item3}
single: single的意思,顧名思義,就是單獨的交易,簡單說,交易記錄為:顧客1買了產品1, 顧客1買了產品2,顧客2買了產品3……(產品1,產品2,產品3中可以是單個產品,也可以是多個產品),如下形式:
trans1 item1
trans2 item1
trans2 item2
讀入後:
items transactionID
1 {item1} trans1
2 {item1,
item2} trans2
sep:文件中數據是怎麼被分隔的,默認為空格,click_detail裡面用逗號分隔
cols:對basket, col=1,表示第一列是數據的transaction ids(交易號),如果col=NULL,則表示數據裡面沒有交易號這一列;對single,col=c(1,2)表示第一列是transaction ids,第二列是item ids
rm.plicates:是否移除重復項,默認為FALSE
encoding:寫到這里研究了encoding是什麼意思,發現前面txt可以不是」ANSI」類型,如果TXT是「UTF-8」,寫encoding=」UTF-8」,就OK了.
3) rules <- apriori(click_detail,parameter = list(supp=0.01,conf=0.5,target="rules")):apriori函數
apriori(data, parameter = NULL, appearance = NULL, control = NULL)
data:數據
parameter:設置參數,默認情況下parameter=list(supp=0.1,conf=0.8,maxlen=10,minlen=1,target=」rules」)
supp:支持度(support)
conf:置信度(confidence)
maxlen,minlen:每個項集所含項數的最大最小值
target:「rules」或「frequent itemsets」(輸出關聯規則/頻繁項集)
apperence:對先決條件X(lhs),關聯結果Y(rhs)中具體包含哪些項進行限制,如:設置lhs=beer,將僅輸出lhs含有beer這一項的關聯規則。默認情況下,所有項都將無限制出現。
control:控制函數性能,如可以設定對項集進行升序sort=1或降序sort=-1排序,是否向使用者報告進程(verbose=F/T)
補充
通過支持度控制:rules.sorted_sup = sort(rules, by=」support」)
通過置信度控制:rules.sorted_con = sort(rules, by=」confidence」)
通過提升度控制:rules.sorted_lift = sort(rules, by=」lift」)
Apriori演算法
兩步法:
1. 頻繁項集的產生:找出所有滿足最小支持度閾值的項集,稱為頻繁項集;
2. 規則的產生:對於每一個頻繁項集l,找出其中所有的非空子集;然後,對於每一個這樣的子集a,如果support(l)與support(a)的比值大於最小可信度,則存在規則a==>(l-a)。
頻繁項集產生所需要的計算開銷遠大於規則產生所需的計算開銷
頻繁項集的產生
幾個概念:
1, 一個包含K個項的數據集,可能產生2^k個候選集
2,先驗原理:如果一個項集是頻繁的,則它的所有子集也是頻繁的(理解了頻繁項集的意義,這句話很容易理解的);相反,如果一個項集是非頻繁的,則它所有子集也一定是非頻繁的。
3基於支持度(SUPPORT)度量的一個關鍵性質:一個項集的支持度不會超過它的子集的支持度(很好理解,支持度是共同發生的概率,假設項集{A,B,C},{A,B}是它的一個自己,A,B,C同時發生的概率肯定不會超過A,B同時發生的概率)。
上面這條規則就是Apriori中使用到的,如下圖,當尋找頻繁項集時,從上往下掃描,當遇到一個項集是非頻繁項集(該項集支持度小於Minsup),那麼它下面的項集肯定就是非頻繁項集,這一部分就剪枝掉了。
一個例子(網路到的一個PPT上的):
當我在理解頻繁項集的意義時,在R上簡單的復現了這個例子,這里採用了eclat演算法,跟apriori應該差不多:
代碼:
item <- list(
c("bread","milk"),
c("bread","diaper","beer","eggs"),
c("milk","diaper","beer","coke"),
c("bread","milk","diaper","beer"),
c("bread","milk","diaper","coke")
)
names(item) <- paste("tr",c(1:5),sep = "")
item
trans <- as(item,"transactions") #將List轉為transactions型
rules = eclat(trans,parameter = list(supp = 0.6,
target ="frequent itemsets"),control = list(sort=1))
inspect(rules) #查看頻繁項集
運行後結果:
>inspect(rules)
items support
1{beer,
diaper} 0.6
2{diaper,
milk} 0.6
3{bread,
diaper} 0.6
4{bread,
milk} 0.6
5{beer} 0.6
6{milk} 0.8
7{bread} 0.8
8{diaper} 0.8
以上就是該例子的所有頻繁項集,然後我發現少了{bread,milk,diaper}這個項集,回到例子一看,這個項集實際上只出現了兩次,所以是沒有這個項集的。
規則的產生
每個頻繁k項集能產生最多2k-2個關聯規則
將項集Y劃分成兩個非空的子集X和Y-X,使得X ->Y-X滿足置信度閾值
定理:如果規則X->Y-X不滿足置信度閾值,則X』->Y-X』的規則一定也不滿足置信度閾值,其中X』是X的子集
Apriori按下圖進行逐層計算,當發現一個不滿足置信度的項集後,該項集所有子集的規則都可以剪枝掉了。
㈣ R語言 apriori中規則如何忽略先後順序
a→b,b→a 本來就是兩個不一樣的規則。
對照置信度的定義 他們的值都不一樣,
它們只是支持度一樣,
如果你只要一個, 那就只挖頻繁項集就可以,不必生成規則。
㈤ 如何實現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);
}
}
}
}
㈥ 多維關聯規則挖掘演算法r語言能實現嗎
一下自己學習關聯規則經典演算法Apriori的筆記。
1、概述
Apriori演算法是用一種稱為逐層搜索的迭代方法,從項集長度k=1開始,選出頻繁的k=1項集,根據先驗性質:頻繁項集的子集一定是頻繁的(逆否命題:非頻繁項集的超集一定是非頻繁的,通俗的說就是某件事發生的概率很低,比這件事發生條件更嚴苛的事情發生的概率會更低),篩選k=2項集中的頻繁項集,以此迭代k=3...。每迭代一次都要完整的掃描一次資料庫。
2、關聯規則三度:
支持度:佔比
置信度:條件概率
提升度:相關性
3、R語言示例代碼如下:(小眾語言的辛酸:選項里沒有。。)
[plain] view plain
library(arules)
#從rattle包中讀入數據
dvdtrans <- read.csv(system.file("csv", "dvdtrans.csv",package="rattle"))
str(dvdtrans)
#將數據轉化為合適的格式
data <- as(split(dvdtrans$Item,dvdtrans$ID),"transactions")
data
#用 apriori命令生成頻繁項集,設其支持度為0.5,置信度為0.8
rules <- apriori(data, parameter=list(support=0.5,confidence=0.8,minlen = 2))
#用inspect命令查看提取規則
inspect(rules)
常用數據形式有data.frame格式和list格式,前者即A項集為一列B項集為另一列,後者為A和B放在同一個購物籃中。
去除冗餘規則以及提取子規則代碼如下:
[plain] view plain
rendant.rm <- function(rule,by="lift")
{
#rule:需要進行簡化的規則
#by:在清除的時候根據那個變數來選擇,
#可能取值為"support","lift","confidence"
a <- sort(rule,by=by)
m<- is.subset(a,a,proper=TRUE)
m[lower.tri(m, diag=TRUE)] <- NA
r <- colSums(m, na.rm=TRUE) >= 1
finall.rules <- a[!r]
return(finall.rules)
}
rules <- rendant.rm(rules)
rules.sub <- subset(rules, subset = lhs %in% "篩選項集名稱" & lift > 1)
㈦ 利用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,由頻繁項集產生強關聯規則,結束。
㈧ apriori演算法是什麼
經典的關聯規則挖掘演算法包括Apriori演算法和FP-growth演算法。
apriori演算法多次掃描交易資料庫,每次利用候選頻繁集產生頻繁集;而FP-growth則利用樹形結構,無需產生候選頻繁集而是直接得到頻繁集,大大減少掃描交易資料庫的次數,從而提高了演算法的效率,但是apriori的演算法擴展性較好,可以用於並行計算等領域。
基本演算法:
Apriori algorithm是關聯規則里一項基本演算法
Apriori演算法將發現關聯規則的過程分:
第一通過迭代,檢索出事務資料庫1中的所有頻繁項集,即支持度不低於用戶設定的閾值的項集;
第二利用頻繁項集構造出滿足用戶最小信任度的規則。其中,挖掘或識別出所有頻繁項集是該演算法的核心,占整個計算量的大部分。
㈨ 機器學習有哪些演算法
1. 線性回歸
在統計學和機器學習領域,線性回歸可能是最廣為人知也最易理解的演算法之一。
2. Logistic 回歸
Logistic 回歸是機器學習從統計學領域借鑒過來的另一種技術。它是二分類問題的首選方法。
3. 線性判別分析
Logistic 回歸是一種傳統的分類演算法,它的使用場景僅限於二分類問題。如果你有兩個以上的類,那麼線性判別分析演算法(LDA)是首選的線性分類技術。
4.分類和回歸樹
決策樹是一類重要的機器學習預測建模演算法。
5. 樸素貝葉斯
樸素貝葉斯是一種簡單而強大的預測建模演算法。
6. K 最近鄰演算法
K 最近鄰(KNN)演算法是非常簡單而有效的。KNN 的模型表示就是整個訓練數據集。
7. 學習向量量化
KNN 演算法的一個缺點是,你需要處理整個訓練數據集。
8. 支持向量機
支持向量機(SVM)可能是目前最流行、被討論地最多的機器學習演算法之一。
9. 袋裝法和隨機森林
隨機森林是最流行也最強大的機器學習演算法之一,它是一種集成機器學習演算法。
想要學習了解更多機器學習的知識,推薦CDA數據分析師課程。CDA(Certified Data Analyst),即「CDA 數據分析師」,是在數字經濟大背景和人工智慧時代趨勢下,面向全行業的專業權威國際資格認證,旨在提升全民數字技能,助力企業數字化轉型,推動行業數字化發展。點擊預約免費試聽課。