大數(shù)據(jù)挖掘

數(shù)據(jù)挖掘

數(shù)據(jù)挖掘定義

技術(shù)層面：

數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中、人們事先不知道的、但又==潛在有用的信息==的過程。

數(shù)據(jù)準(zhǔn)備環(huán)節(jié)

數(shù)據(jù)選擇 質(zhì)量分析 數(shù)據(jù)預(yù)處理

數(shù)據(jù)倉庫

從多個(gè)數(shù)據(jù)源搜集的信息存放在一致的模式之下

特征化

對(duì)目標(biāo)數(shù)據(jù)的一般特性和特征匯總

聚類分析

最大化類內(nèi)相似度 最小化類間相似性

數(shù)據(jù)準(zhǔn)備

大數(shù)據(jù)定義

超出正常處理范圍

由海量數(shù)據(jù)＋復(fù)雜類型的數(shù)據(jù) 構(gòu)成

數(shù)據(jù)對(duì)象

組成數(shù)據(jù)集的元素，每個(gè)數(shù)據(jù)對(duì)象均為一個(gè)實(shí)體

數(shù)據(jù)對(duì)象由屬性描述

數(shù)據(jù)的正確性分析

缺失值

數(shù)據(jù)錯(cuò)誤

度量標(biāo)準(zhǔn)錯(cuò)誤

編碼不一致

處理缺失數(shù)據(jù)

忽視

較小缺失率 有缺失值的樣本或?qū)傩?/p>

人工補(bǔ)全缺失值

重新采樣

領(lǐng)域知識(shí)

自動(dòng)補(bǔ)全缺失值

固定值

均值

基于算法

插補(bǔ)法

均值插補(bǔ)

回歸插補(bǔ)

極大似然估計(jì)

噪聲過濾

回歸法

均值平滑法

離群點(diǎn)分析

處理噪聲數(shù)據(jù)

局部離群因子LOF計(jì)算

數(shù)據(jù)量

子集選擇

數(shù)據(jù)量太大

減小時(shí)間復(fù)雜度

數(shù)據(jù)聚合

尺度變換

數(shù)據(jù)更穩(wěn)定

調(diào)整類分布

不平衡數(shù)據(jù)

哈爾小波交換

通過調(diào)整分辨率

數(shù)據(jù)標(biāo)準(zhǔn)化

最小最大標(biāo)準(zhǔn)化

Z-score標(biāo)準(zhǔn)化

大數(shù)據(jù)挖掘與分析

鄰近性

相似性和相異性統(tǒng)稱為鄰近性

數(shù)據(jù)矩陣

存放數(shù)據(jù)對(duì)象

相異性矩陣

存放數(shù)據(jù)對(duì)象的相異性值

二元屬性鄰近性

數(shù)值數(shù)據(jù)距離

閔可夫斯基距離

h=1 2 正無窮

維度詛咒

基于距離的聚類在高緯度下無效

在高維情況下 P（0,1）更有效

逆文檔頻率

IDF 或 Goodall度量

基本思路：

將基本詞匯看做全部屬性的集合

每個(gè)詞頻是屬性的值

余弦度量

余弦相似度

逆文檔頻率 阻尼系數(shù)

累計(jì)距離矩陣（大概率）

計(jì)算等圖

算法題目APRIORI

基本的Apriori算法
Apriori算法的基本思路是采用層次搜索的迭代方法，由候選(k-1)-項(xiàng)集來尋找候選k-項(xiàng)集，并逐一判斷產(chǎn)生的候選k-項(xiàng)集是否是頻繁的。
　　設(shè)C k 是長度為k的候選項(xiàng)集的集合，L k 是長度為k的頻繁項(xiàng)集的集合。為了簡單，設(shè)最小支持度閾值min_sup為最小元組數(shù)，即采用最小支持度計(jì)數(shù)。

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閾值min_sup。
輸出：所有的頻繁項(xiàng)集集合L。
方法：其過程描述如下：

