【正文】 y ???ead [support, confidence]‖. ? buys(x, ―diapers‖) ?? buys(x, ―beers‖) [%, 60%] ? major(x, ―CS‖) ^ takes(x, ―DB‖) ???grade(x, ―A‖) [1%, 75%] 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 什么是關(guān)聯(lián)挖掘 ? ? 關(guān)聯(lián)規(guī)則挖掘： ? 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 主要聚類方法 ? 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 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 混合類型的變量 ? 一個(gè)數(shù)據(jù)庫可能包含了所有這 6中類型的變量 用以下公式計(jì)算對象 i， j之間的相異度 . 其中， p為對象中的變量個(gè)數(shù) 如果 xif或 xjf 缺失（即對象 i或?qū)ο?j沒有變量 f的值），或者 xif = xjf =0，且變量 f是不對稱的二元變量，則指示項(xiàng) δij(f)=0；否則δij(f)=1 )(1)()(1),(fijpffijfijpf djid???????169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 比例標(biāo)度型變量 ? 比例標(biāo)度型變量 （ Ratioscaled variable） : 總是取正的度量值 ， 有一個(gè)非線性的標(biāo)度 ， 近似的遵循指數(shù)標(biāo)度 ， 比如 AeBt or AeBt ? 計(jì)算相異度的方法 : ? 采用與處理區(qū)間標(biāo)度變量相同的方法 — 不是一個(gè)好的選擇 ? 進(jìn)行對數(shù)變換 ， 對變換得到的值在采用與處理區(qū)間標(biāo)度變量相同的方法 yif = log(xif) ? 將其作為連續(xù)的序數(shù)型數(shù)據(jù) ， 將其秩作為區(qū)間標(biāo)度的值來對待 。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 序數(shù)型變量 ?相異度的計(jì)算 與區(qū)間標(biāo)度變量的計(jì)算方法相類似 ?將 xif 用它對應(yīng)的秩代替 ?將每個(gè)變量的值域映射到 [， ]上，使得每個(gè)變量都有相同的權(quán)重。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 序數(shù)型變量 ? 一個(gè)序數(shù)型變量可以是離散的也可以是連續(xù)的 ? 離散的序數(shù)型變量類似于標(biāo)稱變量，除了它的 M個(gè)狀態(tài)是以有意義的序列排序的，比如職稱 ? 連續(xù)的序數(shù)型變量類似于區(qū)間標(biāo)度變量，但是它沒有單位，值的相對順序是必要的，而其實(shí)際大小并不重要。 當(dāng) q = 1時(shí) , d 稱為 曼哈坦距離 （ Manhattan distance） q qppqq jxixjxixjxixjid )||. ..|||(|),( 2211 ???????||...||||),( 2211 pp jxixjxixjxixjid ???????169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 計(jì)算對象之間的相異度 ? 通常使用距離來衡量兩個(gè)對象之間的相異度。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 聚類分析中的數(shù)據(jù)類型 ? 區(qū)間標(biāo)度變量（ Intervalscaled variables） : ? 二元變量（ Binary variables） : ? 標(biāo)稱型，序數(shù)型和比例型變量（ Nominal, ordinal, and ratio variables） : ? 混合類型變量（ Variables of mixed types） : 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 兩種數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)矩陣 ? (two modes) ? 差異度矩陣 ? (one mode) ??????????????????npx. . .nfx. . .n1x. . .. . .. . .. . .. . .ipx. . .ifx. . .i1x. . .. . .. . .. . .. . .1px. . .1fx. . .11x????????????????0.. .)2,()1,(:::)2,3().. .ndnd0dd ( 3 , 10d ( 2 , 1 )0169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 聚類方法性能評價(jià) ?一個(gè)好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果 ——簇，這些簇要具備以下兩個(gè)特點(diǎn)： ?高的簇內(nèi)相似性 ?低的簇間相似性 ?聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實(shí)現(xiàn)； ?聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式； 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 聚類的常規(guī)應(yīng)用 ?模式識別 ?空間數(shù)據(jù)分析 ?在 GIS中，通過聚類發(fā)現(xiàn)特征空間來建立主題索引； ?在空間數(shù)據(jù)挖掘中，檢測并解釋空間中的簇； ?圖象處理 ?經(jīng)濟(jì)學(xué) (尤其是市場研究方面 ) ? WWW ?文檔分類 ?分析 WEB日志數(shù)據(jù)來發(fā)現(xiàn)相似的訪問模式 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 四、數(shù)據(jù)挖掘算法－聚類 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 評估分類法的準(zhǔn)確性 ? 導(dǎo)出分類法后，再使用訓(xùn)練數(shù)據(jù)評估分類法，可能錯(cuò)誤的導(dǎo)致樂觀的估計(jì) ? 保持方法 ? 給定數(shù)據(jù)隨機(jī)劃分為兩個(gè)集合：訓(xùn)練集 (2/3)和測試集 (1/3) ? 訓(xùn)練集導(dǎo)出分類法，測試集對其準(zhǔn)確性進(jìn)行評估 ? 隨機(jī)子選樣 ：保持方法的一個(gè)變形，將保持方法重復(fù) k次，然后取準(zhǔn)確率的平均值 ? k折交叉確認(rèn) ? 初始數(shù)據(jù)被劃分為 k個(gè)不相交的，大小大致相同的子集S1,S2…S k ? 進(jìn)行 k次訓(xùn)練和測試，第 i次時(shí)，以 Si做測試集，其他做訓(xùn)練集 ? 準(zhǔn)確率為 k次迭代正確分類數(shù)除以初始數(shù)據(jù)集樣本總數(shù) 169。 ? 預(yù)測和分類的異同 ? 相同點(diǎn) ? 兩者都需要構(gòu)建模型 ? 都用模型來估計(jì)未知值 預(yù)測當(dāng)中主要的估計(jì)方法是回歸分析 ? 線性回歸和多元回歸 ? 非線性回歸 ? 不同點(diǎn) ? 分類法主要是用來預(yù)測類標(biāo)號（分類屬性值） ? 預(yù)測法主要是用來估計(jì)連續(xù)值（量化屬性值） 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 其他分類方法 ? k最臨近分類 ? 給定一個(gè)未知樣本， k最臨近分類法搜索模式空間，找出最接近未知樣本的 k個(gè)訓(xùn)練樣本；然后使用 k個(gè)最臨近者中最公共的類來預(yù)測當(dāng)前樣本的類標(biāo)號 ? 基于案例的推理 ? 樣本或案例使用復(fù)雜的符號表示，對于新案例，先檢測是否存在同樣的訓(xùn)練案例；如果找不到，則搜索類似的訓(xùn)練案例 ? 遺傳算法 ? 結(jié)合生物進(jìn)化思想的算法 ? 粗糙集方法 ? 模糊集方法 ? 允許在分類規(guī)則中定義“模糊的”臨界值或邊界 169。在學(xué)習(xí)階段，通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使得能夠預(yù)測輸入樣本的正確標(biāo)號來學(xué)習(xí)。 )()()|()|(DPhPhDPDhP ?169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 貝葉斯分類 ? 貝葉斯分類利用統(tǒng)計(jì)學(xué)中的貝葉斯定理，來預(yù)測類成員的概率，即給定一個(gè)樣本，計(jì)算該樣本屬于一個(gè)特定的類的概率。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 用判定樹歸納分類 ? 什么是判定樹？ ? 類似于流程圖的樹結(jié)構(gòu) ? 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測試 ? 每個(gè)分枝代表一個(gè)測試輸出 ? 每個(gè)樹葉節(jié)點(diǎn)代表類或類分布 ? 判定樹的生成由兩個(gè)階段組成 ? 判定樹構(gòu)建 開始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn) 遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） ? 樹剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹剪枝試圖檢測和剪去這種分枝 ? 判定樹的使用：對未知樣本進(jìn)行分類 ? 通過將樣本的屬性值與判定樹相比較 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 準(zhǔn)備分類和預(yù)測的數(shù)據(jù) ? 通過對數(shù)據(jù)進(jìn)行預(yù)處理，可以提高分類和預(yù)測過程的準(zhǔn)確性、有效性和可伸縮性 ? 數(shù)據(jù)清理 消除或減少噪聲，處理空缺值，從而減少學(xué)習(xí)時(shí)的混亂 ? 相關(guān)性分析 數(shù)據(jù)中的有些屬性可能與當(dāng)前任務(wù)不相關(guān)；也有些屬性可能是冗余的；刪除這些屬性可以加快學(xué)習(xí)步驟，使學(xué)習(xí)結(jié)果更精確 ? 數(shù)據(jù)變換 可以將數(shù)據(jù)概化到較高層概念，或?qū)?shù)據(jù)進(jìn)行規(guī)范化 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 第一步：建立模型 訓(xùn)練數(shù) 據(jù)集 N A M E RANK Y E A R S T E N U R E DM ik e A s s is t a n t P r o f 3 noM a r y A s s is t a n t P r o f 7 y e sB il l P r o f e s s o r 2 y e sJ im A s s o c ia t e P r o f 7 y e sD a v e A s s is t a n t P r o f 6 noA n n e A s s o c ia t e P r o f 3 no分類算法 IF rank = ‘professor’ OR years 6 THEN tenured = ‘yes’ 分類規(guī)則 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 分類 VS. 預(yù)測 ?分類： ?預(yù)測分類標(biāo)號（或離散值） ?根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù) ?預(yù)測： ?建立連續(xù)函數(shù)值模型，比如預(yù)測空缺值 ?典型應(yīng)用 ?信譽(yù)證實(shí) ?目標(biāo)市場 ?醫(yī)療診斷 ?性能預(yù)測 169。 ? 方法 ? 由用戶和專家在模式級顯式的說明屬性的部分序 ? 通過顯式的數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分 ? 說明屬性集，但不說明他們的偏序 ? 只說明部分的屬性集 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 分類數(shù)據(jù)的概念分層生成 ? 分類數(shù)據(jù)是離散數(shù)據(jù)。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)值數(shù)據(jù)離散化 ?聚類分析 ?基于熵的離散化 ?通過自然劃分分段 345規(guī)則 ?如果一個(gè)區(qū)間最高有效位上包括 3 6 9 個(gè)不同的值，劃分為 3個(gè)等寬區(qū)間。 ? 對于給定的數(shù)值屬性，概念分層定義了該屬性的一個(gè)離散化的值。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 離散化和概念分層 ? 離散化技術(shù)用來減少給定連續(xù)屬性的個(gè)數(shù) ? 通常是遞歸的。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)值規(guī)約 ? 聚類 ? 多維索引樹 ： 對于給定的數(shù)據(jù)集合，索引樹動態(tài)的劃分多維空間。 ?主要成分分析 169。 ? 屬性子集選擇 ? 找出最小屬性集合，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布 ? 如何選??？ 貪心算法 逐步向前選擇 逐步后向刪除 向前選擇和后向刪除相結(jié)合 判定樹歸納 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)立方體聚集 ? 尋找感興趣的維度進(jìn)行再聚集 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)變換