Những khái niệm cơ bản trong Machine Learning

icon1

Mở đầu

Như hiện nay, với sự trợ giúp của máy tính, hầu như các công việc bình thường ta đã có thể giải quyết một cách dễ dàng thông qua các phần mềm cài đặt. Nhưng đôi khi ta mong chơ nhiều hơn nữa từ máy tính, không phải từ những phần mềm cứng nhắc được thiết kế ngay theo những yêu cầu từ các dữ liệu input -> output, và dữ liệu output đó luôn phụ thuộc vào dữ liệu input trong mọi thời điểm. Ta mong muốn máy tính có thể xử lý các công việc dựa vào dữ liệu và kinh nghiệm vào thông qua quá trình làm việc rồi đưa ra kết quả phù hợp, hay nói đúng hơn, ta mong muốn máy tính có thể xử lý và đưa ra quyết định giống với con người hơn. Ví dụ: Ta dạy máy tính cách đánh poker, tại thời điểm trước, với những quân bài bốc được, máy tính đưa ra quyết định “theo”, kết quả ván đó bị thua. Tại ván bài trong tương lai với những quân bài từng bốc được trong những ván cũ, dựa vào kinh nghiệm trong qua khứ, máy tính sẽ lựa chọn quyết định “từ bỏ”, vì biết nếu cược tiếp thì sẽ thua.

Tại sao lại cần đến Machine Learning

_ Đối với những bài toán đơn giản, ta hoàn toàn có thể xây dựng những thuật toán hợp lý để giải quyết bài toán. Nhưng với những bài toán phức tạp hơn, ví dụ với những ứng dụng liên quan đến thị giác máy tính, hay xử lý ngôn ngữ tự nhiên, hoàn toán rất khó để nhận diện hình ảnh, mặt chữ, âm thanh nếu như không sử dụng đến quá trình học và kinh nghiệm

_ Với những hành vi của người dùng trong tương lai có thể thay đổi, vì vậy ta cần thiết kế ra những chương trình có thể thích nghi được với hành vi người dùng, thông qua dữ liệu thu thập được. Mà những điều đó yêu cầu chương trình phải có khả năng học.

_ Đối với những ngành đặc thù, nhưng ta vẫn muốn áp dụng những chương trình máy tính, thay thế cho việc thuê những chuyên gia, ví dụ trong ngành dự báo tài chính, chứng khoán, chẩn đoán y học, …

Phân loại Machine Learning

Về cơ bản có thể chia hệ thống học máy thành những loại chính như sau:

Supervised learning:

Là dạng học máy có giám sát, trong đó dữ liệu huấn luyện được cho dưới dạng các mẫu có đính kèm các giá trị đầu ra ( có thể nói là được gán nhãn label ). Dựa trên dữ liệu huấn luyện, ta cần xây dựng một hệ thống, hay các hàm để có thể dự đoán giá trị đầu ra đối với những dữ liệu với. Hay có thể nói ta có 1 tập data X, với giá trị đầu ra, hay tập đích với mỗi y tương đương với x là tập Y, vậy ta cần xây dựng hàm để thoả mãn với tất cả X -> Y. Cuối cùng ta xây dựng f thoả mãn: y = f(x). Vậy với một dữ liệu x(n) mới, với hàm ta xây dựng được, hoàn toàn có thể dự đoán được giá trị đầu ra y(n). Về cơ bản, supervised learning được chia làm hai loại chính:

  • Classification: Khi các dữ liệu đầu ra là rời rạc, học giám sát được gọi là phân loại. Ta cần phân loại tập dữ liệu X phân phối vào tập các đầu ra hữu hạn Y, ví dụ như: Với tập dư liệu về chiều cao (m) và cân nặng (kg) và giới tính của 10000 người, ta cần xây dựng một hệ thống học máy để có thể phán giới tính của một người sau khi có dữ liệu về chiều cao, cân nặng của người đó. Có thể thấy đầu ra chỉ nhận giá trị hữu hạn [Nam, Nữ].
  • Regression: Khi các dữ liệu đầu ra là liên tục, học giám sát gọi là hồi quy. Ta có tập dữ liệu X tương ứng với tập dữ liệu đầu ra Y là các số thực, với một giá trị x bất kì ta có thể dự đoán gía trị thực đầu ra y. Ví dụ ta có tập dữ liệu thông số của 10000 chiếc máy tính gồm ram, ổ cứng, nguồn, … và giá bán ra của mỗi chiếc máy tính. Ta hoàn toàn có thể xây dựng hệ thống học máy để phán đoán giá trị của một chiếc máy tính thông qua các thông số về cấu hình máy.

Unsupervised learning:

Khác với dạng học máy có giám sát, trong đó dữ liệu huấn luyện được cho dưới dạng các mẫu nhưng không được đính kèm đầu ra. Ta cũng chia unsupervised learning được chia làm hai loại chính:

  • Clustering: Thay vì cố tìm ra các gía trị đầu ra, ta cố gắng phân loại các dữ liệu X thành các cụm dựa trên độ tương tự giữa các dữ liệu. Ta gọi loại học không giám sát như vật là phân cụm. Ví dụ ta có dữ liệu hình ảnh về các hình tròn, tam giác, vuông. Với loại học máy phân cụm, hoàn toàn có thể phân loại những hình ảnh trên về 3 cụm riêng biệt chứa các hình ảnh về tam giác, tròn, vuông tương ứng, mặc dù ta không hề gán nhãn cho mỗi cụm là gì, vì tiêu chi được xếp vào mỗi nhóm dựa trên tính tương đồng trên mỗi hình ảnh.
  • Association rule: Đây là một dạng học không giám sát khi cố gắng tim ra tính tương quan giữa các dữ liệu, ta gọi là luật kết hợp. Luật kết hợp có dạng P(A|B), biểu diễn này có nghĩa là nếu dữ liệu có tính chất A thì có xác xuất P xuất hiện cả tính chất B. Ví dụ với dữ liệu đánh giá điện thoại ta có thể nhận thấy P( Màn hình | Độ phân giải) = 68%. Điều này có nghĩa là vỡi mỗi đánh giá về điện thoại thì với đặc tính “Màn hình” thì có 68% sẽ xuất hiện đặc tính “Độ phân giải”.

