Posted in Khác

Design Pattern – Singleton Pattern

Gần đây , khi làm 1 job spark streaming . Mình được yêu cầu làm 1 job liên quan tới spark rồi tính toán lại 1 kết quả phần trăm công việc đó và hiển thị visualize lại cái phần trăm đó được theo mốc thời gian để có thể xem khi nào phần trăm đó đi lên hay đi xuống . Thường thì mọi người đã từng làm job này sẽ đẩy cái phần trăm này lên elasticsearch rồi dùng grafana để load cái phần trăm này lên và hiển thị .

 

maxresdefault

Một trong những vấn đề mình gặp phải , đó chính là mỗi batch streaming thì thường là vài giây là sẽ load data lại một lần . Với mỗi batch như thế , nếu mỗi lần đẩy dữ liệu vào elastic mà phải tạo một kết nối mới tới Elastic thì sẽ khá tốn thời gian và tài nguyên và cảm giác hơi ngu ngu . Quá nhiều connections cũng không phải hay ho gì .

Từ đó mình thấy có thể dùng Singeleton Pattern

1.Giới thiệu

Mọi người có thể đọc qua về singeleton ở trang này : http://code5s.com/ngon-ngu-lap-trinh/java/design-pattern-singleton.html

2. Code

Khởi tạo 1 class ESMoritoringService

public class ESMonitoringService {

    private static ESMonitoringService esMonitoringService;
// để hàm khởi tạo private để chỉ class này có thể khởi tạo 
chính nó 
    private ESMonitoringService(){
        // khoi tao
    }
//vì có thế có nhiều threads cùng gọi tới method getInstance để sử dụng 
object ESMonitoringService nên dùng từ khóa synchronized
    public static ESMonitoringService getInstance(){
        synchronized (esMonitoringService){
            if (esMonitoringService==null){
                // create instance
                esMonitoringService= new ESMonitoringService();
            }
            return esMonitoringService;
        }
    }
}

Khi đó trong job spark streaming , khi muốn đẩy dữ liệu vào elastic ta có thể :

ESMonitoringService esMonitoringService= ESMonitoringService.getInstance();
và gọi các method trong ESMonitoringService để index document vào elastic
Advertisements
Posted in Khác

SPARK

1.Khởi tạo Spark trong Java

import org.apache.spark.SparkConf;

import org.apache.spark.api.java.JavaSparkContext;

 

SparkConf conf = new SparkConf().setMaster(“local”).setAppName(“Filtering”);

JavaSparkContext sc = new JavaSparkContext(conf);

Hai tham số của SparkConf đó là :

  • Cluster URL , local có nghĩa là Spark sẽ chạy 1 thread trong máy local , không kết nối với các cluster khác
  • Tên của application , Nó sẽ xác định tên của applicating của bạn trong cluster manager’s UI nếu bạn kết nối tới một clusster
  • Và một số các tham số khác để configuring ứng dụng của bạn sẽ hoạt động ntn ….

Để shut down Spark , có thể gọi stop() method , hoặc thoát application như : System.exit(0) hoặc sys.exit()

2.Programming with RDDs

Spark’s core abstraction for working with data , the resilient distributed dataset(RDD). RDD là tập hợp rời rạc của các elements . Spark tự động phân tán dữ liệu trong RDDs trong các cluster và song song thực hiện chúng

Mỗi RDD trong Spark đơn giản là một tập phân phối bất biến của các objects . Mỗi RDD được chia ra thành các partitions , có thể được tính toán ở các nodes khác nhau của các cluster . RDD có thể chưas tất các các type Python , Java , Scala object , kể cả user-defined classes .

Users create RDDs in two ways : by loading an external dataset , or distributing a collection of objects ( list or set ) in their driver program .Sau khi khởi tạo , RDDs cung cấp 2 dạng operations : transformations actions . Transformations xây dựng RDD mới từ precious one . Ví dụ , tạo RDD mới mà chỉ bao gồm các string mà bao gôm từ Python . Actions thì tính toán kết quả dựa vào một RDD , và trả về kết quả cho driver program hoặc lưu nó vào external storage system ( như HDFS) . Ví dụ first() sẽ trả về elements đầu tiên của một RDD.

Transformations và actions khác nhau theo cách mà Spark xử lý RDDs đó . Chúng ta có thể định nghĩa RDDs mới bất kì lúc nào , nhưng Spark chỉ tính toán nó theo a lazy fashion , đó là thực hiện khi RDDs này trong action đầu tiên . Điều này có thể là khó hiểu , nhưng lại hợp lý khi bạn làm việc với Big Data . Ví dụ , trong phương thức first() , Spark sẽ scan file để tìm ra first matching line ; nó sẽ không đọc hết cả file .

Sparks’s RDDs mặc định tính toán lại mỗi lần bạn chạy một action trong nó . Nếu bạn muốn dùng một RDD trong nhiều actions , bạn có thể yêu cầu Spark persit , sử dụng RDD.persit(). Điều này là hợp lý bởi vì , nếu bạn không sử dụng lại RDD , chả có lý do gì để tốn bộ nhớ để lưu.

CREATING RDDs

Users create RDDs in two ways : by loading an external dataset , or distributing a collection of objects ( list or set ) in their driver program .Cách đơn giản nhất để tạo ra RDDs là sử dụng một collection có sẵn và pass it to SparkContext’s parallelize() method (đòi hỏi bạn phải có dataset trong memory ở một machine )

JavaRDD<String> lines = sc.parallelize(Arrays.asList(“pandas”,”i like pandas”));

Một cách phổ biến khác để tạo ra RDDs đó là load data from external storage . Chúng ta có thể load rất nhiều các định dạng file khác nhau như text,json , csv,…Với file text :

JavaRDD<String> lines = sc.textFile(“README.txt”);

RDD Operations

RDDs hỗ trợ 2 kiểu operations : transformations actions . Transformations là một operations trong RDDs mà sẽ trả lại một RDD mới , như map() hay filter() . Actions là một operations mà sẽ trả về kết quả cho driver program hoặc write it to storage và tính toán như count() first()

Transformations

Giả dụng chúng ta có một logfile , log.txt , có một số các messages , chúng ta muốn chọn ra các error message . Chúng ta có thể sử dụng filter() transformation :

JavaRDD<String> inputRDD = sc.textFile(“README.txt”);

JavaRDD<String> errorsRDD = inputRDD.filter(

new Function<String,Boolean>(){

public Boolean call(String x){return x.contains(“error”);}

}

);

filter() sẽ không thay đổi inputRDD mà sẽ trỏ đến một RDD hoàn toàn mới . Chúng ta thu được RDDs mới từ các RDD sử dụng transformations . Spark sẽ lưu trữ các phụ thuộc giữa các RDDs khác nhau , được gọi là lineage graph . Nó sẽ được sử dụng để tính toán RDD và recover lost data nếu một phần của persistent RDD bị mất mát :

ACTIONS

Ở ví dụ trước , chúng ta có thể muốn in ra thông tin về errorsRDD . Chúng ta có thể sử dụng các actions như , count() sẽ trả về số lượng , và take() sẽ thu thập một số lượng elements từ RDD

System.out.println(“Input had ” + badLinesRDD.count() + ” concerning lines”)

System.out.println(“Here are 10 examples:”)

for (String line: badLinesRDD.take(10)) {

System.out.println(line);

}

RDD cũng có collect() function trả về toàn bộ RDD (Phải đảm bảo là toàn bộ dataset phải fit in memory on a single machine , không nên sử dụng với datasets quá lớn ). Trong phần lớn RDDs không thể sử dụng collect bởi vì nó quá lớn . Chúng ta sẽ viết data ra các hệ lưu trữ dữ liệu phân tán như là HDFS hoặc AMAZON S3 . Chúng ta có thể lưu contents của một RDD sử dụng saveAsTextFile() action , saveAsSequenceFile() ,

LAZY EVALUATION

Spark sẽ không thực thi cho đến khi nó nhìn thấy một action . Ví dụ nếu ta gọi một transformation ở một RDD ( ví dụ map() ) , operation sẽ không thực thi ngay tức thì . Thay vào đó , Spark internally records metadata để chỉ ra rằng operation này đã được yêu cầu . Thay vì nghĩ RDD chứa dữ liệu cụ thể , chúng ta có thể nghĩ rằng mỗi RDD sẽ bao chứa các chỉ dẫn rằng các data sẽ được xử lý như thế nào . Trong một hệ thống như Hadoop MapReduce , các lập trình viên thường xuyên dành nhiều thời gian để nghĩ ra cách gộp các operations lại với nhau để minimize the number of MapReduce passes . Trong Spark , không có ích lợi gì nếu việt một single complex map thay vì dàn trải thành nhiều simple operations

