【文章內(nèi)容簡介】 其中 ? 計算標(biāo)準(zhǔn)度量值 (zscore) ? 使用絕對偏差的平均值比使用標(biāo)準(zhǔn)偏差更健壯（ robust） .)...211 nffff xx(xn m ????|)|...|||(|1 21 fnffffff mxmxmxns ???????ffifif smx z ??計算對象之間的相異度 ? 通常使用距離來衡量兩個對象之間的相異度。 ? 常用的距離度量方法有 : 明考斯基距離 （ Minkowski distance） : 其中 i = (xi1, xi2, … , xip) 和 j = (xj1, xj2, … , xjp) 是兩個 p維的數(shù)據(jù)對象 , q是一個正整數(shù)。 當(dāng) q = 1時 , d 稱為 曼哈坦距離 （ Manhattan distance） q qppqq jxixjxixjxixjid )||. ..|||(|),( 2211 ???????||...||||),( 2211 pp jxixjxixjxixjid ???????計算對象之間的相異度 ? 當(dāng) q=2時 , d 就成為 歐幾里德距離 : ? 距離函數(shù)有如下特性： d(i,j) ? 0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j) ? d(i,k) + d(k,j) ? 可以根據(jù)每個變量的重要性賦予一個權(quán)重 )||. ..|||(|),( 2222211 pp jxixjxixjxixjid ???????序數(shù)型變量 ? 一個序數(shù)型變量可以是離散的也可以是連續(xù)的 ? 離散的序數(shù)型變量類似于標(biāo)稱變量，除了它的 M個狀態(tài)是以有意義的序列排序的，比如職稱 ? 連續(xù)的序數(shù)型變量類似于區(qū)間標(biāo)度變量，但是它沒有單位，值的相對順序是必要的，而其實際大小并不重要。 序數(shù)型變量 ?相異度的計算 與區(qū)間標(biāo)度變量的計算方法相類似 ?將 xif 用它對應(yīng)的秩代替 ?將每個變量的值域映射到 [， ]上，使得每個變量都有相同的權(quán)重。這通過用 zif來替代 rif來實現(xiàn) ?用前面所述的區(qū)間標(biāo)度變量的任一種距離計算方法來計算 11???fifif Mrz},.. .,1{ fif Mr ?比例標(biāo)度型變量 ? 比例標(biāo)度型變量 （ Ratioscaled variable） : 總是取正的度量值 ， 有一個非線性的標(biāo)度 ， 近似的遵循指數(shù)標(biāo)度 ， 比如 AeBt or AeBt ? 計算相異度的方法 : ? 采用與處理區(qū)間標(biāo)度變量相同的方法 — 不是一個好的選擇 ? 進(jìn)行對數(shù)變換 ， 對變換得到的值在采用與處理區(qū)間標(biāo)度變量相同的方法 yif = log(xif) ? 將其作為連續(xù)的序數(shù)型數(shù)據(jù) ， 將其秩作為區(qū)間標(biāo)度的值來對待 。 混合類型的變量 ? 一個數(shù)據(jù)庫可能包含了所有這 6中類型的變量 用以下公式計算對象 i， j之間的相異度 . 其中， p為對象中的變量個數(shù) 如果 xif或 xjf 缺失（即對象 i或?qū)ο?j沒有變量 f的值），或者 xif = xjf =0，且變量 f是不對稱的二元變量，則指示項 δij(f)=0；否則δij(f)=1 )(1)()(1),(fijpffijfijpf djid???????混合類型的變量 ? f 是二元變量或標(biāo)稱變量 : if xif = xjf dij(f) = 0, else dij(f) = 1 ? f 是區(qū)間標(biāo)度變量 : dij(f) = | xifxjf |/maxhxhfminhxhf 其中 h遍取變量 f的所有非空缺對象 ? f 是序數(shù)型或比例標(biāo)度型 計算秩 rif 計算 zif并將其作為區(qū)間標(biāo)度變量值對待 11???fifMrz if主要聚類方法 ? Partitioning algorithms: Construct various partitions and then evaluate them by some criterion ? Hierarchy algorithms: Create a hierarchical deposition of the set of data (or objects) using some criterion ? Densitybased: based on connectivity and density functions ? Gridbased: based on a multiplelevel granularity structure ? Modelbased: A model is hypothesized for each of the clusters and the idea is to find the best fit of that model to each other 五、數(shù)據(jù)挖掘算法－關(guān)聯(lián) 什么是關(guān)聯(lián)挖掘 ? ? 關(guān)聯(lián)規(guī)則挖掘： ? 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 ? 應(yīng)用： ? 購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、 lossleader analysis、聚集、分類等。 ? 舉例： ? 規(guī)則形式： “ Body ???ead [support, confidence]‖. ? buys(x, ―diapers‖) ?? buys(x, ―beers‖) [%, 60%] ? major(x, ―CS‖) ^ takes(x, ―DB‖) ???grade(x, ―A‖) [1%, 75%] 關(guān)聯(lián)規(guī)則：基本概念 ? 給定 : (1)交易數(shù)據(jù)庫 (2)每筆交易是：一個項目列表 (消費(fèi)者一次購買活動中購買的商品 ) ? 查找 : 所有 描述一個項目集合與其他項目集合相關(guān)性的規(guī)則 ? ., 98% of people who purchase tires and auto accessories also get automotive services done ? 應(yīng)用 ? * ? 護(hù)理用品 (商店應(yīng)該怎樣提高護(hù)理用品的銷售？ ) ? 家用電器 ? * (其他商品的庫存有什么影響 ?) ? 在產(chǎn)品直銷中使用 附加郵寄 ? Detecting ―pingpong‖ing of patients, faulty ―collisions‖ 規(guī)則度量：支持度與可信度 ?查找所有的規(guī)則 X amp。 Y ? Z 具有最小支持度和可信度 ?支持度 , s, 一次交易中包含 {X 、 Y 、 Z}的可能性 ?可信度 , c, 包含 {X 、 Y}的交易中也包含 Z的條件概率 交易 ID 購買的商品2022 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F設(shè)最小支持度為 50%, 最小可信度為 50%, 則可得到 ? A ? C (50%, %) ? C ? A (50%, 100%) 買尿布的客戶 二者都買的客戶 買啤酒的客戶 關(guān)聯(lián)規(guī)則挖掘：路線圖 ? 布爾 vs. 定量 關(guān)聯(lián) (基于 處理數(shù)據(jù)的類型 ) ? buys(x, ―SQLServer‖) ^ buys(x, ―DMBook‖) ???buys(x, ―DBMiner‖) [%, 60%] ? age(x, ―30..39‖) ^ ine(x, ―42..48K‖) ???buys(x, ―PC‖) [1%, 75%] ? 單維 vs. 多維 關(guān)聯(lián) (例子同上 ) ? 單層 vs. 多層 分析 ? 那個品種牌子的啤酒與那個牌子的尿布有關(guān)系 ? ? 各種擴(kuò)展 ? 相關(guān)性、因果分析 關(guān)聯(lián)并不一定意味著相關(guān)或因果 ? 最大模式和閉合相集 ? 添加約束 如 , 哪些 “ 小東西 ” 的銷售促發(fā)了 “ 大家伙 ” 的買賣？ 關(guān)聯(lián)規(guī)則挖掘 —一個例子 對于 A ? C： support = support({A 、 C}) = 50% confidence = support({A 、 C})/support({A}) = % Apriori的基本思想 : 頻繁項集的任何子集也一定是頻繁的 交易 ID 購買商品2022 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F頻繁項集 支持度{ A } 75%{ B } 50%{ C} 50%{ A ,C} 50%最小值尺度 50% 最小可信度 50% 關(guān)鍵步驟：挖掘頻繁集 ? 頻繁集 :是指滿足最小支持度的項目集合 ? 頻繁集的子集也一定是頻繁的 如 , 如果 {AB} 是頻繁集，則 {A} {B} 也一定是頻繁集 ? 從 1到 k（ k頻繁集）遞歸查找頻繁集 ? 用得到的頻繁集生成關(guān)聯(lián)規(guī)則 多層關(guān)聯(lián)規(guī)則 ? 項通常具有層次 ? 底層的項通常支持度也低 ? 某些特定層的規(guī)則可能更有意義 ? 交易數(shù)據(jù)庫可以按照維或?qū)泳幋a ? 可以進(jìn)行共享的多維挖掘 食品 面包 牛奶 脫脂奶 光明 統(tǒng)一 酸奶 白 黃 T I D I t e m sT1 { 1 1 1 , 1 2 1 , 2 1 1 , 2 2 1 }T2 { 1 1 1 , 2 1 1 , 2 2 2 , 3 2 3 }T3 { 1 1 2 , 1 2 2 , 2 2 1 , 4 1 1 }T4 { 1 1 1 , 1 2 1 }T5 { 1 1 1 , 1 2 2 , 2 1 1 , 2 2 1 , 4 1 3 }挖掘多層關(guān)聯(lián)規(guī)則 ?自上而下，深度優(yōu)先的方法： ?先找高層的 “ 強(qiáng) ” 規(guī)則： 牛奶 ? 面包 [20%, 60%]. ?再找他們底層的 “ 弱 ” 規(guī)則： 酸奶 ? 黃面包 [6%, 50%]. ?多層關(guān)聯(lián)規(guī)則的變種 ?層次交叉的關(guān)聯(lián)規(guī)則： 酸奶 ? 面包房 黃面包 ?不同種分層方法間的關(guān)聯(lián)規(guī)則： 酸奶 ? 面包房 面包 多層關(guān)聯(lián)規(guī)則 ? 支持度不變 : 在各層之間使用統(tǒng)一的支持度 ? + 一個最小支持度閾值 . 如果一個項集的父項集不具有最小支持度，那他本身也不可能滿足最小支持度。 ?– 底層項不會成為頻繁集，如果支持度 太高 ? 丟失底層關(guān)聯(lián)規(guī)則 太低 ? 生成太多的高層關(guān)聯(lián)規(guī)則 ? 支持度遞減 : 隨著層次的降低支持度遞減 ? 4種搜索策略： 層與層獨(dú)立 用 k項集跨層過濾 用項跨層過濾 用項進(jìn)行可控跨層過濾 支持度不變 支持度不變多層挖掘 牛奶 [support = 10%] 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 5% 支持度遞減 支持度遞減多層挖掘 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 3% 牛奶 [support = 10%] 多層關(guān)聯(lián)：冗余過濾 ? 由于 “ 祖先 ” 關(guān)系的原因，有些規(guī)則可能是多余的。 ? 例子 ? 牛奶 ? 白面包 [support = 8%, confidence = 70%] ? 酸奶 ? 白面包 [support = 2%, confidence = 72%] ? 我們稱第一個規(guī)則是第二個規(guī)則的祖先 ? 參考規(guī)則的祖先，如果他的支持度與我們 “ 預(yù)期 ”的支持度近似的話，我們就說這條規(guī)則是冗余的。 多層挖掘：深度優(yōu)先 ?自頂向下，深度優(yōu)先的方法： ?先挖掘高層頻繁項： 牛奶 (15%), 面包 (10%) ?再挖掘他們底層的相對較弱的頻繁項： 酸奶 (5%), 白面包 (4%) ?跨層時對支持度的不同處理方法，對應(yīng)了不同的算法 : ?層之間支持度不變： 如果 t的祖先是非頻繁的，則不用考慮 t ?支持度隨層遞減： 則只考慮那些其祖先是頻繁的 /不可忽略的項 數(shù)據(jù)挖掘查詢的逐步精化 ?為什么要逐步精化 ?挖掘操作的代價可能高或低，結(jié)果可能細(xì)致或粗糙 ?在速度和質(zhì)量之間折衷：逐步精化 ?超集覆蓋特征： ?預(yù)存儲所有正面答案 —允許進(jìn)一步正確性驗證，而不必驗證已經(jīng)錯誤的 ? 2或多步挖掘： ?先執(zhí)行粗糙的、容易的操作 (超集覆蓋 ) ?然后在減少后的候選集上進(jìn)行計算量大的算法 (Koperski amp。 Han, SSD’95). 逐步求精空間關(guān)聯(lián)規(guī)則挖掘 ?空間關(guān)系的層