基本介紹
- 中文名：關聯數據結構
- 外文名：associative data structure
- 學科：計算機
- 定義：將有關數據通過數據結構表示
- 有關術語：數據結構
- 領域：資料庫
簡介,關聯數組,數據結構研究對象,關聯分析,
簡介
關聯數據結構一般有兩種解釋：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中交易總數的 乘積，即項集滿足最小支持度閾值要求，則該項集 是頻繁項集；其餘稱為非頻繁項集。
強關聯規則： 強關聯規則是指同時滿足用戶定義的最小支持度閾值和最小置信度閾值的關聯規則。相反，不滿足用戶定義的最小支持度閾值和最小置信度閾值的規則，是弱關聯規則。