Passing Functions to Spark

Trong Java,các functions được quy định như các objects mà implement một trong những Spark’s function interfacces từ org.apache.spark.api.java.function package. Có rất nhiều các interfaces dựa vào kiểu trả về của function .

Function name Method to implement Usage
Function<T,R> R call(T) 1 đàu vào , 1 đầu ra , sử dụng với operations như map() filter()
Function2<T1,T2,R> R call(T1,T2) 2 đầu vào , 1 đầu ra , sử dụng với operations như aggregate() fold()
FlatMapFunction<T,R> Iterable<R> call(T) 1 đầu vào , không hoặc nhiều outputs , sử dụng với operations như flatMap()

 

Java function passing with anonymous inner class

 

RDD<String> errors = lines.filter(new Function<String, Boolean>() {

public Boolean call(String x) { return x.contains(“error”); }

});

Java function passing with named class

class ContainsError implements Function() {

public Boolean call(String x) {

return x.contains(“error”); } }

RDD errors = lines.filter(new ContainsError());

Java function class with parameters

class Contains implements Function() {

private String query;

public Contains(String query) { this.query = query; }

public Boolean call(String x) { return x.contains(query); } }

RDD errors = lines.filter(new Contains(“error”));

Trong Java 8 , chúng ta có thể sử dụng lambda expressions để implement ngắn gọn function interfaces :

Java function passing with lambda expression in Java 8

RDD errors = lines.filter(s -> s.contains(“error”));

Common Transformations and Actions

Element-wise transformations

Hai transformations phổ biến nhất mà thường xuyên sử dụng đó là map() filter() . The map() transformations sẽ cần một function và áp dụng nó vào từng element trong RDD với kết quả của function sẽ trở thành giá trị mới của từng element trong RDD kết quả . The filter() transformation sẽ cần một function và trả về một RDD mà chỉ chứa các phần từ mà vượt qua được filter() function.

Nên nhớ rằng , map()’s sẽ trả về kiểu có thể không giống như input type . Ví dụ về một map() mà bình phương các số trong một RDD

Java squaring the values in an RDD

JavaRDD rdd = sc.parallelize(Arrays.asList(1, 2, 3, 4));

JavaRDD result = rdd.map(new Function() {

public Integer call(Integer x) { return x*x; }

});

System.out.println(StringUtils.join(result.collect(), “,”));

Đôi khi chúng ta muốn sinh ra multiple output elements từ mỗi input element . Operation này tên là flatMap() . Như với map() , function flatMap() sẽ được gọi riêng biệt cho từng element của input RDD . Nhưng thay vì chỉ trả về một element , chúng ta trả về một iterator với giá trị trả về . Một flatMap() đơn giản để tách các string thành các word :

flatMap() in Java, splitting lines into multiple words

JavaRDD lines = sc.parallelize(Arrays.asList(“hello world”, “hi”)); JavaRDD words = lines.flatMap(new FlatMapFunction() {

public Iterable call(String line) {

return Arrays.asList(line.split(” “));

}

});

words.first(); // returns “hello”

Pseudo set operations

RDDs hỗ trợ rất nhiều các operations toán , như union intersection . Các operations này đòi hỏi các RDD cùng loại

Tập các elements của chúng ta có thể có trùng lặp , nếu muốn lấy các phần tử riêng biệt , chúng ta có thể sử dụng RDD.distinct() transformation . distinct() khá tốn kém , vì nó phải load tất cả các data .

Toán tử đơn giản nhất là union(other), nó sẽ trả về RDD bao hồm data tử cả 2 RDD input . Spark’s union() có thể chứa dữ liệu trùng lặp

Toán tử intersection(other)  trả về phần tử mà nằm ở cả hai RDD , intersection() thì loại bỏ trùng lặp .

Toán tử subtract(other) sẽ trả về RDD mà năm trong RDD đầu tiên và không nằm trong RDD thứ hai

Toán tử cartesian(other) transformation trả về kết quả tất cả các cặp (a,b) với a năm trong source RDD và b trong RDD còn lại .

ACTIONS

Action phổ biến nhất là reduce() , nó sẽ takes a function triển trên 2 element của RDD của bạn và trả về một element mới cùng kiểu .

reduce() in Java

Integer sum = rdd.reduce(new Function2() {

public Integer call(Integer x, Integer y) { return x + y; }

});

fold() aggregate() …………

Operation đơn giản và phổ biến nhất để trả về dữ liệu cho driver program đó chính là collect() . collect() thường được sử dụng trong unit tests khi mà toàn bộ contents của RDD có thể fit in memory .

take(n) trả về n phần tử từ RDD và cố gắng tối thiểu số partitions mà nó truy cập . Nếu mà tồn tại thứ tự trong data của chúng ta , chúng ta có thể lấy về top elements từ một RDD sử dụng top() . top() sẽ sử dụng sắp xếp mặc định trong data của chúng ta , nhưng chúng ta có thể sử dụng hàm so sánh của chúng ta để lấy về top elements .

Đôi khi chúng ta cần lấy mẫu trong dữ liệu chúng ta . The takeSample(withReplecement, num, seed) function cho phép chúng ta lấy mẫu trong dữ liệu của chúng ta with or without replacement

Actions foreach() sẽ cho chúng ta tính toán trên từng element trong RDD

Converting Between RDD Types

Một số functions chỉ thích hợp cho một vài kiểu RDDs , như mean() variance() trên numeric RDDs hoặc join() trên key/value pair RDDs .

Thông thường , có một vài classes đặc biẹt tên là JavaDoubleRDD JavaPairRDD với một vài phương thức thêm vào cho những kiểu dữ liệu data này .

Creating DoubleRDD in Java

JavaDoubleRDD result = rdd.mapToDouble(

new DoubleFunction() {

public double call(Integer x) {

return (double) x * x;

}

});

System.out.println(result.mean());

Persistence (Caching)

Đôi khi chúng ta muốn sử dụng một RDD nhiều lần . Nếu chúng ta ngây thơ , thì Spark sẽ tính toàn lại RDD vào mỗi lần chúng ta gọi một action trên RDD . Để loại trừ tính toán RDD rất nhiều lần , chúng ta có thể yêu cầu Spark persist data . Khi chúng ta yêu cầu Spark persist một RDD , nodes mà tính toán RDD sẽ lưu lại partitions của nó . Nếu một node chứa data persisted mà fails , Spark sẽ tính toán lại lost partitions của data khi cần thiết . Spark có rất nhiều cấp độ persistence để chọn dựa vào mục đích cũng chúng ta , persist() mặc định sẽ lưu trữ dữ liệu trong JVM heap như một unserialized objects . Khi chúng ta viết dữ liệu ra disk hay off-heap storage , dữ liệu luôn luôn được serizlized .

Nếu bạn thử cache quá nhiều dữ liệu fit in memory . Spark sẽ tự động thu hồi old partitions sử dụng Least Recently Used(LRU) cache policy.Với memory-only storage levels , nó sẽ tính toán lại các partitions vào lần kết tiếp access , còn với memory-and-disk , nó sẽ ghi ra disk . Hay có nghĩa là , bạn sẽ không phải quá lo lắng khi yêu cầu Spark to cache quá nhiều data . Nhưng cũng k nên caching unnecessary data dẫn đến phải tính toán lại useful data và thêm thời gian tính toán lại

Cuối cùng , RDDs cung cấp một method tên là unpersist() cho phép remove các RDDs từ cache

3.Working with Key/Value Pairs

Spark cung cấp một operations đặc biệt bao gồm key/value pairs . Những RDDs này được gọi là pair RDDs . Pair RDDs cho phép chúng ta act on each key song song hoặc regroup dữ liệu thông qua mạng . Ví dụ , pair RDDs có một phương thức reduceByKey() có thể tổng hợp data riêng cho từng key , và một phương thức join() có thể gộp 2 RDDs lại với nhau bằng cách nhóm các elements với cùng key .

Creating Pair RDDs

Có một số cách để get pair trong Spark . Rất nhiều cách đọc file mà trả về pair RDDs . Trong trường hợp chúng ta có một RDD thông thường mà chúng ta muốn biến đổi thành pair RDD . Chúng ta có thể chạy map() function .

 

 

 

 

