Lập trình

Lập trình

Thứ Bảy, 21 tháng 1, 2017

[Machine learning] K-means, giới thiệu về bài toán phân cụm

K-means

I. Tư tưởng
- Xét bài toán cho :
    + Một số K (number of cluster)
    + Tập data (X)
- Thuật toán K-means sẽ phân loại cho ta K cụm data, với mỗi một cụm sẽ có tâm (centroid) của nó.
- Ứng dụng : Phân loại đối tượng trong market, phân loại người dùng trong social network, ...

II. Thuật toán
- Input : K và tập data X
- Ta chọn random một tập K centroids (tức tâm của các cụm)
- Thuật toán gồm 2 bước chính :
+ findClosetCentroids : tạo một mảng ci có độ dài bằng số example trong tập data. ci chứa "nhãn" (số thứ tự từ 1..K) là centroid là example thứ i gần nhất. Công thức để xét xem tâm nào gần 1 example nhất là :
sum(power(example - centroids(1, :), 2)) (ở Octave/Matlab) // Với centroids là tập các centroid (tâm) của các cụm (cluster);example là 1example của tập data

+ ComputeCentroids : Tính lại tâm (move centroids) bằng cách : mỗi tâm (centroid) được tính lại bằng cách là trung bình cộng của tập data hiện tại trong cụm của nó.

III. Tối ưu
- Mục tiêu tối ưu của ta là hàm :
    J = (1 / m) * sum( sum(power(example - centroids(1, :), 2)) ) (code in Octave)
- 2 bước của thuật toán K-means sẽ minimize hàm trên.

IV. Randomly Initialize   
- Thuật toán K-means đặc biệt liên quan đến việc chọn cụm (cluster), vì vậy việc khởi tạo giá trị cho các cụm rất quan trọng, thông thường ta chọn K giá trị cho cụm nằm trong tập data m phần tử (k <= m). Nhưng việc khởi tạo như vậy rất nhiều rủi ro vì các cụm có thể hội tụ không như mong muốn. Như vậy ta có một cách để chọn được một cụm tối ưu, liên quan đến hàm mục tiêu (như đã trình bày ở mục III.)
- Mã giả :
   
    for i = 1 to 100  : // ta có thể thay 100 là 200, …
        Chọn K cluster có giá trị là K phần tử được lấy ngẫu nhiên trong tập data set
        Chạy K-means :
            + FindClosetCentroids
            + ComputeCentroids
        Tính hàm mục tiêu J
    Chọn cụm nào có hàm mục tiêu J nhỏ nhất trong các cụm đã tính ở trên .

- Trong octave có thể dùng lệnh sau để pick randomly K centroids từ tập data det X :
randidx = randperm(size(X, 1));
centroids = X(randidx(1:K), :);


V. Ứng dụng

Ví dụ : khi ta có một sites có 100000 thánh viên ta phân thành 10 cụm (thành viên tích cực, tương đối tích cực, ....) sau đó website sẽ có chế độ để "đối đãi " với từng cụm thành viên.
Hoặc ta có thể dùng K-means để nén ảnh: Khi ta có ảnh 3 channel : 128 * 128 khi đó ta đưa ảnh về 2 chiều : A * 3 với A = 128 * 128. Khi đó giả sử ta có 16 cụm 3 features, ta phân các pixels này vào các cụm, sau đó chuyển hết giá trị cả pixel trong cụm về giá trị của centroid của cụm đó.

Thứ Bảy, 29 tháng 10, 2016

[OOP] Những chú ý về OOP trong Java (updating)

- Khi ta tạo một hàm cùng tên với class (ý muốn tạo hàm constructor ) nhưng lại có kiểu trả về : void, int, double, ... Thì hàm đó không phải là một constructor mà nó là method bình thường, có thể gọi được. Vì constructor là một method đặc biệt không có kiểu trả về.

- Trong hàm khởi tạo của base class gọi một method public (derive class có thể inheritant được) thì hàm được gọi đó vẫn ở subclass . 2 hàm cùng tên nhưng private ở baseclass và super class là 2 hàm khác nhau không phải override của nhau

