竞赛 题目:基于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.name=nameValue #节点名
            self.count=numOccur #节点元素出现次数
            self.nodeLink=None #存放节点链表中,与该节点相连的下一个元素
            self.parent=parentNode
            self.children={} #用于存放节点的子节点,value为子节点名
        
        def inc(self,numOccur):
            self.count+=numOccur
        
        def disp(self,ind=1):
            print("   "*ind,self.name,self.count) #输出一行节点名和节点元素数,缩进表示该行节点所处树的深度
            for child in self.children.values():
                child.disp(ind+1) #对于子节点,深度+1
    
    # 构造FP树
    # dataSet为字典类型,表示探索频繁项集的数据集,keys为各项集,values为各项集在数据集中出现的次数
    # minSup为最小支持度,构造FP树的第一步是计算数据集各元素的支持度,选择满足最小支持度的元素进入下一步
    def createTree(dataSet,minSup=1):
        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]
        freqItemSet=set(headerTable.keys())
        
        #若没有元素满足最小支持度要求,返回None,结束函数
        if len(freqItemSet)==0:
            return None,None
        for key in headerTable.keys():
            headerTable[key]=[headerTable[key],None] #[元素出现次数,**指向每种项集第一个元素项的指针**]
        retTree=treeNode("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(),key=operator.itemgetter(1),reverse=True)] #根据元素全局出现次数对每个项集(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的情况,对剩下的元素迭代updateTree
        if len(items)>1:
            updateTree(items[1::],inTree.children[items[0]],headerTable,count)


    #元素链表更新函数
    #nodeToTest为待被更新的元素链表的头部
    #targetNode为待加入到元素链表的元素节点
    def updateHeader(nodeToTest,targetNode):
        #若待被更新的元素链表当前元素的下一个元素不为空,则一直迭代寻找该元素链表的末位元素
        while nodeToTest.nodeLink!=None: 
            nodeToTest=nodeToTest.nodeLink #类似撸绳子,从首位一个一个逐渐撸到末位
        #找到该元素链表的末尾元素后,在此元素后追加targetNode为该元素链表的新末尾元素
        nodeToTest.nodeLink=targetNode



测试

#加载简单数据集
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)]=1
    return retDict