通過掃描D得到1-頻繁項(xiàng)集L1;
for (k=2;Lk-1!=Ф;k++)
{      Ck=由Lk-1通過連接運(yùn)算產(chǎn)生的候選k-項(xiàng)集;for (事務(wù)數(shù)據(jù)庫D中的事務(wù)t){	求Ck中包含在t中的所有候選k-項(xiàng)集的計(jì)數(shù);Lk={c | c∈Ck and c.sup_count≥min_sup};//求Ck中滿足min_sup的候選k-項(xiàng)集}
}
return L=∪kLk;

這是通過Apriori計(jì)算最大頻繁項(xiàng)集 和 計(jì)算強(qiáng)關(guān)聯(lián)規(guī)則的題目

要求為超過最小支持度 最小支持度的計(jì)算很簡單

即為

Apriori優(yōu)化

基于散列的Apriori

基于散列的Apriori技術(shù)基于Apriori算法， 為了解決此算法在數(shù)據(jù)集較大的情況下候選項(xiàng)集數(shù)量爆炸的問題 以及支持度計(jì)數(shù)效率低下的問題

基于散列的優(yōu)化：

在生成候選項(xiàng)集時(shí)，通過哈希函數(shù)映射分桶 每個(gè)桶記錄頻數(shù) 如果桶中的頻數(shù)小于最小支持度的閾值 則該桶中所有項(xiàng)集可以直接剪枝

因?yàn)橥ㄟ^哈希函數(shù)可以快速找到相應(yīng)的桶，所以計(jì)算效率較高

h(x,y)=(hash(x)+hash(y))modn

哈希樹分組

算法題目FPgrowth

條件模式基的尋找

在FPtree的項(xiàng)目里倒著找，沿著虛線將出現(xiàn)的頻次進(jìn)行統(tǒng)計(jì)，，寫出條件模式基

條件FP Tree

沿著條件模式基畫FP Tree

記得剪去最小支持度不夠的項(xiàng)

頻繁項(xiàng)集

將條件FPtree與項(xiàng)進(jìn)行組合 得到頻繁項(xiàng)集

列式計(jì)數(shù)Apriori算法

使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集

關(guān)聯(lián)模式挖掘

超集

包含了另一個(gè)集合中所有元素的集合為超集

閉模式

一個(gè)頻繁項(xiàng)集 沒有任何它的超集具有與他相同的支持度

也就是不被冗余覆蓋的核心模式

閉模式顯著減少了需要存儲(chǔ)的頻繁模式數(shù)量

可以推導(dǎo)出所有頻繁模式及其支持度

極大模式

沒有頻繁的超集

極大模式只保留頻繁模式中“最大”的部分

無法還原所有頻繁模式的支持度信息

序列模式

序列模式是指諸如此類的模式，其項(xiàng)中包含多個(gè)項(xiàng)，在計(jì)數(shù)時(shí)，相同項(xiàng)僅計(jì)數(shù)一次

聚類

好的聚類方法產(chǎn)生高質(zhì)量的聚類結(jié)果

要求

高類內(nèi)相似性 高內(nèi)聚

低類間相似性 低耦合

能夠發(fā)掘隱藏模式 有價(jià)值

聚類的好壞在于：

相似度測量方法

不同尺度 不同類型的距離函數(shù)設(shè)計(jì)不同

主要聚類方法

基于代表點(diǎn)的聚類

代表性方法：kmeans kmedians kmedoids CLARANS

層次方法

基于準(zhǔn)則對(duì)數(shù)數(shù)據(jù)層次分解

代表性方法：Diana Agnes BIRCH CAMELEON

基于密度的方法

代表性方法：DBSCAN OPTICS DENClue

基于網(wǎng)格的方法

代表方法：STING WaveCluster CLIQUE

基于模型的方法

代表性方法：EM SOM COBWEB

聚類評(píng)估方法(概率低)

熵不考哈

熵 ：可以反饋特征子集的聚類質(zhì)量

經(jīng)驗(yàn)法

肘方法

交叉驗(yàn)證

基于代表點(diǎn)聚類

K means

kmedians

選取代表點(diǎn)選取中值 對(duì)異常點(diǎn)不那么敏感

Kmedoids

從非代表點(diǎn)中隨機(jī)選取點(diǎn)代替中心點(diǎn)集合中的某個(gè)點(diǎn)，重新劃分 諸葛嘗試 選擇最優(yōu)

PAM

1不受離群點(diǎn)數(shù)據(jù)影響

2適于處理小數(shù)據(jù)集

CLARA(小概率)

