1. MLLib
Là một thư viện hữu ích của Apache Spark về Machine Learning.
Một số ưu điểm của Spark
- Nhanh hơn Hadoop MapReduce: dùng memory là 100x lần, dùng disk là 10x lần
- Dễ dàng sử dụng với Java (7+), Scala (Spark 1.6.1 dùng Scala 2.10), Python (2.6+), R (3.1+)
- Cung cấp nhiều thư viện: Spark SQL, Spark Streaming, MLLib, GraphX
- Có thể chạy Spark
- Standalone mode (https://spark.apache.org/docs/latest/spark-standalone.html)
- Trên EC2 (Amazon Elastic Compute Cloud – Môi trường điện toán đám mây do Amazon cung cấp)
- Trên Hadoop (là một Apache Framework mã nguồn mở cho phép xử lý phân tán các tập dữ liệu lớn trên các cụm máy tính)
- Trên Mesos
- Có thể truy cập dữ liệu trên
- HDFS
- Cassandra
- HBase
- Hive
- S3
- Tachyon
- …
2. Association Rules (AR)
Là một phương pháp phát hiện các mối quan hệ giữa các đối tượng trong một khối dữ liệu lớn.
Ví dụ trên bài toán gợi ý tin tức cho người dùng, ta có tập dữ liệu
User1 đọc Tin tức 1, Tin tức 2, Tin tức 4
User2 đọc Tin tức 1, Tin tức 2
User3 đọc Tin tức 2, Tin tức 3, Tin tức 4
User4 đọc Tin tức 3, Tin tức 5, Tin tức 1
User5 đọc Tin tức 5 ...
Từ tập dữ liệu này AR giúp xác định mối quan hệ giữa các tin tức (đối tượng) và dựa vào đó ta có thể biết nên đưa ra gợi ý nào là hợp lý.
Với User đọc Tin tức 1 => có thể gợi ý Tin tức 2 ...
Sau đây là 1 số khái niệm của AR
2.1 Transaction (Giao dịch)
Là lần thực hiện tương tác với hệ thống.
Ví dụ
User3 đọc Tin tức 2, Tin tức 3, Tin tức 4
là một transaction
2.2 Support (Độ hỗ trợ)
Dùng để đo tần số xuất hiện của các phần tử
# Công thức
Supp (X) = n(X) / |T|
Với n(X) là số transaction chứa X và T là tập transaction
# Tỷ lệ transaction chứa Tin tức 1
Supp (Tin tức 1) = Số transaction chứa Tin tức 1 / Tổng số transaction
= 3/5
Ngoài ra còn có
- minSupport là mức hỗ trợ tối thiểu
- Frequent itemset (tập phần tử phổ biến) là tập phần tử có support thỏa mãn mức hỗ trợ tối thiểu (minSupport)
2.3 Confidence (Độ tin cậy)
Dùng để đo tần suất xuất hiện của 1 phần tử trong điều kiện xuất hiện của một phần tử khác
# Công thức
Conf (X => Y) = Supp (X∪Y) / Supp (X)
# Tỷ lệ transaction chứa Tin tức 1 đồng thời chứa Tin tức 2
Conf (Tin tức 1 => Tin tức 2) = Supp (Tin tức 1 và Tin tức 2) / Supp (Tin tức 2)
= 2/3
Và minConfidence là mức tin cậy tối thiểu
2.4 Khác
Ngoài những khái niệm trên, còn có 1 số khái niệm khác như
- Lift(X => Y): Tỉ lệ dự kiến X và Y là độc lập
- Conviction(X => Y): Tỉ lệ của tần số mong muốn xảy ra X mà không có Y
Có thể đọc thêm ở Association rule learning
3. Dùng thử Spark MLLib
3.1 Download
Có thể download Spark ở
- Trang chủ của Spark (https://spark.apache.org/downloads.html):
- Trang chủ của Apache (https://www.apache.org/dyn/closer.cgi)
Ngoài source code, Spark còn có sẵn các bản Pre-build cho
- CDH 4
- Hadoop (1.x, 2.3, 2.4, 2.6)
Để sử dụng Spark trong 1 dự án thực tế thì có thể tham khảo cấu hình phần cứng được gợi ý bởi Spark (Spark hardware provisioning](https://spark.apache.org/docs/latest/hardware-provisioning.html)). Ngoài ra còn phụ thuộc vào từng dự án để điều chỉnh hợp lý.
- 4-8 disks per node
- 8 GB to hundreds of gigabytes of memory per machine
- 10 Gigabit or higher network
- least 8-16 cores per machine
Sau đây mình sẽ cài đặt
- Spark 1.6.1 bản built cho Hadoop 2.6 (một Apache Framework cho phép lưu trữ và xử lý phân tán các tập dữ liệu lớn trên các cụm máy tính)
- Trên Centos 6.5
# Download (có thể vào trang chủ Apache để lựa chọn mirror site thích hợp)
wget ftp://ftp.riken.jp/net/apache/spark/spark-1.6.1/spark-1.6.1-bin-hadoop2.6.tgz
# Giải nén
tar xvf spark-1.6.1-bin-hadoop2.6.tgz
cd spark-1.6.1-bin-hadoop2.6
# Chạy spark-shell
./bin/spark-shell
3.2 Tạo dữ liệu transaction
Ta sẽ tạo 1 file text gồm mỗi dòng là 1 transaction
# Raw
User1 đọc Tin tức 1, Tin tức 2, Tin tức 4
User2 đọc Tin tức 1, Tin tức 2
User3 đọc Tin tức 2, Tin tức 3, Tin tức 4
User4 đọc Tin tức 3, Tin tức 5, Tin tức 1
User5 đọc Tin tức 5
# File TXT (/tmp/ar_sample.txt)
TT1,TT2,TT4
TT1,TT2
TT2,TT3,TT4
TT3,TT5,TT1
TT5
3.3 Dùng thử
Spark cung cấp API cho Java, Scala, Python và R. Sau đây sẽ dùng Scala shell để dùng thử AR:
# Chạy spark shell
./bin/spark-shell
# Import
import org.apache.spark.mllib.fpm.FPGrowth
import org.apache.spark.rdd.RDD
import org.apache.spark.mllib.fpm.AssociationRules
import org.apache.spark.mllib.fpm.FPGrowth.FreqItemset
# Đọc dữ liệu transaction
val data = sc.textFile("/tmp/ar_sample.txt")
val transactions: RDD[Array[String]] = data.map(s => s.trim.split(','))
# Dùng Spark MLLib FPGrowth để tìm ra tập phần tử phổ biến (Frequent itemset) từ tập transaction dựa vào minSupport được chỉ định
val fpg = new FPGrowth().setMinSupport(0.2)
val model = fpg.run(transactions)
# In ra tập phần tử phổ biến và tần số của phần tử đó
model.freqItemsets.collect().foreach { itemset =>
println(itemset.items.mkString("[", ",", "]") + ", " + itemset.freq)
}
# Dùng Spark MLLib Association Rule để đưa ra các rule và độ tin cậy của nó
val ar = new AssociationRules().setMinConfidence(0.1)
val results = ar.run(model.freqItemsets)
# In ra kết quả
results.collect().foreach { rule =>
println("[" + rule.antecedent.mkString(",") + "=>" + rule.consequent.mkString(",") + "]," + rule.confidence)
}
Hoặc đơn giản hơn, có thể gọi tạo AR trực tiếp từ kết quả của FP Growth
val minConfidence = 0.8
model.generateAssociationRules(minConfidence).collect().foreach { rule =>
println( rule.antecedent.mkString("[", ",", "]") + " => " + rule.consequent .mkString("[", ",", "]") + ", " + rule.confidence)
}
3.4 Kết quả
# Tập phần tử phổ biến (Frequent itemset) có support >= minSupport (0.2)
# Phần tử và tần suất của nó
[TT3], 2
[TT3,TT1], 1
[TT3,TT2], 1
[TT4], 2
[TT4,TT3], 1
[TT4,TT3,TT2], 1
[TT4,TT1], 1
[TT4,TT1,TT2], 1
[TT4,TT2], 2
[TT1], 3
[TT1,TT2], 2
[TT5], 2
[TT5,TT3], 1
[TT5,TT3,TT1], 1
[TT5,TT1], 1
[TT2], 3
# Tập luật và độ tin cậy của nó (>= minConfidence)
[TT2=>TT3],0.3333333333333333
[TT2=>TT4],0.6666666666666666
[TT2=>TT1],0.6666666666666666
[TT3,TT2=>TT4],1.0
[TT1,TT2=>TT4],0.5
[TT3,TT1=>TT5],1.0
[TT1=>TT3],0.3333333333333333
[TT1=>TT4],0.3333333333333333
[TT1=>TT2],0.6666666666666666
[TT1=>TT5],0.3333333333333333
[TT4=>TT3],0.5
[TT4=>TT1],0.5
[TT4=>TT2],1.0
[TT5=>TT3],0.5
[TT5=>TT1],0.5
[TT3=>TT1],0.5
[TT3=>TT2],0.5
[TT3=>TT4],0.5
[TT3=>TT5],0.5
[TT4,TT2=>TT3],0.5
[TT4,TT2=>TT1],0.5
[TT4,TT3=>TT2],1.0
[TT5,TT3=>TT1],1.0
[TT5,TT1=>TT3],1.0
[TT4,TT1=>TT2],1.0
Từ các tập luật và độ tin cậy của nó ta có thể đưa ra các gợi ý. Độ tin cậy càng cao thì rule đó càng chính xác.
# Ví dụ
Người dùng đọc Tin tức 1 và 4 => Gợi ý Tin tức 2 (sẽ có độ chính xác cao nhất)
Người dùng đọc Tin tức 2 và 4 => Gợi ý Tin tức 1
...
4. Kết luận
- Spark MLLib giúp cho việc sử dụng các thuật toán Machine Learning dễ dàng hơn, thay vì phải tự cài đặt thuật toán ta có thể dễ dàng gọi và sử dụng nó
- Spark MLLib hỗ trợ Association Rules từ phiên bản 1.5.0 trở đi
- Khi áp dụng với dữ liệu lớn, việc dựa trên kích thước dữ liệu của mình để tính toán để có thể thiết lập các giá trị (minSupport, minConfidence) một cách hợp lý là rất quan trọng.
- Nếu bé quá, lượng dữ liệu phải xử lý sẽ rất lớn, có thể dẫn đến OOM (Out Of Memory)
- Nếu quá lớn thì kết quả đưa ra lại ít đi
