电商网站设计思路,SEO网站链接模型,自己做网站外包,电子商城网站制作文章目录 0 前言1 项目背景2 算法架构3 FP-Growth算法原理3.1 FP树3.2 算法过程3.3 算法实现3.3.1 构建FP树 3.4 从FP树中挖掘频繁项集 4 系统设计展示5 最后 0 前言
#x1f525; 优质竞赛项目系列#xff0c;今天要分享的是
基于FP-Growth的新闻挖掘算法系统的设计与实现… 文章目录 0 前言1 项目背景2 算法架构3 FP-Growth算法原理3.1 FP树3.2 算法过程3.3 算法实现3.3.1 构建FP树 3.4 从FP树中挖掘频繁项集 4 系统设计展示5 最后 0 前言 优质竞赛项目系列今天要分享的是
基于FP-Growth的新闻挖掘算法系统的设计与实现
该项目较为新颖适合作为竞赛课题方向学长非常推荐 更多资料, 项目分享
https://gitee.com/dancheng-senior/postgraduate
1 项目背景
如今新闻泛滥令人眼花缭乱即使同一话题下的新闻也多得数不胜数。人们可以根据自己的职业和爱好关注专业新闻网站的不同热点要闻。因此通过对人们关注新闻的热点问题进行分析可以得出民众对某个领域的关切程度和社会需要解决的问题也有利于了解当前的舆论焦点有助于政府了解民意便于国家对舆论进行正确引导使我们的社会更加安定和谐。本文以财经领域为例通过爬虫技术抓取网络上的大量财经新闻通过对新闻内容文本进行预处理及密度聚类分析来发现热点从发现的热点中再进行词汇聚类分析得出热点所涉及的人或事物以此分析出社会对经济领域关注的问题和需要解决的问题。 2 算法架构
该项目学长要通过文本挖掘技术进行新闻热点问题分析把从网上抓取到的财经新闻通过对新闻内容的聚类得到新闻热点再对热点进行分析通过对某一热点相关词汇的聚类得到热点问题所涉及的人物、行业或组织等。 1、利用新闻 API、爬虫算法、多线程并行技术抓取三大专业财经新闻网站新浪财经、搜狐财经、新华网财经的大量财经新闻报道
2、对新闻进行去重、时间段过滤然后对新闻内容文本进行 jieba 分词并词性标注过滤出名词、动词、简称等词性分词前使用自定义的用户词词典增加分词的准确性分词后使用停用词词典、消歧词典、保留单字词典过滤掉对话题无关并且影响聚类准确性的词建立每篇新闻的词库利用 TF-IDF 特征提取之后对新闻进行 DBSCAN 聚类并对每个类的大小进行排序
3、针对聚类后的每一类新闻为了得到该处热点的话题信息还需要提取它们的标题利用 TextRank 算法对标题的重要程度进行排序用重要性最高的标题来描述该处热点的话题
4、对所有的新闻内容进行 jieba 分词并训练出 word2vec 词嵌入模型然后对聚类后的每一类新闻提取它们的内容分词后的结果运用 word2vec 模型得到每个词的词向量再利用 FP-Growth类算法进行相关新闻挖掘。
3 FP-Growth算法原理
3.1 FP树
FP树是一种存储数据的树结构如下图所示每一路分支表示数据集的一个项集数字表示该元素在某分支中出现的次数 3.2 算法过程
1 构建FP树
遍历数据集获得每个元素项的出现次数去掉不满足最小支持度的元素项构建FP树读入每个项集并将其添加到一条已存在的路径中若该路径不存在则创建一条新路径每条路径是一个无序集合
2 从FP树中挖掘频繁项集
从FP树中获得条件模式基利用条件模式基构建相应元素的条件FP树迭代直到树包含一个元素项为止
算法过程写得比较简略具体过程我们在下节的实操中进一步理解。
3.3 算法实现
3.3.1 构建FP树
class treeNode:def __init__(self,nameValue,numOccur,parentNode):self.namenameValue #节点名self.countnumOccur #节点元素出现次数self.nodeLinkNone #存放节点链表中与该节点相连的下一个元素self.parentparentNodeself.children{} #用于存放节点的子节点,value为子节点名def inc(self,numOccur):self.countnumOccurdef disp(self,ind1):print( *ind,self.name,self.count) #输出一行节点名和节点元素数缩进表示该行节点所处树的深度for child in self.children.values():child.disp(ind1) #对于子节点深度1# 构造FP树# dataSet为字典类型表示探索频繁项集的数据集,keys为各项集values为各项集在数据集中出现的次数# minSup为最小支持度构造FP树的第一步是计算数据集各元素的支持度选择满足最小支持度的元素进入下一步def createTree(dataSet,minSup1):headerTable{}#遍历各项集,统计数据集中各元素的出现次数for key in dataSet.keys():for item in key:headerTable[item]headerTable.get(item,0)dataSet[key] #遍历各元素删除不满足最小支持度的元素for key in list(headerTable.keys()):if headerTable[key]minSup:del headerTable[key]freqItemSetset(headerTable.keys())#若没有元素满足最小支持度要求返回None结束函数if len(freqItemSet)0:return None,Nonefor key in headerTable.keys():headerTable[key][headerTable[key],None] #[元素出现次数**指向每种项集第一个元素项的指针**]retTreetreeNode(Null Set,1,None) #初始化FP树的顶端节点for tranSet,count in dataSet.items():localD{} #存放每次循环中的频繁元素及其出现次数便于利用全局出现次数对各项集元素进行项集内排序for item in tranSet:if item in freqItemSet:localD[item]headerTable[item][0]if len(localD)0:orderedItems[v[0] for v in sorted(localD.items(),keyoperator.itemgetter(1),reverseTrue)] #根据元素全局出现次数对每个项集(tranSet)中的元素进行排序updateTree(orderedItems,retTree,headerTable,count) #使用排序后的项集对树进行填充return retTree,headerTable#树的更新函数#items为按出现次数排序后的项集是待更新到树中的项集count为items项集在数据集中的出现次数#inTree为待被更新的树headTable为头指针表存放满足最小支持度要求的所有元素def updateTree(items,inTree,headerTable,count):#若项集items当前最频繁的元素在已有树的子节点中则直接增加树子节点的计数值增加值为items[0]的出现次数if items[0] in inTree.children: inTree.children[items[0]].inc(count)else:#若项集items当前最频繁的元素不在已有树的子节点中即树分支不存在则通过treeNode类新增一个子节点inTree.children[items[0]]treeNode(items[0],count,inTree)#若新增节点后表头表中没有此元素则将该新增节点作为表头元素加入表头表if headerTable[items[0]][1]None: headerTable[items[0]][1]inTree.children[items[0]]else:#若新增节点后表头表中有此元素则更新该元素的链表即在该元素链表末尾增加该元素updateHeader(headerTable[items[0]][1],inTree.children[items[0]])#对于项集items元素个数多于1的情况对剩下的元素迭代updateTreeif len(items)1:updateTree(items[1::],inTree.children[items[0]],headerTable,count)#元素链表更新函数#nodeToTest为待被更新的元素链表的头部#targetNode为待加入到元素链表的元素节点def updateHeader(nodeToTest,targetNode):#若待被更新的元素链表当前元素的下一个元素不为空则一直迭代寻找该元素链表的末位元素while nodeToTest.nodeLink!None: nodeToTestnodeToTest.nodeLink #类似撸绳子从首位一个一个逐渐撸到末位#找到该元素链表的末尾元素后在此元素后追加targetNode为该元素链表的新末尾元素nodeToTest.nodeLinktargetNode
测试
#加载简单数据集
def loadSimpDat():simpDat [[r, z, h, j, p],[z, y, x, w, v, u, t, s],[z],[r, x, n, o, s],[y, r, x, z, q, t, p],[y, z, x, e, q, s, t, m]]return simpDat#将列表格式的数据集转化为字典格式
def createInitSet(dataSet):retDict{}for trans in dataSet:retDict[frozenset(trans)]1return retDictsimpDatloadSimpDat()
dataSetcreateInitSet(simpDat)
myFPtree1,myHeaderTab1createTree(dataSet,minSup3)
myFPtree1.disp(),myHeaderTab1输入数据 由此数据集构建的FP树长这样看看是不是满足上一节介绍的FP树结构 3.4 从FP树中挖掘频繁项集
具体过程如下
1 从FP树中获得条件模式基
条件模式基以所查找元素项为结尾的路径集合每条路径都是一条前缀路径路径集合包括前缀路径和路径计数值。例如元素r的条件模式基为 {x,s}2,{z,x,y}1,{z}1前缀路径介于所查找元素和树根节点之间的所有内容路径计数值等于该条前缀路径的起始元素项即所查找的元素的计数值
2 利用条件模式基构建相应元素的条件FP树
对每个频繁项都要创建一棵条件FP树。例如对元素t创建条件FP树使用获得的t元素的条件模式基作为输入利用构建FP树相同的逻辑构建元素t的条件FP树
3 迭代步骤(1)(2)直到树包含一个元素项为止 接下来继续构建{t,x}{t,y}{t,z}对应的条件FP树(tx,ty,tz为t条件FP树的频繁项集)直到条件FP树中没有元素为止 至此可以得到与元素t相关的频繁项集包括2元素项集、3元素项集。。。 #由叶节点回溯该叶节点所在的整条路径
#leafNode为叶节点treeNode格式prefixPath为该叶节点的前缀路径集合列表格式在调用该函数前注意prefixPath的已有内容
def ascendTree(leafNode,prefixPath):if leafNode.parent!None:prefixPath.append(leafNode.name)ascendTree(leafNode.parent,prefixPath)#获得指定元素的条件模式基
#basePat为指定元素treeNode为指定元素链表的第一个元素节点如指定r元素则treeNode为r元素链表的第一个r节点
def findPrefixPath(basePat,treeNode):condPats{} #存放指定元素的条件模式基while treeNode!None: #当元素链表指向的节点不为空时即尚未遍历完指定元素的链表时prefixPath[]ascendTree(treeNode,prefixPath) #回溯该元素当前节点的前缀路径if len(prefixPath)1:condPats[frozenset(prefixPath[1:])]treeNode.count #构造该元素当前节点的条件模式基treeNodetreeNode.nodeLink #指向该元素链表的下一个元素return condPats#有FP树挖掘频繁项集
#inTree: 构建好的整个数据集的FP树
#headerTable: FP树的头指针表
#minSup: 最小支持度用于构建条件FP树
#preFix: 新增频繁项集的缓存表set([])格式
#freqItemList: 频繁项集集合list格式def mineTree(inTree,headerTable,minSup,preFix,freqItemList):#按头指针表中元素出现次数升序排序即从头指针表底端开始寻找频繁项集bigL[v[0] for v in sorted(headerTable.items(),keylambda p:p[1][0])] for basePat in bigL:#将当前深度的频繁项追加到已有频繁项集中然后将此频繁项集追加到频繁项集列表中newFreqSetpreFix.copy()newFreqSet.add(basePat)print(freqItemList add newFreqSet,newFreqSet)freqItemList.append(newFreqSet)#获取当前频繁项的条件模式基condPatBasesfindPrefixPath(basePat,headerTable[basePat][1])#利用当前频繁项的条件模式基构建条件FP树myCondTree,myHeadcreateTree(condPatBases,minSup)#迭代直到当前频繁项的条件FP树为空if myHead!None:mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)接着刚才构建的FP树测试一下
freqItems[]
mineTree(myFPtree1,myHeaderTab1,3,set([]),freqItems)
freqItems我们从FP树中挖掘到的频繁项集如下这里设置的最小支持度为3 上图表示数据集中支持度大于3(出现3次以上)的元素项集即频繁项集。
4 系统设计展示
为了方便操作及理解学长使用 Python 的 tkinter 模块设计了一个系统操作界面 分析可视化 (未完待续。。。。)
5 最后 更多资料, 项目分享
https://gitee.com/dancheng-senior/postgraduate