Reinforcement learning:

Học tăng cường là một dạng học máy, thay vì việc cho bộ dữ liệu đầu vào và giá trị đích cho mỗi hành động, mà hệ thống sẽ nhận được điểm thưởng là kết quả cho một chuỗi hành động. Thuật toán cần tối ưu hoá chuỗi hành động để có thể khuếch đại cao nhất điểm thưởng. Ví dụ với trò đánh cờ, nước đi tối ưu nhất là nước đi nằm trong chuỗi nước đi mà kết quả cuối cùng thắng ván cờ, cho nên tại mỗi nước đi, không có nước đi nào là hợp lý và tối ưu cả.

Kết Luận

Hầu hết những bài toán hiện tại thường rơi vào hai dạng học máy chính là học giám sát và học không giám sát. Khi tiếp cận với học máy, không phải ta đang bước chân vào thế giới kì diệu của máy tính, hay một lớp thư viện và dữ liệu đồ sộ, mà ta đang bước chân vào toán học, một thứ mà có thể rất nhiều năm trước chắc không ít người thắc mắc, mình học cái méo này để làm gì nhỉ ? Sau này mình sẽ làm gì với nó ? Khi nhắc đến học máy, sẽ có xu hướng nghĩ ngay đến việc làm thế nào để dùng cái thư viện để xử lý bài toán mà bỏ qua việc tìm hiểu cái thuật toán nó như thế nào. Nhưng cái hay chắc chắn nó nằm ở việc hiểu cách thuật toán thực hiện.

Tài liệu tham khảo

https://machinelearningcoban.com

Bài giảng Trí tuệ nhân tạo _ Từ Minh Phương

Deep learning _ Ian Goodfellow and Yoshua Bengio and Aaron Courville

https://www.coursera.org/learn/machine-learning

Advertisements

Phương pháp nhân tử Lagrange với đẳng thức

Mở đầu

Trong ngành toán học tối ưu, với phương pháp nhân tử Lagrange (đặt theo tên một nhà toán học) ta có thể tìm được cực tiểu hoặc cực đại địa phương của một hàm số nhưng chịu các điều kiện giới hạn.

Lagrange_portrait

Phát biểu bài toán

  1. Ta muốn tìm cực tiểu của hàm z = f(x;y) với điều kiện ràng buộc φ(x; y) = 0.
  2. Ta thiết lập hàm Lagrange L(x; y; λ) = f (x; y) + λφ(x; y).
  3. Tìm điểm dừng của L, tức là giải hệ phương trình:
  4. Screen Shot 2018-11-13 at 10.26.04 AM
  5. Xét dấu đạo hàm bậc 2 của hàm L tại điểm (x0;y0) mà (x0;y0;λ0) là nghiệm của hệ phương trình ở bước 4
  • L”(x0; y0; λ0) < 0 = f(x0; y0)    (Hàm Z đạt cực đại)
  • L”(x0; y0; λ0) > 0 = f(x0; y0)    (Hàm Z đạt cực tiểu)

Bài toán

Cho hai số thực x, y thoả mãn điều kiện x + y = 10. Tìm giá trị nhỏ nhất của biểu thức f(x;y) = x^2 + y^2
  1. Ta tìm cực trị đối với hàm f(x;y) = x^2 + y^2 thoả mãn  φ(x;y) = x + y – 10 = 0
  2. T thiết lập hàm L(x; y; λ) = x^2 + y^2 + λ(x + y = 10)
  • Ta đạo hàm L(x; y; λ) theo x : L'(x; y; λ)(x) = 2x + λ = 0 => x = -λ/2 (1)
  • Ta đạo hàm L(x; y; λ) theo y : L'(x; y; λ)(y) = 2y + λ = 0 => y = -λ/2 (2)
  • Ta đạo hàm L(x; y; λ) theo λ : L'(x; y; λ)(λ) = x + y – 10 = 0. Từ (1) (2) => λ = -10

=> Ta có điểm dừng x0 (5,5,-10).

Kết luận

Phần tìm giá trị nhỏ nhất đã được bỏ qua ở đoạn cuối, phần quan trọng nhất là tìm điểm dừng x0, và với chủ đề này blog cũng chỉ đề cập đến phương pháp nhân tử Lagrange với đẳng thức, phần bất đẳng thức hoàn toàn không được đề cập đến. Bài này cũng khá ngắn, chỉ đề cập về toán học thông thường, nhưng tất nhiên là cũng có lý do riêng của nó, và là để chuẩn bị cho một blog dài hơi hơn.

Tản mạn về toán và cuộc sống

Ngay từ khi học cập 3, thương ta gặp rất nhiều bài toán, dạng toán mà đôi khi ta tự hỏi, sau này nó giúp gì cho mình không ? Tại sao phải học toán, biết cộng trừ nhân chia là đủ rồi, phải không ?

Ngày xưa, khi cuộc sống mà con người ta chỉ biết đến những tài sản mà họ có như là một con trâu, 2 thửa ruộng,… Nhưng lại đối với những người đang nợ nần, tức là họ phải đạt được một một tiền nào đó thì họ mới trở về tình trạng vô sản. Vậy người ta mới nghĩ ra số âm, để biểu diễn cho trạng thái đó. À vậy đó là lí do số âm ra đời.

Đến một ngày kia, khi người ta phát hiện ra bất kì chu vi của một đường tròn nếu chia cho bán kính thì đều ra một hằng số, sau đó họ đặt tên là số pi, rồi cạnh huyền của một tam giác vuông bằng một số nào đó mà thoả mãn c^2 = a^2 + b^2. Nhưng không thể viết chính xác được số đó, và thế là họ nghĩ ra đến căn bậc 2 ( √ ). À vậy là đó là lí do ra đời của số hữu tỉ.

