Frequent itemset (Aprori, FP-growth, sequential patternsㄎ

這些演算法

都是希望能在資料群中找出常發生的資料

1. Aprori

非常耗時間，但直覺且簡單

2. FP growth

(1) 不錯的slide
http://www.slideshare.net/deepti92pawar/the-comparative-study-of-apriori-and-fpgrowth-algorithm

3. Tree projection algorithm - lexicographical tree

4. PROPAD algorithm

整個演算法大致為前三步驟循環
(1)建立transaction/tempory itemset
(2)由上建立frequent itemset table
(3)由上建立projected transaction table
(4)以上面table中的點，從(1)開始繼續
(5)建立frequent set tree

ex.

(1) 可以參考這篇paper
Depth-First Frequent Itemset Mining in RelationalDatabases

4. ECLAT algorithm

不同transaction但同樣的element以自己的TID作為標記，放在一起

再利用merge的方式，即可快速得到support counting，而不必搜尋全部資料

---------------------------------------------------------------------------------

3. Sequential patterns (data stream mining)

(1) Maxspan constraint: 以最大時間來限制可考慮的資料範圍，會影響support counting 的值

(2) Maxgap and Mingap constraint: 跟上面方法很類似，但同時考慮最大和最小範圍，一樣會影響support counting 的值。

但要注意的是

若是採用這些限制可能影響Aprori演算法中，subsequence 一定也是frequent itemset

因此有新的modified Aprori Principle判斷法則

就是只考慮同樣指符合時間限制的subsequence

ex.

<1,3,5> 的 subsequence 可以有 <1,3>, <1,5>, <3,5>

但若限制 maxgap = 1

則subsequence只考慮 <1,3>, <3,5>

Cluster method (DBSCAN, K-means), cluster tendency, cluster validity

1. Method of classification

(1)DBSCAN :
優點 可以解決資料不規則分佈(歪七扭八參雜)

(2)K-means
缺點 不能解決不規則分佈資料

1. 隨機在空間中放下K點為中心點
2. 利用 Vironoi diagram 和中心點，將空間的所有點分成數個區塊
3. 計算區塊中所有點的平均值，將中心點移至那裡
4. 重複第2步驟，直至收斂

(3) MAX- distance

(4) MIN- distance




(1) 中文講解不同區分法k-means, DBSCAN
http://123android.blogspot.se/2012/01/28dec11-data-mining.html 

(2) wiki 演算法講解滿清楚
http://en.wikipedia.org/wiki/DBSCAN

-----------------------------------------------------------------------------

2. Cluster tendency

在我們真的去用演算法劃分cluster前

其實可以先借由一些方法來得知資料的分佈狀況

像是『平均分佈』或是『集中分佈』方式


ex. Hopkins statistic演算法

p 為資料空間中任意挑選的點，可以參雜真正的資料點
ui 為p點到彼此最近的點的距離
wi 為p點到最近的真正資料點的距離

從Ｈ值可以粗估一些狀況
-  接近0.5, 資料為平均分佈在空間中
-  接近1, 資料高度集中

-----------------------------------------------------------------------------

3. Cluster validity

在我們利用不同方法將資料區分成不同cluster之後

總得去分析這些方法的是否可行

下面就是幾種最為參考的數值

舉個例  

Ex.

Entropy 和 Purity 可以參考上表

但若考慮cluster 1 內

對於Metro 的 Precision = 506/667 = 0.75

對於Metro 的 Recall = 506/943 = 0.26

所以cluster 1 的 Metro 的 F measure = 2*0.75*0.26/(0.75+0.26) = 0.39

Web mining algorithm (HITS, PageRank)

1. HITS

(1) 起始化hub和authority 的值為1
(2) 計劃 Authority,  a = At * h
(3) 計算 Hub,  h = A * a
(4) 正規化 Authority 和 Hub
(5) 重複2-4的動作，直到收斂

!? a = AtA*h
!? h = AAt*a


----
[1] http://sls.weco.net/node/10937
[2] http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture4/lecture4.html
[3] http://en.wikipedia.org/wiki/HITS_algorithm#Normalization

2. Pagerank

可以分成迭代法(Iteration)和代數法(algebra)來計算得到結果

(1) 不同範例，且有小程式可計算測試
http://www.webworkshop.net/pagerank.html#toolbar_pagerank

(2) 公式推導
http://mathscinotes.com/2012/01/worked-pagerank-example/

(3) 起始值推敲說明
http://www.sirgroane.net/google-page-rank/

(4)兩種算法解說
http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html