# 資料探勘
* paper presentation：20min + 5min Q&A
* HW1(4月中)：data preprocessing (data -> vector -> Reduction)
## 1-Data Preprocessing!
[](https://i.imgur.com/BbxQOpX.png)
### Cleaning data
* Why Data Preprocessing？
* ->Data是imcomplete、noisy、inconsistent(表示方式有差異)
* Handle Missing Data
* 方法：
1. 忽略
2. 人為or自動處理
* handle noisy data
1. Binning method:
1. Data排序，分到好幾個桶子中(bin)
1. Equal-width：同寬度。0-20000、20001-40000
2. Equal-depth：固定切n個，每個bin的數目大致相同
2. 做smoothing：4 8 9 15
1. by means：4 4 4 4
2. by bin boundaries：看Data與頭尾的值誰較近4 4 4 15

2. clustering：在cluster以外的Data視為noisy data
3. 半人工半機器處理noisy Data
4. regression：離線越遠的點視為noisy data

### Data Integration：整合多個database
* data integration：把不同source的data整合在一起。
* schema integration(名稱)：id vs 序號
* 統一度量衡
### data transformation
* smoothing：remove noise
* aggregation：summarization， data cube construction
* Generalization：concept hierarchy (以同一相似階層做分系，EX年齡層)
* normalization：

1. min-max：將資料等比例縮放到 [0, 1] 區間中。
2. z-score：$z=\frac{x-mean}{std}$
3. log scaling：log(x)
4. softmax function：x' = $\frac{e^x}{\sum e^x}$，頻率高的data影響力更大。
### Data discretization資料離散化：將資料以區間重新劃分，常用於數據資料。
### data reduction：用較少資料，但能表示原本大量資料的結果。
* feature/dimension/attribute selection(較不熱門)
#### dimensionality Reduction
1. 一個個加(greedy)：一個個feature測試效果，前一個找到的feature搭配。
2. 一個個減
3. 1+2混用(先加後減)
4. Decison tree：把分類效果最好的feature作為root分2類。靠近root的feature優先選
#### data compression
* 儲存可處理的資料中有效的部分
* Haar：任何函數都可用2個正交函數(內積=0)(1,1)、(1,-1)表示，同除以根號2
* 步驟：
1. 以2個為一組
2. 先與(1,1)做內積、再做(1,-1)
* 即2個為單位相加除以根號2，全跑完再做相減除以根號2
* Wavelet Transforms：可用於降維
* 
* 轉換前後：內積不變，絕對值不變，無損壓縮
* 其他更多組合：Daubechies wavelet：以n個為一組
* 可用於圖片壓縮
* Principal Component Analysis
* 找到較少的feature數量表示原資料
* Singular Value Decomposition (SVD)
* X1用新的feature投影到Y1、Y2
* 以可顯區分資料最多的Y投影。Y1比Y2好
* Y1 Y2怎麼來? -> eigenvalue、eigenvector
* 以eigenvalue較大的Attribute作為新的Y
* SVD decomposition奇異值分解：$A=U * \lambda * V^T$
* 是一種線性代數演算法，拆分後可得關鍵資訊。奇異值分解同時包含了旋轉，縮放和投影三種作用
* U：資料數目的單位向量， 將$AA^T$的特徵向量組成的就是我們SVD中的U矩陣，
* $\lambda$：eigenvlaue重要性，由左上到右下遞減，只有對角線元素有值，且代表想下降到的維度。不一定是方陣。
* 在某個奇異值的數目（r個）之後，其他奇異值都置為零，這就意味著資料集中僅有 r 個重要特徵，其餘的都是噪聲或冗餘資料。
* V：attribute數目的單位向量
* 實務上k不會很大(基本上遠小於n)，即可降維並包含很多資訊
*

* 
* 
* 5維資料投影到2維：原資料與做內積得x,y值
* 用$A*V=U * \lambda$比較好算，即AV (= UL) defines the transformed dataset
1. 先用$A^TA$拆分eigenvalue與eigenvvector得到V
2. 再用原資料$A*V=U * \lambda$極為壓縮後的資料。
* 取的維度可用$\dfrac{\sum \lambda(c個)}{\sum \lambda(全部)}$約為80%~90%較好
* (SVD應用在IR)Latent Semantic Analysis (LSA, LSI)
* 負值無法得到資訊
* Non-negative Matrix Factorization (NMF)：為解決負值無法顯示意義的問題
* 拆成2個矩陣，$V=W*H$，皆為正值
* 目標：Minimize $||V-WH||^2$ with respect to W and H, W,H>0
* n個維度下降至c個維度
* 理想的狀況：W的單位向量互相垂直$W^TV=W^TWH$
* 學習過程
* 分解之後出來的兩個矩陣，參考上圖，H矩陣是書目隊上一個新的維度，你可以把他想成不同的書可以被分成不同的群，所以裡面的數值就是不同的書目被歸到不同群的程度，W矩陣顧客對上一個新的維度，你可以把他想成這些客戶喜歡不同群的程度
* 有時處理結果反而更清楚(因為非負值?)
* NMF Basis Images
* Only allowing adding of basis images makes intuitive sense
* NMF可用於填空值(影片推薦系統)
* 參考類似user or 影片來填空值
* Autoencoder(非線性reduction)：非線性mapping。x與x'越相近越好
* 使用activation function達到non-linear mapping
* Training autpencoder：若input為bit vector或機率vector，常使用cross entropy
* 使用cross entropy loss：計算2個機率分布(x、$x^'$)的距離
* 
* 左邊適合處理已看過的資料 -> 新資料不要太多
* 適用於training階段
* hidden nodes對training來說會是好的feature
* 右邊有些feature是湊出來的，要挑。但較適合複雜的分布

* Numerosity Reduction：減少數量
* 2種方式
* 有參數方法：假設資料符合某種model分布，以model(函數)表示，紀錄model即可。例：Regression
* 常使用最小平方法to fit the line
* 無參數方法：沒有相似model，要用其他方式，例：Sampling、Clustering、直方圖記錄分布(只挑重要的feature)
* 
* Sampling(取樣)：通常用adaptive sampling method，如：分層抽樣(Stratified sampling)用一些特徵分層，不同層間變異大，在各自層裡取樣。
* Hierarchical Reduction
* 以不同解析度觀點來切資料
* Discretization離散分法：訂定數值範圍來切(1-10，11-20...)
* Concept hierarchies：以較高層次的概念來切(青少年、青年、中年...)
* Entropy-Based Discretization：先假設一個切割點,在計算該點左右兩邊的值以評估該點是否屬於好的分割點,反覆作業直到找到最好的分割點,屬於supervised
* Entropy = $\sum -P_i*log(P_i)$
* ，此為遞迴方法，直到中止條件如
* 資料分布平均時，entropy值越大
* entropy用於分辨資料一致性，越大->資料分布越分散
* 可協助決定切資料entropy越小越好
* Segmentation by Natural Partitioning
* A simply 3-4-5 rule can be used to segment numeric data into relatively uniform, “natural” intervals.
## 2-Classification
### Classification vs. Prediction
* Prediction：models continuous-valued functions, i.e., predicts unknown or missing values
### Classification: A Two-Step Process
* training、testing
### Evaluating Classification Methods
* Accuracy
* Speed
* Robustness：對資料欄位是否都要有值才能預測?
* Scalability
* Interpretability可解釋性
### Decision Tree
* 
#### 挑attribute的方法
* 找出有鑑別力的attribute做分類
* top-down recursive divide-and-conquer manner
* 連續性資料做分段切割
* 何時停止？
1. 分類內全部一致
2. 有一定threshold數量一致
* 如何選attribute？用Information Gain(entropy算)，稱為ID3方法
* 
* Information gain = 初始entropy - 參數entropy
* Information gain越大越好
* Computing Information-Gain for Continuous-Value Attributes
* 用切的(best split point)
* ID3 -> C4.5，Gain Ratio for Attribute Selection (C4.5)
* Information gain的正規化
* 
* Gini index (CART, IBM IntelligentMiner)
* GINI INDEX越小，各組資料一致性較高 -> 可選此attribute
* All attributes are assumed continuous-valued

* 基本上，分成越多組(越多label)的attribute，越有機會成為分類依據。但不一定表現越好 -> 用gain ratio處理
* 但gain ratio也有問題，傾向選會分小堆的attribute

* decision tree的解釋力較高
* 
#### Overfitting and Tree Pruning
* 避免overfitting的方法：剪枝
1. Prepruning: Halt tree construction early—do not split a node if this would result in the goodness measure falling below a threshold
2. Postpruning: Remove branches from a “fully grown” tree—get a sequence of progressively pruned trees。bottom-up方式修剪過多的樹枝

#### Enhancements to Basic Decision Tree Induction
### Bayesian classification
#### 基礎介紹：以機率為主的分類方式
* 假設：事件獨立、incrementally漸進方式增加/減少機率
* 事前機率、事後機率
* ，可省略分母(都一樣)
* 獨立：
* 解決連乘越小的問題 -> 取log連加
#### Bayesian Belief Networks
#### Neural Network
##### Feed & foreward
* x交運算後若通過threshold$\theta$，進行下一NODE運算
* 若發生error，threshold與w參數需調整
* threshold調整
* w參數調整
* 
* Hidden layer的調整：用output layer的調整做反向權重加總
* 

#### CNN & RNN
* Convolutional Neural Network (CNN)
* 

* 
* 解為：上式所得的面積(矩陣運算)
* 2種layer組成：
* Convolutional layer：擷取局部重要資訊(EX轉角)
* pooling layer：簡化圖層資訊4x4 -> 2x2
* 以上可擷取特徵，並解決：平移、縮放、旋轉等差距
* 
* Activation functions：主要是利用非線性方程式，解決非線性問題，若不使用激勵函數，類神經網路即是以線性的方式組合運算，這樣機器學習就沒意義了
1. Sigmoid
* 用於分類問題，輸出範圍介於[0, 1]。
* 由於feed-forward network通常會用back-propagation訓練，這個方法是gradient-based method，所以activation是可微的函數比較好計算
* 微分最大值$1/4$
2. Hyperbolic tangent
* 常用於分類問題，輸出範圍介於[-1, 1]，學得比Sigmoid慢
* 微分最大值1
* 
* 例：$Err_3=O_3(1-O_3) [W_{3-6}O_6(1-O_6)(O_6-T_6)+W_{3-7}O_7(1-O_7)(O_7-T_7)+W_{3-8}O_8(1-O_8)(O_8-T_8)]$
* Vanishing gradient problem：太多layer時，微分的learning效果會越來越小，以Hyperbolic tangent為例：$(1/4)^n$
* 解法：使用另一Activation function----Relu函數$f(x)=max(0,x)$
* RNN & LSTM(RNN的一種，在Vanishing gradient problem改良)
* RNN：將input連接output後，再作為input輸入
* 仍然有Vanishing gradient problem
* LSTM
* 加入Cell state：表示network狀態，LSTM會同時學習C、h
* 用來忘掉一些要素
* 
* 
* concat：2向量接起來
* C：忘舊的，記新的
* $f_t$：bit計算後為0的話，忘掉
* $i_t$決定哪些bit要帶到下一層。$C_t'$決定哪些內容要帶到下一層
* 計算以上資訊得到$C_t$
* $o_t$根據上層h與輸入x計算。$h_t$由$o_t$與$C_t$做tanh計算得到
* Neural network
* 缺點：
1. training時間很久
2. 很多參數需調整
3. 解釋性低
* 優點：
1. 對noise data抵抗性高
2. 可平行化計算
3. 對真實世界資料表現良好

## Reinforcement Learning
* 
* 以最大化Reward為目標
* 常用於做很久的learning
* 監督式與增強式學習差距
* Reinforcement learning種類
* actor：由state、reward學習
* critic：評估一個actor的好壞，好的actor會藉由Critic挑出，Q-learning就是這樣的方法。
* 
* 以Reward的總和評量Actor分數
* 
* 以圍棋為例，可能依最後棋局贏輸算一次分
* 條件機率計算，調整$\theta$學習actor(第2項)
* 
* 對reward做gradient descent

* 
* (舊)
* Actor-Critic

## Support Vector Machine分辨模型容忍度，常用OR做最佳化
* 紅色點帶入直線方程式距離大於等於1；綠色點小於等於1

* 點與直線的距離、點在範圍外的距離
* 2次曲線
* 一般式$ax^2+bxy+cy^2+sx+ey+f=0$
* 可做座標轉換簡化問題
* 目標為最大化 margin
* Kernel Functions：通常是多項式(polymonial)
* RBF kernal可優先用，特色是?甚麼時候導致缺點?黃色點應分到與綠色相近，但被分成紅色 -> overfitting
* 若非線性可分怎麼辦?slack variable(允許誤差)
* SVM與Neural Network的差異?
* KNN
* 
* KNN有甚麼問題Curse of dimensionality

## Genetic Algorithm
* 
* 

## Ensemble Methods
* 
### Boosting
* Weights are assigned to each training tuple
* After a classifier Ci is learned, the weights are updated to allow the subsequent classifier, Ci+1, to pay more attention to the training tuples that were misclassified by Ci
* Comparing with bagging: boosting tends to achieve greater accuracy, but it also risks overfitting the model to misclassified data
* Adaboost

## Clustering
* 甚麼時候用? -> label出不來的時候
* clustering時domain knowledge要參與少，減少參數input
* 處理資料：可用z-score做正規化
* similarity：距離公式(Euclidean)
* Binary的距離 Jaccard coefficient
* nominal variable(multi-class)的距離
1. $d(i,j)= \dfrac{p-k}p$
2. 全部binary化表示000 001 010 011 100
* ordinal variable有順序值的距離
* normalize到0-1
* Ratio-scaled variable：數值差異太大時
* 取log
* Mix type(各種資料型態混和時)
1. 分開算，再加權平均
* vector方式：文件
* cosine similarity

### cluster之間的距離
* single link：合併的時候可能使資料點的差異過大問題、complete link：合併時可能併到不是最相近的cluster問題、average link、centriud'：可能不是原本的資料點、medoid：以最靠近centroid的真實資料來計算

#### cluster算中心點
* centroid
* raddius(半徑)
* Diameter(直徑)

#### Clustering的方法
* 分割：資料點到中心點的距離越小越好
* k-means
* 優點：
* 有效率O(tkn)，基本上t, k << n，可視為linear時間複雜
* 大多結束在local minimun -> 就多做幾次看哪個好
* 缺點：
* 中心點要算得出來才能使用(EX文字資料的中心點?)
* 要先決定分成幾個cluster k，不一定直覺
* noise, outlier data 影響很大
* 無法計算出不規則形狀的cluster，大都圓形
* k-means變形：k-mode可處理分類label的資料
* 以出現頻率最多的資料為中心點
* k-medoids：最靠近centoid的點
* PAM(Partitioning Around Medoids)
* starts from an initial set of medoids and iteratively replaces one of the medoids by one of the non-medoids if it improves the total distance of the resulting clustering
* PAM works effectively for small data sets, but does not scale well for large data sets

* Fuzzy C-means：

* 一個資料點可以屬於2個以上的cluster(以機率為基礎)，一樣先任意選c個center
* 以m控制fuzzy程度(m>=1)，m為1時退化為k-means
* 隸屬度與距離的$\dfrac{2}{m-1}$次方成反比，隸屬度計算
* 
* 資料點隸屬度的計算
* 資料點與每個中心點的機率總合為1；中心點對每個中心點的機率總和通常不為1
* 新中心點的計算
* 下圖的分母應該要個別m次方
* 優點：非監督式、一定會收斂(converge)
* 缺點：計算時間長，一樣對noise、outlier

* 階層型Hierarchical clustering
* 每次把最接近的cluster合併
* bottom-up(AGNES)常用
* top-down(DIANA)
* Chameleon：做Graph，Node之間越多連結表示越相似
* 
* 可做出不規則形狀的cluster

* Density-based：密度較高的點為一cluster(較多使用DBSCAN)
* DBSCAN
* 2個參數Eps(半徑)、MinPts(形成一個cluster的最少資料個數)，受參數影響很大
* Directly density-reachable：若以q為中心作圓，若可包含p，則p為q所Directly density-reachable

* Density-connected：若o可以從p、q作Density-reachable，則可能可以合併。
* 
* 做法：
* grid-based：資料點存在的空間切成格子，格子內密度夠高可為一cluster，鄰近間的格子可合併。(Wavecluster)
* Wavecluster
* 透過wave-transform，不同resolusion有不同的cluster

* 特性
*

* model-based：假設資料符合某些model分布
* EM model(Expectation Maximization)統計方法：c-means的延伸，每個點與中心點都有一個機率權重分布關係
* 步驟
* 例子：
* 假設成績服從下列分布
* 做Maximize likelihood
* 一個問題
* 做EM步驟到收斂
* 在cluster時，假設資料成常態分佈
* 
* 目標：最佳化k個中心點位置
* LDA(Latent Dirichlet Allocation)：假設符合Dirichlet分布，常用在text mining
* 計算機率分布
* 怎麼標顏色? -> 用Gibbs sampling algorithm
* 
* -i：先把第i個字MASK掉
* 前項：文章d內，除了MASK掉的那一個字，屬於topic k的字越多，機率越大。
* 後項：所有文章中，除了MASK掉的那一個字，屬於topic k的字越多，機率越大。
* 例子
* Clustering high-dimensional data
* Curse of Dimensionality：因在投影到不同維度下，data間的距離會放大或縮小
* 僅使用部分的dimension來切分資料
* 

* frequent pattern-based：找出常發生的pattern作clustering
* 只使用部分實驗結果來分析

* user-guided(constraint-based)

* What is outlier discovery：找出最少出現的東西
*