Creating a pair RDD using the first word as the key in Java

PairFunction keyData =

new PairFunction() {

public Tuple2 call(String x) {

return new Tuple2(x.split(” “)[0], x);

}

};

JavaPairRDD pairs = lines.mapToPair(keyData);

Để tạo ra pair RDD từ in-memory collection trong Java , chúng ta sử dụng SparkContext.parallelizePairs()

Transformations on Pair RDDs

Pair RDDs cho phép sử dụng tất các các transformations của một RDDs thông thường . Pair RDDs gồm các tuples , chúng ta cần pass functions mà operate on tuples hơn là các phần tử riêng biệt .

Aggregations

Khi datasets được mô tả theo key/value pairs , là điều bình thường nếu muốn aggregate statistics acroos tất cả các elements với cùng key .

reduceByKey() khá là giống với reduce(); cả hai đều take a function và sử dụng để gộp các values . reduceByKey() chạy song song các reduce operations , mỗi operations cho một key trong dataset

foldByKey()cũng khá là tương tự fold(), both use a zero value ò the same type of the data in our RDD and combination function . As with fold() , the provided zẻo value for foldByKey() should have no impact ưhen added ưith your combination function to another element.

Gọi reduceByKey() foldByKey() sẽ tự động thực thi kết hợp locally trên mỗi máy trước khi tính toán global cho từng key . combineByKey() interface sẽ cho phép bạn customize combining behavior

Word count in Java

JavaRDD input = sc.textFile(“s3://…”)

JavaRDD words = rdd.flatMap(new FlatMapFunction() {

public Iterable call(String x) { return Arrays.asList(x.split(” “)); }

});

JavaPairRDD result = words.mapToPair(

new PairFunction() { public Tuple2 call(String x) { return new Tuple2(x, 1); }

}).reduceByKey(

new Function2() {

public Integer call(Integer a, Integer b) { return a + b; }

});

Chúng ta sẽ thực thi word count nhanh hơn sử dụng countByValue() function ở RDD đầu tiên :

input.flatMap(x => x.split(” “)).countByValue()

combineByKey() is the mose general of the per-key aggregation functions . Các combiners per-key khác thường implemented nó . Như aggregate() , combineByKey() cho phép người dùng trả về giá trị không cùng kiểu với input data .

combineByKey() sẽ đi qua các elements trong các partition , mỗi element sẽ có một key mà lần đầu xuất hiện hoặc

 

Posted in Khác

Introduction to Latent Dirichlet Allocation

Latent Dirichlet Allocation – Blei & Ang & Jordan , JMLR 2003

Introduction

Giả sử bạn có một tập các câu sau đây :

  • I like to eat broccoli and bananas.
  • I ate a banana and spinach smoothie for breakfast.
  • Chinchillas and kittens are cute.
  • My sister adopted a kitten yesterday.
  • Look at this cute hamster munching on a piece of broccoli.

Thế thì LDA là gì ? Đó là một cách từ động khám phá ra các topics mà các câu trên chứa. Ví du, cho các câu trên và yêu cầu cho 2 topics, LDA có thể sinh ra một kết quả như kiểu này :

  • Sentences 1 and 2: 100% Topic A
  • Sentences 3 and 4: 100% Topic B
  • Sentence 5: 60% Topic A, 40% Topic B
  • Topic A: 30% broccoli, 15% bananas, 10% breakfast, 10% munching, … ( tại điểm này , bạn có thể diễn tả topic A là về food)
  • Topic B: 20% chinchillas, 20% kittens, 20% cute, 15% hamster, … (tại điểm này , bạn có thể diễn tả topic B là về cute animals)

Làm thế nào để LDA có thể thực hiện được điều này ?

LDA Model

Chi tiết hơn , LDA miêu tả các văn bản như là sự pha trộn của các topics that spit out words với các xác suất nhất định . Nó giả sử các văn bản được tạo ra theo cách sau : khi bạn viết mỗi văn bản , bạn

  • Quyết định số lượng từ N mà document sẽ có ( theo một phân phối Poisson )
  • Chọn một chủ đề hỗn hợp cho document này (theo một phân phối Dirichlet trên một tập hợp cố định K chủ đề). Ví dụ , giả sử bạn có hai topics bên trên : food và cute animal , bạn có thể chọn rằng document này sẽ bao gồm 1/3 food và 2/3 cute animals.
  • Generate each word w_i trong document này bằng cách:
    • Đầu tiên là chọn một topic (theo phân phối đa thức mà bạn đã láy ví dụ bên trên , ví dụ , bạn có thể chọn food topic với xác suất 1/3 và cute animals topic với xác suất 2/3).
    • Sử dụng topic để sinh ra các từ (theo phân phối của topic’s multinomial). Ví dụ , nếu bạn chon food topic , bạn có thể sinh ra được các từ “broccoli” với xác suất 30% , “bananas” với xác suất 15% , và cứ thế …

Giả sử this generative model này cho một tập hợp các documents , LDA sau đó cố gắng để quay lui (backtrack) từ các tài liệu để tìm thấy một tập hợp các chủ đề mà rất có thể đã tạo ra collection .

Example

Ví dụ . Tuân theo quy trình bên trên , khi sinh ra một số document D cụt hể , bạn có thể :

  • Chọn 5 là số lượng từ trong D.
  • Quyết định rằng D sẽ là 1/2 về food và  1/2 về cute animals.
  • Chọn từ đầu tiên trong food topic , và bạn sẽ có từ “broccoli”.
  • Chọn từ thứ hai tới từ cute animals topic, bạn sẽ có “panda”.
  • Chọn từ thứ 3 tới từ cute animals topic , sẽ cho bạn từ “adorable”.
  • Chọn từ thứ tư tới từ food topic, sẽ cho bạn từ “cherries”.
  • Chọn từ thứ năm tới từ food topic, sẽ cho bạn từ “eating”.

Như thế document được sinh ra từ LDA sẽ là  “broccoli panda adorable cherries eating” (ghi nhớ rằng LDA là a bag-of-words model).

Learning

Giả sử bạn đã có tập các documents. You’ve chosen some fixed number of K topics to discover, and want to use LDA to learn the topic representation of each document and the words associated to each topic. How do you do this? One way (known as collapsed Gibbs sampling) is the following:

  • Go through each document, and randomly assign each word in the document to one of the K topics.
  • Notice that this random assignment already gives you both topic representations of all the documents and word distributions of all the topics (albeit not very good ones).
  • So to improve on them, for each document d…
    • Go through each word w in d…
      • And for each topic t, compute two things: 1) p(topic t | document d) = the proportion of words in document d that are currently assigned to topic t, and 2) p(word w | topic t) = the proportion of assignments to topic t over all documents that come from this word w. Reassign w a new topic, where we choose topic t with probability p(topic t | document d) * p(word w | topic t) (according to our generative model, this is essentially the probability that topic t generated word w, so it makes sense that we resample the current word’s topic with this probability). (Also, I’m glossing over a couple of things here, in particular the use of priors/pseudocounts in these probabilities.)
      • In other words, in this step, we’re assuming that all topic assignments except for the current word in question are correct, and then updating the assignment of the current word using our model of how documents are generated.
  • After repeating the previous step a large number of times, you’ll eventually reach a roughly steady state where your assignments are pretty good. So use these assignments to estimate the topic mixtures of each document (by counting the proportion of words assigned to each topic within that document) and the words associated to each topic (by counting the proportion of words assigned to each topic overall).

Layman’s Explanation

In case the discussion above was a little eye-glazing, here’s another way to look at LDA in a different domain.

Suppose you’ve just moved to a new city. You’re a hipster and an anime fan, so you want to know where the other hipsters and anime geeks tend to hang out. Of course, as a hipster, you know you can’t just ask, so what do you do?

Here’s the scenario: you scope out a bunch of different establishments (documents) across town, making note of the people (words) hanging out in each of them (e.g., Alice hangs out at the mall and at the park, Bob hangs out at the movie theater and the park, and so on). Crucially, you don’t know the typical interest groups (topics) of each establishment, nor do you know the different interests of each person.

So you pick some number K of categories to learn (i.e., you want to learn the K most important kinds of categories people fall into), and start by making a guess as to why you see people where you do. For example, you initially guess that Alice is at the mall because people with interests in X like to hang out there; when you see her at the park, you guess it’s because her friends with interests in Y like to hang out there; when you see Bob at the movie theater, you randomly guess it’s because the Z people in this city really like to watch movies; and so on.