- Khi create 1 instance của class (blueprint) thì nó khởi tạo root (Object -> ... ) của cây thừa kế xong mới thừa kế dần đến nó. (Nhắc lại là Object khác với Instance, hiểu đơn giản là Instance là thực thể đã nằm trong ô nhớ, hệ điều hành đã cấp phát và đang quản lý nó, còn object bao gồm cả instance và nhưng đối tượng sẽ được tạo ra).

- Khi tạo một mảng n phần tử, java sẽ tạo ra n tham chiều có kiểu là kiểu của từng phần tử, ban đâu tất cả các tham chiều đó trỏ đền null, muốn những tham chiều này trỏ đến đối tượng cần thêm đoạn:
p[n] = new TypeElement();

[Casting]
+ Muốn down casting (from superclass to sub class) trong tham đầu vào của hàm constructor thì cần ép kiểu explicit : (Employee)ob (ob là object của Person) ta muốn tham số truyền vào kiểu Employee
+ int i = (int)12.5f; là chuyển kiểu hẹp (narrow casting). Nếu không có toán tử casting sẽ dẫn đến lỗi

Đoạn code này :
int big = 1234567890;
float approx = big;
System.out.println(big - (int)approx);

Có kết quả là -46, lý do là vì kiểu float không biểu diễn đến 9 chữ số có nghĩa.

[Abstract class and Interface]
- Đôi khi ta muốn tạo 1 class tổng thể để phục vụ cho thừa kế để giảm số lần viết mã, và đễ bảo trì; và phục vụ cho đa hình để xây dựng một cách tổng quát và chỉ cho lớp con sử dụng những method được đánh dấu ở lớp cha dùng chung cho tất cả lớp con. Ví dụ Animal là lớp cha cho tất cả MÈo, Chó, Ngan. Ta muốn lập trình viên chỉ tạo đối tượng cho các lớp con ít trừu tượng hơn là Chó , Ngan, Mèo không muốn cho lớp Animal vì ta không biết 1 con Animal chung chung nó thế nào => không được tạo đối tượng cho Animal => Abstract class.

+ Các lớp cụ thể (concrete) là các lớp có đủ đặc trưng để có thể tạo một đối tượng, khác với abstract class nó quá trừu tượng để create một object

+ Các phương thức trừu tượng phải được cài đè ở lớp con. Các phương thức trừu tượng trong các lớp trừu tượng không có nội dung, nó chỉ phục vụ mục đích đa hình. Điều đó có nghĩa là các lớp cụ thể đầu tiên nằm bên dưới nó trên cây phả hệ bắt buộc phải cài đặt tất cả các phương thức trừu tượng; các lớp con trừu tượng có thể bỏ qua việc này

+ Trong một abstract class có thể có các phương thức abstract hoặc cũng có thể có các phương thức đã triển khai, các phương thức đã triển khai này khi được gọi sẽ gọi các phương thức của đối tượng gọi nó. Điều này cho thấy một sức mạnh của đa hình: dùng lớp con tổng quát như lớp cha nhưng xử lý method lại là đặc trưng của lớp con. Ví dụ: Lớp abstract Shape (dễ thấy Shape quá trừu tượng, ta không thể tưởng tượng một đối tượng kiểu Shape như thế nào, không đặc trưng nên ta cho nó là abstract class) có 2 abstract method là draw() và erase() (các lớp thừa kế lớp Shape như Circle, Rectange sẽ draw() và erase() theo kiểu riêng của một class cụ thể nên ta để abstract) và một method nữa là moveTo() (đây là phương thức được triển khai cụ thế với 3 bước erase() -> thay đổi tọa độ -> draw(). Dễ thấy với mọi object thuộc class thừa kế lại Shape đều được moveTo với 3 bước chung như trên. Nhưng tại mỗi đối tượng thuộc 1 kiểu khác nhau sẽ xử lý nó theo phong cách đặc trưng của nó : erase() và draw() theo các của nó). Ví dụ này minh họa cho một mẫu thiết kế là template method.

