聚类、关联规则挖掘、图数据库

聚类一、聚类的定义聚类，属于一种非监督学习方法，它试图在无标签的数据集中发现其分布状况或模式。

通常，我们认为同一聚类中的数据点比不同聚类的数据点具有更大的相似性。

二、传统的聚类算法的分类1、基于划分的聚类算法主要思想：基于划分的聚类算法通过构造一个迭代过程来优化目标函数，当优化到目标函数的最小值或极小值时，可以得到数据集的一些不相交的子集，通常认为此时得到的每个子集就是一个聚类。

典型方法：k-means算法FCM算法。

2、层次聚类算法主要思想：层次聚类方法使用一个距离矩阵作为输入，经过聚类后得到一个反映该数据集分布状况的聚类层次结构图。

层次聚类算法通常分为两种：凝聚的层次聚类算法：它首先把每个数据点看作是一个聚类，然后以一种自底向上的方式通过不断地选择最近邻居聚类对的合并操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。

分类的层次聚类算法：它首先把所有的数据点看作是一个聚类，然后以一种以自顶向下的方式通过不断地选择最松散簇进行分裂操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。

典型方法：AGNES (AGglomerative NESting)BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)CURE (Clustering Using REpresentative)3、基于密度的聚类算法主要思想：基于密度的聚类算法试图通过稀疏区域来划分高密度区域以发现明显的聚类和孤立点，主要用于空间型数据的聚类。

典型方法：DBSCAN (Density-based Spatial Clustering of Application with Noise)OPTICS (Ordering Points to Identify the Clustering Structure)4、基于网格的聚类算法主要思想：基于网格的聚类算法是一种基于网格的具有多分辨率的聚类方法。

它首先将数据集的分布空间划分为若干个规则网格(如超矩形单元)或灵活的网格(如任意形状的多面体)，然后通过融合相连的带数据概要信息的网格来获得明显的聚类。

典型方法：STING (Statistical Information Grid)CLIQUE (Clustering In QUEst)5、基于模型的聚类算法主要思想：基于模型的聚类算法借助于一些统计模型来获得数据集的聚类分布信息。

该方法假定数据集是由有限个概率分布模型共同作用生成的。

在这种方法中，多变量的高斯分布混合模型应用最为广泛。

典型方法：COBWEBCLASSIAutoClass6、基于图的聚类算法主要思想：采用图聚类方法进行聚类分析时，首先是建立与具体问题相适应的图。

图的结点代表被分析数据的基层单元，图的边代表基层单元数据之间的相似性度量(或相异性度量)。

通常，每个基层单元数据之间都会有一个度量表达，这样可以保持数据集的局部分布特性。

图聚类方法是以数据集的局部连接特征作为聚类的主要信息源，因而易于处理局部数据的特性。

典型方法：CHAMELEON: a hierarchical clustering algorithm using dynamic modeling.7、其他聚类算法量子聚类算法、谱聚类算法、基于粒度的聚类算法、概率图聚类方法、同步聚类算法SynC (Synchronization Clustering)关联规则挖掘一、关联规则的定义一般地，给定一个数据库，挖掘关联规则的问题可以转换为寻找满足最小支持度和最小置信度阈值的强关联规则过程，分为两步：a) 生成所有频繁项集，即找出支持度大于等于最小支持度阈值的项集；b) 生成强关联规则，即找出频繁项集中大于等于最小置信度阈值的关联规则。

二、关联规则的分类1、基于规则中处理的变量类别关联规则分为布尔型和多值属性型。

布尔型关联规则处理的是离散、种类化的数据，它研究项是否在事务中出现; 多值属性关联规则又可分为数量属性和分类属性，它显示了量化的项或属性之间的关系。

2、基于规则中数据的抽象层次关联规则分为单层和多层。

根据规则中对应项目的粒度层次，多层关联规则可以划分为同层和层间关联规则。

多层关联规则挖掘的两种设置支持度的策略为统一的最小支持度和不同层次设置不同的最小支持度。

3、基于规则中数据的维度关联规则分为单维和多维。

单维关联规则处理的对象只是一维的; 多维关联规则处理的则是两个或两个以上的变量。

