1.Apriori算法与关联分析
1.1 什么是关联分析？
关联分析是要在大量数据集中寻找数据之间关系。这种关系主要包含以下两种形式： - 1.频繁项集：频繁一起出现的数据的集合 - 2.关联规则：两条数据之间可能存在很强的关系
1.2 频繁项集和关联规则、支持度和可信度
关联分析的主要意图就是为了发现频繁项集和关联规则。首先要找到频繁项集然后才能发现关联规则。
以如下案例为例，游戏的场次id和参与本场游戏（可组队游戏）玩家的姓名。
| 游戏场次id | 玩家名称 |
|---|---|
| 1 | a,b,c,d,e,h,i,j,k,p |
| 2 | b,c,h,i,j,q,w,e,r,t |
| 3 | b,c,h,i,u,y,t,q,b,v |
通过表格很容易发现，b,c,h,i,j经常同时出现在一局游戏中，因此他们可能是组队游戏的。那么{b,c,h,i,j}就是一个频繁项集。b->c则是一个关联规则，即有b出现的时候c很有可能也在这局游戏，他俩很可能是好友。
支持度（针对频繁项集的评价标准）：数据集中包含某个集合记录所占的比例。例如上表的数据中，{a}的支持度为。{i,j}的支持度为
可信度（针对关联规则的评价标准）：针对某一条关联规则来计算。例如b->c,则这条规则的可信度计算公式为:
1.3 Apriori基本原理
对于一个存在n个元素的集合，要找到符合要求的频繁项集需要计算所有子集的支持度。那么就需要计算次，这种指数型增长的算法显然效率非常低。
前人提出了一种Apriori原理，即如果一个项集是频繁的，那么他的所有子集也都是频繁的。例如在上面的例子中，{b,c,h,i}是频繁的，那么{b},{c,h},{b,h,i}这些子集都是频繁的。
将Apriori原理反过来说，也就变成了所有非频繁项集的超集（父集）也都是非频繁的。通过这种方式，可以非常有效的帮户我们减小运算。例如，在上面的例子中，{v}的支持度仅为，是一个非频繁集，那么我们就可以不需要再去计算{a,v},{b,v}等这些包含{v}的超集的支持度。
1.4 Apriori算法流程简述
- 1.设置一个最小值支持度，读入训练集合，生成所有单项的集合列表保存至候选集，time=2
- 2.计算当前列表的支持度，剔除支持度小于最小支持度的集合，若候选集中已无元素则训练结束。
- 3.使用保存下来集合中的单项进行组合，生成包含time个元素的所有子集，time+=1，跳转至第2步。
1.5 使用Apriori算法查找频繁项集使用实例
1.5.1 获取支持度大于特定值的频繁项集
1.读入数据
#返回最初的候选集 def getDataSet(): DataSet = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]] return DataSet def getFirstCandEleList(DataSet): candEleList = [] for row in DataSet: for item in row: if [item] not in candEleList: #为了统一，这里单元素的也弄成列表 candEleList.append([item]) candEleList.sort() #对结果进行一个简单的排序方便后面操作 return candEleList #print(loadData())
2.我感觉这个算法最巧妙的地方就是合并现有的候选集合，得到新的集合
def getCandidateElement(candEleList):#读入现有的候选集 lenOfOldCandEleList = len(candEleList) #现有候选集候选集合总个数 k=len(candEleList[0])+1 #新的候选集中集合中包含的元素个数 newCandEleList=[] for i in range(lenOfOldCandEleList): for j in range(i+1,lenOfOldCandEleList): list1 = candEleList[i][:k-2] list2 = candEleList[j][:k-2] if list1==list2: #这里就是判断如果从0-k-1个元素都一样，那就最后两个不一样了，两个元素求和，正好是k个 new_list = (set(candEleList[i])).union(set(candEleList[j])) #先把列表转成集合，合并 new_list = list(new_list) new_list.sort() #再把集合改成列表排序，保证列表中数据永远都是有序的，方便比较 newCandEleList.append(new_list) return newCandEleList #print(getCandidateElement(candEleList))
3.计算支持度，仅保留支持度大于指定值的集合并返回
def getEleOverMinSupport(dataSet,candEleList,minSupport): newCandEleList = [] supportRateList = [] for ele in candEleList:#计算每一个候选列表中元素的支持度 num = 0.0 for data in dataSet: if (set(ele))&(set(data))==(set(ele)): num+=1 supportRate = num/len(dataSet) if supportRate>=minSupport: newCandEleList.append(ele) supportRateList.append(supportRate) #print(supportRate,ele,dataSet) return newCandEleList,supportRateList #getEleOverMinSupport(dataSet,candEleList,0.75)
4.调用上述算法找出支持度大于0.5的全部数据集
def apriori(dataSet,minSupport): resList = [] #保存所有符合要求的集合 resSupportList = [] #保存所有符合要求集合的支持率 candEleList = getFirstCandEleList(dataSet)#初始化候选集 while(len(candEleList)!=0): candEleList,supportRateList=getEleOverMinSupport(dataSet,candEleList,minSupport) if len(candEleList)>0: resList.extend(candEleList) #添加符合要求的元素至结果列表 resSupportList.extend(supportRateList) #添加符合要求的元素的支持率至结果支持率列表 candEleList=getCandidateElement(candEleList) #更新候选集 return resList,resSupportList dataSet = getDataSet() minSupport = 0.5 freqdataList,freqSupportList = apriori(dataSet,minSupport) print(freqdataList,freqSupportList)
[[1], [2], [3], [5], [1, 3], [2, 3], [2, 5], [3, 5], [2, 3, 5]] [0.5, 0.75, 0.75, 0.75, 0.5, 0.5, 0.75, 0.5, 0.5]
1.5.2 获取可信度大于特定值的关联规则
从频繁项集中我们可以提取出许多的关联规则。当然关联规则的好坏也有统一的评价标准——可信度。这里提取可信度大于最小可信度的关联规则的方式与获取频繁项集的方式非常类似，基于的中心思想是，如果某一条规则不满足最小可信度要求，那么这条规则的所有子集也不满足最小可信度要求，例如：
如果1,2,3->4是一条低可信度的规则，那么以[1,2,3]生成的子集作为规则左侧的规则：{1->4},{2->4},{3->4},{1,2->4}等规则都是低可信度规则。
感觉没啥意思，跟前面那个差不多，不写了。