1. Classification
1.1. Tổng quát:
1.1.1. sử dụng mô hình để học cấu trúc của tập dữ liệu mẫu đã được chia ra thành nhiều cụm, liên quan đến các biến phân loại hoặc các lớp
1.1.2. Cho 1 tập chứa những điểm dữ liệu dùng cho training mà ở đó chúng có liên kết với các nhãn lớp, xác định nhãn lớp của 1 hoặc nhiều trường hợp test chưa từng thấy trước đó
1.1.2.1. 2 giai đoạn:
1.1.2.1.1. 1. Giai đoạn trainning: Mô hình training được xây dựng từ những trường hợp training. Mô hình toán học tóm tắt của các nhóm được gắn nhãn trong tập train
1.1.2.1.2. 2. Giai đoạn test: mô hình train được dùng để xác định nhãn lớp của 1 hay nhiều trg hợp chưa thấy
1.2. Ứng dụng:
1.2.1. Mục tiêu khách hàng Marketing
1.2.2. Quản lý bệnh y tế
1.2.3. Lọc và Phân loại tài liệu
1.2.4. Phân tích dữ liệu đa chiều
1.3. Lựa chọn đặc trưng
1.3.1. Filter models:
1.3.1.1. lọc các đặc trưng không liên quan
1.3.2. Wrapper models:
1.3.2.1. Dùng mô hình phân loại như 1 hộp đen và đánh giá các tập hợp thuộc tính khác nhau dựa trên hiệu suất
1.3.3. Embedded models:
1.3.3.1. Giải pháp cho mô hình phân loại chứa các gợi ý hữu ích về các tính năng phù hợp nhất
1.4. Decision tree:
1.4.1. Khái niệm:
1.4.1.1. Nút nội: -> nút đầu tiên: là gốc tương ứng với không gian đầu vào của đặc trưng -> nút tiếp theo: là các đặc trưng dùng để phân chia dữ liệu dựa theo tiêu chí tách
1.4.1.2. Nút lá: là nút đại diện cho nhãn cuối cùng của cây
1.4.2. Thuật toán:
1.4.2.1. 1. Khởi tạo nút gốc: bắt đầu với toàn bộ dữ liệu và không gian của các thuộc tính hiện có
1.4.2.2. 2. Chọn tiêu chí tách: - Entropy: đo lường mức độ hỗn loạn trong dữ liệu - Information Gain: đo lường mức giảm Entropy sau khi chia dữ liệu theo 1 ttinh cụ thể cao nhất để tách Phù hợp: phân loại + nhị phân - Gini: đo lường xác suất mà 1 mẫu được chọn ngẫu nhiên sẽ bị phân loại sai nếu nó đc gán ngẫu nhiên theo phân phối các nhãn Phù hợp: liên tục + phân loại + nhị phân
1.4.2.3. 3. Chọn thuộc tính tốt nhất để tách: Tính toán cho tất cả ttinh và chọn ttinh có giá trị Entropy giảm cao nhất hoặc Gini Impurity lớn nhất
1.4.2.4. 4. Phân tách dữ liệu Chia dữ liệu theo ttinh được chọn
1.4.2.5. 5. Đệ quy tạo các nút con: Lặp lại 2,3,4 cho từng cặp con được tạo ra. Mỗi tập con thành tập nút gốc cho quá trình đệ quy Điều kiện dừng: -> tất cả điểm dữ liệu trong 1 tập thuộc 1 nhãn -> không còn thuộc tính để tách
1.4.2.6. 6. Gán nhãn cho các nút lá: Nút cuối cùng sẽ được gán nhãn dựa trên lớp phổ biến nhất trong tập con tại nút đó
1.4.3. Thuật toán:
1.4.3.1. Algorithm GenericDecisionTree(Tập dữ liệu: D) begin Tạo nút gốc chứa D; repeat Chọn một nút đủ điều kiện trong cây; Chia tách nút được chọn thành hai hoặc nhiều nút dựa trên tiêu chí chia tách đã được định nghĩa trước; until không còn nút nào đủ điều kiện để chia tách; Cắt tỉa các nút quá khớp từ cây; Gán nhãn cho mỗi nút lá với lớp chiếm ưu thế tại nút đó; end
1.5. SVM
1.5.1. Khái niệm
1.5.1.1. Sử dụng các siêu phẳng phân tách làm ranh giới quyết định giữa 2 lớp
1.5.1.2. Siêu phẳng lề tối đa:
1.5.1.2.1. là siêu phẳng phân tách rõ ràng 2 lớp và trong đó tồn tại 1 vùng lớp ở mỗi bên của đường biên
1.5.1.3. Mục tiêu:
1.5.1.3.1. Tìm mặt phẳng siêu phân tách để chia các lớp dữ liệu với khoảng cách lớn nhát
1.5.2. Hard Margin:
1.5.2.1. Không cho các điểm dữ liệu nằm chồng chéo lên nhau, các dữ liệu phải nằm ngoài hoặc trên biên của mặt phẳng phân cách
1.5.2.2. Vấn đề:
1.5.2.2.1. Nhạy cảm với nhiễu và ngoại lai
1.5.2.2.2. không xử lý được các dữ liệu mà không hoàn toàn tuyến tính
1.5.3. Soft Margin:
1.5.3.1. Cho phép 1 số dữ liệu nằm trong biên bằng các thêm 1 siêu tham số điều chỉnh C để kiểm soát độ cho phép của các điểm dữ liệu vi phạm
1.5.3.2. Vấn đề:
1.5.3.2.1. Phức tạp
1.5.4. Thuật toán:
1.5.4.1. 1.Chuẩn bị dữ liệu
1.5.4.2. 2. Chọn kernel:
1.5.4.2.1. Linear: dùng cho dữ liệu tuyến tính
1.5.4.2.2. Polynominal: dữ liệu có quan hệ đa thức
1.5.4.2.3. Radial basis funtion: dữ liệu phi tuyến tính
1.5.4.2.4. Sigmoid:
1.5.4.3. 3. Xây dựng và huấn luyện mô hình SVM
1.5.4.3.1. Thiết lập các siêu tham số
1.5.4.3.2. Tối ưu hóa mục tiêu:
2. Ngoại lai
2.1. Định nghĩa:
2.1.1. Là điểm dữ liệu rất khác biệt với phần lớn các điểm dữ liệu còn lại
2.1.2. Trong trường hợp gom nhóm:
2.1.2.1. điểm dữ liệu riêng lẻ khác biệt với các điểm còn lại trong nhóm
2.2. Các mô hình phát hiện ngoại lai:
2.2.1. Ứng dụng:
2.2.1.1. làm sạch dữ liệu
2.2.1.2. phát hiện gian lận thẻ tín dụng
2.2.1.3. phát hiện xâm nhập mạng
2.2.2. Output:
2.2.2.1. Điểm giá trị thực
2.2.2.2. nhãn nhị phân
2.2.3. Mô hình xác suất
2.2.3.1. Dựa trên sự tổng quát hóa của các phương pháp phân tích giá trị cực hạn đa biến
2.2.3.2. Gaussian mixture với các mixture đơn:
2.2.3.2.1. Phân tích giá trị cực hạn đa biến theo Mahalanobis
2.2.3.2.2. Tổng quát hóa mô hình này với nhiều thành phần mixture, ta có thể xác định ngoại lai
2.2.4. Pruning:
2.2.4.1. Lấy mẫu
2.2.4.2. Kĩ thuật kết thúc sớm với các vòng lặp chồng nhau
2.2.5. Local Outlier Factor
2.2.5.1. điều chỉnh các thay đổi cục bộ về mật độ cụm bằng cách chuẩn hóa khoản cách cụ thể theo điểm trung bình trong 1 cục bộ dữ liệu
3. Các thuật toán phân cụm:
3.1. K-Means
3.1.1. Hàm mục tiêu: Euclidean = sqrt( sum_{i=1}^n (x_i - y_i)^2)
3.1.2. Begin: 1. Chọn K điểm bất kỳ làm tâm cụm ban đầu Lặp lại cho đến khi các cụm không thay đổi: Phân mỗi điểm dữ liệu vào cụm có dist từ nó đến tâm là gần nhất Cập nhật tâm cụm mới bằng cách lấy trung bình cộng của tất cả điểm dữ liệu của cụm đã được gán end return K tâm cụm và phân bố của các điểm dữ liệu
3.2. Bottom up
3.2.1. Dữ liệu D; tiêu chuẩn liên kết N Begin: Khởi tạo ma trận khoảng cách nxn M từ D; repeat: Chọn cặp cụm i và j gần nhất trong M theo tiêu chuẩn N; Kết hợp 2 cụm lại thành 1 cụm; Xóa hàng và cột của i và j để tạo 1 hàng mới, cột mới cho cụm ij; Cập nhật M bằng cách tính lại khoảng cách từ cặp cụm ij đến các cụm còn lại trong ma trận M bằng tiêu chuẩn liên kết N; until các cụm kết hợp lại thành 1 return tập hợp cụm đã được kết hợp từ các cụm trong dữ liệu D end
3.3. Top down
3.3.1. Dataset D; thuật toán phẳng A (k-means, hierarchical clustering,...) Begin: Khởi tạo cây T với nút gốc chứa D repeat: đến khi không còn nút nào có thể phân tách được nữa Chọn 1 nút lá L trong T dựa trên tiêu chí được định nghĩa trước Sử dụng A để chia L thành L_1, ..., L_k Thêm L_1, L_2,..., L_k làm các nút con trong T; end
3.4. Các thuật toán gom cụm phân tầng (Hierarchical Clustering Algorithms): Các thuật toán phân cụm phân cấp tạo ra một cấu trúc cây (dendrogram) biểu diễn sự phân cấp của các cụm.
4. Cách chọn đặc trưng phân cụm
4.1. Filter model
4.1.1. dùng 1 tiêu chí cụ thể để đánh giá mức độ ảnh hưởng của các đặc trưng
4.1.1.1. Term-stength:
4.1.1.1.1. phù hợp các dữ liệu văn bản thưa thớt
4.1.1.1.2. tập trung vào sự hiện diện hay vắng mặt của các thuộc tính
4.1.1.1.3. Cách thức:
4.1.1.1.4. Nếu dùng cho dữ liệu đa chiều thì phân rã các tt định lượng thành giá trị nhị phân rồi sử dụng
4.1.1.2. Sự phụ thuộc thuộc tính dự đoán
4.1.1.2.1. Khi 1 tt liên quan đến các tt khác, thì có thể dùng các tt đó để dự đoán giá trị của tt trên
4.1.1.2.2. Số: dùng mô hình hồi quy
4.1.1.2.3. Không phải số: dùng mô hình phân lớp
4.1.1.3. Entropy
4.1.1.3.1. Nhóm dữ liệu biểu diễn các đặc trưng trên phân phối khoảng cách tương ứng
4.1.1.4. Thống kê Hopkins:
4.1.1.4.1. D : tập dữ liệu cần được đánh giá và phân cụm S: tập mẫu chứa r điểm dữ liệu R: các điểm dl r được chọn từ D alpha_1, alpha_2,...,alpha_n: khoảng cách từ điểm dữ liệu của R đến hàng xóm gần nhất của nó trong D beta_1,...,beta_n: khoảng cách từ điểm dữ liệu của S đến hàng xóm gần nhất của nó trong D => Hopkins H: H = [sum_{i=1}^r (beta_i)] / [sum_{i=1}^r (beta_i + alpha_i) điểm càng gần 1 thì cụm đó có tính phân cụm càng cao
4.2. Wrapper model
4.2.1. dùng 1 mô hình học máy để đánh giá chất lượng từng tập hợp của các đặc trưng
4.2.2. Cách áp dụng:
4.2.2.1. 1. Dùng thuật toán phân cụm trên 1 tập data hiện tại tạo ra các tập con đặc trưng khác nhau 2. Sử dụng tiêu chí đánh giá gom nhóm để chọn ra tập con đặc trưng tốt 3. Lặp lại quá trình cho đến khi đảm bảo rằng mô hình chọn ra tập con đặc trưng tối ưu nhất
5. các loại dữ liệu
5.1. Dữ liệu định hướng không phụ thuộc
5.1.1. Dữ liệu nhiều chiều, dữ liệu văn bản
5.1.2. Dữ liệu nhiều chiều định lượng được
5.1.3. Dữ liệu phân loại
5.2. Dữ liệu định hướng phụ thuộc
5.2.1. Time-series:
5.2.1.1. 1 tập hợp các điểm dữ liệu được thu thập tại n khoảng thời gian t1, t2,...tn đều đặn hoặc không đều đặn, phụ thuộc theo thời gian
5.2.1.2. Giá trị của 1 điểm dữ liệu sẽ phụ thuộc vào giá trị dl trước đó và có thể dự đoán giá trị tương lai
5.2.1.3. Ví dụ thực tế
5.2.1.3.1. Dữ liệu giá cổ phiếu: Thời gian: Ngày tháng năm (các thời điểm mà giá cổ phiếu được ghi nhận) giá cổ phiếu: giá trị ở mỗi thời điểm
5.2.2. Strings:
5.2.2.1. Là dạng dữ liệu rời rạc, trong đó các dữ liệu được thu thập tại n khoảng thời gian khác nhau, kh liên tục
5.2.2.2. Mỗi đối tượng n sẽ gồm d các thuộc tính rời rạc thu được tại khoảng thời gian tương ứng
5.2.2.3. Ví dụ
5.2.2.3.1. Dữ liệu của 1 học sinh thông qua các kì thi: Kỳ thi: các kỳ thi khác nhau Toán, Văn, Anh: điểm số của học sinh khác nhau qua từng kỳ thi
5.2.3. Spatial
5.2.3.1. là dữ liệu được thu thập cùng với thông tin về vị trí địa lý nơi mà dữ liệu đó được ghi lại
5.2.3.2. có dạng là bản ghi thuộc tính d chiều X1, ..., Xn cùng các vị trí không gian của bản ghi L tương ứng với các thuộc tính có thể được biểu diễn dưới dạng địa chỉ kinh độ, vĩ độ
5.2.3.3. Ví dụ
5.2.3.3.1. Dữ liệu về các địa điểm du lịch thu hút của thành phố Nghệ An: Thuộc tính: Tên địa điểm, lượt khách; Vị trí: Vĩ độ và kinh độ của mỗi điểm du lịch
5.2.4. Network
5.2.4.1. Mạng lưới: G=(N, A)
5.2.4.1.1. 1 bộ thực thể N
5.2.4.1.2. 1 bộ các liên kết A
5.2.4.2. Ví dụ
5.2.4.2.1. Dữ liệu mạng giao thông: Nút: là các địa điểm ví dụ như các địa điểm nổi tiếng của Hồ Chí Minh; Cạnh: là các tuyến đường giao thông kết nối giữa các địa điểm đó với nhau
6. Chuẩn bị dữ liệu
6.1. 1. Trích xuất đặc trưng:
6.1.1. phụ thuộc vào từng ứng dụng cụ thể và bản nguồn của dữ liệu
6.1.2. Các loại biến đổi:
6.1.2.1. Số -> phân loại: rời rạc hóa
6.1.2.2. Phân loại -> số: nhị phân hóa
6.1.2.3. Văn bản -> số: LSA
6.1.2.4. Chuỗi thời gian (time-series) -> số: DWT, DFT
6.1.2.5. Spatial -> số: DWT, DFT
6.1.2.6. Network -> số: MDS, biến đổi phổ
6.1.2.7. Time-series -> strings discreete: SAX
6.1.2.8. Sequence discreete -> số : biển đổi wavelet, nhị phân hóa
6.1.2.9. Bất kỳ -> đồ thị (Graph): gom cụm/ bài toán phát hiện ngoại lai
6.2. 2. Làm sạch dữ liệu
6.2.1. Xử lý dữ liệu bị thiếu
6.2.1.1. Loại bỏ các bản ghi có thông tin bị thiếu
6.2.1.2. Sử dụng phương thức điền khuyết/ ước lượng
6.2.1.3. dùng các thuật toán được thiết kế
6.2.2. Xử lý dữ liệu sai và không đồng nhất
6.2.2.1. Sau khi phát hiện sự không đồng nhất
6.2.2.1.1. Sử dụng kiến thức lĩnh vực chuyên môn, bao gồm việc biến đổi dữ liệu từ các định dạng khác nhau
6.2.3. Scale và chuẩn hóa dữ liệu
6.2.3.1. Dùng pp chuẩn hóa, tham chiếu các dữ liệu về cùng 1 thang đo, chuyển đồi các thuộc tính về cùng 1 quy mô
6.2.4. Các yếu tố ảnh hưởng:
6.2.4.1. Sự đa dạng của dữ liệu
6.2.4.2. Khối lượng dữ liệu
6.2.4.3. Tính phức tạp của dữ liệu
6.2.4.4. Thiếu chuyên môn và sử dụng công cụ không phù hợp
6.2.4.5. Dữ liệu ngoại lai và nhiễu
6.3. 3. Rút gọn và biến đổi dữ liệu
6.3.1. Lấy mẫu dữ liệu:
6.3.1.1. Dữ liệu tĩnh
6.3.1.2. Reservoir
6.3.1.2.1. Với 1 reservoir kích thước k điểm dữ liệu, lấy k điểm đầu tiên trong dòng dữ liệu để khởi tạo reservoir
6.3.2. Chọn lọc đặc trưng
6.3.2.1. không giám sát
6.3.2.2. giám sát
6.3.3. Giảm số chiều bằng cách xoay trục
6.3.3.1. PCA
6.3.3.1.1. Mục tiêu
6.3.3.1.2. Định nghĩa
6.3.3.1.3. Các bước sử dụng:
6.3.3.2. SVD
6.3.3.2.1. Có quan hệ gần với PCA
6.3.3.2.2. Định nghĩa:
6.3.3.2.3. Cách sử dụng
6.3.3.3. LSA
6.3.3.3.1. Định nghĩa
6.3.3.3.2. Cách sử dụng
7. Cách xử lý dữ liệu đa chiều
7.1. Các bước thực hiện
7.1.1. Khám phá dữ liệu
7.1.1.1. Làm sạch dữ liệu và giảm chiều dữ liệu
7.1.1.1.1. Trích xuất và lựa chọn đặc trưng
7.2. Sự tương đồng dữ liệu
7.2.1. Dữ liệu định lượng: các dữ liệu có thể ước lượng, đo lường, tính toán, thống kê
7.2.1.1. Chuẩn Lp
7.2.1.1.1. Dist(X, Y) = [ \sum_{i=1}^n (abs(x_i - y_i)^p]^(1/p)
7.2.1.2. Các ảnh hưởng
7.2.1.2.1. Kiến thức chuyên môn lĩnh vực
7.2.1.2.2. Số chiều cao
7.2.1.2.3. Các đặc trưng không quan trọng cục bộ
7.2.1.2.4. Các chuẩn Lp khác nhau
7.2.1.2.5. Phân phối dữ liệu
7.2.1.2.6. Phân phối dữ liệu cục bộ
7.2.2. Dữ liệu định tính: các dữ liệu mô tả và phân loại, không đo lường bằng con số được
7.2.2.1. Similarity
7.2.2.2. Inverse occurence frequencies
7.2.3. Dữ liệu văn bản
7.2.3.1. Cos(X, Y)
7.2.3.2. Jaccord
8. Khai phá mẫu dữ liệu
8.1. Mục tiêu
8.1.1. Xác định các liên hệ giữa các nhóm hạng mục được mua bởi khách hàng
8.2. Định nghĩa liên quan:
8.2.1. Support
8.2.1.1. tỷ lệ giữa số lượng giao dịch chứa I trong cơ sở dữ liệu T={T1,...,Tn} và tổng số giao dịch của T
8.2.1.2. Dùng để xác định mức độ phổ biến của các tập hạng mục trong cơ sở dữ liệu
8.2.2. Frequent Item set
8.2.2.1. Tập hợp gồm hạng mục I có tần suất xuất hiện trong csdl T ít nhất hoặc bằng minsup
8.2.3. Maximal frequent itemset
8.2.3.1. Tập maximal ở 1 mức minsup nào đó là một tập thường xuyên ở mức minsup, không tồn tại 1 tập siêu nào của nó là thường xuyên ở ngưỡng đó
8.2.4. Confidence
8.2.4.1. conf (X=>Y) = [sup(X v Y)]/ sup(X)
8.2.5. Luật liên kết
8.2.5.1. X => Y được coi là luật liên kết tại minsuf và minconf khi và chỉ khi
8.2.5.1.1. 1. Sup(X => Y) >= minsup
8.2.5.1.2. 2. Conf(X => Y) >= minconf
8.3. Định lý:
8.3.1. Đơn điệu của support
8.3.1.1. Support của mọi tập con J của I ít nhất bằng sup của tập I
8.3.2. Downward closure
8.3.2.1. Mỗi tập con của tập thường xuyên thì thường xuyên
9. Thuật toán:
9.1. Brute-force:
9.1.1. Thuật toán vét cạn nhằm tìm kiếm tất cả các khả năng có thể để giải quyết vấn đề bằng cách kiểm tra nó có thể thỏa mãn điều kiện hay không
9.1.1.1. Tuy nhiên, không khả thi với 1 không gian lớn gồm nhiều các hạng mục
9.1.2. Cách tiếp cận:
9.1.2.1. Giảm kích thước không gian tìm kiếm bằng cách cắt giảm các tập hạng mục tiềm năng
9.1.2.2. Tính support của mỗi tập hạng mục tiềm năng bằng cách cắt giảm các hạng mục kh quan trọng
9.1.2.3. Sử dụng các cấu trúc dl gọn gàng để biểu diễn các dữ liệu cần thiết
9.2. Apriori:
9.2.1. Thuật toán:
9.2.1.1. Apriori ( Tập hợp các giao dịch T, minsup):
9.2.1.2. begin: k = 1 F1 = {tất cả các tập thường xuyên có 1-itemset} while F_k khác rỗng do begin: Khởi tạo C_k+1 bằng cách ghép các cặp-itemset trong F_k; Loại bỏ các tập hạng mục từ C_k+1 nếu như chúng không thỏa định lý down closure; Xác định F_k+1 bằng cách tính sup các tập itemset trên (C_k+1, T) và giữ lại các tập trong C_k+1 thỏa minsup; k = k +1 endw return (U_{i=1}^k Fi);