Bài viết vẫn đang tiếp tục được update .

Thứ Ba, 20 tháng 9, 2016

[Machine learning] Điểm yếu của sigmoid function khi làm activation trong mạng Neural Networks.

    Sigmoid function là một hàm rất nổi tiếng trong machine learning, nó như là một function hợp lý hóa đầu ra của model để các giá trị của output chỉ nằm trong (0, 1). Đây là dạng của hàm sigmoid :
                           
Như ta thấy, giả sử hàm g(z) là sigmoid của biến z, vậy lim g -> 1 khi z -> +∞ ; lim g -> 0 khi z -> -
Mặt khác g(0) = 0.5, đây là một ngưỡng (threshold) rất hợp lý khi ta làm bài toán phân lớp (classifier). Cụ thể là nếu g(z) >= 0.5 thì ouput h là positive class, ngược lại sẽ là negative class. Hơn nữa, hàm sigmoid có tính đồng biến và g(0) = 0.5 vậy ta chỉ cần so sánh z = Theta' * X ( chính là weight nhân với input) với 0: Nếu z >=0, ta được positive class, ngược lại ta được negative class. Vậy đường thẳng Theta' * X sẽ là một đường phân định 2 class positive (1) và negative (0), nó còn gọi là decision boundary.

Ta cũng thấy hàm này được dùng rất nhiều trong Neural Networks (NNs), giá sử ta có một mô hình như sau :
                                               
Model trên có 3 layer : input layer có 3 neurons, hidden layer có 4 neurons, ouput layer có 2 neurons . Giả sử input "nối với" hidden qua bộ weight W1, hidden với ouput qua bộ W2, hàm activation dĩ nhiên vẫn là sigmoid.
      Chúng ta đã biến thuật toán backpropagation, chú ý rằng, các đạo hàm riêng của J theo các Theta đều liên quan đến đạo hàm của hàm sigmoid :  
                                  
Công thức của dJ / dTheta(l)(i, j) = delta (l + 1) i * a (l) j
Do các giá trị của Theta tương đương nhau sau khi khởi tạo (kernel Gaussion)  nên ta xét delta và a để xem nếu dùng sigmoid thì các delta có "cân bằng" nhau không.
Ta xét đố thị của hàm số là đạo hàm của hàm sigmoid :
                                  
Ta thấy khi z dẫn đến vô cực thì giá trị sẽ dẫn đến 0, z nằm ở lân cận 0 thì giá trị > 0. Vậy với model ở trên ta thấy đạo hàm riêng của cost function với W1  khác nhiều so với đạo hàm riêng của cost function J với W2, cụ thể là với W1 và W2 được random theo kernel của Gaussion thì do z1 khác z2 khác nhau nên g'(a1) khác g'(a2), a1 chính là input X còn a2 là giá trị của các neurons ở hidden layer dễ thấy a2 nằm trong khoảng (0, 1) còn a1 thì không như vậy g'(a1) > g'(a2). (Nhưng thấy nếu input X đầu vào có các giá trị 0, 1 thì lại hợp lý). Vấn đề trên gọi là các đạo hàm riêng của cost function theo các weight "không cân bằng" nhau. Như vậy khi chạy gradient với tham số learning rate :

+ Với learning rate lớn, điều này có thể phù hợp với đạo hàm riêng của J với W2 vì nó nhỏ nên lượng giảm của biển vì thể sẽ không lớn, nên chạy gradient có thể gặp global minimum một cách nhanh chóng, nhưng đối với đạo hàm riêng của J với W1, vì nó rất lớn nhân với learning rate lớn nên độ giảm của Theta lớn, vì vậy có thể không gặp global minimum hoặc chạy rất lâu mới gặp 
                               
+ Với learning rate nhỏ, phù hợp với W1 vì đạo hàm riêng của J với W1 lớn nhân với learning rate nhỏ ta được độ giảm cho weight hợp lý nên khả năng cao là gặp global minimum, ngược lại vì đạo hàm riêng của J với W2 nhỏ nên độ giảm của weight quá nhỏ, nên khi chạy gradient rất lâu 
                                 
