【数据挖掘学习笔记】12.复杂类型数据挖掘

一、模糊挖掘

不确定性挖掘方法——模糊挖掘
– 基于概率
– 基于粗糙集

– 基于模糊集

模糊集的表示

（1）Zadeh表示法

（2）序偶表示法

（3）向量表示法

模糊集运算
定义：设A，B是论域U的两个模糊子集，定义

模糊统计法

模糊矩阵

我们称为满足条件R=(r_{ij})_{m \times n}且0 \leq r_{ij} \leq 1的矩阵R；特别地，在这种情况下（即r_{ij}仅取值于集合\{0, 1\}），我们将该类型的矩阵简称为布尔（Boole）矩阵；如果该方阵满足其主对角线元素r_{ii}=1(对于所有i=1,2,\dots,n))，则我们将其称为模糊单位矩阵

模糊矩阵运算

截矩阵

模糊聚类

相似矩阵建立方法

计算相似度：相似系数、距离、贴近度

贴近度

σ (A,B)表示两个模糊集A，B之间的贴近程度。

二、空间挖掘

空间挖掘（Spatial Mining）

– 属于基于空间数据的数据挖掘技术的一种应用形式。
– 基于空间数据库的方法用于提取隐含的知识、建立空间关系模型以及识别非显式存在的模式组合来分析理解空间数据间的相互关联性（包括时空关系）。
– 空间数据来源于遥感技术、地理信息系统（GIS）、多媒体处理以及医学影像等多个领域的实际应用场景。
– 空间数据集通常包含丰富的时空拓扑特征与度量信息，并通过复杂的多维空间索引结构来进行高效的空间数据分析与处理。

空间数据

– 涉及二维坐标系及其以上维度的数据类型包括位置信息及其相关范围。这些类型涵盖的地图要素有经度纬度标记点以及线状面状实体如河流湖泊城市建筑设施等地理实体和器官系统设备组件等。
– 获取和处理空间数据的过程通常比处理非空间数据更为复杂。为了有效管理这些类型的数据需要依赖特定的操作符和组织方式。
– 可以通过带有如“邻近”“上下”“前后”“包含于”等操作符的语句来进行查询。
– 本研究的核心关注点是那些具有地理位置特征的区域数据库。

基于近似方法的空间索引技术主要依据低维度到高维度的空间转换方式

• 空间索引是基于空间实体的位置、形状及其间的特定空间关系进行组织的一种数据结构，并包含与这些实体相关的综述性信息。
• 基于其性能特性的优劣程度的空间索引设计直接影响着相关系统的技术性能水平，并对其应用效率产生重要影响。

空间数据操作

– 假设A和B是二维空间中的两个空间实体。每个实体由空间中的点集构成：<xa,ya>∈ A, <xb,yb>∈B。两个空间实体间存在多种拓扑关系；
• 分离（Disjoint）：A与B分离指B内任何点均不在A内反之亦然；
• 重叠或相交：A与B重叠或相交表明至少有一个点既属于A又属于B；
• 等价：A与B完全等价即它们共享所有点；
• 包含于：当A的所有点均在B内时称A包含于B；
• 覆盖/包含：若B的所有点都在A内则称A覆盖或包含B；
– 空间谓词有以下三种类型：
• 表示拓扑关系的谓词如相交覆盖等；
• 表示方向的空间位置谓词如东南西北等；
• 表示距离的空间度量谓词如接近远离等。

常用的两个空间实体之间的距离有：

最小值方法 最大值方法 平均值方法 中心方法

空间关联规则

• 空间关联规则描述了不同空间实体之间的相互联系，在非空
• 间条件下出现的结果具有空
• 间属性的情况下（例如，在北京），所有重点学校都位
• 于老住宅区附近。
• 当一个区域具有特定的空间特征时（例如，在北京），其附
• 近区域的空间实体往往会表现出特定属性（例如，在国贸附
• 近区域的房子往往价格较高）。
• 在特定的空间条件下（例如，在北京），随着地理位置的变
• 化（例如位于三环以内），相关模式会频繁发生并且伴随
• 着较强的空间关系。
• 空间关联规则挖掘作为传统数据挖掘领域的重要拓展方
• 法之一，在研究对象上进行了显著扩展。
• 为了发现这些模式及其内在关系，
• 通常采用最小支持度与最小置信度作为核心统计指标，
• 并通过层次化搜索策略进行分析：
  • 首先从高层次概念开始逐步细化至低层次概念；
  • 在高层次中寻找频繁发生的模式及其强
  • 大隐含关系；
  • 当发现这些模式时，则进一步深入到更低层概念中进
  • 行详细分析；
  • 直到无法找到新的频繁模式为止。

典型的五步算法：

– 步骤1：基于输入查询提取相关数据集合。
– 步骤2：采用粗粒度的空间运算策略对所有相关数据进行整体分析。
– 步骤3：筛选出支持度低于预设阈值的一阶谓词。
– 步骤4：通过精细粒度的空间计算模型进一步挖掘隐含的知识。
– 步骤5：深入分析多层概念结构以全面捕捉潜在模式

空间关联规则算法