Và rồi họ cũng nghĩ ra logarit log(x) = y, vì đơn giản họ thấy rằng số đó tồn tại, khi vẽ lên hàm số, đường cong log(x) giao với đường thằng y = x tại một điểm, chỉ là người ra không thể chỉ chính xác nó mà thôi.

Vậy toán học chỉ đơn giản là một công cụ, hay một trò chơi mà con người ra nghĩ ra để đặt tên chỉ điểm cho những cái mà họ không thể biểu diễn chính xác. Đôi khi những bài toán đơn thuần được nghĩ ra, nhưng tồn tại và không ai giải được hoặc chứng minh được, hoặc là những bài toán có thể giải được nhưng có khi mất đến vài … trăm năm chẳng hạn. Ví dụ giải hệ phương trình bậc n, tìm mặt phẳng trong chiều thứ n, … đơn giản vì ta chỉ sống trong không gian 4 chiều (x, y, z, t), nhưng những vấn đề ta gặp phải nó vượt xa ngoài tầm cái 4 chiều rồi. Và máy tính, tin học ra đời, một thứ tuyệt vời, nó giúp ta chứng minh và giải hầu hết các bài toán trong thời gian realtime. Và với cái thời đại thông tin và học máy bùng nổ, mà vẫn chỉ muốn cộng trừ nhân chia, hay là … học toán xong chẳng để áp dụng vào đâu, thì đúng thật là … ấu trĩ =)).

Tài liệu tham khảo

METHOD OF LAGRANGE MULTIPLIERS _ đienantoanhoc.net

Tản mạn về Singleton

singleton-pattern-uml

Mở đầu

Quá dễ dàng để nhận thấy rằng, khi ta chỉ cho phép tạo một đối tượng của một lớp cụ thể mặc cho người khác có cố gắng tạo bao nhiêu đối tượng đi nữa, thì ta phải dùng mẫ pattern Singleton này. Trong cuốn sách GoF nói rằng, mẫu Singleton “Đảm bảo rằng một lớp chỉ có duy nhất một thể hiện và cung cấp một biến toàn cục để truy cập nó”.

Bạn sử dụng mẫu Singleton khi bạn muốn hạn chế việc sử dụng tài nguyên (thay vì việc tạo không hạn chế số lượng đối tượng) hoặc khi bạn cần phải xử lý một đối tượng nhạy cảm, mà dữ liệu của nó không thể chia sẻ cho mọi thể hiện.

Ví dụ:

Screen Shot 2018-09-27 at 9.55.47 AM

 

 

 

 

Ngoài ra bạn có thể sử dụng mẫu Singleton khi bạn muốn hạn chế số lượng các thể hiện được tạo bởi vì bạn muốn chia sẻ dữ liệu của các đối tượng này. Ví dụ như khi bạn có một đối tượng cửa sổ window hay hộp thoại dialog, cần phải hiện thị và thay đổi dữ liệu, bạn sẽ không muốn tạo nhiều thể hiện của đối tượng này, vì bạn sẽ bị bối rối trong việc phải truy cập dữ liệu của thể hiện nào.

Screen Shot 2018-09-27 at 10.02.56 AM

Bài toán

Ồ, vậy bài toán đặt ra là: Ta có một class Boo vậy làm cách nào để ta thực hiện được mẫu pattern Singleton lên class Boo đó. Nhưng class đó phải đảm bảo được việc hạn chế cho các class khác có thể truy cập, đồng thời cũng đảm bảo được việc nó chỉ tạo một đối tượng duy nhất tại mọi thời điểm. 

Bắt đầu

Đầu tiên ta phải tạo class Boo đã:

Screen Shot 2018-09-27 at 10.25.05 AM

Ồ, vấn đề là ở đây, cái hàm khởi tạo quá riêng tư, mỗi khi ta cần khởi tạo đối tượng mới bằng toán tử new, lại có một đối tượng được sinh ra. Có lẽ ta nên thay đổi một chút.

Screen Shot 2018-09-27 at 10.30.38 AM.png

Mọi thứ có vẻ khá hơn, nhưng con vấn đề đa luồng thì sao, nếu hai luồng chạy cùng một thời điểm, có thể ta sẽ tạo ra 2 đối tượng cũng 1 lúc. Ta cần giải quyết điều đó ngay. Không khó, ta chỉ cần thay đổi 1 chút hàm getInstance thôi.

Screen Shot 2018-09-27 at 10.34.30 AM.png

Mọi thứ thật hoàn hảo, nhưng dường như code quá dài, ta có thể tối ưu hơn một chút. Giả sử ta thấy thằng việc “lazy init” là không cần thiết, vì đàng nào cũng phải khởi tạo ngay từ đầu. Các tham số của hàm khởi tạo có thể thay đổi sau, hoặc để default, ta có thể thay đổi source code như sau. Với việc khởi tạo đối tượng ngay từ đầu ta còn không cần từ khoá synchronized cho việc đồng bộ. Quá hay

Screen Shot 2018-09-27 at 10.52.29 AM.png

Lưu ý

Việc tạo class theo Singleton thường sẽ rất khó test ở phía client, vì việc không thể test mock cho các singleton.

Mặc dù việc thực hiện tạp pattern singleton không quá phức tạp nhưng chúng ta nên tiếp cận theo nhiều phương pháp khác nhau.

  • Singleton với các member là các trường final

Screen Shot 2018-09-27 at 11.04.49 AM

Việc gọi đối tượng khá đơn giản với Boo.singletonBoo. Việc ta thiết lập private hay protected cho hàm khởi tạo để đẩm bảo đối tượng là duy nhất, không nhiều hơn, không ít hơn. Client không thể thay đổi được điều đó, trừ phi họ dùng refeflection, bằng cách gọi private constructor reflectively cùng với AccessibleObject.setAccessible. Để hạn chế việc này, ta nên thêm vào hàm khởi tạo các throw exception, nếu có yêu cầu khởi tạo lần thứ hai.

  • Singleton với member là các hàm static factory 