基于抽樣的方法 找到最優(yōu)中心點(diǎn)集為目標(biāo)

CLAEANS（小概率）

采樣并隨機(jī)選擇

層次聚類

AGNES凝聚法

不斷將簇進(jìn)行合并 最后得到所有合并后的集合為止

DIANA法

分裂法

Birch

CHAMELEON

基于密度聚類

1. 發(fā)現(xiàn)任意形狀簇Discover clusters of arbitrary shape
2. 能容忍噪音Handle noise
3. 一邊掃描One scan
4. 需要以密度相關(guān)的參數(shù)作為終止條件

DBSCAN

原理：

? 對(duì)象的密度可以用靠近該對(duì)象的節(jié)點(diǎn)數(shù)量表示。

? 找出核心對(duì)象和其鄰域，形成稠密區(qū)為簇

參數(shù)：

Eps ： 鄰域半徑

MinPts ： 鄰域半徑內(nèi)的最小節(jié)點(diǎn)數(shù) 判斷是否為核心節(jié)點(diǎn)的閾值

核心節(jié)點(diǎn)q 滿足

|N_Eps (q) | ≥ MinPts

核心節(jié)點(diǎn)擴(kuò)展區(qū)域 邊緣節(jié)點(diǎn)定義邊界

或者

OPTICS（可能不考）

定義了兩種距離，核心距離與可達(dá)距離

對(duì)于不同對(duì)象可能有不同的可達(dá)距離

DENCLUE（大概率不考）

引入影響函數(shù)與密度函數(shù)的概念進(jìn)行聚類

離群點(diǎn)檢測

離群點(diǎn)Outlier:

以一種不同機(jī)制產(chǎn)生的不同于大多數(shù)據(jù)表現(xiàn)的不正常的數(shù)據(jù)。

如：虛假行為，電信詐騙，醫(yī)藥分析，網(wǎng)絡(luò)攻擊，等。

與噪音數(shù)據(jù)區(qū)別

噪音數(shù)據(jù)是錯(cuò)的數(shù)據(jù)

是一個(gè)測量變量中的隨機(jī)錯(cuò)誤或誤差 包括錯(cuò)誤的值 偏離期望的孤立點(diǎn)

噪音數(shù)據(jù)在數(shù)據(jù)處理前已經(jīng)被移除。

分類

全局離群點(diǎn)

情境（條件）離群點(diǎn)

今天的最高溫度是-15度

集體離群點(diǎn)

數(shù)據(jù)對(duì)象的子集形成集體離群點(diǎn)

例如:一些計(jì)算機(jī)之間頻繁發(fā)送信息

離群點(diǎn)特征

有趣的 少量的

基于離群點(diǎn)方法檢測出的離群點(diǎn)不能對(duì)應(yīng)真正的異常行為

只能為用戶提供可疑數(shù)據(jù)

基于密度的方法

直方圖

通過直方圖找到

核密度估計(jì)

確定數(shù)據(jù)中的稀疏區(qū)域以便報(bào)告異常點(diǎn)

基于概率的方法

極值：對(duì)應(yīng)概率分布的統(tǒng)計(jì)尾部

識(shí)別模型低概率區(qū)域中的對(duì)象

一元離群點(diǎn)檢測

根據(jù)概率密度函數(shù)進(jìn)行

基于距離的方法

基本思路

數(shù)據(jù)集中顯著偏離其他對(duì)象的點(diǎn)

根據(jù)每個(gè)點(diǎn)在局部區(qū)域上的密度和其鄰近點(diǎn)的密度來判斷異常程度

基于聚類的方法

檢測方法

建立正常模型

離群點(diǎn)為不能正常符合這個(gè)模型的數(shù)據(jù)點(diǎn)

將異常數(shù)據(jù)度量為數(shù)值

分?jǐn)?shù)越大越可能是離群點(diǎn)

形式

基于聚類產(chǎn)生簇

尋找遠(yuǎn)離簇的數(shù)據(jù)點(diǎn)

考慮對(duì)象和它最近簇之間的距離

半監(jiān)督學(xué)習(xí)

結(jié)合聚類與分類檢測離群點(diǎn)

先基于聚類識(shí)別正常簇，然后使用這個(gè)簇的一類模型識(shí)別離群點(diǎn)