精华内容
下载资源
问答
  • 【空间模式挖掘】POI频繁同位模式

    千次阅读 2021-11-13 12:40:06
    数据 实验区:昆明市呈贡区 实验数据:14个类型(如下) 共约8000个POI 方法 参数设置:以科教文化服务POI...挖掘得满足最小支持度和最小置信度的频繁同位模式、同位规则以及对应支持度和置信度。 (主要参考.

    数据

    • 实验区:昆明市呈贡区
    • 实验数据:14个类型(如下) 共约8000个POI

    Apriori挖掘

    前期处理

    • 参数设置:以科教文化服务POI作为中心类别,设定距离范围(缓冲区半径)为300m

    用户设定中心类别、空间相关距离和分析范围,检索得到同位模式实例集

    以分析范围内中心类别POI作为中心,相关距离为半径划定一个样本范围,此样本范围内的所有类别组成一个事务,形成事务集合,即同位模式实例集。遍历事务集合得到项目集合。

    挖掘得满足最小支持度和最小置信度的频繁同位模式、同位规则以及对应支持度和置信度。

    (主要参考文献:纪莹莹. 互联网POI同位模式挖掘方法研究[D].山东农业大学,2014.)

    • ArcGIS叠置分析:将缓冲区面序号附到POI点
    • Excel简单处理:即合并同一缓冲区内的POI类别号

    •  POI同位模式挖掘:Apriori算法
    • 补充“同位模式挖掘是否需要考虑数量”:其实同位模式挖掘中也是要考虑数量的,同位模式的频繁性是由其实例的频繁邻近程度来决定的,虽然最后的模式呈现上只有类别,但在挖掘过程中大部分的事情是在搜索每个特征下的实例组成的团。上述做法则为另外一种思路:将空间事物和邻近关系转化成事务数据库,然后使用事务数据库中的频繁项集挖掘方法进行挖掘,该做法有一定的缺陷性:进行事务数据库转化时,可能会丢失邻近关系。 

    结果

    • 请输入最小支持度(如0.05)和最小置信度(如0.6)
      0.8 0.8

    • 结果解析:在最小支持度与最小置信度均设为0.8时,POI频繁3-项集为{8, 9, 3},对应:
    {科教文化服务, 生活服务, 公共设施}
    • 在最小支持度与最小置信度均设为0.5时,POI频繁5-项集对应:
    {科教文化服务, 生活服务, 住宿服务, 体育休闲服务, 公共设施}
    {科教文化服务, 生活服务, 住宿服务, 公共设施, 医疗保健服务}
    {科教文化服务, 生活服务, 体育休闲服务, 公共设施, 医疗保健服务}
    {科教文化服务, 生活服务, 公共设施, 公司企业, 医疗保健服务}
    {科教文化服务, 生活服务, 公共设施, 医疗保健服务, 政府机构及社会团体}

    Apriori优化:FPTree挖掘

    代码

    package FPTree3;
    
    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.io.IOException;
    import java.text.DecimalFormat;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.Set;
    
    
    
    public class FPTree {
        /**频繁模式的最小支持数**/
        private int minSuport;
        /**关联规则的最小置信度**/
        private double confident;
        /**事务项的总数**/
        private int totalSize;
        /**存储每个频繁项及其对应的计数**/
        private Map<List<String>, Integer> frequentMap = new HashMap<List<String>, Integer>();
        /**关联规则中,哪些项可作为被推导的结果,默认情况下所有项都可以作为被推导的结果**/
        private Set<String> decideAttr = null;
    
        public int getMinSuport() {
            return this.minSuport;
        }
    
        /**
         * 设置最小支持数
         * 
         * @param minSuport
         */
        public void setMinSuport(int minSuport) {
            this.minSuport = minSuport;
        }
    
        public double getConfident() {
            return confident;
        }
    
        /**
         * 设置最小置信度
         * 
         * @param confident
         */
        public void setConfident(double confident) {
            this.confident = confident;
        }
    
        /**
         * 设置决策属性。如果要调用{@linkplain #readTransRocords(String[])},需要在调用{@code readTransRocords}之后再调用{@code setDecideAttr}
         * 
         * @param decideAttr
         */
        public void setDecideAttr(Set<String> decideAttr) {
            this.decideAttr = decideAttr;
        }
    
        /**
         * 获取频繁项集
         * 
         * @return
         * @Description:
         */
        public Map<List<String>, Integer> getFrequentItems() {
            return frequentMap;
        }
    
        public int getTotalSize() {
            return totalSize;
        }
    
        /**
         * 根据一条频繁模式得到若干关联规则
         * 
         * @param list
         * @return
         */
        private List<StrongAssociationRule> getRules(List<String> list) {
            List<StrongAssociationRule> rect = new LinkedList<StrongAssociationRule>();
            if (list.size() > 1) {
                for (int i = 0; i < list.size(); i++) {
                    String result = list.get(i);
                    if (decideAttr.contains(result)) {
                        List<String> condition = new ArrayList<String>();
                        condition.addAll(list.subList(0, i));
                        condition.addAll(list.subList(i + 1, list.size()));
                        StrongAssociationRule rule = new StrongAssociationRule();
                        rule.condition = condition;
                        rule.result = result;
                        rect.add(rule);
                    }
                }
            }
            return rect;
        }
    
        /**
         * 从若干个文件中读入Transaction Record,同时把所有项设置为decideAttr
         * 
         * @param filenames
         * @return
         * @Description:
         */
        public List<List<String>> readTransRocords(String[] filenames) {
            Set<String> set = new HashSet<String>();
            List<List<String>> transaction = null;
            if (filenames.length > 0) {
                transaction = new LinkedList<List<String>>();
                for (String filename : filenames) {
                    try {
                        FileReader fr = new FileReader(filename);
                        BufferedReader br = new BufferedReader(fr);
                        try {
                            String line = null;
                            // 一项事务占一行
                            while ((line = br.readLine()) != null) {
                                if (line.trim().length() > 0) {
                                    // 每个item之间用","分隔
                                    String[] str = line.split(",");
                                    //每一项事务中的重复项需要排重
                                    Set<String> record = new HashSet<String>();
                                    for (String w : str) {
                                        record.add(w);
                                        set.add(w);
                                    }
                                    List<String> rl = new ArrayList<String>();
                                    rl.addAll(record);
                                    transaction.add(rl);
                                }
                            }
                        } finally {
                            br.close();
                        }
                    } catch (IOException ex) {
                        System.out.println("Read transaction records failed." + ex.getMessage());
                        System.exit(1);
                    }
                }
            }
    
            this.setDecideAttr(set);
            return transaction;
        }
    
        /**
         * 生成一个序列的各种子序列。(序列是有顺序的)
         * 
         * @param residualPath
         * @param results
         */
        private void combine(LinkedList<TreeNode> residualPath, List<List<TreeNode>> results) {
            if (residualPath.size() > 0) {
                //如果residualPath太长,则会有太多的组合,内存会被耗尽的
                TreeNode head = residualPath.poll();
                List<List<TreeNode>> newResults = new ArrayList<List<TreeNode>>();
                for (List<TreeNode> list : results) {
                    List<TreeNode> listCopy = new ArrayList<TreeNode>(list);
                    newResults.add(listCopy);
                }
    
                for (List<TreeNode> newPath : newResults) {
                    newPath.add(head);
                }
                results.addAll(newResults);
                List<TreeNode> list = new ArrayList<TreeNode>();
                list.add(head);
                results.add(list);
                combine(residualPath, results);
            }
        }
    
        private boolean isSingleBranch(TreeNode root) {
            boolean rect = true;
            while (root.getChildren() != null) {
                if (root.getChildren().size() > 1) {
                    rect = false;
                    break;
                }
                root = root.getChildren().get(0);
            }
            return rect;
        }
    
        /**
         * 计算事务集中每一项的频数
         * 
         * @param transRecords
         * @return
         */
        private Map<String, Integer> getFrequency(List<List<String>> transRecords) {
            Map<String, Integer> rect = new HashMap<String, Integer>();
            for (List<String> record : transRecords) {
                for (String item : record) {
                    Integer cnt = rect.get(item);
                    if (cnt == null) {
                        cnt = new Integer(0);
                    }
                    rect.put(item, ++cnt);
                }
            }
            return rect;
        }
    
        /**
         * 根据事务集合构建FPTree
         * 
         * @param transRecords
         * @Description:
         */
        public void buildFPTree(List<List<String>> transRecords) {
            totalSize = transRecords.size();
            //计算每项的频数
            final Map<String, Integer> freqMap = getFrequency(transRecords);
            //先把频繁1项集添加到频繁模式中
            //        for (Entry<String, Integer> entry : freqMap.entrySet()) {
            //            String name = entry.getKey();
            //            int cnt = entry.getValue();
            //            if (cnt >= minSuport) {
            //                List<String> rule = new ArrayList<String>();
            //                rule.add(name);
            //                frequentMap.put(rule, cnt);
            //            }
            //        }
            //每条事务中的项按F1排序
            for (List<String> transRecord : transRecords) {
                Collections.sort(transRecord, new Comparator<String>() {
                    @Override
                    public int compare(String o1, String o2) {
                        return freqMap.get(o2) - freqMap.get(o1);
                    }
                });
            }
            FPGrowth(transRecords, null);
        }
    
        /**
         * FP树递归生长,从而得到所有的频繁模式
         * 
         * @param cpb  条件模式基
         * @param postModel   后缀模式
         */
        private void FPGrowth(List<List<String>> cpb, LinkedList<String> postModel) {
            //        System.out.println("CPB is");
            //        for (List<String> records : cpb) {
            //            System.out.println(records);
            //        }
            //        System.out.println("PostPattern is " + postPattern);
    
            Map<String, Integer> freqMap = getFrequency(cpb);
            Map<String, TreeNode> headers = new HashMap<String, TreeNode>();
            for (Entry<String, Integer> entry : freqMap.entrySet()) {
                String name = entry.getKey();
                int cnt = entry.getValue();
                //每一次递归时都有可能出现一部分模式的频数低于阈值
                if (cnt >= minSuport) {
                    TreeNode node = new TreeNode(name);
                    node.setCount(cnt);
                    headers.put(name, node);
                }
            }
    
            TreeNode treeRoot = buildSubTree(cpb, freqMap, headers);
            //如果只剩下虚根节点,则递归结束
            if ((treeRoot.getChildren() == null) || (treeRoot.getChildren().size() == 0)) {
                return;
            }
    
            //如果树是单枝的,则直接把“路径的各种组合+后缀模式”添加到频繁模式集中。这个技巧是可选的,即跳过此步进入下一轮递归也可以得到正确的结果
            if (isSingleBranch(treeRoot)) {
                LinkedList<TreeNode> path = new LinkedList<TreeNode>();
                TreeNode currNode = treeRoot;
                while (currNode.getChildren() != null) {
                    currNode = currNode.getChildren().get(0);
                    path.add(currNode);
                }
                //调用combine时path不宜过长,否则会OutOfMemory
                if (path.size() <= 20) {
                    List<List<TreeNode>> results = new ArrayList<List<TreeNode>>();
                    combine(path, results);
                    for (List<TreeNode> list : results) {
                        int cnt = 0;
                        List<String> rule = new ArrayList<String>();
                        for (TreeNode node : list) {
                            rule.add(node.getName());
                            cnt = node.getCount();//cnt最FPTree叶节点的计数
                        }
                        if (postModel != null) {
                            rule.addAll(postModel);
                        }
                        frequentMap.put(rule, cnt);
                    }
                    return;
                } else {
                    System.err.println("length of path is too long: " + path.size());
                }
            }
    
            for (TreeNode header : headers.values()) {
                List<String> rule = new ArrayList<String>();
                rule.add(header.getName());
                if (postModel != null) {
                    rule.addAll(postModel);
                }
                //表头项+后缀模式  构成一条频繁模式(频繁模式内部也是按照F1排序的),频繁度为表头项的计数
                frequentMap.put(rule, header.getCount());
                //新的后缀模式:表头项+上一次的后缀模式(注意保持顺序,始终按F1的顺序排列)
                LinkedList<String> newPostPattern = new LinkedList<String>();
                newPostPattern.add(header.getName());
                if (postModel != null) {
                    newPostPattern.addAll(postModel);
                }
                //新的条件模式基
                List<List<String>> newCPB = new LinkedList<List<String>>();
                TreeNode nextNode = header;
                while ((nextNode = nextNode.getNextHomonym()) != null) {
                    int counter = nextNode.getCount();
                    //获得从虚根节点(不包括虚根节点)到当前节点(不包括当前节点)的路径,即一条条件模式基。注意保持顺序:你节点在前,子节点在后,即始终保持频率高的在前
                    LinkedList<String> path = new LinkedList<String>();
                    TreeNode parent = nextNode;
                    while ((parent = parent.getParent()).getName() != null) {//虚根节点的name为null
                        path.push(parent.getName());//往表头插入
                    }
                    //事务要重复添加counter次
                    while (counter-- > 0) {
                        newCPB.add(path);
                    }
                }
                FPGrowth(newCPB, newPostPattern);
            }
        }
    
        /**
         * 把所有事务插入到一个FP树当中
         * 
         * @param transRecords
         * @param F1
         * @return
         */
        private TreeNode buildSubTree(List<List<String>> transRecords,
                                      final Map<String, Integer> freqMap,
                                      final Map<String, TreeNode> headers) {
            TreeNode root = new TreeNode();//虚根节点
            for (List<String> transRecord : transRecords) {
                LinkedList<String> record = new LinkedList<String>(transRecord);
                TreeNode subTreeRoot = root;
                TreeNode tmpRoot = null;
                if (root.getChildren() != null) {
                    //延已有的分支,令各节点计数加1
                    while (!record.isEmpty()
                           && (tmpRoot = subTreeRoot.findChild(record.peek())) != null) {
                        tmpRoot.countIncrement(1);
                        subTreeRoot = tmpRoot;
                        record.poll();
                    }
                }
                //长出新的节点
                addNodes(subTreeRoot, record, headers);
            }
            return root;
        }
    
        /**
         * 往特定的节点下插入一串后代节点,同时维护表头项到同名节点的链表指针
         * 
         * @param ancestor
         * @param record
         * @param headers
         */
        private void addNodes(TreeNode ancestor, LinkedList<String> record,
                              final Map<String, TreeNode> headers) {
            while (!record.isEmpty()) {
                String item = (String) record.poll();
                //单个项的出现频数必须大于最小支持数,否则不允许插入FP树。达到最小支持度的项都在headers中。每一次递归根据条件模式基本建立新的FPTree时,把要把频数低于minSuport的排除在外,这也正是FPTree比穷举法快的真正原因
                if (headers.containsKey(item)) {
                    TreeNode leafnode = new TreeNode(item);
                    leafnode.setCount(1);
                    leafnode.setParent(ancestor);
                    ancestor.addChild(leafnode);
    
                    TreeNode header = headers.get(item);
                    TreeNode tail=header.getTail();
                    if(tail!=null){
                        tail.setNextHomonym(leafnode);
                    }else{
                        header.setNextHomonym(leafnode);
                    }
                    header.setTail(leafnode);
                    addNodes(leafnode, record, headers);
                }
                //                        else {
                //                            System.err.println(item + " is not F1");
                //                        }
            }
        }
    
        /**
         * 获取所有的强规则
         * 
         * @return
         */
        public List<StrongAssociationRule> getAssociateRule() {
            assert totalSize > 0;
            List<StrongAssociationRule> rect = new ArrayList<StrongAssociationRule>();
            //遍历所有频繁模式
            for (Entry<List<String>, Integer> entry : frequentMap.entrySet()) {
                List<String> items = entry.getKey();
                int count1 = entry.getValue();
                //一条频繁模式可以生成很多关联规则
                List<StrongAssociationRule> rules = getRules(items);
                //计算每一条关联规则的支持度和置信度
                for (StrongAssociationRule rule : rules) {
                    if (frequentMap.containsKey(rule.condition)) {
                        int count2 = frequentMap.get(rule.condition);
                        double confidence = 1.0 * count1 / count2;
                        if (confidence >= this.confident) {
                            rule.support = count1;
                            rule.confidence = confidence;
                            rect.add(rule);
                        }
                    } else {
                        System.err.println(rule.condition + " is not a frequent pattern, however "
                                           + items + " is a frequent pattern");
                    }
                }
            }
            return rect;
        }
    
        public static void main(String[] args) throws IOException {
            String infile = "……POI_886.txt";
            FPTree fpTree = new FPTree();
            fpTree.setConfident(0.2);
            fpTree.setMinSuport(709);
            if (args.length >= 2) {
                double confidence = Double.parseDouble(args[0]);
                int suport = Integer.parseInt(args[1]);
                fpTree.setConfident(confidence);
                fpTree.setMinSuport(suport);
            }
    
            List<List<String>> trans = fpTree.readTransRocords(new String[] { infile });
            Set<String> decideAttr = new HashSet<String>();
            decideAttr.add("9");
            //decideAttr.add("3");
            fpTree.setDecideAttr(decideAttr);
            long begin = System.currentTimeMillis();
            fpTree.buildFPTree(trans);
            long end = System.currentTimeMillis();
            System.out.println("buildFPTree use time " + (end - begin));
            Map<List<String>, Integer> pattens = fpTree.getFrequentItems();
    
            String outfile = "pattens.txt";
            BufferedWriter bw = new BufferedWriter(new FileWriter(outfile));
            System.out.println("模式\t频数");
            bw.write("模式\t频数");
            bw.newLine();
            for (Entry<List<String>, Integer> entry : pattens.entrySet()) {
                System.out.println(entry.getKey() + "\t" + entry.getValue());
                bw.write(joinList(entry.getKey()) + "\t" + entry.getValue());
                bw.newLine();
            }
            bw.close();
            System.out.println();
            List<StrongAssociationRule> rules = fpTree.getAssociateRule();
    
            outfile = "rule.txt";
            bw = new BufferedWriter(new FileWriter(outfile));
            System.out.println("条件\t结果\t支持度\t置信度");
            bw.write("条件\t结果\t支持度\t置信度");
            bw.newLine();
            DecimalFormat dfm = new DecimalFormat("#.##");
            for (StrongAssociationRule rule : rules) {
                System.out.println(rule.condition + "->" + rule.result + "\t" + dfm.format(rule.support)
                                   + "\t" + dfm.format(rule.confidence));
                bw.write(rule.condition + "->" + rule.result + "\t" + dfm.format(rule.support) + "\t"
                         + dfm.format(rule.confidence));
                bw.newLine();
            }
            bw.close();
    
        }
    
        private static String joinList(List<String> list) {
            if (list == null || list.size() == 0) {
                return "";
            }
            StringBuilder sb = new StringBuilder();
            for (String ele : list) {
                sb.append(ele);
                sb.append(",");
            }
            //把最后一个逗号去掉
            return sb.substring(0, sb.length() - 1);
        }
    }

    结果

    展开全文
  • 上一章:假定输入数据由称作项的二元属性组成。...当涉及数据中的负相关时,如大家一般不会同时购买黄油与人造黄油——这种负相关模式有助于识别竞争项,即可以相互替代的项。////////// 某些非频繁

    处理分类属性

    • 上一章:假定输入数据由称作项的二元属性组成。
    • 本章:扩展到具有对称二元属性、分类属性、连续属性的数据集。
    • 处理分类属性:通过将其转换成二元项表示,即二元化

    处理连续属性

    • 处理连续属性:基于离散化的方法(划分区间)、基于统计学的方法、非离散化方法。
    • 基于统计学的方法:①产生规则(借助均值、中位数、方差等统计量):如{年收入>¥100K,网上购物=是} →年龄:均值=38  ②确认规则:如,为了确定产生的平均年龄是否有统计意义,应当使用统计假设检验方法,进行检验。
    • 非离散化方法:eg 文档-词矩阵

    频繁子图挖掘

    •  eg:Web图中,顶点对应于Web页面,边表示Web页面之间的超链接。

    • 频繁子图挖掘:给定图的集合、支持度阈值minsup,频繁子图挖掘的目标是找出所有使得s(g)≥minsup的子图。

    • 开发类(似)Apriori算法→挖掘频繁子图:图表示→事务表示

    • 广义上讲, 知识图谱是一种图数据, 因此可基于已有的频繁子图模式挖掘算法获得知识图谱的模式信息

     非频繁模式

    • 模式挖掘是一个比频繁模式挖掘更一般的术语,因为前者还涵盖了稀有模式和负模式。【非频繁模式:支持度<阈值minsup的项集或规则】
    • 稀有模式:某些非频繁模式也可能暗示数据中出现了有趣的罕见事件或例外情况:eg如果{火灾=yes}频繁,而{火灾=yes,警报=on}非频繁,则可能说明警报系统故障。
    • 负模式:当涉及数据中的负相关时,如大家一般不会同时购买黄油与人造黄油——这种负相关模式有助于识别竞争项,即可以相互替代的项。

    零碎知识

    • 序列模式:考虑时间或空间的先后次序

    展开全文
  • 关联规则--Apriori算法部分讨论的关联模式概念都强调同时出现关系,而忽略数据中的序列信息(时间/空间):...注:1)序列模型=关联规则+时间/空间维度2)这里讨论的序列模式挖掘指的是时间维度上的挖掘。一、基本定义序...

    关联规则--Apriori算法部分讨论的关联模式概念都强调同时出现关系,而忽略数据中的序列信息(时间/空间):

    时间序列:顾客购买产品X,很可能在一段时间内购买产品Y;

    空间序列:在某个点发现了现象A,很可能在下一个点发现现象Y。

    例:6个月以前购买奔腾PC的客户很可能在一个月内订购新的CPU芯片。

    注:1)序列模型=关联规则+时间/空间维度

    2)这里讨论的序列模式挖掘指的是时间维度上的挖掘。

    一、基本定义

    序列:将与对象A有关的所有事件按时间戳增序排列,就得到对象A的一个序列s。

    元素(事务):序列是事务的有序列表,可记作

    cb083ff9c7f9ca046b1c945c2bca9e7a.png,其中每个

    f17d87c59134d7ff4cd895b70d9569e3.png是一个或多个事件(项)的集族,即

    0ac0912851a36381717bb87e100dfa44.png

    序列的长度:序列中元素的个数。

    序列的大小:序列中事件的个数,K-序列是包含k个事件的序列。

    如:如下课程序列中包含4个元素,8个事件。

    5a31f4a9bb9528e37cc1118c2c7a1388.png

    子序列:序列t是另一个序列s的子序列,若t中每个有序元素都是s中一个有序元素的子集。即,序列

    1df1cd9861d49ddc14c4f3ca8fb6adc4.png是序列

    0558ac7dadcb0c8eb416f15cad3d935e.png的子序列,若存在整数

    91cb5d63f2832ec67abb443e58ad8ca4.png,使得

    be01bf0f243daecc09bf01746c611f6b.png

    例:

    d922b8732ee73291e139d3fdacb69208.png

    序列数据库:包含一个或多个序列数据的数据集,如下:

    ee9ffc5ed7a74c0ea25572c488d93c24.png

    二、序列模式挖掘

    序列的支持度:序列s的支持度指包含s的所有数据序列(与单个数据对象(上例中的A/B/C)相关联的事件的有序列表)所占的比例,若序列s的支持度大于或等于minsup,则称s是一个序列模式(频繁序列)。

    序列模式挖掘:给定序列数据集D和用户指定的最小支持度minsup,找出支持度大于或等于minsup的所有序列。

    例:下例中,假设minsup=50%,因为序列(子序列)包含在A,B,C中,所以其支持度=3/5=0.6,其他类似。

    44f3e755f9627ae47aeed9d45aebfe34.png

    产生序列模式

    1、蛮力法

    枚举所有可能的序列,并统计它们各自的支持度。值得注意的是:候选序列的个数比候选项集的个数大得多,两个原因如下:

    d719561ef8d4bbe3e1977d480165d5cb.png

    2、类Apriori算法

    候选过程:一对频繁(k-1)序列合并,产生候选k-序列。为不重复产生,合并原则如下:

    序列S1与序列S2合并,仅当从S1中去掉第一个事件得到的子序列与从S2中去掉最后一个事件得到的子序列相同,合并结果为S1与S2最后一个事件的连接,连接方式有两种:

    1)若S2的最后两个事件属于相同的元素,则S2的最后一个事件在合并后的序列中是S1的最后一个元素的一部分;

    2)若S2的最后两个事件属于不同的元素,则S2的最后一个事件在合并后的序列中成为连接到S1的尾部的单独元素。

    例:

    + = :除去S1中第一个事件(1)与除去S2中最后一个事件(4)所剩下的子序列均为,且S2最后两个事件(3)(4)属于不同的元素,故单独列出;

    + = :除去事件2和事件4,剩下子序列相同,由于S2最后两个事件(3 4)属于相同的元素,所以合并到S1最后,而不是写成。

    b5df9d25391b89fc7575b28fb7ea94bf.png

    候选剪枝:若候选k-序列的(k-1)-序列至少有一个是非频繁的,则被剪枝。

    上例中,候选剪枝后只剩下。

    3、时限约束

    施加时限约束时,序列模式的每个元素都与一个时间窗口[l,u]相关联,其中l是该时间窗口内事件的最早发生时间,u是该时间窗口内事件的最晚发生时间。

    最大跨度约束:整个序列中所允许的事件的最晚和最早发生时间的最大时间差,记为maxspan,一般地,maxspan越长,在数据序列中检测到模式的可能性越大,但较长的maxspan也可能捕获不真实的模式。

    注:最大跨度影响序列模式发现算法的支持度计数,施加最大时间跨度约束之后,有些数据序列就不再支持候选模式。

    最小间隔和最大间隔约束:假设最大间隔maxgap=3(天),最小间隔mingap=1,即元素中的事件必须在前一个元素的事件出现后三(一)天内出现。

    注:使用最大间隔约束可能违反先验原理,以图2.1为例,无约束情形下,和的支持度都是60%,若施加约束mingap=0,maxgap=1,的支持度下降至40%(缺少D的支持),而的支持度仍是60%,即超集的支持度比原集要高——与先验原理违背。使用邻接子序列的概念可避免这一问题。

    dcba98bae74a72f430d76cf0e8fb3ff7.png

    例:

    af8f9a919f14420390a1b4032212b952.png

    使用邻接子序列修改先验原理如下:

    修订的先验原理:若一个k-序列是频繁的,则它的所有邻接(k-1)-子序列也一定是频繁的。

    注:根据上述原理,在候选剪枝阶段,并非所有k-1-序列都序列都需要检查(违反最大间隔约束)。

    例:若maxgap=1,则不必检查的子序列是否频繁,因为{2,3}和{5}之间的时间差为2,大于一个单位,只需考察其邻接子序列:,,<1}{2}{4}{5}>,。

    窗口大小约束:元素

    9afd4c19ccf95c87876a6604e862f6eb.png中的事件不必同时出现,可定义一个窗口大小阈值(ws)来指定序列模式的任意元素中事件最晚和最早出现之间的最大允许时间差。(ws=0表示同一元素中的所有事件必须同时出现)。

    --GSP算法

    算法基本思路:

    1、长度为1的序列模式L1,作为初始的种子集;

    2、根据长度为i的种子集Li,通过连接操作和剪切操作生成长度为i+1的候选序列模式

    bdb708b0cc9855292d235d040e601e50.png,然后扫描数据库,计算每个候选序列模式的支持度,产生长度为i+1的序列模式

    20e5500952e34b72dda726ccefe170c4.png并作为新的种子集。

    3、重复第二步,直到没有新的序列模式或新的候选序列模式产生为止。

    解决两大问题:

    1、候选集产生:合并+剪枝=期望尽可能少的候选集;

    2、支持度计数

    两个技巧:

    1)哈希树存储数据,减少对于候选序列需要检查的原数据序列个数。

    2)改变原数据系列的表达形式以有效发现一个候选项是否是数据序列的子序列。

    3、具体做法:

    对事物数据库中的每个数据序列的每一项进行哈希,从而确定应该考察哈希树哪些叶子节点中的候选K序列;对于叶子节点中的每个候选K序列,须考察其是否包含在该数据序列中,对每个包含在该数据序列中的候选序列,其计数值加1。

    如何考察数据序列d是否包含某个候选K序列s?分两步:

    4712b059aa94cfa45b019ca79576e6ec.png

    例:假设maxgap=30,mingap=5,ws=0,考察候选序列s=是否包含在下列数据序列中。

    b8a225b982ffaa49fa832452d80d990e.png

    1)首先寻找s的第一个元素(1,2)在该数据序列中第一次出现的位置,对应时间为10;

    2)由mingap=5,故在时间15后寻找下一元素(3),发现其第一次出现时间为45,而45-10>30,转入向后阶段;

    3)重新寻找(1,2)的第一次出现位置:50,接着在时间55后寻找(3):65,由65-50<30,故满足最大时间间隔约束,转入向前阶段;

    4)寻找(3)的下一个元素(4)在时间70(65+5)后的第一次出现位置:90,由90-65<30,满足;

    5)考察结束,包含。

    参考:

    Srikant R ,Agrawal.R.   Mining Sequential Patterns: Generalizations and Performance Improvements.

    Pang-Ning Tan 数据挖掘导论.

    展开全文
  • 频繁模式挖掘-FP-Growth

    2021-02-24 16:49:29
    FP-Growth是频繁模式挖掘的一种算法,由韩家炜等在2000年提出,算法通过建立一棵频繁项集树来实现频繁项集的搜索,同时能实现事务的压缩,相比Apriori能减少数据的扫描次数。 算法逻辑 1、扫描数据,统计项目...

    目录

    算法简介

    算法逻辑

    案例

    Spark程序实现例子(Java语言)


     

    算法简介

    FP-Growth是频繁模式挖掘的一种算法,由韩家炜等在2000年提出,算法通过建立一棵频繁项集树来实现频繁项集的搜索,同时能实现事务的压缩,相比Apriori能减少数据的扫描次数。

    算法逻辑

    1、扫描数据,统计项目(item)在数据集中出现的频数,例如苹果出现(被购买)了4次、牛奶出现(被购买)了5次等

    2、再次扫描数据,构建频繁树(FP-Tree),并生成头表。将每条事物中的项目按照步骤1中的频数由高到底排列后,依次放到树中,并用头表记录每个项目在树中的位置

    3、依据头表和支持度,在频繁树种搜索频繁项集

    案例

    数据:

    交易ID(TID)item(项)
    1苹果,牛奶,香蕉
    2苹果,烤串
    3牛奶,香蕉,啤酒
    4牛奶,啤酒
    5香蕉,啤酒,尿布
    6香蕉
    7苹果,牛奶,香蕉,啤酒,尿布,烤串
    8香蕉
    9牛奶
    10啤酒

    1、扫描数据,统计项目的频数,按照频数由大到小排序结果如下:

    item(项)频数
    香蕉6
    牛奶5
    啤酒5
    苹果3
    烤串2
    尿布2

    2、再次扫描数据,构建频繁树(FP-Tree),并生成头表。构建FP-Tree时首先建立根节点root(或者叫NULL),根节点不保存数据

    TID=1:苹果,牛奶,香蕉

    根据频数对事务中的项目进行排序,得到:香蕉,牛奶,苹果

    根据排序后的事务创建FP-Tree:根据频数倒序生成,香蕉紧跟在root节点后面,然后是牛奶在香蕉后面,苹果在牛奶后面,并在节点上记录项目的频数,生成头表指向各节点,如下图:

    TID=2:苹果,烤串

    根据频数对事务种项目进行排序,得到:苹果,烤串

    插入到FP-Tree中,因root节点只有一个香蕉节点,没有苹果节点,因此root下面新增一个苹果节点;苹果节点之间增加指针,增加烤串指针

    TID=3:牛奶,香蕉,啤酒

    根据频数对事务种项目进行排序,得到:香蕉,牛奶,啤酒

    插入到FP-Tree中,相同节点上的频数相加,如下图黑色文字部分

    TID=4:牛奶,啤酒

    根据频数对事务种项目进行排序,得到:牛奶,啤酒

    插入到FP-Tree中,从root节点下面新增“牛奶”节点,建立啤酒之间的指针,如下图黑色文字部分

     

    TID=5:香蕉,啤酒,尿布

    根据频数对事务种项目进行排序,得到:香蕉,啤酒,尿布

    插入到FP-Tree中,如下图黑色文字部分

    TID=6:香蕉

    插入到FP-Tree中,香蕉节点的频数由3增加到4,如下图黑色文字部分

    TID=7:苹果,牛奶,香蕉,啤酒,尿布,烤串

    根据频数对事务种项目进行排序,得到:香蕉,牛奶,啤酒,苹果,烤串,尿布

    插入到FP-Tree中,如下图黑色文字部分

     

    TID=8:香蕉

    插入到FP-Tree中,如下图黑色文字部分

     

    TID=9:牛奶

    插入到FP-Tree中,如下图黑色文字部分

    TID=10:啤酒

    插入到FP-Tree中,如下图黑色文字部分。完整的FP-Tree如下图,从root开始生长的一棵频繁树,除root节点外,每个节点存储一个item(项目),以及item(项目)在事务数据中的频数,以及指向相同项目其他节点的指针;还有一张存储节点指针的头表。

    3、挖掘频繁模式

    从头表底部开始,由下到上挖掘频繁模式,最底部是尿布,在频繁树中,有两条路径:(香蕉6-牛奶3-啤酒2-苹果1-烤串1-尿布1)、(香蕉6-啤酒1-尿布1);

    假如最小支持度设为2,即项目或项目组合大于等于2才算是频繁项,则以上两条路径被裁剪为(香蕉6-啤酒2-尿布1)、(香蕉6-啤酒1-尿布1)。苹果、烤串和尿布组合的数量只有1 ,不满足最小支持度,因此被裁剪掉;建立如下子树:

    根据子树,得到频繁项集:以“尿布”结尾的频繁项集有:(尿布)(尿布,啤酒)(尿布,香蕉)(尿布,啤酒,香蕉)

    然后根据指针的头表,继续向上挖掘以“烤串”、“苹果”,“啤酒”,“牛奶”,“香蕉”结尾的频繁项集
     

     

    Spark程序实现例子(Java语言)

    Spark中实现了FP-Growth算法,官方例子点这里,下面是代码

    
    public class JavaFPGrowthExample {
      public static void main(String[] args) {
        //创建SparkSession
        SparkSession spark = SparkSession
          .builder()
          .appName("JavaFPGrowthExample")
          .master("local")
          .getOrCreate();
    
        // 创建List数据
        List<Row> data = Arrays.asList(
          RowFactory.create(Arrays.asList("1 2 5".split(" "))),
          RowFactory.create(Arrays.asList("1 2 3 5".split(" "))),
          RowFactory.create(Arrays.asList("1 2".split(" ")))
        );
        StructType schema = new StructType(new StructField[]{ new StructField(
          "items", new ArrayType(DataTypes.StringType, true), false, Metadata.empty())
        });
        // 创建DataFrame
        Dataset<Row> itemsDF = spark.createDataFrame(data, schema);
        // 显示原始数据
        System.out.println("原始数据在同一列里面,这是Spark的规则,数据框如下:");
        itemsDF.show(false);
    
        // 创建FPGrowth实例
        FPGrowthModel model = new FPGrowth()
          .setItemsCol("items") // 设置输入列,交易数据需要进行拆分后,将项目(item)数据放在同一列中,这是Spark的要求
          .setMinSupport(0.5) // 设置最小支撑度
          .setMinConfidence(0.6) // 设置最小置信度
          .fit(itemsDF);  // 拟合数据,返回一个FPGrowthModel
    
        // 展示频繁项
        System.out.println("频繁项集如下,第一列是项集组合,第二列是频数:");
        model.freqItemsets().show();
    
        // 生成关联规则
        System.out.println("关联规则如下,第一列是前项,第二列是后项,第三列是置信度");
        model.associationRules().show();
    
        //
        System.out.println("得到模型后,可以调用模型的transform方法,对数据集进行预测,得到规则。第一列是项集,第二列是推出的结果");
        model.transform(itemsDF).show();
        System.out.println("例如:1、2组合能够推出5");
        // $example off$
    
        spark.stop();
      }
    }

    执行代码后得到以下结果

     

    原始数据在同一列里面,这是Spark的规则,数据框如下:
    +------------+
    |items       |
    +------------+
    |[1, 2, 5]   |
    |[1, 2, 3, 5]|
    |[1, 2]      |
    +------------+
    
    2021-03-02 17:16:57 WARN [org.apache.spark.mllib.fpm.FPGrowth] - Input data is not cached.
    频繁项集如下,第一列是项集组合,第二列是频数:
    +---------+----+
    |    items|freq|
    +---------+----+
    |      [5]|   2|
    |   [5, 1]|   2|
    |[5, 1, 2]|   2|
    |   [5, 2]|   2|
    |      [1]|   3|
    |   [1, 2]|   3|
    |      [2]|   3|
    +---------+----+
    
    关联规则如下,第一列是前项,第二列是后项,第三列是置信度
    +----------+----------+------------------+
    |antecedent|consequent|        confidence|
    +----------+----------+------------------+
    |    [1, 2]|       [5]|0.6666666666666666|
    |    [5, 1]|       [2]|               1.0|
    |       [2]|       [5]|0.6666666666666666|
    |       [2]|       [1]|               1.0|
    |       [5]|       [1]|               1.0|
    |       [5]|       [2]|               1.0|
    |       [1]|       [5]|0.6666666666666666|
    |       [1]|       [2]|               1.0|
    |    [5, 2]|       [1]|               1.0|
    +----------+----------+------------------+
    
    得到模型后,可以调用模型的transform方法,对数据集进行预测,得到规则。第一列是项集,第二列是推出的结果
    +------------+----------+
    |       items|prediction|
    +------------+----------+
    |   [1, 2, 5]|        []|
    |[1, 2, 3, 5]|        []|
    |      [1, 2]|       [5]|
    +------------+----------+
    
    例如:1、2组合能够推出5
    

     

     

     

     

    展开全文
  • 频繁序列模式挖掘广泛应用于时序、文本、基因工程等领域. 与模式匹配不同, 模式挖掘需要进行模式的构造, 因此更具有挑战性. 本讲座描述该领域的一个具体方向的发展历程, 以及与粒计算的关系. 带周期性通配符区间的...
  • 一、空间同位模式挖掘概述 二、经典co-location算法实现及演示 1.代码实现 2.演示操作 总结 前言 经典co-location算法是经典的空间 提示:以下是本篇文章正文内容,下面案例可供参考 一、空间同位模式挖掘...
  • GSP,Spade,FreeSpan,PrefixSpan都是频繁序列挖掘算法 关联规则挖掘的的目标是寻找达到某种程度联系的事物集合,再由其产生相关的关联规则。...可以看出,序列模式挖掘类似于Apriori算法中的频繁项目集挖掘是类似...
  • 数据挖掘关联分析频繁模式挖掘apriorifpgrowth及eclat算法的java及c++实现.doc (update 2012.12.28 关于本项目下载及运行的常见问题 FAQ 见 newsgroup18828 文本分 类器、文本聚类器、关联分析频繁模式挖掘算法的 ...
  • 进化模式挖掘(最大候选集): 评价(最大候选集中的个体): 进化模式挖掘(最小候选集): 评价(最小候选集中的个体): 环境选择: 变异: 二目运算: p是突变概率,n是维度为零非零变量的个数,D...
  • 频繁模式挖掘及相关的基本概念,包括项目 (item),项目集 (itemset),k-项目集 (k-itemset),交易 (transaction),包含 (contain),支持量 (support count),支持度 (support),最小支持度阈值,频繁项 (frequent ...
  • 国内图书分类号:TP311.131国际图书分类号:621.3工学硕士学位论文数据流中基于优化的 FP-tree 的频繁模式挖掘方法研究万方数据硕 士 研 究 生:导 师:申请学位级别:学 科、专 业:所 在 单 位:授予学位单位:何...
  • 频繁模式挖掘(Frequent Pattern Mining):频繁项集挖掘是通常是大规模数据分析的第一步,多年以来它都是数据挖掘领域的活跃研究主题。建议用户参考维基百科的association rule learning 了解更多信息。MLlib支持了一...
  • 频繁项集导致发现大型事物或者数据集之间有趣的关联或相关性,频繁项集挖掘的一个典型案例是购物篮分析,该过程通过发现顾客放入他们的购物篮中的商品之间的关系,分析客户的购物习惯; 下面了解频繁模式中的相关概念...
  • 新建Java Project 在src目录下新建class——编辑代码并运行 FP-Tree 挖掘 代码 FP-Tree算法的实现 - 张朝阳 - 博客园 (cnblogs.com)https://www.cnblogs.com/zhangchaoyang/articles/2198946.html 结果
  • 文章目录一、 问题背景与意义:二、 问题定义三、 经典的关联规则...随着大数据时代的到来,数据的收集和存储愈加重要,许多场景也对从数据中挖掘出频繁模式有着愈加迫切的需求,比如从大量商务事务记录中发现有价值的
  • 今天给大家分享一篇在遥感影像时间序列中挖掘频繁出现的序列模式的论文,本文通过提取森林景观格局的演化过程,来评价森林的稳定性和健康程度。该论文的题目是《Extracting Frequent Sequential Patterns of Forest ...
  • 频繁模式的增量挖掘

    2021-11-16 16:26:20
    假设 DB 表示原数据库,s 表示最小支持度阈值,FPDB 表示 DB 中对应 s 的 频繁模式集。...频繁模式的增量挖掘,就是通过已获得的频繁模式和更新后的数据库,按 照与原来相同的最小支持度阈值 s,高效发现新的频繁模...
  • 关联规则挖掘是一种识别不同项目之间潜在关系的技术。以超级市场为例,客户可以在这里购买各种商品。通常,客户购买的商品有一种模式。例如,有婴儿的母亲购买婴儿产品,如牛奶和尿布。少女可以购买化妆品,而单身汉...
  • 今天老肥和大家分享的是三一数据应用大赛-挖掘机工作模式识别的Baseline方案,全流程需在DCLab平台上进行,选手需要在平台上进行数据处理、算法调试。现在很多比赛平台出于数据保密等原因...
  • 我正在使用Apriori算法和FPA执行顺序规则挖掘,我在excel中有如下所示的数据集,我将数据加载到pandas dataframe中,我使用的是如下read_excel命令,如下所示。在Station1 Station2 Station3 Repetition0 Singapore ...
  • 本文详细介绍了共享单车数据挖掘,包括数据分析和模型开发。它包含以下步骤:共享单车数据挖掘数据集简介关于共享单车数据集自行车共享系统是传统自行车租赁的新一代,从注册会员、租赁到归还的整个过程...
  • 包括特征化与区分,频繁模式、关联和相关性挖掘,分类与回归,聚类分析,离群点分析。 数据挖掘功能用于指定数据挖掘任务发现的模式。 一般而言,这些任务可以分为两类:描述性和预测性。描述性挖掘任务刻画目标数据...
  • 文章目录1 竞赛背景2 任务3 数据 ...现在希望利用这些回传的传感器数据(C端数据)对挖掘及工作模式进行识别,从而加强对挖掘机使用情况的监管。 产品研发方面,挖掘机工作模式的有效识别,能加深研发
  • 根据项头表从底下开始挖掘: F:我们开始从F节点开始挖掘,那么根据上面条件模式基的求法可以得出F的条件模式基为:(B E C A),然后我们在根据排序好的项目集,在有F存在的数据里,依次找出B E C A的支持度,即...
  • 关联规则挖掘算法——Apriori算法

    千次阅读 2021-03-19 08:34:45
    在关联规则挖掘这一章中,Apriori算法是非常重要的~之后本章的实验中也要实现—— 理解&自己编程实现Apriori算法 (所以要好好学一下哈~) 为啥需要Apriori算法呢?—— 在关联规则挖掘中,要产生频繁项集,要...
  • 数据挖掘复习

    2021-12-01 20:44:23
    决策树修剪 预先剪枝(Pre-Pruning):在构造决策树的 同时 进行剪枝 后剪枝(Post-Pruning):决策树构造完成后进行剪枝, 从树的叶子开始剪枝,逐步向根的方向剪 剪枝用于克服噪声 序列模式挖掘主要有五个步骤:...
  • 大数据分析与挖掘

    2021-02-23 21:20:35
    第一章 绪论 大数据分析与挖掘简介 大数据的四个特点(4v):容量(Volume)、多样性(Variety)、速度(Velocity)和价值 ...提取出来的知识一般可表示为概念、规则、规律、模式等形式。 大数据分析与挖掘主要技术
  • 一、 数据挖掘特点、 二、 数据挖掘组件化思想、 三、 决策树模型、 1、 决策树模型创建、 2、 树根属性选择
  • 数据挖掘近年来的研究方向、方法总结 ...其包含的基础理论研究涉及到规则和模式挖掘、分类、聚类、话题学习、时间空间数据挖掘、机器学习方法,监督、非监督、半监督等方面,同时这些也是人工智能领域的相关研
  • 数据挖掘 期末超重点习题(不挂科) 一、 单选题 1. 某超市研究销售纪录数据后发现,买啤酒的人很大概率也会购买尿布,这种属于数据挖掘的哪类问题?(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 2. ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 153,974
精华内容 61,589
关键字:

模式挖掘