机器学习算法学习---关联分析算法（一）

你的名字 2021-12-23 01:37 374阅读 0赞

Apriori算法

优点：易编码实现。

缺点：在大数据集上可能较慢。

适用数据：数值型、标称型。

1、关联分析

关联分析寻找的关系可以有两种形式：频繁项集或者关联规则。

频繁项集：经常出现在一块的物品的集合；

关联规则：暗示两种物品之间可能存在很强的关系。

支持度：数据集中包含该项集的记录所占的比例。（针对项集）

可信度/置信度：一条关联规则\{A\}-->\{B\}，支持度(\{A,B\})/支持度(\{A\})的比值为可信度。（针对关联规则）

2、Apriori原理

对于包含N种物品的数据集共有2N\-1种项集组合。

目的：为了降低所需的计算时间。减少可能感兴趣的项集

原理：如果某个项集是频繁的，那么它的所有子集也是频繁的；如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

3、使用Apriori算法来发现频繁集

关联分析的目标：发现频繁集和发现关联规则。

频繁项集的量化指标：满足最小支持度

算法过程（输入为最小支持度和数据集）：首先会生成所有单个物品的项集列表；接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉；然后对剩下的集合进行组合以生成包含两个元素的项集；接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。

python实现如下：

获取频繁集

\#辅助函数

def loadDataSet():\#创建数据集

return \[\[1,3,4\],\[2,3,5\],\[1,2,3,5\],\[2,5\]\]

def createC1(dataSet):\#构建集合C1(大小为1的所有候选项集的集合)

C1=\[\]

for transaction in dataSet:\#遍历交易记录

for item in transaction:

if not \[item\] in C1:

C1.append(\[item\])

C1.sort()

return map(frozenset,C1)\#对C1中每个项构建一个不变集合

def scanD(D,Ck,minSupport):\#从Ck生成Lk

ssCnt=\{\}

for tid in D:

for can in Ck:

if can.issubset(tid):

if not ssCnt.has\_key(can):

ssCnt\[can\]=1

else:

ssCnt\[can\]+=1

numItems=float(len(D))

retList=\[\]

supportData=\{\}

for key in ssCnt:

support=ssCnt\[key\]/numItems

if support>=minSupport:

retList.insert(0,key)

supportData\[key\]=support

return retList,supportData

\#Apriori算法

def aprioriGen(Lk,k):\#创建候选项集Ck

retList=\[\]

lenLk=len(Lk)

for i in range(lenLk):

for j in range(i+1,lenLk):

L1=list(Lk\[i\])\[:k-2\]

L2=list(Lk\[j\])\[:k-2\]

L1.sort()

L2.sort()

if L1==L2:\#前k-2项同，合并；避免产生重复值

retList.append(Lk\[i\]|Lk\[j\])

return retList

def apriori(dataSet,minSupport=0.5):\#主函数

C1=createC1(dataSet)

D=map(set,dataSet)

L1,supportData=scanD(D,C1,minSupport)

L=\[L1\]\#存储频繁项集

k=2

while len(L\[k-2\])>0:

Ck=aprioriGen(L\[k-2\],k)

Lk,supK=scanD(D,Ck,minSupport)

supportData.update(supK)

L.append(Lk)

k+=1

return L,supportData

4、从频繁项集中挖掘关联规则

关联规则箭头左边的集合称作前件，箭头右边的集合称为后件。

关联规则的量化指标：满足最小可信度

一条规则P->H的可信度：support(P|H)/support(P)

性质属性：如果某条规则并不满足最小可信度要求，那么该规则的所有子集（左件的子集）也不会满足最小可信度要求。

算法过程（分级法）：首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试；接下来合并所有剩余规则来创建一个新的规则列表，其中规则右部包含两个元素。

python实现如下：

获取关联规则\#关联规则生成函数

def calcConf(freqSet,H,supportData,br1,minConf=0.7):\#规则评估函数

prunedH=\[\]

for conseq in H:

conf=supportData\[freqSet\]/supportData\[freqSet-conseq\]

if conf>=minConf:

print(freqSet-conseq,'-->',conseq,'conf:',conf)

br1.append((freqSet-conseq,conseq,conf))

prunedH.append(conseq)

return prunedH

def rulesFromConseq(freqSet,H,supportData,br1,minConf=0.7):

m=len(H\[0\])

if len(freqSet)>(m+1):

Hmp1=aprioriGen(H,m+1)

Hmp1=calcConf(freqSet,Hmp1,supportData,br1,minConf)

if len(Hmp1)>1:

rulesFromConseq(freqSet,Hmp1,supportData,br1,minConf)

def generateRules(L,supportData,minConf=0.7):\#主函数

bigRuleList=\[\]

for i in range(1,len(L)):\#只获取有两个或更多元素的集合

for freqSet in L\[i\]:

H1=\[frozenset(\[item\]) for item in freqSet\]\#右部元素

if i>1:

rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)

else:

calcConf(freqSet,H1,supportData,bigRuleList,minConf)

return bigRuleList

转载于:https://www.cnblogs.com/zhenpengwang/p/10913716.html

机器学习算法学习---关联分析算法（一）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关机器学习实战：使用 Apriori 算法进行关联分析

相关 apriori伪代码_机器学习：Apriori算法进行关联分析

相关【机器学习】Apriori 算法进行关联分析和FP-growth算法

相关机器学习算法

相关机器学习降维算法一：PCA(主成分分析算法)

相关机器学习（十五）关联分析之Apriori算法

相关机器学习：PCA算法分析

相关深度学习（机器学习）算法面试(一)

相关机器学习算法入门(一)

相关机器学习算法学习---关联分析算法（一）