Of course, your random guesses are very likely to be incorrect (they’re random guesses, after all!), so you want to improve on them. One way of doing so is to:

  • Pick a place and a person (e.g., Alice at the mall).
  • Why is Alice likely to be at the mall? Probably because other people at the mall with the same interests sent her a message telling her to come.
  • In other words, the more people with interests in X there are at the mall and the stronger Alice is associated with interest X (at all the other places she goes to), the more likely it is that Alice is at the mall because of interest X.
  • So make a new guess as to why Alice is at the mall, choosing an interest with some probability according to how likely you think it is.

Go through each place and person over and over again. Your guesses keep getting better and better (after all, if you notice that lots of geeks hang out at the bookstore, and you suspect that Alice is pretty geeky herself, then it’s a good bet that Alice is at the bookstore because her geek friends told her to go there; and now that you have a better idea of why Alice is probably at the bookstore, you can use this knowledge in turn to improve your guesses as to why everyone else is where they are), and eventually you can stop updating. Then take a snapshot (or multiple snapshots) of your guesses, and use it to get all the information you want:

  • For each category, you can count the people assigned to that category to figure out what people have this particular interest. By looking at the people themselves, you can interpret the category as well (e.g., if category X contains lots of tall people wearing jerseys and carrying around basketballs, you might interpret X as the “basketball players” group).
  • For each place P and interest category C, you can compute the proportions of people at P because of C (under the current set of assignments), and these give you a representation of P. For example, you might learn that the people who hang out at Barnes & Noble consist of 10% hipsters, 50% anime fans, 10% jocks, and 30% college students.

Real-World Example

Finally, I applied LDA to a set of Sarah Palin’s emails a little while ago (see here for the blog post, hoặc đây là một ứng dụng cho phép bạn duyệt qua các emails bằng LDA-learned categories), dưới đây là 1 bán tóm gọn . Đây là một vài topics mà thuật toán học được :

  • Trig/Family/Inspiration: family, web, mail, god, son, from, congratulations, children, life, child, down, trig, baby, birth, love, you, syndrome, very, special, bless, old, husband, years, thank, best, …
  • Wildlife/BP Corrosion: game, fish, moose, wildlife, hunting, bears, polar, bear, subsistence, management, area, board, hunt, wolves, control, department, year, use, wolf, habitat, hunters, caribou, program, denby, fishing, …
  • Energy/Fuel/Oil/Mining: energy, fuel, costs, oil, alaskans, prices, cost, nome, now, high, being, home, public, power, mine, crisis, price, resource, need, community, fairbanks, rebate, use, mining, villages, …
  • Gas: gas, oil, pipeline, agia, project, natural, north, producers, companies, tax, company, energy, development, slope, production, resources, line, gasline, transcanada, said, billion, plan, administration, million, industry, …
  • Education/Waste: school, waste, education, students, schools, million, read, email, market, policy, student, year, high, news, states, program, first, report, business, management, bulletin, information, reports, 2008, quarter, …
  • Presidential Campaign/Elections: mail, web, from, thank, you, box, mccain, sarah, very, good, great, john, hope, president, sincerely, wasilla, work, keep, make, add, family, republican, support, doing, p.o, …

Đây là một ví dụ một email rời vào Trig/Family/Inspiration category (particularly representative words are highlighted in blue):

Trig Email

Đây là một trích đoạn từ một email mà sẽ 10% rời vào Presidential Campaign/Election category (màu đỏ ) và  90% rơi vào Wildlife/BP Corrosion category (màu xanh):

Wildlife-Presidency Email

Lược dịch từ : https://www.quora.com/What-is-a-good-explanation-of-Latent-Dirichlet-Allocation/answer/Edwin-Chen-1?srid=nqv8

Posted in Khác

Recommender systems

  1. Introduction to Recommender Systems

Recommender Systems (RSs) là một software tools hay một kĩ thuật cung cấp gợi ý cho items tùy mục đích sử dụng của user . Gợi ý cung cấp mục đích để hỗ trợngười dùng trong rất nhiều quá trình quyết định , như là items nào nên mua , bài nhạc nào nên nghe . Phát triển một RSs là một nỗ lực đa ngành trong đó bao gồm các chuyên gia từ nhiều lĩnh vực như Artificial intelligence, Human Computer Interaction, Information Technology, Data Mining, Statistics, Adaptive User Interfaces, Decision Support Systems, Marketing, or Consumer Behavior.

Trong trường hợp của một book RSs , nó sẽ hỗ trợ người dùng chọn sách để đọc . Trong một trang Web rất phổ biến , Amazon.com , trang nay triển khai một RS để cá nhân hoá của hàng online cho từng khách hàng . Hệ thống recommendations thường là được cá nhân hoá , các người dùng hay nhóm người dùng khác nhau thường nhận được các gợi ý khác nhau . Cũng có những hệ thống gợi ý non-personalized . Điển hình là 10 bài hát đang phổ biến nhất hay , 10 quyển sách đang bán chạy nhất . Hệ thống non-personalized có thể hữu dụng trong các trường hợp nhất định , tuy nhiên trong RS research nó không được qua tâm nhiều lắm .

Recommender systems have proven to be valuable means for online users to cope with the information overload and have . Trong những năm gần đây , hệ thống recommender đã được phát triển đáng kể . RSs đóng vai trò quan trọng trong các trang web có xếp hạng cao như Amazonlcom , Youtube , Netflix , Yahoo , Tripadvisor , IMDb . Các công ty media phát triển và triển khai các RSs như một phần của dịch dụ cung cấp cho người dùng , Ví dụ Netflix , hệ thống dịch vụ thuê phim trực tuyến , trao giải thưởng 1 triệu đô cho team đầu tiên mà cải tiến đáng kể so với hệ thống RSs của họ ( 10% với RSME) . Tương ứng , có rất nhiều kĩ thuộc cho recommendation đã được đề xuất trong thập kỉ vừ qua , rất nhiều trong số đó đã thực thi thành công trong môi trường thương mại

  1. Data Mining Methods for Recommender Systems

Real-life data cần được tiền xử lý để làm sao có thể sử dụng các kĩ thuật machine learning để làm tiếp . 3 vấn đề mà đặc biệt quan trọng khi thiết kế một RS . Đầu tiên sẽ là các similarity hoặc distance meansures . Rồi vấn đề lấy mấu dữ liệu để làm giảm số lượng itesm trong tập lớn giữ liệu mà vẫn giữ được đặc điểm chính của nó . Cuối cùng là một số kĩ thuật để reduce dimensionality

  • Similarity Meansures

Một trong những phương pháp ưa thích để collaborative filtering recommenders là sử dụng phân loại kNN . Phương pháp phân loại này – hay các phương pháp phân loại và phân cụm khác phụ thuộc rất nhiều vào định nghĩa một độ đo khoảng cách hay độ tương tự thích hợp . Distane meansure đơn giản và phổ biến nhất đó là Eucidean distane :

euclidean-distance

với n là số chiều (hay số features) và  và  là attributes thứ k của data objects x và y

Minkowski Distance là phương trình tổng quát của Euclidean Distance

minkowski-distance

Phụ thuộc vào giá trị của r , khoảng cách Minkowski sẽ được gọi với những tên gọi riêng : Với r=1 , là city block ( Manhattan , taxicab hay L1 norm ) . Với r=2 , khoảng cách Euclidean …

Một phương pháp rất phổ biến khác xem xét các items như các vector không gian n-chiều , và tính toán độ tương tự của chúng như là cosine giữa các góc :

cosine-distance

với . là vector dot product và ||x|| là độ lớn của vector x . Độ tương tự này được biết đến như là cosine similarity hay L2 Norm

  • Sampling

Sampling là kĩ thuật chính được sử dụng trong Data mining để chọn một tập các dữ liệu liên quan từ một tập lớn dữ liệu . Sampling có thể được sử dụng bởi vì xử lý toàn bộ dataset tốn kém mặt tính toán . Nó cũng có thể được sử dụng để tạo ra training testing datasets .

Vấn đề chủ yếu của sampling đó là tìm được tập con từ tập dữ liệu gốc làm sao mà tượng trưng cho toàn bộ bộ dữ liệu . Kĩ thuật sampling đơn giản nhất đó là random sampling  , xác suất chọn bất kì 1 item nào là như nhau . Có những phương pháp phức tạp hơn như stratified sampling

  • Reducing Dimensionality