Screen Shot 2018-09-27 at 12.54.13 PM

Việc gọi Boo.getInstance() sẽ trả về tham chiếu của đối tượng, và tất nhiên không có đối tượng nào được khởi tạo thêm ở đây. Hướng tiếp cận này là hướng tiếp cận kiểu API, làm cho class Boo khá rõ ràng, do đối tượng được khai báo là final nên ta đang tham chiếu đến duy nhất một đối tượng. vá tất nhiên hướng tiếp cận này cũng khá đơn giản để cài đặt. Hướng tiếp cận này rất linh hoạt khi ta muốn thay đổi bản thân bên trong phương thức mà không cần phải thay đổi API, có thể nói rằng ta đang tách riêng đối tượng với mỗi luồng gọi đến phương thức. Và tất nhiên ta hoàn toàn có thể viết một generic singleton factory. Ngoài ra ta có thể sử dụng cả method reference  ( tính năng mới trên java 8).

Tất nhiên để class singleton, ta nên nhìn nhận vấn đề khi class đó implement Interface Serializable, nếu như việc implement là bắt buộc, nhưng ta vẫn muốn đảm bảo việc class là singleton, ta cần làm hai việc: 1) Khai báo tất cả các trường với từ khoá là transient (Để khi writeObject, jvm sẽ bỏ qua các trường này). 2) cung cấp phương thức readResolve, vì mỗi lần đối tượng được readObject khi deserialized, phương thức trên sẽ được gọi trước, nếu như ta bỏ qua phương thức readResolve, đối tượng ta nhận về sẽ không phải là đối tượng ta khởi tạo ban đầu khi serialized.

Screen Shot 2018-09-27 at 1.51.16 PM.png

Đừng quá quan tâm đến cái serialVersionUID, vì đó chỉ là cái định danh cho mỗi đối tượng, và trong quá trình jvm thực hiện serialized, nó sẽ phân biệt các đối tượng với nhau thôi.

  • Singleton với enum

Screen Shot 2018-09-27 at 1.55.46 PM.png

Với hướng tiếp cận này, ta không phải lo lắng vấn đề serialization, cũng không lo về việc khởi tạo lại nhiều lần, vì đó là cơ chế của enum không cho phép điều đó. Có thể nói đây là hướng tiếp cận tốt nhất cho việc thiết kế pattern Singleton. Duy chỉ có việc là nó chỉ extend được mỗi enum thôi, nhưng vẫn implement được interface nhé.

Tài liệu tham khảo

Effective Java 3rd Edition _ Joshua Bloch

Software Architecture Design Patterns in Java _ Partha Kuchana

Design Patterns For Dummies _ Steve Holzner, PhD

( Bài viết nếu có gì sai sót, mong nhận thêm gạch đá để hoàn thiên hơn ạ )

 

 

Khai phá dữ liệu với thuật toán Apriori (Phần 2)

Mở đầu

Tiếp nối phần lý thuyết mình đã trình bày ở bài trước về luật kết hợp ( Link nè: Khai phá dữ liệu với thuật toán Apriori (Phần 1) ). Phần này mình chỉ tập trung trình bày về thuật toán Apriori thôi. Nói lại một chút thì thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng Binary association rules. Không quá khó để tìm kiếm các source code của thuật toán này, cũng như tìm hiểu các biến thể của thuật toán, tuỳ mục đích sử dụng mà mình sẽ cài đặt lại hoặc tìm các source code có sẵn. Trong phần này mình chỉ nêu lên tư tưởng chính của thuật toán, phần tối ưu thuật toán mình cũng có tham khảo qua một số bài báo, nên nếu có, mình sẽ trình bài trong phần 3 sau. Bây giờ, bắt đầu nhé.

Bài toán 

Đầu tiên ta sẽ có 1 file data.txt gồm các thông tin như sau :

2.0 0.8   // Ta quy ước 2.0 là giá trị của min_support và giá trị thứ 2 là min_confidence
A C D    // Các hàng tiếp theo là các record
B C E
A B C E
B E

Và thông qua thuật toán Apriori, ta sẽ tìm ra được tập phổ biến thông qua các record trên.

Thuật toán

1.    Duyệt (Scan)  toàn bộ transaction database để có được support S của 1-itemset, so sánh S với min_sup, để có được 1-itemset (L1)

Ví dụ: Với bài toán trên, ta sẽ tìm ra những tập con phổ biến của 1-itemset = { A{2}, C{3}, D{1}, B{3}, E{3}}. Ta quy ước mỗi tập con có dạng Ni{m} với Ni  là tập con với số i thuộc tính, và m là số lần xuất hiện trong mỗi reccord. Ta nhận thấy rằng tập con D{1} không thoả mãn vì m < min_support ( m = 1 và min_support = 2 ). 

2.    Sử dụng Lk-1 nối (join) Lk-1  để sinh ra candidate k-itemset. Loại bỏ các itemsets không phải là frequent itemsets thu được k-itemset

Ví dụ: Ở bước tiếp theo sử dụng join tập 1-itemset với chính nó để sinh ra tập ứng viên 2-itemset, ta sẽ loại bỏ các tập không phổ biến ( có tần suất nhỏ hơn min_support, và những thuộc tính trùng lặp), vậy ở bước trên ta sẽ thu được các tập sau: 2-itemset = { {A, B}{1}, {A, C}{2}, {A, E}{1}, {B, C}{2}, {B, E}{3}, {C, E}{2}}. Và với giá trị min support ta loại bỏ đi những tập không phổ biến là {A, B}{1}, {A, E}{1}

3.    Scan transaction database để có được support của mỗi candidate k-itemset, so sánh S với min_sup để thu được frequent k –itemset (Lk)

4.    Lặp lại từ bước 2 cho đến khi Candidate set (C) trống (không tìm thấy frequent itemsets)

5.    Với mỗi frequent itemset I, sinh tất cả các tập con s không rỗng của I

