[科普中国]-关联数据结构

简介

关联数据结构一般有两种解释：1、将有关联的数据用一种数据结构表示，如关联数组；2、将有关数据结构通过一种方法联系起来，如在数据库，经常通过外键和主键将不同表联系起来。关联数据结构的建立主要是为了进行数据的关联分析。在数据挖掘中，关联数据结构建立，会给数据分析带来不少便利。

关联数组在计算机科学中，关联数组（Associative Array），又称映射（Map）、字典（Dictionary）是一个抽象的数据结构，它包含着类似于（键，值）的有序对。一个关联数组中的有序对可以重复（如C++中的multimap）也可以不重复（如C++中的map）。

这种数据结构包含以下几种常见的操作：

向关联数组添加配对

从关联数组内删除配对

修改关联数组内的配对

根据已知的键寻找配对

字典问题是设计一种能够具备关联数组特性的数据结构。解决字典问题的常用方法，是利用散列表，但有些情况下，也可以直接使用二叉查找树或其他结构。

许多程序设计语言内置基本的数据类型，提供对关联数组的支持。而内容定址存储器则是硬件层面上实现对关联数组的支持。

数据结构研究对象计算机软件中的数据结构一般包括数据的逻辑结构、数据的物理结构和数据的运算等三个方面。数据的逻辑结构描述数据间的逻辑关系，可以用一个二元组B=(K，R)来表示.其中K是结点的有穷集合，结点(或称元素)是数据结构中讨论的基本单位；R是K上的关系的有穷集合。数据结构分为线性结构和非线性结构。

1.线性结构。有且仅有一个终端结点和一个开始结点，并且所有的结点都最多只有一个前驱和一个后继.向量、栈、队列等顺序表以及字符串、链表等线性表都是线性结构。

2.非线性结构。树形结构、图、多维数组、稀疏矩阵、广义表等都是非线性结构。

数据的物理结构即数据的存储结构，描述数据的逻辑结构在计算机存储器的表示方式。通常有四种基本的存储映像方法：

1.顺序的方法。把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现.这种方法主要用于线性的数据结构。对非线性结构也可以采用局部线性化的方法实现顺序存储。例如，在树形结构中可以把结点按某种规则排成序列，用顺序存储方法把结点内部的信息稠密地存放在一起，而对结点之间的关系采用其他的存放方法。

2.链接的方法。将结点所占的存储单元分为两部分，分别存放数据项和指针项。

3.索引的方法。用结点的索引号来确定结点的存储地址。

4.散列的方法。在结点k的字段里取一个或几个字段的值Wik作为关键码，结点k对应的存储地址LOC(k)由函数f(称为散列函数)确定，LOC(k)=f(Wik).

数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的运算包括对结点进行的检索、插入、删除、更新、排序等。数据结构尚有静态和动态之分。静态结构就是数据的结构(逻辑结构和物理结构)特性在该数据结构存在期间是不能改变的，例如向量、数组、记录等。而动态结构是在整个使用期间，数据的结构特性是可变化的，例如栈、队列、链表、树、动态数组结构、递归数据结构等。

关联分析关联分析指的是在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。或者说，关联分析是发现交易数据库中不同商品（项）之间的联系。

关联分析是一种简单、实用的分析技术，就是发现存在于大量数据集中的关联性或相关性，从而描述了一个事物中某些属性同时出现的规律和模式。一般采用关联规则分析。关 联规则发现是寻找事物之间的关联。如，它可从一 组(假设是商品采购)事务包含的一组数据项中发现规则如下：如果采购事务包含项X和项Y，则在全部采购事务的N%中包含采购事务的项Z。序列规则发现类似于关联规则发现，是寻找事物之间的序列关系。如，同样可从消费者购物的一组事务所包含的一组数据项中，进一步对这些事务的每个消费者给以标识。关联规则一般有以下度量：

兴趣度度量(interest measure)：帮助用户评估得 到的关联规则。与关联规则评估相关的兴趣度包括简洁性、正确性、实用性、新颖性。

简洁性度量是衡量一个规则结构的复杂程度， 复杂结构的规则难以解释与理解，造成其兴趣度降低；正确性度量用以判断规则令人信服的程度有多 高，在关联规则中用置信度表示；实用性度量用以判断该规则再次出现的可能性有多大，在关联规则中用支持度表示；新颖性度量判断规则是否已被导 出的规则集中的另一规则所蕴涵，用以去除冗余规则。

频繁项集(frequent itemset)： 项集出现的频率表 示包含项集的交易数，如果项集的出现频率大于或等于最小支持度阈值与交易数据集D中交易总数的 乘积，即项集满足最小支持度阈值要求，则该项集 是频繁项集；其余称为非频繁项集。

强关联规则： 强关联规则是指同时满足用户定义的最小支持度阈值和最小置信度阈值的关联规则。相反，不满足用户定义的最小支持度阈值和最小置信度阈值的规则，是弱关联规则1。