Features trong data set có thể được định nghĩa trong một không gian có số chiều lớn , và thông tin thì rất rải rác , chỉ có môt số features trong mỗi object là có giá trị . Những khái niệm về mật độ và khoảng cách giữa các điểm, mà quan trọng cho clustering và phát hiện outlier, trở nên ít ý nghĩa trong không gian rất chiều . Điều này được biết đến là Curse of Dimensionality . Kĩ thuật giảm chiều sẽ giúp chúng ta vượt qua được vấn đề này bằng cách chuyển không gian nhiều chiều ban đầu sang không gian có số chiều nhỏ hơn .

Hai phương pháp giảm chiều được sử dụng nhiều nhất trong ngữ cảnh RS là : Principal Component Analysis (PCA) Singular Value Decomposition (SVD) .

  1. Content-based RS

Hệ thống sẽ học cách gợi ý items mà tương tự với items mà user đã từng thích trong quá khứ . Độ tương tự của các items được tính toán dựa vào features . Ví dụ , nếu một user từng đánh giá một phim hài cao , thì hệ thống sẽ có thể sẽ gợi ý các phim hài khác cho người dùng . Quá trình recommendation đơn giản có thể là nối giữa attributes của user profile và các attributes của content object

3.1. Kiến trúc của Content-based RS

content-based-recommender

Content-based RSs cần một kĩ thuật đúng đắn để biểu diễn item , sinh ra user profile và một phương pháp để so sánh giữa user profile và item . Quá trình recommendation sẽ được thực thi qua 3 bước :

– CONTENT ANALYZER : Với những thông tin không có cấu trúc ( như text ) , một số bước tiền xử lý la cần thiết để thu được các thông tin có cấu trúc liên quan

– PROFILE LEARNER : Module này sẽ thu thập thông tin tượng trưng cho sở thích của user , cố gắng từ dữ liệu này , xây dựng user profile .

– FILTERING COMPONENT

Posted in Khác

Linear Regression – Hồi quy tuyến tính

  1.  Linear Regression

Trong thống kê , chúng ta sử dụng hai cái tên khác nhau cho nhiệm vụ nối một số input features thành một số giá trị output : chúng ta sử dụng từ Regression khi output là giá trị thực , và Classification khi output là một trong tập rời rạc các classes . Linear Regression là một trong những kĩ thuật cơ bản và quan trọng để dự đoán giá trị cho một attribute(y) .

Ý tưởng của Linear Regression là chúng ta sẽ được cho một tập các observations , mỗi observations sẽ được liên kết tới một vài features , chúng ta sẽ muốn dự đoán giá trị thực cho mỗi observations . Một ví dụ nổi tiếng về dự đoán giá nhà (Levitt and Dubner (2005)) chỉ ra rằng những từ được sử dụng trong những quảng cáo bất động sản có thể là một dự đoán tốt xem một ngôi nhà sẽ được bán với giá cao hơn hay ít hơn so với giá chào bán của nó . Họ chỉ ra rằng , ví dụ , một ngôi nhà  được quảng cáo bất động sản có những từ như fantastic , cute , hoặc charming , thường có xu hướng bán với giá thấp hơn , trong khi những ngôi nhà có quảng cáo có những từ như maple granite thường bán với giá cao hơn . Giả thuyết của họ là các môi giới sử dụng các từ tích cực mơ hồ như fantastic để che giấu những sự thiếu hụt những định lượng tích cực trong ngôi nhà .

Một vài dữ liệu chúng ta tự tạo ra :

Số các tính từ mơ hồ Giá bán được cao hơn giá mời chào
4 0
3 $1000
2 $1500
2 $6000
1 $14000
0 $18000

 

Hình dưới mô tả các điểm dữ liệu trong dữ liệu tự tạo của chúng ta , với số các tính từ mơ hồ trong trục x , và giá trong trục y . Chúng ta sẽ vẽ được một regression line , mà có thể phù hợp tốt nhất với dữ liệu chúng ta quan sát được .

1

Với Linear regression một biến như ví dụ trên , chúng ta có thể tìm một phương trình có dạng

price = w0 + w1 * Num_Adjectives

Khi có nhiều hơn một feature , được gọi là multiple linear regression . Ví dụ , giá một ngôi nhà có thể phụ thuộc vào rất nhiều các yếu tố như số ngồi nhà chưa bán trong thị trường , tỷ lệ thế chấp trung bình . Chúng ta có thể coi những yếu tố này là một biến , độ quan trọng các yếu tố sẽ là weight của nó

price = w0 + w1 * Num_Adjectives + w2 * Mortgage_Rate + w3* Num_Unsold_Houses

Trong xử lý ngôn ngữ tự nhiên , chúng ta thường gọi các yếu tố dự đoán như số tính từ mơ hồ là các feature . Chúng ta sẽ biểu diễn mỗi observation( mỗi một ngôi nhà để bán) bằng một vector của những features này . Giả sử một ngôi nhà có một tính từ mơ hồ trong quảng cáo của nó , và tỷ lệ thế chấp trung bình là 6.5 và có 10,000 ngôi nhà chưa bán trong thành phố . Như thế feature vector cho ngôi nhà này sẽ là f = (1,6.5,10000) . Giả sử chúng ta sẽ học được weight vector là w =(w0,w1,w2,w3) = (18000,-5000,-3000,-1.8) . Như thế giá trị dự đoán cho ngôi nhà này sẽ tính bằng cách nhân các giá trị feature với weight của nó :

2

Thông thường , chúng ta sẽ giả vờ như là sẽ có thêm một feature mang giá trị 1 , gọi là Intercept feature , khi đó chúng ta có thể biểu diễn linear regression dự đoán cho y sẽ là :

3         2 . Quá trình học của linear regression

Làm sao để học ra các trọng số weights cho linear regression . Bằng trực giác , chúng ta sẽ mong muốn chọn được các weights sao cho giá trị y ước lượng sẽ gần nhất với giá trị thực tế chúng ta nhìn thấy trong tập training set .

Chúng ta có thể sử dụng sum squared cost function , định nghĩa như sau :

4

Chúng ta sẽ chọn tập weights tối ưu để làm cho sum-squared error nhỏ nhất . Sum Squared error cost function là một lựa chọn có lý do , và nó hoạt động tốt trong hầu hết các vấn đền , cho hầu hết bài toán regression . Có những cost functions khác hoạt động cũng tốt , nhưng sum squared error cost function là một trong những cost function sử dụng nhiều nhất cho bài toán regression [5]

Nếu chúng ta cho tất cả tập dữ liệu huấn luyện vào một ma trận X , với mỗi hàng trong ma trận sẽ là vector features ứng với observations x(i) (nên nhớ cột 1 của ma trận X sẽ mang giá trị 1 bởi vì chúng ta đã giả sử extra value bên trên) , và chúng ta sẽ cho hết các giá trị y vào  vector y . Như thế chúng ta sẽ tính ra được W bằng công thức :

5

 Ngoài Normal equation trên để tìm ra regression line , chúng ta có thể sử dụng gradrient descent . Đây cũng là một thuật toán thông dụng và không chỉ sử dụng trong linear regression [5] . So sánh giữa Gragient Descent và Normal Equation để tìm ra regression line

6

Nếu XT X không thể có nghịch đảo (khi det(XT X)=0)  , chúng ta sẽ xem xét các feature , xem các feature có phụ thuộc vào nhau không : Vì dụ có 1 feature là size in feet , 1 feature là size in meters squared , như thế 2 feature này sẽ không độc lập với nhau . Việc của chúng ta là sẽ xoá đi 1 features .

  • .Một vài vấn đề trong linear regression
    • Linear regression for classification [6]

7Scaling input features

3 . Thực thi

Chúng ta biết rằng , có thể tính W bằng công thức bên trên

8

Như vậy chúng ta sẽ đi xây dựng các phép toán trên ma trận : Nhân ma trận , chuyển vị ma trận , nghịch đảo ma trận

Object matrix

9

Class các phép toán với Matrix

Nhân hai ma trận

10

Chuyển vị ma trận

11

Nghịch đảo ma trận

Định nghĩa : Một ma trận nghịch đảo của ma trận vuông A là

A-1 sao cho A . A-1 = I

Công thức ma trận chuyển vị :

A-1 = 1/detA * adj(A^T)

12

Có thể thấy nếu det A = 0 thì không tồn tại ma trận nghịch đảo

Ta có thể tính định thức bằng quy nạp

* Nếu n = 1 Þ a = (a) Þ detA = a.

* Nếu n > 1 thì:

delA = (-1)i+1ai1|Ai1| + (-1)i+2ai2|Ai2| + … + (-1)i+jaij|Aij|+… + (-1)i+nain|Ain|.

Tức là ta tính định thức bằng cách khai triển theo dòng thứ i.

Trong đó:

* (-1)i+jaij|Aij| là phần bù đại số của aij.

* (-1)i+j  là dấu chỉ số của phần tử ở dòng i cột j.

* aij là phần tử ở dòng i cột j.

* |Aij| là định thức con được lập bằng cách bỏ dòng i cột j.

Tuy nhiên : + Một định thức cấp 3 ta khai triển được 3 định thức cấp 2.

+ Một định thức cấp 4 ta khai triển được 4 định thức cấp 3.

Như vậy: một định thức cấp n ta khai triển được (n!)/2 định thức cấp 2.

Nếu n>10 việc tính toán định thức rất chậm , dẫn đến việc tính toán ma trận nghịch đảo cũng thế

Chúng ta sẽ tìm hiểu một phương pháp có độ phức tạp  O(n^2.3) để tìm ma trận nghịch đảo của một ma trận vuông .

LU Decompostion

            Các ma trận vuông có thể được phân rã thành tích của một ma trận lower triangular và một ma trận upper triangular matrix U

A = L U

Ví dụ ma trận A 3*3

13

Chúng ta sẽ có 9 phương trình với 12 ẩn . Để phương trình có nghiệm duy nhất , chúng ta sẽ set các phần tử trên đường chéo của L là 1

14

Như thế chúng ta sẽ giải hệ phương trình 9 ẩn ,9 phương trình

15

Như thế thì :

16

17

Chúng ta có thể tổng quát hoá công thức U và L như sau

18

19

Thuật toán giả mã phân tích A thành L và U

 

 

lu

Giả sử chúng ta phân tích được A = L . U

Như thế det A = det L . det U

Mà hàng chéo của L = 1 nên det A = det U = tích hàng chéo của U

Nếu u jj  = 0 sẽ dẫn tới det U = 0 = det A => không có ma trận nghịch đảo

Giả sử ta có thể phân tích được A = L . U

với L : Lower triangular matrix

U : Upper triangular matrix

 

Capture3.JPG

Ví dụ : Sử dụng LU decompostion để tìm nghịch đảo của ma trận A

20

Chúng ta có thể tính ra được ma trận L với U như sau

21

Ta sẽ đi giải phương trình : L Z = I

Với cột 1 của Z và I

22

Sẽ cho ta phương trình :

23

Ta sử dụng thuật toán “forward substitution” từ phương trình đầu đến cuối sẽ ra

24

Như thế có thể viết được thuật toán forward substitution giải Phương trình L z = i

Capture

Cột 1 của Z sẽ là :

25

Giờ đi giải phương trình U   = Z

Với cột 1 của Z :

26

 

Thuật toán backward substitution sẽ bắt đầu từ phương trình thứ 3 ngược về :

27

28

Như thế , chúng ta có thể viết được thuật toán back substitution giải phương trình U x = d

 

Capture1

Như thế cột đầu tiên của nghịch đảo của A sẽ là :

29

Tương tự , giải các phương trình

30

31

Như thế :

32

Chúng ta có thể xác nhận lại bằng cách :

33

Sau khi viết được hàm tính toàn L, U từ A . Rồi từ  L , U tính toán nghịch đảo
Ta có thể tính được W 1 cách dễ dàng :

4. Đánh giá

  • Mean absolute error ( MAE)

MAE là đại lượng dùng để meansure độ gần của dự đoán với giá trị outcomes thực tế . Công thức của MAE như sau : [4]

36

Trong đó ,  là giá trị dự đoán và  là giá trị thực tế

  • . Root Mean Squared Error ( RMSE )

Căn của trung bình tổng các lỗi bình phương [3]

37

Tham khảo :
[1] Steven Chapra and Raymond Canale, Numerical Methods for Engineers, Fourth Edition, McGraw-

Hill, 2002 (see Sections 10.1-10.2).

[2] Jurafsky and Martin , Speech And Language Processing , Second Edition ,  2007 (Chapter 6 – Hidden Markov and maximum entropy models)

[3] http://statweb.stanford.edu/~susan/courses/s60/split/node60.html

[4] https://en.wikipedia.org/wiki/Mean_absolute_error

[5] Machine Learning , Andrew NG

[6] Machine Learning , Caltech

Câu hỏi

  1. Những dự án mà công ty mình có dùng regression , các feature chọn ra như thế nào , định lượng ra sao , kết quả thực tế như thế nào ?
  2. Với những feature hay dữ liệu không phải dạng số . Có cách nào có thể chuyển được sang số để dùng linear regression như dữ liệu ví dụ dưới đâyzz.png
  3. Với việc làm việc với vector , việc scaling dữ liệu luôn luôn cần thiết ?
Posted in Khác

Sử dụng LibSvm trong Java

LibSvm có file jar để có thể chạy trong chương trình Java . Tuy nhiên chỉ có 1 số hàm được cung cấp như hàm : svm-train  , svm-predict  . Không có hàm để train tìm tham số tốt nhất . Vì thế chúng ta sẽ phải chạy cmd để tìm tham số tốt nhất . Sau khi tìm được tham số tốt nhất và train ra model . Chúng ta sẽ đi xây một thư viện Java cung cấp API phân loại 1 chuỗi String nội dung bài báo .

Load model từ filePath

model = svm.svm_load_model(filePath);

Xây dựng vector của chuỗi String bài báo

Sẽ có dạng svm_node[] nodes

Khai báo :  svm_node[] nodes = new svm_node[nodes size];

Với mỗi node trong nodes , set node.index là tên feature và node.index là giá trị của feature này . Mỗi node sẽ có index giống index của features định dạng libsvm.Có value sẽ là giá trị features định dang libsvm(Phải scaling giống như cách scaling  từ model file , bạn có thể scaling bằng phương pháp của bạn , hoặc dùng scaling của libsvm thì phải biết đc min_value , max_value của từng feature trong tập train để scaling lại test)

Sau đó có thể lấy ra nhãn bằng cách :

double label=svm.svm_predict(model,nodes);

Từ đây chúng ta có thể xây dựng 1 thư viện phân loại báo .

Mọi người có thể download thư viện ở đây : https://drive.google.com/file/d/0ByH8KMtJGmHHVi15dTlfdVRkc1E

Posted in Khác

TF-IDF

1. Giới thiệu

TF-IDF (Term Frequency-Inverse Document Frequency) là 1 kĩ thuật khai phá dữ liệu từ text sử dụng để phân loại văn bản . Trọng số này sử dụng để đánh giá tầm quan trọng của một từ trong một văn bản , 1 collection hoặc một corpus . Độ quan trọng tăng dần dựa vào số lần từ xuất hiện trong văn bản nhưng bù lại bởi tần suất của từ đó trong corpus . Một vài biến thể của tf-idf thường xuyên được sử dụng trong các hệ thống tìm kiếm như một công cụ chính để đánh giá và sắp xếp văn bản dựa vào user query.  Tf-idf có thể sử dụng để lọc những từ stop-words trong một số bài toán như tóm tắt văn bản và phân loại văn bản . [1]

TF : Term Frequency , là số lần term xuất hiện trong văn bản . Vì các văn bản có thể có độ dài ngắn khác nhau nên mọt số term có thể xuất hiện nhiều lần trong một văn bản dài hơn là một văn bản ngắn . Như thế , term frequency thường được chia cho độ dài văn bản ( tổng số term trong một văn bản) như một các normalization .

IDF: Inverse Document Frequency , đánh giá tầm quan trọng của một term . Khi tính toán TF , tất cả các terms được coi như có độ quan trọng như nhau . Nhưng  một số terms, như “is” , “of” và “that” thường xuất hiện rất nhiều lần nhưng độ quan trọng là không cao . Như thế chúng ta cần giảm wegh xuống

IDF(t) = log(Tổng số văn bản/ Số văn bản chứa term t ).

Ví dụ một văn bản chưa 100 từ mà từ “cat” xuất hiện 3 lần . Term frequency cho từ cat này là (3/100) = 0.03 . Giả sử , chúng ta có 10 triệu văn bản và từ “cat” xuất hiện trong một nghìn văn bản . Như thế , idf được dính là  log(10,000,000 / 1,000) = 4. Như thế , tf-idf của từ “cat” trong văn bản này sẽ là : 0.03 * 4 = 0.12.

 

2. Biến thể [2]