6.    Với mỗi tập con s không rỗng của I, sinh ra các luật  s => (I-s) nếu độ tin cậy (Confidence)  của nó >= min_conf

Các bước trên sẽ thực hiện cho đến khi nào ta tìm được tập k-itemset, mà tại (k + 1)-itemset tập đó sẽ rỗng, thì tập k-itemset là tập phổ biến ta cần tìm, và thuật toán dừng lại.

Source code

https://aloha.apriori

Ngày trước khi cài đặt thuật toán, mình dùng java, nhưng khi thực hiện xử lý với dữ liệu lớn thì java có vẻ không phải là sự lựa chọn hoàn hảo. Sau đó, khi biết đến Scala và Python, mình thấy có vẻ đây là sự lựa chọn hoàn hảo hơn. Scala có akka, nếu apply để xử lý cho việc tìm ra các tập ứng viên và tìm tần suất xuất hiện của những tập ứng viên trong từng record, việc mà ngày trước khi dùng java để chia luồng xử lý, cực vất vả. Python thì có bộ thư viện pandas cho việc xử lý dữ liệu dạng bảng cực tốt.

Phần source cài đặt có thể chưa đẹp và tối ưu, mọi “gạch đá” xin gửi bên dưới comment giúp mình nhé.

Các tài liệu tham khảo

http://bis.net.vn/forums/t/389.aspx

Hu, M., and Liu, B. 2004. Mining Opinion Features in Customer Reviews. To appear in AAAI’04, 2004

Liu, B., Hsu, W., Ma, Y. 1998. Integrating Classification and Association Rule Mining. KDD’98, 1998.

Minqing Hu and Bing Liu. Mining and Summarizing Customer Reviews, Department of Computer Science University of Illinois at Chicago

 

Khai phá dữ liệu với thuật toán Apriori (Phần 1)

Mở đầu

Trong lĩnh vực phá dữ liệu (Data mining) việc trích chọn ra được những thông tin cần thiết là rất quan trọng. Bài toán được áp dụng khi ta có một tập dữ liệu lớn về một đối tượng X nào đó mà ta đang quan tâm, muốn khảo sát, nhưng ta không biết làm thế nào để trích chọn ra thông tin quan trọng. Giả sử ta có tập dữ liệu về thông tin mua bán, hay hoá đơn bán hàng của siêu thị, từ đó ta có thể biết được những nhóm sản phẩm nào được mua nhiều nhất, hay ta có được dữ liệu của tất cả những comment của một diễn đàn, mà họ đang quan tâm về một sản phẩm X nào đó, ta có thể biết được họ đang tâm đến những đặc trưng gì về sản phẩm. Và tất nhiên, nếu ta đọc hết những lượng dữ liệu đó thì ta cũng có thể có được thông tin ta muốn, nhưng nếu lượng dữ liệu đó quá lớn thì thực sự ta đang phí thời gian, hãy để việc đó cho máy tính xử lý, việc của ta là tìm cách để máy tính làm được điều đó. Có rất nhiều thuật toán giúp ta thực hiện, nhưng hôm nay mình sẽ giới thiệu về thuật toán Apriori dựa trên luật kết hợp (Association Rule)

Apriori-Algorithm

Luật kết hợp (Association Rule)

Phần đầu tiên, mình sẽ giới thiệu về luật kết hợp trong khai phá dữ liệu, luật kết hợp nhằm mục đích để tìm ra mối quan hệ giữa các đối tượng với nhau trong khối lượng lớn dữ liệu. Luật kết hợp có thể mô tả như sau:

Giả sử ta có một tập các dữ liệu, mỗi dữ liệu như một record trong database. Ví dụ: ta coi mỗi một đánh giá của người dùng cho sản phẩm X nào đó là một record, hoặc mỗi một hoá đơn mua hàng gồm n các sản phầm được mua là một record. Nhưng đối với luật kết hợp, ta gọi mỗi record là một transaction T. Ta có :

T = { t1, t2, t3, …} gọi là một tập các dữ liệu giao dịch ( transaction database )

Với mỗi một giao dịch T thường có một tập các thuộc tính item I. Ví dụ: mỗi một hoá đơn thường có một tập các mặt hàng như nước ngọt, giấy ăn, bàn chải, dầu gội, … mỗi mặt hàng ta coi là một item. Mỗi một comment về một sản phẩm X đang đề cập đến nhiều đặc trưng của X, mỗi một đặc trưng đó là một item i. Item chính là thông tin mà ta mong muốn có được trong mỗi Transaction. Ta có:

I = {i1, i2, i3, i4, …} gọi là các item của mỗi giao dịch T ( item set )

Và mục đich của luật kết hợp chính là tìm ra sự tương quan, dự kết hợp giữa các tập item đó với nhau. Luật kết hợp này có dạng X => Y. Ta có thể hiểu là nếu X xuất hiện thì Y cũng sẽ xuất hiện. Ví dụ: Trong hoá đơn mua hàng có X = { điện thoại, tai nghe } , Y = { sạc dự phòng, ốp điện thoại }, vậy nên ta có thể hiểu là, nếu người mua hàng mua điện thoại và tai nghe thì họ cũng hay mua sạc dự phòng và ốp điện thoại, chúng hay xuất hiện với nhau.

X được xem là biến độc lập (Independent variable) còn Y được xem là biến phụ thuộc (Dependent variable)

Độ hỗ trợ (Support)

Độ hỗ trợ (Support) của luật kết hợp X => Y là tần suất của giao dịch chứa tất cả các items trong cả hai tập X và Y. Ví dụ, support của luật X =>Y là 5% có nghĩa là  5% các giao dịch X và Y được mua cùng nhau.

Công thức để tính support của luật X =>Y như sau:

support( X -> Y) = P( X ∪ Y ) = n(X ∪ Y) / N 

n(X ∪ Y): số lần xuất hiện đồng thời X và Y

N: tổng số các giao dịch

Độ tin cây (Confidence)

