Elvis Hsieh Blog

今天國網中心電子報 有一則關於 Apache Spark 的報導 ，對於 Hadoop 的 MapReduce 效能點出了最大的致命傷： MapReduce 最大的缺點在於運算時需要將中間產生的資料存在 Hadoop 獨有的分散式檔案系統中(HDFS)。尤其在執行迭代演算法（註1）時，每次的輸入與輸出皆需要頻繁讀寫HDFS，這將導致大量的時間花費在資料的讀取。 也因此 Apache Spark 誕生 ，在 Apache Spark 網站的標題寫著： Apache Spark™ is a fast and general engine for large-scale data processing. 讓我比較感興趣的是： Spark 支援 Java, Scala, Python, R 語言來開發各種應用程式，也可以在單機版本運行： Ease of Use Write applications quickly in Java, Scala, Python, R. Runs Everywhere Spark runs on Hadoop, Mesos, standalone, or in the cloud. It can access diverse data sources including HDFS, Cassandra, HBase, and S3. 簡單瀏覽 Spark's Github 的網址 內的 Readme， clone 回來安裝步驟如下： 下載及解壓縮 Maven 專案套件軟體 設定環境變數讓 Maven/bin 程式可以在 cmd 中被執行：[圖 1] cmd 中輸入 mvn -v 測試：[圖 2] clone Spark stable 版本到 github 目錄：[圖 3]  build Spark: cd spark; mvn -DskipTests clean package     Spark github Readme 的說明，測試 Spark 是否安裝成功： 測試 Spark-shell：           cd bin; spark-sh...

What is association rule mining?  A:   Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction Definition • Support count (\sigma):  itemset  出現的次數 ∘ Frequency of occurrence of an itemset ∘ E.g.   \sigma({Milk, Bread,Diaper}) = 2 • Support: 某一個 itemset / itemset 的總數 ∘ Fraction of transactions that contain an itemset ∘ E.g.    s({Milk, Bread, Diaper}) = 2/5 • Frequent Itemset ∘ An itemset whose support is greater than or equal to a minsup threshold •  Rule Evaluation Metrics ∘ Support (s): Fraction of transactions that contain both X and Y, i.e.    \sigma({X, Y}}/T ∘ Confidence (c): Measures how often items in Y appear in transactions that contain X,   \sigma({X, Y}}/ \sigma (X)    Maximal Frequent Itemset: • An itemset is maximal frequent if none of its immediate supersets is frequent(最相近的 superset 都不是 frequent it...

Type of Clustering:[1] k-means clustering The algorithm steps are: • Choose the number of clusters, k. • Randomly generate k clusters and determine the cluster centers, or directly generate k random points as cluster centers. • Assign each point to the nearest cluster center, where "nearest" is defined with respect to one of the distance measures discussed above. • Recompute the new cluster centers. • Repeat the two previous steps until some convergence criterion is met (usually that the assignment hasn't changed). Hierarchical Algorithm • Produces a set of nested clusters organized as a hierarchical tree • Two main types of hierarchical algorithm are  either agglomerative ("bottom-up") or divisive ("top-down") •  Agglomerative(凝聚) algorithms begin with each element as a separate cluster and merge them into successively larger clusters • Divisive(分離) algorithms begin with the whole set and proceed to divide it into successively smaller ...

Sequence  Data(ch7 ppt 28) • 討論有關與資料出現順序有關的 itemsets, 例如:生物的 DNA, ATGC 字母的出現順序是有關係 • 在 sequence 中的 elements 是有順序關係，但是在 elements 中的 itemsets 是沒有順序性，如同之前章節所討論的 itemsets 一樣，與順序無關 • 算 sequence 長度是計算其中 events 的個數，但是所謂 k-sequence 是計算 sequence 中所有 items 的個數，即 k-sequence 共有 k 個 events(items) 的 sequence, for example, <{a,b} {a,c} b {d, f}> sequence is 7-sequence. Formal Definition of a subsequence(ppt 30) • A sequence <a1 a2 … an> is contained in another sequence <b1 b2 … bm> (m >=n) if there exist integers i1 < i2 < … < in such that a1 \in bi1 , a2 \in bi1, …, an \in bin • 在表第二列中，因為 {1},{2} 不同時間發生，所以不是<{1,2} {3,4}> 的 subsequence    • 檢查是否是某一個 sequence 的 subsequence 的方法 ∘ 檢查順序是否相同 ∘ 檢查是否為 sequence 的子集合 Contiguous Subsequences s is a contiguous subsequence of  w = <e1>< e2>…< ek> • if any of the following conditions hold: ∘ s is obtained from w by deleting an item from either e1 or ek ∘ s is obtained fro...

Data Mining Project 2010Fall Data Mining course 的 project 原本是選 content-base Image Retrival 的題目，但是因為無法取得 data set，而且要自己產生 data set 必須花費很多時間，所以更換了 use of KNN for Netflix Prize 這個題目，如果有時間可以將原來使用 boosting algorithm 擷取 images 的題目實做看看，已經找到 Fire[1], Firewatch[2] 的 source code. 在 KNN project 中，William 修改了 ice Netflix framework 的程式，其中 probe.ccp comment out 169-170 line 取消了 執行到 297 就停止的限制，comment out 175-178 line 把 compile 時將結果輸出到螢幕的部份 comment out，減少 compile 的時間。 基本上要先安裝 Qt4 SDK ，然後將 Netflix data set 放到 root folder，也就是與 icefox-netflixrecommenderframework-b0315e1 同一層的目錄中，然後開啟 algorithm/knn/knn.pro 的 project 執行 Build all 即可。 [1] http://thomas.deselaers.de/fire/ [2] not found