Như vậy ta cần một hàm có đạo hàm "cân bằng" nhau hơn để khi chạy gradient descent một cách hợp lý. Đó là hàm ReLU (rectified linear unit)
               
Đồ thị đạo hàm của nó :
                                      


Thứ Bảy, 26 tháng 3, 2016

[Viết game Pacman] Game pacman bằng C++ Tut 2 – Xây dựng map

  

  Ở bài lần trước ta đã nêu ý là coi màn hình là một mảng 2 chiều, nên ta đã tạo class xoay quang đối tượng matrix đó.

Trước hết ta nhìn code lại code của file header:

class Matrix
{
private:
       int matrix[XMAX + 3][YMAX + 3];
       ToaDo pacman;
       computer m_com1, m_com2, m_com3, m_com4;
public:
       Matrix();
       ~Matrix();
       void drawMatrix();
       void updateMatrix();
       void creatMap();
       void completeMap();
       void controlPacman();
       void drawScore();
       void checkWin();
       inline void checkLost();
       void veLive();

       // Computer
       void initComputer();
       void moveComputer1();
       void moveComputer2();
       void moveComputer3();
       void moveComputer4();

       void moveComputers();
       void restoreCell(int x, int y);
};

I, Trước hết ta làm một vài thao tác trong hàm khởi tạo gồm:
 + Sử dụng hàm resizeConsole(int, int) trong thư viện GameLib.h mà ta đã tạo ở tut 1.

       resizeConsole(1000, 800);

 + Cài các giá trị mặc định cho các phần tử trong mảng 2 chiều là SPACE (0) – tức là lúc mới vào, mọi điểm trên map đều là dấu châm mà pacman có thể ăn để tăng điểm.

       for (int i = 0; i <= XMAX; i++){
              for (int j = 0; j <= YMAX; j++){
                     matrix[i][j] = SPACE;
              }
       }

+ Dĩ nhiên ta tạo tường (WALL ) để pacman không đi ra khỏi map:
 Tạo tường thì ta tạo cả trên và dưới:
       for (int i = 0; i <= XMAX; i++){
              matrix[i][YMIN] = matrix[i][YMAX] = WALL;
       }

       for (int i = 0; i <= YMAX; i++){
              matrix[XMIN][i] = matrix[XMAX][i] = WALL;
       }
Như vậy trên mảng biểu diễn màn hình đã có tường.

Bước tiếp theo ta cần thiết lập tọa độ ban đầu của pacman trong mảng, và Score (điểm), mạng sống (live) :

       pacman.x = XMAX - 1;
       pacman.y = YMAX - 1;

       matrix[pacman.x][pacman.y] = 2;
       pacman.Score = 0;
       pacman.live = 3;

Như vậy thật dễ dàng hoàn tất hàm khởi tạo Matrix().

II. Cài đặt hàm drawMatrix()
            Ở trên ta đã cài đặt xong các giá trị của mảng matrix, cái mà nó biểu diễn toàn bộ màn hình chơi. Vậy biểu diễn trên mảng thì ta cũng phải vẽ ra màn hình cái mà mảng đã biểu diễn cho nó chứ.
Vậy ta cùng làm việc trong hàm drawMatrix(), tức là hàm trung chuyển từ mảng ra màn hình.

            Như ta đã lên ý tưởng, mảng matrix biểu diễn cho màn hình các đối tượng sau: dấu “.”, cái này khi PacMan ăn thì sẽ tăng điểm lên; tường (WALL) , pacman và dấu trắng (dấu cách). Như vậy để biểu diễn tường, pacman, màu tường, màu pacman ta cần khai báo các hằng sau:


       const int X0 = 20;
       const int Y0 = 15;
       const char wall = 219;
       const int colorWall = 9;
       const int colorScore = 13;
       const char pacman = 2;
       const char colorPacman = 11;