Độ tin cậy (Confidence) của luật kết hợp X => Y là xác suất xảy ra Y khi đã biết X. Ví dụ độ tin cậy của luật kết hợp { điện thoại, tai nghe } => { sạc dự phòng, ốp điện thoại } là 80% có nghĩa là 80% khách hàng mua { điện thoại, tai nghe } thì cũng mua { sạc dự phòng, ốp điện thoại }.

Công thức để tính độ tin cậy của luật kết hợp X => là xác suất có điều kiện Y khi đã biết X như sau :

confidence( X -> Y) = P( X | Y ) = n(X ∪ Y) / n(X)

n(X ∪ Y) : số lần xuất hiện đồng thời X và Y

n(X): tổng số các giao dịch chứa X

Áp dụng các luật kết hợp

Ta thường áp dụng 2 tiêu chí: minimum support (min_sup) và  minimum confidence (min_conf)

Các luật thỏa mãn có support và confidence thỏa mãn (lớn hơn hoặc bằng)  cả Minimum support và Minimum confidence gọi là các luật mạnh (Strong Role)

Minimum support và Minimum confidence gọi là các giá trị ngưỡng (threshold) và phải xác định trước khi sinh các luật kết hợp.

Một itemsets tần suất xuất hiện của nó >= min_sup goi là frequent itemsets

Một số loại luật kết hợp

  • Binary association rules (luật kết hợp nhị phân)
  • Quantitative association rules (luật kết hợp định lượng):
  • Fuzzy association rules (Luật kết hợp mờ)

Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng Binary association rules.

( Phần 2 )

Các tài liệu tham khảo

http://bis.net.vn/forums/t/389.aspx

Hu, M., and Liu, B. 2004. Mining Opinion Features in Customer Reviews. To appear in AAAI’04, 2004

Liu, B., Hsu, W., Ma, Y. 1998. Integrating Classification and Association Rule Mining. KDD’98, 1998.  

Minqing Hu and Bing Liu. Mining and Summarizing Customer Reviews, Department of Computer Science University of Illinois at Chicago

 

Pattern matching với KMP

Mở đầu

Có một bài toán cũng được sử dụng tương đối nhiều và phổ biến là họ những bài toán “Pattern Searching”, tìm một chuỗi con trong một chuỗi lớn. Với những ứng dụng “cực kì” thực tế và phổ biến như hàm contain hay indexOf trong java, sẽ trả về vị trí i trong chuỗi lớn mà bắt đầu xuất hiện chuỗi con (với indexOf) và true, hoặc false nếu chuỗi lớn thực sự đang chứa chuỗi bé. Đối với những bài toán mà lượng thông tin không nhiều, thuật toán indexOf ( bản chất là thuật toán brute-force ) thì thuật toán này tỏ ra cực hữu dụng và cho tốc độ xử lý rất nhanh. Vậy đối với những bài toán lớn hơn như so khớp gen trong ngành tin sinh học, hay tìm kiếm nhanh thông tin, keyword, hoặc các bài toán so khớp chuỗi để tìm ra những đoạn chương trình virus, mã độc, … Ta cần những thuật toán tối ưu hơn, cho Preprocessing time, matching time, space tốt hơn. Ta có thể áp dụng rất nhiều thuật toán như Rabin-Karp, KMP, Boyer-moore, Naive String … Rabin sẽ cho space xử lý là O(1), KMP thì cho matching time là O(n), Boyer-moore trong trường hợp tốt nhất matching-time sẽ là O(n/m). Naive String còn thậm chí không tiêu tốn bộ nhớ và thời gian xử lý, và còn rất nhiều các thuật toán khác. Trong chủ đề lần này mình sẽ đề cập đến thuật toán KMP ( Knuth-Morris-Pratt)

Pattern-Searching-2.png

Bài toán

Đầu tiên ta đặt ra bài toán. Cho một chuỗi lớn có M kí tự và một chuỗi con có N kí tự. Hãy kiểm tra xem chuỗi lớn có chứa chuỗi con không, và bắt đầu xuất hiện chuỗi con ở vị trí nào. Ví dụ chuỗi lớn y = { A A B A A C A A D A A B A A B A } và chuỗi con x = {A A B A}

Ta bắt đầu với thuật toán indexOf trước nhé.

/**
 * Code shared by String and StringBuffer to do searches. The
 * source is the character array being searched, and the target
 * is the string being searched for.
 *
 * @param   source       the characters being searched.
 * @param   sourceOffset offset of the source string.
 * @param   sourceCount  count of the source string.
 * @param   target       the characters being searched for.
 * @param   targetOffset offset of the target string.
 * @param   targetCount  count of the target string.
 * @param   fromIndex    the index to begin searching from.
 */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    if (targetCount == 0) {
        return fromIndex;
    }

    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);

    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        /* Look for first character. */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        /* Found first character, now look at the rest of v2 */
        if (i <= max) {
            int j = i + 1;
            int end = j + targetCount - 1;
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);

            if (j == end) {
                /* Found whole string. */
                return i - sourceOffset;
            }
        }
    }
    return -1;
}

Thuật toán không sử dụng String, mà sử dụng char để tăng performance, tránh việc xử lý trên String, và đồng thời thuật toán tìm kiếm kí tự đầu tiên trong chuỗi lớn khớp với kí tự đầu tiên trong chuỗi con, giá trị max được tính thông qua vị trí tìm kiếm đầu tiên, và độ dài chuỗi so khớp được giảm bớt vì giả sử tại vị trí j tới M mà nhỏ hơn N thì việc có so khớp tiếp cũng là thừa. Mỗi khi việc so khớp đang sai tại vị trí k nào đó. Ví dụ, tại vị trí j = 4, y[j] = B vị trí so khớp đáng sai. và ta phải nhích chuỗi x lên 1 đơn vị để tiếp tục so khớp lại từ đầu. Mỗi lần dịch chuyển như vậy ta gọi là “bước nhảy”, đó là ý tưởng đơn thuần của thuật toán brute-force.

