输入:D - 事务数据库;min_sup - 最小支持度计数阈值
输出:L - D中的频繁项集
方法:
L1=find_frequent_1-itemsets(D)// 找出所有频繁1项集
For(k=2Lk-1!=nullk++){
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=所有的频繁集;
Procedure 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
Procedure has_infrequent_sub(c:candidate k-itemsetLk-1:frequent(k-1)-itemsets)
For each(k-1)-subset s of c
If s不属于Lk-1 then
Return true
Return false
用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.duplicates =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.duplicates:是否移除重复项,默认为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按下图进行逐层计算,当发现一个不满足置信度的项集后,该项集所有子集的规则都可以剪枝掉了。
1. 判断存在:一个元素是不是在向量中用 a%in%b>a="TT"
>b=c("AA","AT","TT")
>a %in% b
[1] TRUE
2. 判断某一元素这向量中的索引(第几个位置): index.TT=which(b==”TT”)
>index.TT=which(b=="TT")#index.TT是想知道的索引号,which是判断函数,b是想知道的元素所在的向量
>index.TT
[1] 3
3. 相当于 python 中的字典, names 函数
>b
[1] "AA" "AT" "TT"
>names(b)=c("geno1","geno2","geno3")#geno mean genotype
>names(b)
[1] "geno1" "geno2" "geno3"
>names(b)[1]
[1] "geno1"
>names(b)[1]="test"
>names(b)
[1] "test""geno2" "geno3"
>names(b)=NULL
>b
[1] "AA" "AT"
>b["geno2"]
"AT"
pop_name=c(“CEU”,"YRI")
names(pop_name)=c(1,2)
names(pop_name[1])=1
4. 去除某一元素: b[-index.nu]
#想去除元素”TT”,如果你不知道是第几个索引,可以先判断索引,再删除。
>b=c("AA","AT","TT")
>names(b)=c("geno1","geno2","geno3")
>index.TT=which(b=="TT")
>b=b[-index.TT]
>b
geno1 geno2
"AA""AT"
5. 相当于 Python 中的 set() 函数 和 count() 函数: unique() , table()
>b=c("TT","AT","AT","TT","AA")
>unique(b)#即相当于去除所有的重复,只保留一个
[1] "TT" "AT" "AA"
>table(b)#以元素为name,统计各元素的个数
b
AA AT TT
122
6. 字符串的分割: strsplit()
>test="AA"
>strsplit(test)
错误于strsplit(test) :缺少参数"split",也没有缺省值
>strsplit(test,split='')
[[1]]
[1] "A" "A"
>test=strsplit(test,split='')[[1]]
>test
[1] "A" "A"
7. 文本文档的写入: write.table()
write.table( res.matrix,file=new.file,sep='\t',quote=F,row.names=F,col.names=F,append=T)#quote=F去掉引号后写入,row.names=F去掉行的名字写入,否则会把名字写进去
##写入数据时候最好把数据存储成一个matrix然后直接写。要是每行每行写的话要注意数据的格式了。先建立一个空的matrix,见8,然后通过rbind或者cbind叠加上去。
方法一:
a=c()
b=c(“AA”,”TT”,”CC”)
for (i in 1:3){
a=c(a,b)
}
write.table(a,file=”test.txt”)#你会发现结果是
AA
TT
CC
….
##而且还有行和列的名字,因为没有设置参数。因为对于c向量来说,写的话默认是竖着写的,每个元素占一行。所以比较方便的就是rbind
方法二:
a=c()
b=c(“AA”,”TT”,”CC”)
for (i in 1:3){
a=rbind(a,b)
}
write.table(a,file=”test.txt”,quote=F,row.names=F,col.names=F)#你会发现结果是
AA TT CC
AA TT CC
AA TT CC
##原因是rbind把最总结果当做矩阵了。对于R数据的写入最好能生成最后的矩阵再写入。但是西面的梅一行写一次和方法二的效果是想通的,但是要用到append参数。
a=c()
b=c(“AA”,”TT”,”CC”)
for (i in 1:3){
a=rbind(a,b)
write.table(a,file=”test.txt”,quote=F,row.names=F,col.names=F,append=T)
}
8. 建立一个空的 matrix :
res.matrix <- matrix( ,nrow=0,ncol=6 )##这样就建立了一个0行6列的空matrix了。
9. 如何将 R 运行结果输出到文件
>x=read.table("F:/my/work/chengxu/PValue/pc2jieguo/pc2302.txt")
>z=t(x)
>ks.test(y,z)
Two-sample Kolmogorov-Smirnov test
data:y and z
D = 0.207, p-value <2.2e-16
alternative hypothesis: two-sided
如上面运行结果,我想将p-value <2.2e-16自动保存到一个文件中,如何用R程序实现,谢谢!
sink("output.txt")
print(ks.test(y,z)$p.value)
sink()
http://cos.name/cn/topic/16300
10 降序排列:
>a=c(1,1.2,0.1,4,5,-0.1)
>a=sort(a,decreasing=T)
>a
[1]5.04.01.21.00.1 -0.1
11. 取前1%的数
>a=c(1:10,4:20,1:100,1:1000)
>a=sort(a,decreasing=T)#先降序
>sig=a[round(length(a)*0.01)]
>sig
[1] 990
12.在shell中直接执行R脚本
R CMD BATCH --argstest.R
13. R中高级作图的方法
http://qizhi502.blog.163.com/blog/static/11497002520120611451736/
14:设置字体类型:
par(family='Times New Roman')
15:控制图形四周的空白大小
par(mfrow=c(3,1),mar=c(0,0,0,0))
其中mar是四周的间距,分别为x,y上下的距离
16控制作图区域的大小layout
layout(c(1,2,3),height=c(1,1,0.5))
分成竖着三份, 其中三份比列依次为(高度依次为2:2:1)
17保留两位小数
round(0.123,digits=2)
18 在原有图的基础上画图:
par(fig=c(0.1,0.5,0.43,0.65), new=TRUE)
19 只显示y轴
plot(1:10,1:10,axes=F)
axis(2,at.....)
20 调节刻度方向 las
plot(1:10,1:10,las=1)
21 屏幕分割
layout(matrix(1:16,4,4))###竖着plot
par(mfrow=c(4,4))##横着plot
22.逻辑表示或者
xor为异或,两值不等为真,两值相等为假。例:xor(0, 1)
23. 从向量中随机取几个数sample
sample(rep(1:1000),10)
23 字符串转换成小数浮点型
as.numeric("0.123")
24. 读取不规范的文本
f=readLines(afile,n=1)#n表示读几行
f=strsplit(f,'\t')##分割
f[1][[1]]##第一行
f[1][[1]][1]##第一行 第一个字符串
25. write 写入文件
write(afile, "a\tb\t",append=T) #沿着每行一次 写入
26. 不需要循环,这直接对matrix没行或者每列进行筛选操作apply()
apply(data,col2 or row1, max>0)
27.保留2位小数
a=2.300
a=as.numeric(sprintf(“%.3f”,a))
28。调出假设检验的p value
t.test(data1,data2)$p.value