Ở đâu ta không được nhầm lẫn giữa X0, Y0 ở đây với XMIN và YMIN ở file header. Nó khác nhau ở chỗ: XMIN và YMIN là biểu diễn cột và dòng nhỏ nhất của mảng matrix còn X0 và Y0 biểu thị tung độ và hoành độ nhỏ nhất để biểu diễn các đối tượng ra màn hình chính:
            Ví dụ: Khi pacman có tung độ x, y thì ta gotoxy(XMIN + x, YMIN + y); rồi vẽ đối tượng này.

X0 và Y0 có công dụng duy nhất là làm cho map cân xứng và hợp lý hơn ở trên console.

 Ta khai báo wall = 219 là “chất liệu” xây dựng ra cái tường, khi đến tọa độ của tường ta in cái kí tự có mã ASCII là 219 ra ; colorWall là màu của tường. colorScore = 13 là màu của điểm Score (cái score: XX mà bạn thấy ở hình đầu đó). Pacman = 2 tương tự như wall = 219, pacman này dùng làm “chất liệu” để vẽ Pacman ra màn hình, colorPacman là màu mà ta muốn biểu trị pacman.

            Như vậy ở đây ta phải dùng hàm gotoxy(int x, int y) và textcolor(int mau) đưa con trỏ đên vị trí (x, y)  và thay đổi màu vẽ thành màu có số hiệu mau. Hai hàm trên ta đã khai báo và cài đặt ở thư viện GameLib.h, như vậy khi cài đặt các hàm trong file Matrix.cpp ta cần include file GameLib.h vào.

            Ok, giờ là bước quan trọng nhất, ta vẽ mảng matrix ra màn hình:


       for (int i = XMIN; i <= XMAX; i++){
              for (int j = YMIN; j <= YMAX; j++){

                     gotoxy(i + X0, j + Y0);

                     if (matrix[i][j] == SPACE){
                           textcolor(colorScore);
                           std::cout << ".";
                     }

                     if (matrix[i][j] == 1){
                           textcolor(colorWall);
                           std::cout << wall;
                     }

                     if (matrix[i][j] == 2){
                           textcolor(colorPacman);
                           std::cout << pacman;
                     }
                     if (matrix[i][j] == -1){
                           std::cout << " ";
                     }
              }
       }
            Như thông lệ, ta cần 2 vòng for để truy xuất hết các giá trị phần tử của matrix.  Các giá trị SPACE (0), 1, 2, -1 trong mảng tượng trưng cho dấu ‘.’ ; tường; pacman; và dấu cách trên màn hình.

III, Tạo map với creatMap()
            Nếu để map như đã cài đặt ban đầu trong hàm khởi tạo thì không có gì là thú vị cả, ta cần map có nhiều tường hơn. Muốn như vậy thật dễ dàng, ta chỉ cần thêm vào trong mảng matrix là sau đó sử dụng drawMatrix() là đã có một map đẹp theo ý muốn.

      
       for (int i = YMIN + 5; i <= YMIN + 17; i++){
              matrix[5][i] = 1;
              matrix[10][i] = 1;
              matrix[15][i] = 1;
              matrix[20][i] = 1;
              matrix[25][i] = 1;
       }

       for (int i = XMIN + 5; i <= XMIN + 25; i++){
              matrix[i][YMAX - 10] = matrix[i][YMAX - 7] = matrix[i][YMAX - 3] = 1;
       }
}

Với các giá trị đầu của i và j bạn có thể thay đổi theo ý của các bạn để được một map theo ý của các bạn.

Vậy đã xong creatMap(), giờ ta chỉ cần in nó ra màn hình là xong. Để cho gọn ta dùng thêm hàm completeMap() gồm:

void Matrix::completeMap(){
       creatMap();
       drawMatrix();
}

            Để tạo map và vẽ map luôn.
Như vậy việc tạo map đã xong, tiếp theo ta cần làm là điều khiển Pacman. Hẹn gặp các bạn ở tut sau nhé. Cảm ơn các bạn đã theo dõi.