2.1 . Sublinear tf scaling

Nếu một term trong 1 văn bản xuất hiện 12 lần thì không có nghĩa là nó thực sự mang thông tin gấp 12 lần so với từ xuất hiện 1 lần . Một biến thể của tf được sử dụng logarithm của tf như sau

img449

Như thế , chúng ta có thẻ thay tf thành wf thành công thức :

img451

Một vài biến thể khác :

– Maximum tf normalization [2]

3 . Thực nghiệm

Với bộ dữ liệu như đã làm bằng bag of word . Kết quả dùng với tf-idf tăng khá ít :

tdidf.JPG

Với bộ dữ liệu sentiment thì kết quả đạt tầm 77.23144 %

sentiment.JPG

4 . Tham khảo

[1] http://www.tfidf.com/

[2] http://nlp.stanford.edu/IR-book/html/htmledition/tf-idf-weighting-1.html

Posted in Khác

Ngrams SVMs

1. Ngrams

Thay ví đối xứ words là một từ thì words sẽ là N từ cạnh nhau

 

2. Kết quả thực nghiệm

Với 2-grams thì số features sẽ lên tầm 400.000

Chạy lâu gấp đôi so với tf-idf và bag-of-words ở giai đoạn tìm kiếm tham số tốt nhất

Kết quả thực nghiệm

ngrams.JPG

Posted in Khác

Bag of Words Model

Như trong bài trước đã chỉ ra : Chúng ta cần vector hoá văn bản hoặc câu văn thành một vector của các features để có thể dùng SVMs để phân loại . Bài này sẽ giới thiệu một model đơn giản và khá là trực quan để chuyển 1 văn bản về vector các features . Cuối bài viết , mình sẽ mô tả dữ liệu mình có và code demo để có thể chuyển đổi dữ liệu đó về đúng với định dạng file theo yêu cầu của LibSVM để có thể thử phân loại bài báo . Kết quả sẽ so sánh với thuật toán Naive Bayes (một baseline method của text classification ).

Bag-of-words model là một trong những phương pháp phổ biến nhất dành cho phân loại object (đặc biệt trong xử lý ảnh ) .Bag-of-words không quan tâm đến thứ tự từ trong câu và  cũng chả quan tâm đến ngữ nghĩa của từ  [1] . Một lựa chọn phổ biến khác để diễn đạt từ thành vector  (aka. word2vec) [2]. Họ đã có những nỗ lực gần đây để mở rộng biểu diễn cụm từ, câu, đoạn văn [3]. Word2vec được sử dụng rất nhiều trong các nghiên cứu gần đây . Về phần word2vec sẽ được nói đến ở những bài viết sau này .

I ) Bag-of-Word là gì ?

Model Bag-of-word học được một bộ từ vựng từ tất cả các văn bản , rồi model các văn bản bằng cách đếm số lần xuất hiện của mỗi từ trong văn bản đó . Như thế 2 câu sau có thể được đính là như nhau “Cool for the Summer” and “for the Cool Summer” .

Ví dụ , với hai câu sau :

Sentence 1: “The cat sat on the hat”

Sentence 2: “The dog ate the cat and the hat”

Từ hai câu trên , vocabulary sẽ là :

{ the, cat, sat, on, hat, dog, ate, and }

Để có thể xây dựng được bag of words của 2 câu này , chúng ta đếm số lần xuất hiện của mỗi từ trong mỗi câu . Trong  Sentence 1, “the” xuất hiện hai lần , và “cat”, “sat”, “on”, và “hat” mỗi từ xuất hiện một lần , như thế  feature vector cho Sentence 1 sẽ là :

{ the, cat, sat, on, hat, dog, ate, and }

Sentence 1: { 2, 1, 1, 1, 1, 0, 0, 0 }

Tương tự ,  features cho Sentence 2 sẽ là : { 3, 1, 0, 0, 1, 1, 1, 1}

Một số sách tiếng anh viết về Bag-of-word [4] [5] [6]

2 . Một số vấn đề

2.1 . Tách từ 

Tiếng Anh : Từ thường được ngăn bởi khoảng trắng (space).

Tiếng Việt : Từ có thể gồm một hoặc nhiều âm tiết , các âm tiết được ngăn với nhau bởi khoẳng trắng .

Tách từ là bước xử lý cơ bản trong xử lý văn bản tiếng Việt . Chất lượng của hệ tách từ ảnh hưởng trực tiếp đến các bước sau như gán nhãn từ loại , phân tích cú pháp , phân tích ngữ nghĩa , cũng như các ứng dụng xử lý ngôn ngữ tự nhiên .

Ví dụ
Input: Để đóng vai quần chúng chúng tôi phải mặc quần áo theo lối phong kiến
Output: Để đóng vai quần_chúng chúng_tôi phải mặc quần_áo theo lối phong_kiến

Có 1 thư viện đáp ứng khá tốt bài toán tách từ . Đó là thư viện tách từ của vnu .

2.2 Remove stopwords

Chúng ta phải xử lý mới những từ mà xuất hiện nhiều , tuy nhiên lại không mang lại quá nhiều ý nghĩa . Những từ này được gọi là “stop words” . Trong tiếng Anh , đó là những từ như “is” , “this” , “that” . Còn trong tiếng Việt , đó có thể là những từ “để” , “này” , “kia” .

2.3 Giới hạn số features 

Trong dữ liệu của tôi , chúng ta có khoảng 4.000 bài báo được phân loại  , dẫn tới một vocabulary cực kì lớn . Để làm giảm độ lớn của feature vectors , chúng ta có thể chọn một vài từ xuất hiện nhiều nhất . Ví dụ , 5000 từ xuất hiện nhiều nhất ( stop words đã bị loại bỏ ở phần tiền xử lý )

2.4 Giới hạn độ lớn 1 vector của 1 văn bản

Nếu 1 từ trong vocabulary không xuất hiện trong văn bản thì giá trị feature đó bằng 0 . Vì thế ta có thể loại bỏ nó đi . Bằng cách làm nay với tập dữ liệu của tôi , file train giảm từ 700MB xuống còn 7MB

3. Cài đặt và thử nghiệm

3.1 Mô tả dữ liệu

Sẽ có 1 file data_test.txt để lưu id của bài viết và tên nhãn . Mỗi cụm này sẽ ở 1 dòng

Capture11.JPG

Một file articles.txt sẽ lưu id bài viết và nội dung . Mỗi cụm này sẽ ở 1 dòng

Capture111.JPG

3.2 Tiền xử lý dữ liệu

Chuyển đổi những nhãn kinh_te y_te thành số  để phù hợp với dataformat của libsvm . Vì thế sẽ đánh số theo vị trí xuất hiện . Sau đó từ id bài viết truy ra thể loại của bài viết rồi thay thế id thành thể loại bài viết thôi  .

Sau đó dùng thư viện tách từ . Tách từ xong thì loại bỏ stopwords . Loại bỏ stopword xong sẽ chia dữ liệu trong file articles.txt random thành 10 phần bằng nhau .

Chúng ta sẽ train 9 phân , test 1 lần . Xoay vòng 10 lần như thế lấy trung bình kết quả

Ở phần train sẽ đọc hết file train để xây dụng túi từ bag-of-word của chúng ta . Sau đó với mỗi văn bản , thì đếm số lần xuất hiện của bag-of-word trong văn bản này . Sau khi tiền xử lý , ta sẽ có 10 file Train và 10 file Test như sau

s.JPG

Đúng định dạng data của LibSvm

label feature1:value1 feature2:value2 ….

với feature1<feature2…

Capture.JPG

 

References :

[1] https://www.quora.com/What-are-the-alternatives-to-bag-of-words-for-analyzing-text-documents/answer/Kenneth-Tran?srid=nqv8

[2] http://arxiv.org/pdf/1310.4546.pdf

[3] http://jmlr.org/proceedings/papers/v32/le14.pdf

[4] http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf

[5] Jurafsky Martin , Speech And Language Processing , http://stp.lingfil.uu.se/~santinim/ml/2014/JurafskyMartinSpeechAndLanguageProcessing2ed_draft%202007.pdf

[6] Manning and Schuetze , Foundations of Statistical Natural Language Processing , http://nlp.stanford.edu/fsnlp/

[7] Yin Zhang and Rong Jin and Zhi-Hua Zhou , Understanding Bag-of-Words Model: A Statistical Framework :http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/ijmlc10.pdf

[9] https://www.kaggle.com/c/word2vec-nlp-tutorial/details/part-1-for-beginners-bag-of-words