simpDat=loadSimpDat()
dataSet=createInitSet(simpDat)
myFPtree1,myHeaderTab1=createTree(dataSet,minSup=3)
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 #构造该元素当前节点的条件模式基
            treeNode=treeNode.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(),key=lambda p:p[1][0])] 
        for basePat in bigL:
            #将当前深度的频繁项追加到已有频繁项集中,然后将此频繁项集追加到频繁项集列表中
            newFreqSet=preFix.copy()
            newFreqSet.add(basePat)
            print("freqItemList add newFreqSet",newFreqSet)
            freqItemList.append(newFreqSet)
            #获取当前频繁项的条件模式基
            condPatBases=findPrefixPath(basePat,headerTable[basePat][1])
            #利用当前频繁项的条件模式基构建条件FP树
            myCondTree,myHead=createTree(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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/139687.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JavaScript 基本数据类型

字符串 在JS中&#xff0c;数据类型有&#xff1a;字符串、数字、布尔、数组、对象、Null、Undefined 用到最多的还是字符串和数组的转换。 <!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>首页</title><style&g…

Rust语言做数据抓取代码示例

这个任务需要使用到Rust语言和网络爬虫相关的库&#xff0c;以下是一个简单的示例代码。请注意&#xff0c;由于涉及到的具体问题和数据的复杂性&#xff0c;这个示例可能并不能直接满足你的需求&#xff0c;需要根据你的具体情况进行修改和扩展。 use reqwest; use serde::{De…

Splashtop 如何维护 GDPR 合规性

2018年&#xff0c;欧盟颁布了一项新法律&#xff0c;以保护欧洲公民的个人数据免遭任何收集数据的人不当处理。这可能意味着企业和组织&#xff0c;包括面对面和虚拟形式。这项开创性的法律为其他立法铺平了道路&#xff0c;例如加利福尼亚州的《加州消费者隐私法》&#xff0…

linux线程

文章目录 前言一、线程1、线程概念2、线程使用2.1 pthread_create2.2 线程共享数据和私有数据2.3 为什么线程切换的成本更低&#xff1f; 3、线程性质3.1 线程的优点3.2 线程的缺点3.3 线程异常3.4 线程用途 4、vfork接口 二、线程控制1、线程创建2、线程等待3、线程退出4、线程…

行业追踪,2023-11-13

自动复盘 2023-11-13 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…

集成Line、Facebook、Twitter、Google、微信、QQ、微博、支付宝的三方登录sdk

下载地址&#xff1a; https://githubfast.com/anerg2046/sns_auth 安装方式建议使用composer进行安装 如果linux执行composer不方便的话&#xff0c;可以在本地新建个文件夹&#xff0c;然后执行上面的composer命令&#xff0c;把代码sdk和composer文件一起上传到项目适当位…

【STM32】定时器+基本定时器

一、定时器的基本概述 1.软件定时器原理 原来我们使用51单片机的时候&#xff0c;是通过一个__nop()__来进行延时 我们通过软件的方式来进行延时功能是不准确的&#xff0c;受到很多不确定因素。 2.定时器原理&#xff1a;计数之间的比值 因为使用软件延时受到影响&#xff0c…

Scala---介绍及安装使用

一、Scala介绍 1. 为什么学习Scala语言 Scala是基于JVM的语言&#xff0c;与java语言类似&#xff0c;Java语言是基于JVM的面向对象的语言。Scala也是基于JVM&#xff0c;同时支持面向对象和面向函数的编程语言。这里学习Scala语言的原因是后期我们会学习一个优秀的计算框架S…

企业如何管理员工电脑和规范电脑的使用

企业如何管理员工电脑和规范电脑的使用 在现代信息时代&#xff0c;数据安全问题已经成为各个领域都面临的挑战。随着大数据的快速发展和互联网的普及&#xff0c;数据泄露的风险也逐渐增加。而作为企业或个人用户&#xff0c;如何保护自己的数据&#xff0c;避免泄露给不法分…

ios 对话框UIAlertController放 tableview

//强弱引用 #define kWeakSelf(type)__weak typeof(type)weak##type type; -(void) showUIAlertTable {kWeakSelf(self)UIAlertController *alert [UIAlertController alertControllerWithTitle:NSLocalizedString("select_stu", nil) message:nil prefer…

构建Docker基础镜像(ubuntu20.04+python3.9.10+pytorch-gpu-cuda11.8)

文章目录 一、前置条件1.创建 ubuntu 镜像源文件【sources.list】2.下载 python 安装包【Python-3.9.10.tgz】 二、构建方法1.构建目录2.创建DockerFile3.打包镜像 一、前置条件 配置一下 ubuntu 的镜像源下载 python 安装包 1.创建 ubuntu 镜像源文件【sources.list】 内容…

麒麟信安登录央视,深度展现为中国信息安全铸“魂”之路

麒麟信安登录央视&#xff0c;深度展现为中国信息安全铸“魂”之路 近日&#xff0c;麒麟信安登录央视频道&#xff0c;《麒麟信安——为中国信息安全铸“魂”》在CCTV-4中文国际频道、CCTV-7国防军事频道、CCTV-10 科教频道、CCTV-12社会与法频道、CCTV-17农业农村频道&#x…

动态调整学习率Lr

动态调整学习率Lr 0 引入1 代码例程1.1 工作方式解释 2 动态调整学习率的几种方法2.1 lr_scheduler.LambdaLR2.2 lr_scheduler.StepLR2.3 lr_scheduler.MultiStepLR2.4 lr_scheduler.ExponentialLR2.2.5 lr_scheduler.CosineAnnealingLR2.6 lr_scheduler.ReduceLROnPlateau2.7 …

后门程序2

System\CurrentControlSet\Services\Disk\Enum Windows 操作系统注册表中的一个路径。这个路径通常包含有关磁盘设备的信息。在这个特定的路径下&#xff0c;可能存储了有关磁盘枚举的配置和参数 Enum&#xff08;枚举&#xff09;子键通常包含了系统对磁盘的枚举信息&#xf…

网络安全/黑客技术(0基础入门到进阶提升)

前言 前几天发布了一篇 网络安全&#xff08;黑客&#xff09;自学 没想到收到了许多人的私信想要学习网安黑客技术&#xff01;却不知道从哪里开始学起&#xff01;怎么学 今天给大家分享一下&#xff0c;很多人上来就说想学习黑客&#xff0c;但是连方向都没搞清楚就开始学习…

高通SDX12:ASoC 音频框架浅析

一、简介 ASoC–ALSA System on Chip ,是建立在标准ALSA驱动层上,为了更好地支持嵌入式处理器和移动设备中的音频Codec的一套软件体系。 本文基于高通SDX12平台,对ASoC框架做一个分析。 二、整体框架 1. 硬件层面 嵌入式Linux设备的Audio subsystem可以划分为Machine(板…

关于企业海外Social平台营销布局,你需要了解这三件事

01 企业Social营销布局模式 Social营销走到现在&#xff0c;早已进入了标准配置期。任何企业和组织&#xff0c;进行营销宣传的时候都会在社媒社交平台上创建账号和运营。目前&#xff0c;海外Social平台营销模式基本分为四类&#xff1a; 官方社媒账号运营&#xff1a;以Hoot…

HTML5学习系列之主结构

HTML5学习系列之主结构 前言HTML5主结构定义页眉定义导航定义主要区域定义文章块定义区块定义附栏定义页脚 具体使用总结 前言 学习记录 HTML5主结构 定义页眉 head表示页眉&#xff0c;用来表示标题栏&#xff0c;引导和导航作用的结构元素。 <header role"banner…

使用Python和requests库的简单爬虫程序

这是一个使用Python和requests库的简单爬虫程序。我们将使用代理来爬取网页内容。以下是代码和解释&#xff1a; import requests from fake_useragent import UserAgent # 每行代理信息 proxy_host "jshk.com.cn" # 创建一个代理器 proxy {http: http:// proxy_…

SQLServer添加Oracle链接服务器

又一次在项目中用到了在SQLServer添加Oracle链接服务器&#xff0c;发现之前文章写的也不太好使&#xff0c;那就再总结一次吧。 1、安装OracleClient 安装64位&#xff0c;多数SQLServer是64位&#xff0c;所以OracleClient也安装64位的&#xff1b; 再一个一般安装的Oracl…