頻繁專案集.
給定全域性專案集i和資料庫d，d中所有滿足使用者指定的最小支援度(minsupport)的專案集，即大於或等於minsupport的i的非空子集，稱為頻繁專案集(frequent itemsets)或者大專案集(large itemsets)。在頻繁專案集中挑選出所有不被其他元素包含的頻繁專案集稱為最大頻繁專案集(最大頻集： maximum frequent itemsets)或最大大專案集(maximum large iitemsets) 。
agrawal等人建立了用於事務資料庫挖掘的專案集格空間理論(1993, appriori屬性)。
理論的核心：
頻繁專案集的子集仍是頻繁專案集；
非頻繁專案集的超集是非頻繁專案集。
這個理論一直作為經典的資料探勘理論被應用。
定理(appriori 屬性1).
如果專案集x是頻繁專案集，那麼它的所有非空子集都是頻繁專案集。
證明設x是乙個專案集，事務資料庫d中支援x的元組數為s。對x的任一非空子集為y，設d中支援y的元組數為s1。
根據專案集支援數定義，很容易知道支援x的元組一定支援y，所以s1≥s，即support(y)≥support(x)。
按假設：專案集x是頻繁專案集，即
support(x)≥minsupport
所以support(y)≥support(x)≥minsupport，因此y是頻繁專案集。□
定理(appriori 屬性2).
如果專案集x是非頻繁專案集，那麼它的所有超集都是非頻繁專案集。
證明:設事務資料庫d中支援x的元組數為s。設x的任一超集z(xz)，事務資料庫d中支援z的元組數為s2。
根據專案集支援度定義，很容易知道支援z的元組一定支援x，所以s2≤s，即support(z)≤support(x)
按假設專案集x是非頻繁專案集，即
support(x)所以support(z)≤support(x) 2023年，agrawal等人提出了著名的apriori演算法。
演算法3-1 apriori（發現頻繁專案集）
（1） l1 = ; //所有1-專案頻集
（2） for （k=2; lk-1 ; k++） do begin
（3） ck=apriori-gen（lk-1）; // ck是k-候選集
（4） for all transactions t d do begin
（5） ct=subset(ck，t); //ct是所有t中包含ck元素
（6for all candidates c ct do
（（8） end
（9） lk=
（10） end
（11） l= lk;
演算法apriori中呼叫了apriori-gen(lk-1)，是為了通過(k-1)-頻集產生k-侯選集。
（1）for all itemset p lk-1 do
（2） for all itemset q lk-1 do
（3） if
< then begin
（4） c= p∞q;//把q的第k-1個元素連到p後
（5） if has_infrequent_subset(c，lk-1) then
（6delete c;//刪除含有非頻繁專案子集的侯選元素
（7） else add c to ck;
（8） end
（9）return ck;
has_infrequent_subset（c，lk-1），判斷c是否加入到k-侯選集中。
(1) for all (k-1)-subset s of c
(2) if s lk-1 then return true
(3) return false
apriori演算法例子
minsupport=50%
apriori演算法有兩個致命的效能瓶頸:
1．多次掃瞄事務資料庫，需要很大的i/o負載
對每次k迴圈，侯選集ck中的每個元素都必須通過掃瞄資料庫一次來驗證其是否加入lk。假如有乙個頻繁大專案集包含10個元素的話，那麼就至少需要掃瞄事務資料庫10遍。
2．可能產生龐大的侯選集
由lk-1產生k-侯選集ck是指數增長的，例如104個1-頻繁專案集就有可能產生接近107個元素的2-侯選集。如此大的侯選集對時間和主存空間都是一種挑戰。
一些演算法雖然仍然遵循apriori 屬性，但是由於引入了相關技術，在一定程度上改善了apriori演算法適應性和效率。
主要的改進方法有：
基於資料分割(partition)方法：基本原理是「在所有劃分中，支援度小於最小支援度的k-項集不可能是全域性頻繁的」。
基於雜湊(hash)的方法：基本原理是「在所有hash桶內支援度小於最小支援度的k-項集不可能是全域性頻繁的」。
基於取樣(sampling)的方法：基本原理是「通過取樣技術，評估被取樣的子集，並依次來估計k-項集的全域性頻度」。
其他：如，動態刪除沒有用的事務：「不包含任何lk的事務對未來的掃瞄結果不會產生影響，因而可以刪除」。
定義4-1 給定乙個資料庫 d=和一組類c=，分類問題是去確定乙個對映 f: dc，使得每個元組ti被分配到乙個類中。乙個類cj 包含對映到該類中的所有元組，即cj=。
解決分類問題的關鍵是構造乙個合適的分類器：從資料庫到一組類別集的對映。一般地，這些類是被預先定義的、非交疊的。
構造分類器，需要有乙個訓練樣本資料集作為輸入。分類的目的是分析輸入資料，通過訓練集中的資料表現出來的特性，為每乙個類找到一種準確的描述或者模型。
資料分類(data classification)分為兩個步驟:建模和使用。
資料分類的兩個步
1．建立乙個模型，描述預定的資料類集或概念集
資料元組也稱作樣本、例項或物件。
為建立模型而被分析的資料元組形成訓練資料集。
訓練資料集中的單個元組稱作訓練樣本，由於提供了每個訓練樣本的類標號，因此也稱作有指導的學習。
通過分析訓練資料集來構造分類模型，可用分類規則、決策樹或數學公式等形式提供。
2．使用模型進行分類
首先評估模型（分類法）的**準確率。
如果認為模型的準確率可以接受，就可以用它對類標號未知的資料元組或物件進行分類。
圖5.1資料分類過程：a)學習：用分類演算法分析訓練資料。這裡，類標號屬性是loan_decision，學習的模型或分類器以分類規則形式提供。
圖5.1資料分類過程：b)分類：檢驗資料用於評估分類規則的準確率。如果準確率是可以接受的，則規則用於新的資料元組分類
id3演算法：
設s是s個資料樣本的集合，定義m個不同類ci(i=1,2,…,m)，設si是ci類中的樣本數。對給定的樣本s所期望的資訊值由下式給出：
其中pi是任意樣本屬於ci的概率： si/s 。
設屬性a具有個不同值，可以用屬性a將樣本s劃分為，設sij是sj中ci類的樣本數，則由a劃分成子集的熵由下式給出：
由a進行分枝將獲得的資訊增益可以由下面的公式得到：
id3演算法例子：
根據feathers的取值，資料集被劃分成兩個子集
對於feathers=1的所有元組，其目標分類屬性=lays_eggs均為1。所以，得到乙個葉子結點。
對於feathers=0的右子樹，計算其他屬性資訊增益：
gain(warm_blooded)=0.918
gain(fur)=0.318
gain(swims)=0.318
根據warm_blooded的取值，左右子樹均可得到葉子結點，結束。
c4.5演算法
c4.5演算法是從id3演算法演變而來，除了擁有id3演算法的功能外，c4.5演算法引入了新的方法和增加了新的功能：
用資訊增益比例的概念；
合併具有連續屬性的值；
可以處理具有缺少屬性值的訓練樣本；
通過使用不同修剪技術以避免樹的過度擬合；
k交叉驗證；
規則的產生方式等。
資訊增益比例是在資訊增益概念基礎上發展起來的，乙個屬性的資訊增益比例用下面的公式給出： 其中
假如我們以屬性a的值為基準對樣本進行分割，splitl(a)就是前面熵的概念。
對於連續屬性值，c4.5其處理過程如下：
根據屬性的值，對資料集排序；
用不同的閾值將資料集動態的進行劃分；
當輸出改變時確定乙個閾值；
取兩個實際值中的中點作為乙個閾值；
取兩個劃分，所有樣本都在這兩個劃分中；
得到所有可能的閾值、增益及增益比；
每乙個屬性會變為取兩個取值，即小於閾值或大於等於閾值。
針對屬性有連續數值的情況，則在訓練集中可以按公升序方式排列。如果屬性a共有n種取值，則對每個取值vj(j=1,2,…,n)，將所有的記錄進行劃分：一部分小於vj；另一部分則大於或等於vj。
針對每個vj計算劃分對應的增益比率，選擇增益最大的劃分來對屬性a進行離散化。
c4.5處理的樣本中可以含有未知屬性值，其處理方法是用最常用的值替代或者是將最常用的值分在同一類中。
具體採用概率的方法，依據屬性已知的值，對屬性和每乙個值賦予乙個概率，取得這些概率依賴於該屬性已知的值。
規則的產生：一旦樹被建立，就可以把樹轉換成if-then規則。
規則儲存於乙個二維陣列中，每一行代表樹中的乙個規則，即從根到葉之間的乙個路徑。表中的每列存放著樹中的結點。
資料倉儲和資料探勘
編號 data warehouse data mining 一 課內學時 32 學分 2 二 適用專業 計算機軟體與理論 計算機應用等。三 預修課程 資料庫 四 教學目的 通過資料倉儲和資料探勘的有關基礎知識介紹，使學生對其含義 作用及發展有所了解，為進一步做有關的研究打下基礎。五 大綱內容 第一章...
資料倉儲與資料探勘考試題
選擇題1.某超市研究銷售紀錄資料後發現，買啤酒的人很大概率也會購買尿布，這種屬於資料探勘的哪類問題 a.關聯規則發現 b.聚類 c.分類d.自然語言處理 2.將原始資料進行整合 變換 維度規約 數值規約是在以下哪個步驟的任務 a.頻繁模式挖掘 b.分類和 c.資料預處理 d.資料流挖掘 3.當不知道...
資料倉儲與資料探勘 實驗指導書
適用於資訊系統與資訊管理專業 江蘇科技大學經濟管理學院 2012 2 目錄前言 1 實驗一 spss clementine 軟體功能演練 5 實驗二 spss clementine 資料視覺化 9 實驗三 決策樹c5.0 建模 10 實驗四 關聯規則挖掘 21 實驗五 欺詐遮蔽 異常檢測 神經網路 ...