根据同一维在规则中是否重复出现，多维关联规则又可分为维内关联规则和混合关联规则。

三、关联规则挖掘算法1、经典关联规则挖掘算法对于Apriori算法，我们使用支持度作为我们判断频繁项集的标准。

Apriori算法的目标是找到最大的K项频繁集。

这里有两层意思，首先，我们要找到符合支持度标准的频繁集。

但是这样的频繁集可能有很多。

第二层意思就是我们要找到最大个数的频繁集。

比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。

Apriori算法是如何做到挖掘K项频繁集的呢？Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。

然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

典型算法：Apriori算法针对Apriori算法的缺点进行改进的算法：基于散列技术、基于划分、基于采样、FP增长等串行算法和并行分布式算法。

2、基于数据流的关联规则挖掘基于数据流的新型数据挖掘模型不同于传统的静态数据库模型，数据流是在线联机产生的，其具有连续、无界、无序的特征。

因此，基于数据流的关联规则挖掘不能采用以往多次扫描数据的形式，而应随着数据更新进行单次扫描。

为了适应数据流的特征，解决存储空间不足的问题，一般通过滑动窗口技术对数据流作区域性限制进行窗口查询。

典型算法：FP-stream频繁项集挖掘算法Moment算法FIMoTS算法FIUT-Stream算法基于数据分段思想的数据流挖掘算法Sampling, Lossy counting3、基于图的关联规则挖掘图挖掘是指将关联分析用于基于图的数据，在图的集合中发现一组公共子结构，即频繁子图挖掘。

根据挖掘的搜索路径频繁子图挖掘算法分为BFS 广度优先搜索( broad first search)和DFS 深度优先搜索( depth first search) 两类。

典型算法：基于广度优先搜索算法包括AGM、FSG。

基于深度优先搜索算法包括gSpan、FFSM、closeGraph。

4、基于序列的关联规则挖掘Agrawal和Strikant 最早提出了序列模式挖掘的概念，即从序列数据库中挖掘满足最小支持度的频繁子序列的过程。

序列模式挖掘不同于关联规则挖掘项集属性内部的联系，它主要研究项集之间的联系。

典型算法：AprioriAll、AprioriSome、DynamicSome类Apriori算法GSP带通配符的序列模式挖掘方法One-Off mining图数据库一、图数据库的定义图数据库技术以“图”这种数据结构存储和查询数据。

图数据库的基本存储单元为：节点、关系、属性。

图形数据库是NoSQL数据库的一种类型，它应用图形理论存储实体之间的关系信息。

图形数据库是一种非关系型数据库，它应用图形理论存储实体之间的关系信息。

最常见例子就是社会网络中人与人之间的关系。

关系型数据库用于存储“关系型”数据的效果并不好，其查询复杂、缓慢、超出预期，而图形数据库的独特设计恰恰弥补了这个缺陷。

二、主流的图数据库1、Neo4j:Neo4j是一个流行的图形数据库，它是开源的。

最近，Neo4j的社区版已经由遵循AGPL 许可协议转向了遵循GPL许可协议。

尽管如此，Neo4j的企业版依然使用AGPL许可。

Neo4j 基于Java实现，兼容ACID特性，也支持其他编程语言，如Ruby和Python。

2、dgraph:dgraph是GO语言写的，比较新，相比于Neo4j有后发优势，创始人的技术背景相当不错，有自己的存储后端，golang保证了性能，从设计到结构都是照着google的论文来的。

目前已经到了1.0版本。

缺点是还是太新了，graphql+-查询语言不是标准的版本，目前还不支持gremlin和opencypher查询语言，但是都在roadmap里面。

另外不支持授权，所以目前api都是不需要授权的。

3、OrientDB:OrientDB是java语言实现的，兼具文档数据库的灵活性和图形数据库管理链接能力的可深层次扩展的文档-图形数据库管理系统。

可选无模式、全模式或混合模式下。

支持许多高级特性，诸如ACID事务、快速索引，原生和SQL查询功能。

可以JSON格式导入、导出文档。

若不执行昂贵的JOIN操作的话，如同关系数据库可在几毫秒内可检索数以百记的链接文档图。