Posted in Khác

Support Vector Machine

 

  1. Giới thiệu

Một số phương pháp phân loại state-of-the-art : SVM , boosted decision trees, regularized logistic regresstion , neural network , random forests . Và SVMs là một “baseline method” cho bài toán phân loại . Support Vector Machines (SVMs) là 1 kĩ thuật học máy thống kê được giới thiệu bởi Vapnik et al [1] [2]

Sẽ chọn một hyperplane phân biệt các mãu trong bài toán classification .  SVMs sử dụng một chiến lược tối đa hoá margin giữa tập dữ liệu huấn luyện . Trong trường hợp không thể phân biệt dữ liệu huấn luyện một cách tuyến tính ( bởi vì một số noises trong tập dữ liệu huấn luyện ……… ) , chúng ta sẽ tìm một hyperplane chấp nhận một số phân loại sai . Trong trường hợp này chúng ta sẽ xây một optimal hyperplane bằng cách thêm vào một soft margin parameter , nó sẽ cân đối giữa training error và độ lớn của margin [2] . Parameter C này sẽ kiểm soát overfitting

1

Một hyperplane sẽ được định nghĩa bởi một intercept term b và một normal vector w mà vuông góc với hyperplane . Phương trình phân loại tuyến tính sẽ là :

2

Margin giữa 2 lớp sẽ là 2/độ lớn của w . Nên bài toán quy về tìm vector w và b sao cho

3

4

  1. Mở rộng của SVM model

Soft margin classification

16

Nếu tập dữ liệu trainning không phân biệt tuyến tính , phương pháp cơ bản là cho pháp một “fat decision margin” mà có một số lỗi – nằm trong hoặc sai bên của margin . Chung ta sẽ trả giá cho mỗi example mà phân loại sai , phụ thuộc vào độ xa cho tới margin . Bài toán trở thành

6

Multiclass

OnevsRest : Xây dựng một tập phân loại one-versus-rest , chọn class mà bộ phân loại tạo ra margin lớn nhất với dữ liệu test .

OnevsOne :Xây dựng một tập phân loại one-versus-one , và chọn class nào mà được lựa chọn nhiều nhất bởi các bộ phân loại . Sẽ có k(k-1)/2 bộ phân loại , thời gian huấn luyện có thể tăng nhưng dataset của mỗi bộ phân loại thì nhỏ hơn nhiều .

LibSVM sử dụng OnevsOne [4]

Dùng chung tham số cho k (k-1) /2 models [7]

Các method multi-class như :

  • One vs. One multi-class classification using a bound-constrained formulation
  • Multi-class classification by solving a single optimization problem (again, a bounded formulation). See Section 3 of our comparison paper.
  • Multi-class classification using Crammer and Singer’s formulation.
  • Regression using a bound-constrained formulation
  • Multi-class classification using Crammer and Singer’s formulation with squared hinge (L2) loss

đều được hỗ trợ ở [5]

  • Nonlinear SVMs7

Nếu dữ liệu không cho phép chúng ta phân loại theo linear classifier , chúng ta có thể map data lên một không gian có số chiều lớn hơn và sử dụng liner classifier trong không gian lớn hơn đó .

SVMs , cũng như các linear classifiers khác , cũng cấp một cách thuận tiện để mapping tới không gian có số chiều lớn hơn , thường được gọi là “the kernel trick” . SVM linear classifiers dựa vào dot product giữa các điểm dữ liệu .  Một kernel function K sẽ là một function chịu trách nhiệm tính toán dot product trong không gian vừa được mở rộng .

  1. Feature set

Words : all words in the sentence (== bag of word ??)

Important words : Main words in the sentence , including proper-nouns , common nouns , verbs , adjectives , adverbs , and subordinating conjunctions

N-grams of words : Uni , bi , tri hoặc kết hợp 3 thằng hay 2 thằng lại . Kết quả khá ổn [3]

Naïve Bayes feature [3]

Word2vec

Doc2vec

Glove

Tf-idf

Có thể chọn tay các features

Có thể dùng LDA để giảm số chiều của features

  1. NaiveBayes SVMs

Multiclass thì tính

Ví dụ với bài toán Sentiment classification có 3 lớp Positive , Neutral , Negative tương ứng với tập nhãn {-1,0,1} [5]

Capture

α là smoothing parameter (=1 theo [3] )

p là tổng tất cả binarization vectors của positive samples

q là tổng tất cả các binarization vectors của các samples khác (negative and neutral)

Log-ratio của positive samples sẽ tính như sau :

8

x mang nhãn 1 sẽ thay thế bằng r . x (elementwise product)

  1. Sử dụng LibSVM

Không cho kết quả tốt nhất , chỉ cho ra kết quả chấp nhận được

Là một thư viện dễ dùng

Data format

<label> <index1>:<value1> <index2>:<value2> …

.

.

.

Scaling

Scaling trước khi áp dụng SVM là rất quan trọng [8]

Bước này thu hẹp giá trị các feature về ở trong khoảng [-1..1] hoặc [0..1]

Model Selection

Có 4 loại kernels cơ bản :

9

Khi nào dùng Kernel nào : Khi số features là rất lớn , chúng ra có thể không cần map data tới không gian có số chiều nhiều hơn . Như thế , nonlinear mapping không cải thiện hiệu năng . Sử dụng linear kernel là đủ tốt và nó chỉ cần tìm tham số C nên rất nhanh .

Khi số mẫu << số features nên dùng Linear Kernel

Kho số mẫu và số features đều rất lớn dùng LIBLINEAR (chạy nhanh hơn LIBSVM)

Khi số mẫu >> số features nên dùng : Nên sử dụng nonlinear kernels , vì thường xuyên maps data tới không gian có chiều lớn hơn . Nếu muốn dùng linear kernel thì cũng được .

Nói chung nên thử hết mọi loại Kernel

Các tham số

Các tham số khi train model

10

Các tham số khi scaling dữ liệu

11

Chú ý : Phải scaling dữ liệu huấn luyện và dữ liệu test cùng 1 range để ra keets quả chính xác nhất

Các tham số khi dự đoán

12

Có thể sử dụng file checkdata.py để kiểm tra dataset đã đúng định dạng dữ liệu chưa

Tối ưu hoá tìm ra các tham số tối ưu

13

Grid.py là tool lựa chọn tham số cho C-SVM classification sử dụng Kernel RBF

Tự động hoá quá trình tối ưu

14

Chia dữ liệu có thể dùng :

15

Cách tối ưu

Ví dụ :

Sử dụng tham số mặc định
$ ./svm-train svmguide1

$ ./svm-predict svmguide1.t svmguide1.model svmguide1.t.predict

→ Accuracy = 66.925%

Scaling data với tham số mặc định

$ ./svm-scale -l -1 -u 1 -s range1 svmguide1 > svmguide1.scale

$ ./svm-scale -r range1 svmguide1.t > svmguide1.t.scale

$ ./svm-train svmguide1.scale

$ ./svm-predict svmguide1.t.scale svmguide1.scale.model svmguide1.t.predict

→ Accuracy = 96.15%

Scaling data với tham số được lựa chọn

$ python grid.py svmguide1.scale

  • · · 2.0 2.0 96.8922

(Best C=2.0, γ=2.0 with five-fold cross-validation rate=96.8922%)

$ ./svm-train -c 2 -g 2 svmguide1.scale

$ ./svm-predict svmguide1.t.scale svmguide1.scale.model svmguide1.t.predict

→ Accuracy = 96.875%

Sử dụng script tự động

$ python easy.py svmguide1 svmguide1.t

Scaling training data…

Cross validation…

Best c=2.0, g=2.0

Training…

Scaling testing data…

Testing…

Accuracy = 96.875% (3875/4000) (classification)

[1] C. Cortes and V. Vapnik. Support-Vector Networks. Machine Learning, 20(3):273–297,1995.

[2]V.N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.

[3] S.Wang and CD.Manning , Baselines and Bigrams: Simple, Good Sentiment and Topic Classification , 2012

[4] http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f419

[5]  Remi Lebret and Ronan Collobert , N-GRAM-BASED LOW-DIMENSIONAL REPRESENTA – TION FOR DOCUMENT CLASSIFICATION , Accepted as a workshop contribution at ICLR 2015l

 

[6] https://www.csie.ntu.edu.tw/~cjlin/bsvm/

[7] http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f507

[8] ftp://ftp.sas.com/pub/neural/FAQ.html