Nhưng đôi khi ta có thể biết được việc so khớp tiếp tục cũng không chắc là đúng đắn, vì ta vừa so khớp, và các vì trí i, i +1…j trong chuỗi P là đúng, tại vị trí j + 1 thì đang sai , ta shift vị trí so chuỗi lên 1 và bắt đầu lại từ i+1, i+2, … , nhưng ta có thể thừa biết vị trí thứ i + 1 sau khi shift, nó cũng không khớp từ trước, việc đó ta hoàn toàn đoán được, nên thay vì ta shift lên 1, ta có thể shift k vị trí. Đó chính là ý tưởng của thuật toán KMP.

Thuật toán

Thuật toán này được thiết kế một cách chặt chẽ hơn so với thuật toán Morris-Pratt. Ta có thể xem xét tại một vị trí j một chuỗi lớn y[j .. j+m-1]. Và giả sử tại vị trí i với 0 < i < m, việc so với bị sai đối với x[i] và y[j + i], và tất nhiên trước đó x[0 .. i -1] = y[j .. j+i-1] = u nhưng a = x[i] ≠ y[i + j] = b. Và khi ta dịch chuyển, ta mong muốn rằng tiền tố v của mẫu sau khi dịch chuyển phải khớp được phần nào so với hậu tố u trước khi dịch chuyển.

Screen Shot 2018-04-06 at 1.38.32 PM

Và tất nhiên là tại vị trí mới i – k của mẫu phải cho giá trị c khác so với  đoạn mẫu lúc chưa dịch chuyển  (k là số bước dịch chuyển), hay nói đúng hơn c phải khác a. Vì vậy thay vì việc sử dụng hai vòng lặp để so khớp chuỗi, ta sẽ thực hiện việc tính toán số bước nhảy trên từng vị trí của chuỗi con, để nếu tại vị trí i nào đó sai khác, ta sẽ dịch chuyển chuỗi mẫu so với bao nhiêu đơn vị, mà không phải là 1 như đối với thuật toán brute-force.

Gọi kmpNext[i] là độ dài nhất có thể của đoạn tiền tố v, được tính toán bắt đầu từ giá trị c với x[0 .. i-1], nếu đoạn đó không tồn tại ta coi là -1, với 0 < i ≤ m., và sau mỗi lẫn dịch chuyển, t sẽ tiếp tục so khớp giá trị x[kmpNext[i]] với y[i + j], với kmpNext[0] = -1.

Ví dụ:

Screen Shot 2018-04-06 at 1.57.53 PM

Source code:

public static void main(String[] args) {
    char[] x = "GCAGAGAG".toCharArray();
    char[] y = "GCATCGCAGAGAGTATACAGTACGGCAGAGAG".toCharArray();

    int[] kmpNext = new int[x.length + 1];
    preKmp(x, x.length - 1, kmpNext);

    int i, j;
    i = j = 0;
    while (j < y.length - 1) {         while (i > -1 && x[i] != y[j]) i = kmpNext[i];
        i++;
        j++;
        if (i >= x.length - 1) {
            System.out.println("position: " + (j - i));
            i = kmpNext[i];
        }
    }
}

public static void preKmp(char[] x, int m, int[] kmpNext) {
    int i, j;

    i = 0;
    j = kmpNext[0] = -1;
    while (i < m) {         while (j > -1 && x[i] != x[j])
            j = kmpNext[j];
        i++;
        j++;
        if (x[i] == x[j])
            kmpNext[i] = kmpNext[j];
        else
            kmpNext[i] = j;
    }
}

Tài liệu tham khảo

https://en.wikipedia.org/wiki/String_searching_algorithm

Handbook of Exact String-Matching Algorithms _ Christian Charras, Thiery Lectoq

Các thuật toán Sinh

Mở đầu

Hôm nay mình sẽ viết về những thuật toán sinh cơ bản, đó là những thuật toán khá quen thuộc đối với những sinh viên khi bắt đầu làm quen với lập trình. Tại sao lại là thuật toán mà không phải là những thuật toán cơ bản khác như pattern matching, sort, … Bởi vì, đó là thuật toán mình vấp phải nhiều nhất trong công việc hay những lúc code những thứ linh tinh.

Bài toán

Bài toán đặt ra như sau: Mình hay chơi trò xì tố 5 cây với bạn bè ( Mỗi người có 5 quân bài, hãy chọn ra 3 quân sao cho tổng của chúng chia hết cho 10, nếu không có thì mặc định thua luôn, và một trong hai quân còn lại sẽ được sắp xếp sao cho tổng lớn nhất có thể, và một trong hai quân sẽ là quân tẩy) => Nếu như mình muốn tạo một con bot có thể đánh bài với mình, rõ ràng phải phổ biến luật chơi cho nó =)), tức là nó phải biết cách làm thế nào để chọn được 3 quân có tổng chia hết cho 10, nhưng 2 quân còn lại phải có tổng cao nhất có thể ( lấy tổng chia hết cho 10, nên điểm có thể nằm trong khoảng từ 1 -> 10). Dĩ nhiên có nhiều thuật toán có thể giải quyết trò đó, nhưng sao ta không nghĩ đơn giản rằng, ta hãy liệt kê những trường hợp nhiều nhất có thể xảy ra, rồi lấy cách sắp xếp tốt nhất với N = 5, K = 3. Vậy số trường hợp có thể là “tổ hợp chập 3 của 5” (không nhiều lắm). Các bài toán liên quan đến xác suất, tổ hợp, chỉnh hợp, hoán vị … là những bài toán rất quan trọng trong ngành CNTT của mình, nên biết càng nhiều càng tốt. Do đó mình sẽ đi vào 3 thuật toán cụ thể như sau:

Sinh nhị phân

Đây là bài toán đầu tiên mình nhắc đến vì nó đơn giản nhất, giả sử mình có một số N cho trước, ví dụ N = 4 thì mình phải liệt kê các cấu hình gồm 3 chữ số có thể như:

0   0   0   0

0   0   0   1

0   0   1   0

……………

1   1   1   1