给定空间数据库D、概念层次C以及参数s和α分别表示最小支持度与可信度，并基于查询q来检索感兴趣实体及其相关的拓扑关系p。
• （1）D' = q(D)；
• （2）在D'中利用粗糙集理论构建概念关联模型CP；
// 其中CP由满足D'中实体对的所有粗糙谓词构成
• （3）通过计算满足阈值s的粗糙谓词集合来获取频繁粗糙谓词FCP；
• （4）从FCP中提取所有频繁精确模式FFP；
• （5) 通过提取所有频繁精确模式FFP得到关联规则集合R，并依据归纳准则完成规则提取过程。

空间分类

用于对空间实体集合进行分类的空间分类方法是一种有效的分析工具。为了实现对空间实体的数据分析与分组管理功能,可以通过非空属性、空性质,或是两者的结合来进行特征提取与样本选取,并可依据概念层次选择合适的抽样策略以提高分析效率和准确性；在训练样本数据时可通过改良传统分类算法来实现这一目标

建造一个决策树，有五个主要步骤：

– 基于现有的分类标准，在数据集D中检索实例S。
– 选择合适的谓词p用于分类任务。通常会首先从较粗粒度的层面寻找相关词汇，然后逐步深入到更细致的层级。
– 确定最优缓冲区间格与形状特征。对于采样的每个实体而言，在其周围形成的区域即为缓冲带区域；我们的目标是选取一个能够生成对测试集中各类别样本差异最大的缓冲区域。
– 借助于p属性与类别标签C的信息，在各个缓冲区域内提取相关的特征描述。
– 通过泛化处理后的概念属性以及ID3算法构建决策树模型T。

空间决策树算法

– 输入：空间数据结构D；概念层级C；预定义的分类标准。
– 输出：决策树模型T。
• （1）基于预定义的分类标准从空间数据结构D中筛选出代表实例S；
• （2）确定最优分类谓词p用于区分不同类别的对象；
• （3）识别最合适的边界区域尺寸和几何形状；
• （4）基于p和概念层级C对各个边界区域进行分类归纳；
• （5）通过广义化处理结合ID3算法逐步生成决策树模型T.

空间聚类

– 多变量聚类分析
– 在执行空间聚类时，在确定形成的簇时应避免受输入点顺序的影响，并且还应避免受到无关数据的影响。
– 传统的分类方法可通过对现有技术进行优化以适应多维数据处理需求

DBCLASD（基于分布的大规模空间数据库聚类方法），它是一种DBSCAN的扩展版本。假定在聚类过程中所处理的数据点是均匀分布在空间中的情况较多时，该算法旨在通过分析数据点之间的距离关系来确定合适的簇结构。如果这些近邻的距离符合均匀分布的前提条件，则该数据点将被归入相应的簇中。

DBCLASD算法

三、序列挖掘

时间序列数据库

– 在不同时间段内反复进行测量所得出的一系列数值或事件构成了时间序列数据
– 有规律地记录数据有助于揭示潜在模式
– 分析时间序列中的各个组成部分及其特点
• 趋势指数据长期上升或下降的趋势
• 循环指每隔一段时间出现的波动模式
• 周期是指固定长度的时间间隔内的重复现象
• 突变代表数据中出现的重大转折点

应用

– 金融：股票价格，通货膨胀
– 工业：能量功耗
– 自然科学：实验结果
– 气象学：天气

时间序列运动的种类

– T：趋势线（trend curve）展示了时间序列图中长期运行的方向。
– C：周期性变化（cyclic variations）则关注于趋势线或曲线所呈现的持续波动模式。
• 例如，在商业领域中，周期通常可能固定也可能不固定。
– S：季节性变化（seasonal variations）指的是多年内相同月份出现相似事件的情况。
• 即，在每年同一时间段内都会发生特定事件。
– I：非规律性的变动（irregular or random fluctuations）则表示那些没有明显模式的变动现象。

时间序列分析

– 将时间序列分解为四种基本运动
– 加法模型: TS = T + C + S + I
– 乘法模型: TS = T × C × S × I

基本性质 : 基于Apriori算法（由Agrawal与Srikant于1994年提出）
– 当且仅当序列s不是频繁的
– 所有包含S的超序列也不是频繁的

GSP (广义序列模式)挖掘算法

该方法由Agrawal与Srikant于1996年首次提出，在该数据库中，每个元素均被视为长度为1的候选序列。对于每一个长度为k的序列项集，在每一层操作中都需要执行以下步骤：首先遍历整个数据库以计算各个候选序列的支持度；接着利用Apriori算法从已有的频繁k-长度序列中生成k+1长度的新候选序列。这一过程将不断重复直至没有新的频繁序列被发现为止。

• 主要优点:利用Apriori对候选序列

四、混合高斯分布

混合高斯模型Gaussian Mixture Model GMM

– 在所述方法中, 数据点归于哪一类是确定性的
– 在GMM模型中, 数据点归于哪一类具有概率性
– 优点:
• 在计算过程中, 在两个类别之间的数据点归属不明确时, 采用降低硬性分类以概率减少计算误差的方法

GMM过程

– 基于高斯混合模型（GMM）的分类过程即通过确定k个高斯分布来实现。
– 每个样本点可视为由k个高斯模型组成的混合体，并通过加权计算来综合各分量的影响。
– GMM中的每个高斯分量对应一个类别（Component），即单峰分布代表特定类型的数据特征。
– 将样本点投射至k个不同高斯分量中可获得其在各类别中的概率分布情况。
– 通过比较各分量的概率值，选择具有最大概率的那一类别作为该样本所属的主要类别。