Nhưng đừng nhầm lẫn với việc ta đang coi việc sinh ra những chuỗi như vậy là mục đích cuối cùng của bài toán, nếu vậy ta chỉ cần dùng các phương pháp chia lấy phần dư như cách đổi các số hệ thập phân sang hệ nhị phân và cho vòng lặp chạy từ 0 đến 15 với N = 4, và từ 0 đến 32 với N = 5. Nhưng ta không làm như vậy, ta cần có một phương pháp nào đó để tìm ra quy luật đó hay ho hơn. Bản chất việc sinh ra chuỗi như vậy, để ta coi việc khi xuất hiện mỗi tổ hợp với 0 là “ẩn” và 1 là “hiện”. Từ đó ta có thể giải quyết được rất nhiều bài toán khác nhau từ mỗi tổ hợp như vậy.

xau-nhi-phan

Thuật toán : Cho một mảng n kí tự 0. Ta sẽ duyệt theo chiều ngược từ n – 1 về tới 0, biến tất cả các số 1 thành 0 rồi giảm tiếp, nhưng nếu gặp số 0 thì biến thành 1 và kết thúc lặp. Đến khi cả mảng chỉ chứa 1 thì kết thúc thuật toán.

void binaryGen( int B[], int n ){
    i = n;
    while (i > 0 && b[i] == 1) {
        b[i] = 0;
        i--;
    }
    if(i == 0) return;
    else b[i] = 1;
}

Sinh tổ hợp

Tiếp theo là thuật toán sinh tổ hợp. Bài toán này giúp ta liệt kê được tất cả các tổ hợp chập K của N phần tử. Khi liệt kê, ta sẽ ưu tiên hiển thị các phần tử theo tổ hợp đã được sắp xếp theo kiểu từ điển. Ví dụ : 1, 2, 3 … a, b, c …. Ví dụ: với bài toán liệt kê tất cả các phần tử gồm 4 phần tử trong tổ hợp 6 phần tử với các item được đánh thứ tự từ 1 đến 6.

1   2   3   4   

1   2   3   5

…………….

3   4   5   6

Có thể thấy quy tắc rất đơn giản, ở một ví trí thứ j bất kì khi một tổ hợp mới được chọn ra, nếu j = N – K + j thì ở vị trí j đó, ở vị trí đó giá trị đã đúng với tổ hợp cuối cùng. Ví dụ ở vị trí thứ 4 thì giá trị đó phải là 6 – 4 + 4 = 6. CỨ nhua vậy tổ hợp cuối cùng phải là 3,4,5,6 đúng với ví dụ trên. Nếu có vị trí nào đang chứa giá trị không đúng, thì ta sẽ ngừng duyệt và tăng các giá trị đang sai đó lên 1. Sau đó thay đổi các giá trị đằng sau theo giá trị vừa được thay đổi theo thứ tự từ điển, sao cho giá trị đó không được quá N.

Thuật toán: Cho một mảng gồm N phần tử và một giá trị K cho trước. Đầu tiên ta vẫn duyệt theo chiều ngược, nếu tại mỗi vị trí j có giá trị khác với N – K + j thì ta dừng lặp, giá trị aj = aj + 1. Và các giá trị đằng sau sẽ được tính từ giá trị aj đã được update, tăng dần theo thứ tự từ điển

void combinationGen( int B[], int K ){
    int i = K;
    while (B[i] == N - K + i) i--;
    B[i]++;
    for(j = i + 1; j <= N; j++) B[j] = B[i] + j - i; 
}

Sinh hoán vị

Cuối cùng là thuật toán sinh hoán vị, bài toán này nhìn thì có vẻ không khác mấy với thuật toán sinh tổ hợp, nhưng thuật toán thì lại khác hoàn toàn. Giả sử ta có N phần tử và cũng đang được sắp xếp theo thứ tự từ điển, và ta phải liệt kê tất cả các cấu hình được tạo bởi từ N phần tử đó. Ví dụ với bài toán liệt kê tất cả các hoán vị có thể của một mảng gồm 6 phần từ từ 1 đến 6

1   2   3   4   5   6  

1   2   3   4   6   5

……………………

6   5   4   3   2   1

Có thể thấy hoán vị đầu tiên là một chuỗi các số tăng dần, nhưng hoán vị cuối cùng lại là một chuỗi số giảm dần, vâỵ ta phải áp dụng một thuật toán để có thể hoán vị các vị trí trong mảng để có thể sinh ra chuỗi số thoả mãn hoàn vị cuối cùng.

Thuật toán: Với một mảng gồm N phần tử, và tất nhiên các phần tử đang sắp xếp theo thứ tự từ điển tăng dần. Đầu tiên ta duyệt từ trái qua phải nếu gặp phần tử nào ở vị trí j mà nhỏ hơn vị trí j + 1 thì ta dừng lặp (vì theo lý thuyết, hoán vị cuối cùng phải là một chuỗi số giảm dần). Sau đó ta lại tìm từ vị trí j + 1 tới N để tìm được giá trị ở vị trí k nào đó sao cho giá trị đó nhỏ nhất. Sau đó ta sẽ hoán đổi hai giá trị ở vị trí k và j cho nhau. Cuối cùng từ vị trí j đó tới N, ta đảo ngược vị trí các phần tử trong với nhau.

void permutationGen( int B[]){
    int j,k,r,s,t
    j = N;
    while (B[j] > B[j + 1]) j--;
    k = N;
    while (B[j] > B[k) k--;
    t = B[j]; B[j] = B[k]; B[K] = t;
    r = j + 1; s = N; 
    while(r < s){
        t = r; r = s; s = t;
    }
}

Kết luận

Mặc dù đây là những bài toán cơ bản, nhưng tính ứng dụng lại cực kì phổ biến với nhiều loại bài toán khác nhau. Đối với những bài toán xác suất thống kê, tìm các cấu hình, hoán vị, tổ hợp, chỉnh hợp, từ ba bài toán trên ta có thể tuỳ biến và sử dụng được để góp phần xử lý cho những bài toán lớn và phức tạp hơn.