# Khai phá dữ liệu

## Chương 1: Giới thiệu về KPDL
### 1. Tại sao lại KPDL
- Công bố khoa học về khai phá dữ liệu
- Một ví dụ: Donal Trump Thắng cử Tổng thống Mỹ
- Bùng nổ dữ liệu và dữ liệu lớn (Big Data)
- Lý do công nghệ
- Lý do xã hội
- Thể hiện
- Ngành kinh tế tri thức, dữ liệu và thông tin (Infonomics)
- Kinh tế tri thức
- Phát hiện tri thức từ dữ liệu
- Nhu cầu khai phá dữ liệu tại Việt Nam
- Trường hè KHDL 2016
- Xu thế từ Định luật Moore
- Một quan sát và dự báo
- Lượng bóng bán dẫn (giá) của mạch tích hợp tăng (rẻ) gần gấp đôi sau mỗi chu kỳ hai năm
- Máy tính (điện thoại, v.v.) mạnh hơn, gọn hơn, giá cả phù hợp
- Kinh tế dịch vụ: Từ dữ liệu tới giá trị
- 
- Kinh tế dịch vụ
- Xã hội loài người chuyển dịch từ kinh tế hàng hóa sang kinh tế dịch vụ. Lao động dịch vụ vượt lao động nông nghiệp (2006).
- Mọi nền kinh tế là kinh tế dịch vụ.
- Đơn vị trao đổi trong kinh tế và xã hội là dịch vụ
- Dịch vụ: dữ liệu & thông tin --> tri thức --> giá trị mới
- Khoa học: dữ liệu & thông tin --> tri thức
- Kỹ nghệ: tri thức --> dịch vụ
- Quản lý: tác động tới toàn bộ quy trình thi hành dịch vụ
#### a. Quá trình tiến hóa dữ liệu tới trí tuệ
- 
- Dữ liệu (data): dữ kiện không ngữ cảnh. Trình bày dữ kiện.
- Thông tin (information): dữ kiện với ngữ cảnh và khía cạnh nào đó. Dữ liệu có ý nghĩa, dữ liệu trong ngữ cảnh. Hiểu được quan hệ
- Tri thức (knowledge): Thông tin được dung để phát hiện và hiểu được mẫu trong dữ liệu. Hiểu được mẫu
- Trí tuệ (wisdom): Tri thức nảy sinh khi hiểu được lý do mẫu xuất hiện trong dữ liệu. Hiểu được nguyên lý

### 2. Khái niệm KPDL
- Knowledge discovery from databases (KDD): Trích chọn các mẫu hoặc tri thức hấp dẫn (không tầm thường, ẩn, chưa biết và hữu dụng tiiềm năng) từ một tập hợp lớn dữ liệu
- **Data Mining là một bước trong quá trình KDD**
- Quá trình KDD: 
- Quá trình KPDL: 
- Các bước trong quá trình KDD: 
- Mô hình quá trình KDD: 
#### a. Khoa học dữ liệu
- Quá trình học dữ liệu: 
- Các chuyên ngành liên quan: 
- Lưu ý:
- Khoa học hành vi và các khoa học xã hội
- Mô hình kinh doanh và tiếp thị
- Bảo mật, an ninh, pháp luật và đạo đức
- Tính đa diện:
- một nghề (vai trò) trong công nghiệp
- một khoa học
- một phương pháp nghiên cứu
- một chuyên ngành đào tạo
- một quy trình làm việc: 

#### b. Dữ liệu và mẫu
- 
- Dữ liệu (tập dữ liệu):
- tập F gồm hữu hạn các trường hợp (sự kiện).
- KDD:phải gồm rất nhiều trường hợp
- Mẫu:
- Trong KDD: ngôn ngữ L để biểu diễn các tập con các sự kiện (dữ liệu) thuộc vào tập sự kiện F,
- Mẫu: biểu thức E trong ngôn ngữ L <--> tập con $F_E$ tương ứng các sự kiện trong F. E được gọi là mẫu nếu nó đơn giản hơn so với việc liệt kê các sự kiện thuộc $F_E$.
- Chẳng hạn, biểu thức "THUNHẬP < $t" (mô hình chứa một biến THUNHẬP)
- Tính có giá trị:
- Mẫu được phát hiện: phải có giá trị đối với các dữ liệu mới theo độ chân thực nào đó
- Tính có giá trị: một độ đo tính có giá trị (chân thực) là một hàm C ánh xạ một biểu thức thuộc ngôn ngữ biểu diễn mẫu L tới một không gian đo được (bộ phân hoặc toàn bộ) $M_c$
- Chẳng hạn, đường biên xác định mẫu "THUNHẬP < $t“ dịch sang phải (biến THUNHẬP nhận giá trị lớn hơn) thì độ chân thực giảm xuống do bao gói thêm các tình huống vay tốt lại bị đưa vào vùng không cho vay nợ.
- 
- Tính mới: Mẫu phải là mới trong một miền xem xét nào đó, ít nhất là hệ thống đang được xem xét.
- Có thể đo được:
- Sự thay đổi trong DL: so sánh giá trị hiện tại với quá khứ hoặc kỳ vọng
- Được đo bằng N(E, F) hoặc độ đo về tính mới hoặc độ đo kỳ vọng
- Hữu dụng tiềm năng: Mẫu cần có khả năng chỉ dẫn tới các tác động hữu dụng và được đo bởi một hàm tiện ích
- Tính hiểu được: Mẫu phải hiểu được
- Giả định rằng tính hiểu được là đo được bằng một hàm S ánh xạ biểu thức E trong L tới một không gian đo được có thứ tự (bộ phận /toàn bộ) MS: s = S(E,F).
- Tính hấp dẫn: độ đo tổng thể về mẫu là sự kết hợp của các tiêu chí giá trị, mới, hữu ích và dễ hiểu
- Hoặc dùng một hàm hấp dẫn: $i = I (E, F, C, N, U, S)$ ánh xạ biểu thức trong L vào một không gian đo được $M_i$.
- Hoặc xác định độ hấp dẫn trực tiếp: thứ tự của các mẫu được phát hiện.
- Tri thức: Một mẫu $E \in L$ được gọi là tri thức nếu như đối với một lớp người sử dụng nào đó, chỉ ra được một ngưỡng $i \in M_i$ mà độ hấp dẫn $I(E,F,C,N,U,S) > i$
- Kiến trúc điển hình: 

### 4. KPDL: Kiểu mẫu được khai phá
- Chức năng chung
- KPDL mô tả: tóm tắt, phân cụm, luật kết hợp…
- KPDL dự đoán: phân lớp, hồi quy…
- Các bài toán điển hình
- Mô tả khái niệm
- Quan hệ kết hợp
- Phân lớp
- Phân cụm
- Hồi quy
- Mô hình phụ thuộc
- Phát hiện biến đổi và độ lệch
- Phân tích định hướng mẫu, các bài toán khác
- Sơ đồ phân loại:
- Phân loại theo bài toán
- Dự báo và mô tả
- Mở rộng: Kiểm chứng và phát hiện
- Phân loại theo khung nhìn
- Kiểu dữ liệu được KP
- Kiểu tri thức cần phát hiện
- Kiểu kỹ thuật được dùng
- Kiểu miền ứng dụng
- Gồm hai loại:
- 
- Loại KPDL dự báo
- Xây dựng các mô hình (hàm) mô tả và phân biệt khái niệm cho các lớp hoặc khái niệm để dự đoán trong tương lai
- Trình diễn: cây quyết định, luật phân lớp, mạng nơron
- Dự đoán giá trị số chưa biết hoặc đã mất
- Phân lớp: xây dựng/mô tả mô hình/hàm dự báo để mô tả/phát hiện lớp/khái niệm cho dự báo tiếp
- Hồi quy: học một hàm ánh xạ dữ liệu nhằm xác định giá trị số của một biến theo một số biến khác
- Phân tích tồn tại: Phân tích tồn tại (sống còn), ví dụ, thời gian rời khỏi hoặc cần giám sát
- Dự đoán: Dự đoán, ví dụ dự đoán nhu cầu
- Loại KPDL mô tả:
- Phân cụm: Nhãn lớp chưa biết: Nhóm dữ liệu thành các “lớp” mới
- Ví dụ: phân cụm các hộ gia đình để tìm mẫu phân bố về thu nhập hộ gia đình
- Phân tích bất thường:
- Bất thường: đối tượng dữ liệu không tuân theo hành vi chung của toàn bộ dữ liệu
- VD: Phát hiện gian lận, phân tích các sự kiện hiếm, phát hiện xâm nhập mạng trái phép
- Phát hiện biến đổi và độ lệch:
- Hầu như sự thay đổi có ý nghĩa dưới dạng độ đo đã biết trước/giá trị chuẩn, cung cấp tri thức về sự biến đổi và độ lệch
- Phát hiện biến đổi và độ lệch <> tiền xử lý
- Phân cụm: ví dụ phân cụm khách hàng theo RF
- Phân tích kết hợp: 
- Phân tích dãy: 

## Chương 2: Công nghệ tri thức

### 1. Vai trò của CNTT trong kinh tế
### 2. Dữ liệu, thông tin, tri thức
- 
- 
- Thông tin có giá trị:
- Cho người quản lý và người ra quyết định (“quản lý” và “lãnh đạo”). Nhìn chung “chính xác, đúng người, đúng thời điểm”
- Đặc trưng:
- truy nhập được
- chính xác
- đầy đủ
- kinh tế: chi phí tạo thông tin
- linh hoạt: sử dụng cho nhiều mục đích
- có liên quan
- tin cậy
- an toàn
- đơn giản
- kịp thời
- kiểm chứng được.
#### a. Dữ liệu lớn:
* Dữ liệu lớn là một tập dữ liệu có các **đặc trưng đặc biệt**, được xử lý (lưu trữ, tính toán, chuyển dạng) và phân tích (tìm các mẫu liên quan mới lạ hữu dụng từ dữ liệu) **bằng các quy trình hoặc công cụ đặc biệt** nhằm nhận được **thông tin hỗ trợ ra quyết định hoặc đánh giá có giá trị**
* Được mô tả qua các **đặc trưng đặc biệt** thường là nV
* Đặc trưng 5V:
* Dung lượng lớn (Volume)
* Cỡ Texabytes (1012Bytes)
* Kích thược lớn tiềm ẩn thông tin giá trị
* Tốc độ cao (Velocity)
* Tốc độ cao: tốc độ phát sinh, tốc độ chuyển động
* Thời gian thực hoặc tựa thời gian thực
* Tốc độ cao  tính kịp thời
* Ví dụ: phát hiện gian lận giao dịch cần với tốc độ mili-giây, dữ liệu cần cập nhật tốc độ cao
* Đa dạng (Variety)
* Có/không cấu trúc (văn bản, hình ảnh, video, dữ liệu cảm biến, v.v.), đa yếu tố, có tính xác suất
* Đa dạng  khung nhìn đa chiều (chính xác hơn) về sự vật/hiện tượng
* Xác thực được (Veracity)
* Được xác thực theo độ tin cậy, quy trình, xuất xứ, uy tín, tính khả dụng và được giải trình
* Thông tin giá trị từ nguồn tin cậy, được xác thực
* Có giá trị (Value)
* Đặc trưng giá trị là quan trọng nhất
* Mục tiêu phân tích dữ liệu lớn (mục tiêu kinh doanh) dẫn dắt hoạt động xây dựng/phân tích dữ liệu lớn
* Hiểu biết thực sự về chi phí và lợi ích
* Dữ liệu lớn chỉ bao gồm các dữ liệu liên quan
* Tránh hiện tượng “dữ liệu lớn” theo phong trào
* Dữ liệu cho kinh doanh
* Cải thiện việc quyết định
* Thấu hiểu khách hàng và thị trường
* Tạo sản phẩm tốt hơn
* Tạo dịch vụ tốt hơn
* Cải tiến quy trình kinh doanh
* Tạo doanh thu từ chính dữ liệu
* Thông tin: Một tài sản thực sự?
* Không
* Không nằm trong bảng cân đối kế toán.
* Không thể giải thích vì nó vô hình.
* Không thực sự tiêu hao như các tài sản khác.
* Có
* Có thể có giá trị trao đổi.
* Có thể tạo ra một giá trị kinh tế tích cực.
* Có thể đếm / đo được, nhưng theo cách nào?
* Các yếu tố ảnh hưởng lợi ích của tài sản thông tin và cuối cùng là giá trị kinh tế
* 
### 3. Các mô hình Khai phá dữ liệu
* Nội dung cơ bản của KDD và DM:
* Khai phá dữ liệu và phát hiện tri thức trong CSDL là **bài toán “kinh doanh”, bài toán “chiến lược”** mà không phải là *bài toán công nghệ*.
* Tiếp cận truyền thống và tiếp cận KPDL
* Tiếp cận truyền thống
* Từ lý thuyết (hệ toán mệnh đề) --> phát triển các giả thuyết --> kiểm định (chứng minh) giả thuyết. Ngô Bảo Châu: Bổ đề cơ bản
* Tiếp cận khai phá dữ liệu
* Từ dữ liệu --> phát hiện quan hệ --> phát triển giả thuyết --> Xây dựng mô hình và kiểm định giả thuyết --> Đánh giá mô hình --> Sử dụng mô hình.
* Chuẩn công nghiệp khai phá dữ liệu CRISP-DM
* Hiểu kinh doanh (Business understanding)
* Hiểu dữ liệu (Data understanding)
* Chuẩn bị dữ liệu (Data preparation)
* Mô hình hóa (Modeling)
* Đánh giá (Evaluation)

### 4. Từ tri thức tổ chức tới kinh tế tri thức
* Tri thức
* Hình thức thu nhân tri thức: giáo dục, kinh nghiệm qua hoạt động thực tiễn
* Phân loại tri thức
* 
* "know what": tri thức về sự vật, sự kiện, hiện tượng
* "know why": tri thức về thế giới, xã hội và trí tuệ con người,
* "know who": tri thức về ai và họ làm được gì,
* "know how": tri thức về kỹ năng và kinh nghiệm thực tiễn.
* "know where", "know when": tri thức quan trọng cho một nền kinh tế mềm dẻo và động
* Hàm quản lý tri thức: 

## Chương 3: Hiểu bài toán, hiểu dữ liệu và tiền xử lý dữ liệu

### 1. Hiểu bài toán và hiểu dữ liệu
* 
#### a. Hiểu bài toán
* 5 yếu tố:
* Yếu tố 1:
* Ta đã biết (có) được những gì? Cho INPUT
* Yếu tố 2:
* Cần quyết định điều gì? Xác định OUTPUT, Biến quyết định
* Phân lớp nhị phân: Miền giá trị của biến quyết định có hai giá trị “nhị phân”
* Yếu tố 3:
* Cái gì cố gắng để đạt được
* Hàm mục tiêu (tập các tham số)
* Cái gì cần đạt được ? (Mục đích)
* Khai phá dữ liệu = Tối ưu hóa
* Tối ưu hóa: 3 tiếp cận
* Có thông tin về đường đi tới cực trị toàn cục
* Tiếp cận Monte-Carlo tìm cực trị toàn cục
* Tiếp cận tìm cực trị cục bộ
* Yếu tố 4:
* Cái gì cản trở giải bài toán: Hạn chế tài nguyên, ràng buộc
* Yếu tố 5:
* Cái gì tìm hiểu thêm được

### 2. Hiểu dữ liệu:
#### a. Vấn đề và ràng buộc:
* Vấn đề:
* Phạm vi dữ liệu liên quan tới câu hỏi
* Đặt bài toán sơ bộ
* Phân tích ràng buộc:
* Ràng buộc kinh doanh: Làm rõ hơn mối liên quan giữa dữ liệu với mục tiêu kinh doanh
* Ràng buộc nội tại: Ràng buộc dữ liệu về kiểu, ràng buộc liên quan dữ liệu
#### b. Kiểu dữ liệu:
* Bản ghi:
* Bản ghi quan hệ
* Ma trận DL
* Dữ liệu tài liệu
* Dữ liệu giao dịch
* Đồ thị và mạng:
* World Wide Web
* Mạng xã hội và mạng thông tin
* Cấu trúc phân tử
* Thứ tự:
* Dữ liệu thời gian: Chuỗi thời gian
* Dữ liệu dãy: Dãy giao dịch
* Dữ liệu dãy gene.
* Không gian, ảnh và đa phương tiện:
* DL không gian, bản đò
* Dữ liệu ảnh
* DỮ liệu video
* Dữ liệu audio
#### c. Đặc trưng quan trọng của dữ liệu có cấu trúc
* Kích thước
* Tai họa của kích thước lớn
* Thưa
* Chỉ mang tính hiện diện
* Phân tích
* Mẫu phụ thuộc quy mô
* Phân bố
* Tập trung và phân tán
#### d. Đối tượng dữ liệu
* Tập DL được tạo nên từ các đối tượng DL.
* Mỗi **đối tượng dữ liệu** (data object, data point) trình bày một thực thể.
* Tên khác: mẫu (samples ), ví dụ (examples), thể hiện (instances), điểm DL (data points), đối tượng (objects), bộ (tuples).
* Đối tượng DL được mô tả bằng các đặc trưng/thuộc tính (feature/attribute)
* Dòng CSDL --> đối tượng DL; cột --> thuộc tính.
#### e. Đặc trưng (Thuộc tính)
* Đặc trưng_feature (hoặc Thuộc tính_Attribute chiều_dimension, biến_variables): một trường DL biểu diễn một đặc trưng/thuộc tính của một đối tượng DL.
* Kiểu:
* Đinh danh
* Nhị phân
* Số: định lượng
* Cỡ khoảng
* Cỡ tỷ lệ
* Kiểu thuộc tính:
* Định danh: lớp, trạng thái, hoặc “tên đồ vật”
* Nhị phân: Thuộc tính định danh hai trạng thái (0 và 1)
* Có thứ tự: Các giá trị có thứ tự mang nghĩa (xếp hạng) nhưng độ lớn các giá trị liên kết: không được biết
* Kiểu thuộc tính số
* Thuộc tính rời rạc và liên tục
* Thuộc tính rời rạc:
* Chỉ có một tập hữu hạn hoặc hữu hạn đếm được các giá trị
* Đôi lúc trình bày như các biến nguyên
* Thuộc tính liên tục
* Thực tế, giá trị thực chỉ tính và trình bảng bằng sử dụng một hữu hạn chữ số
* Có rất nhiều các giá trị thuộc tính: Như nhiệt độ, chiều cao, trong lượng
* Thuộc tính liên tục được trình bày phổ biến như biến dấu phảy động
* Tương tự và phân biệt:
* Tương tự:
* Cho biết hai đối tượng giống nhau ra sao
* Thường thuộc đoạn [0,1]
* Phân biệt (khoảng cách):
* Cho biết hai đối tượng khác nhau ra sao
* Càng thấp khi các đối tượng càng giống nhau
* Phân biệt tối thiểu là 0
* Giới hạn trên tùy
* Gần: chỉ dẫn tới tương tự hoặc phân biệt
* Đo khoảng cách thuộc tính định danh:
* Có thể đưa ra $\ge 2$ các trạng thái, như “red, yellow, blue, green” (tổng quát hóa thuộc tính nhị phân)
* 
* Đo khoảng cách thuộc tính nhị phân:
* 
* Chuẩn hóa dữ liệu số:
* Z score: $z = \frac{x - \mu}{\sigma}$
* X: DL thô sẽ được chuẩn hóa, μ: trung bình mẫu (kỳ vọng_ của tập số, σ: độ lệch chuẩn
* Khoảng cách giữa DL thô và kỳ vọng theo đơn vị độ lệch chuẩn
* Âm (-) khi DL thô nhỏ thua kỳ vọng, “+” khi lớn hơn above
* 
* Đo khoảng các dữ liệu số: KC Minkowski
* 
* Các trường hợp đặc biệt: 
#### f. Biến có thứ tự
* Một biến có thứ tự có thể rời rạc hoặc liên tục
* Thứ tự là quan trọng, chẳng hạn như “hạng”
* 

#### g. Thuộc tính có kiểu pha trộn
* 
#### h. So sánh hai phân bố XS: Phân kỳ KL
* “Khoảng cách” / “Phân kỳ” Kullback-Leibler (KD) : Đo sự khác biệt hai phân bố xác suất trên cùng biến x
* 

#### i. Thu thập dữ liệu
* Cách thu thập dữ liệu cần thiết để mô hình hóa Data Acquisition:
* Trích chọn dữ liệu theo câu hỏi từ CSDL tới tập tin phẳng
* Ngôn ngữ hỏi bậc cao truy nhập trực tiếp CSDL
* Kết nối mức thấp để truy nhập trực tiếp CSDL
* Loại bỏ ràng buộc không gian/thời gian khi di chuyển khối lượng lớn dữ liệu
* Hỗ trợ việc quản lý và bảo quản dữ liệu tập trung hóa
* Rút gọn sự tăng không cần thiết của dữ liệu
* Tạo điều kiện quản trị dữ liệu tốt hơn để đáp ứng mối quan tâm đúng đắn
* Mô tả thống kê cơ bản của dữ liệu:
* 
* Một số độ đo thống kê:
* Độ lệch chuẩn: Phân bố dữ liệu xung quanh kỳ vọng
* Cực tiểu, cực đại: Giá trị nhỏ nhất và lớn nhất
* Độ đo phân tán
* Bản tuần suất
* Lược đồ
* Đánh giá và lập hồ sơ dữ liệu:
* Đánh giá dữ liệu:
* Định vị một vấn đề trong dữ liệu cần giải quyết: Tìm ra và quyết định cách nắm bắt vấn đề
* Mô tả dữ liệu sẽ làm hiện rõ một số vấn đề
* Kiểm toán dữ liệu: lập hồ sơ dữ liệu và phân tích ảnh hưởng của dữ liệu chất lượng kém.
* Lập hồ sơ dữ liệu (cơ sở căn cứ: phân bố dữ liệu)
* Tâm của dữ liệu
* Các ngoại lai tiềm năng bất kỳ
* Số lượng và phân bố các khoảng trong trong mọi trường hợp
* Bất cứ dữ liệu đáng ngờ, như mã thiếu (miscodes), dữ liệu học, dữ liệu test, hoặc chỉ đơn giản dữ liệu rác
* Những phát hiện nên được trình bày dưới dạng các báo cáo và liẹt kế như các mốc quan trọng của kế hoạch

### 2. Tiền xử lý dữ liệu:
#### a. Vai trò của Tiền xử lý dữ liệu
* Dữ liệu có chất lượng cao nếu như phù hợp với mục đích sử dụng trong điều hành, ra quyết định, và lập kế hoạch
* Các bài toán chính trong tiền XLDL
* Làm sạch dữ liệu
* Điền giá trị thiếu, làm trơn dữ liệu nhiễu, định danh hoặc xóa ngoại lai, và khử tính không nhất quán
* Tích hợp dữ liệu
* Tích hợp CSDL, khối dữ liệu hoặc tập tin phức
* Chuyển dạng dữ liệu
* Chuẩn hóa và tổng hợp
* Rút gọn dữ liệu
* Thu được trình bày thu gọn về kích thước những sản xuất cùng hoặc tương tự kết quả phân tích
* Rời rạc dữ liệu
* Bộ phận của rút gọn dữ liệu nhưng có độ quan trọng riêng, đặc biệt với dữ liệu số
* Một số bài toán cụ thể:
* Cách thức làm sạch dữ liệu:
* Data Cleaning
* Cách thức diễn giải dữ liệu:
* Data Transformation
* Cách thức nắm bắt giá trị thiếu:
* Data Imputation
* Trọng số của các trường hợp:
* Data Weighting and Balancing
* Xử lý dữ liệu ngoại lai và không mong muốn khác:
* Data Filtering
* Cách thức nắm bắt dữ liệu thời gian/chuỗi thời gian:
* Data Abstraction
* Cách thức rút gọn dữ liệu để dùng: Data Reduction
* Bản ghi : Data Sampling
* Biến: Dimensionality Reduction
* Giá trị: Data Discretization
* Cách thức tạo biến mới: Data Derivation
#### b. Làm sạch dữ liệu
* Là quá trình
* xác định tính không chính xác, không đầy đủ/tính bất hợp lý của dữ liệu
* chỉnh sửa các sai sót và thiếu sót được phát hiện
* nâng cao chất lượng dữ liệu.
* Quá trình bao gồm
* kiểm tra định dạng, tính đầy đủ, tính hợp lý, miền giới hạn,
* xem xét dữ liệu để xác định ngoại lai (địa lý, thống kê, thời gian hay môi trường) hoặc các lỗi khác,
* đánh giá dữ liệu của các chuyên gia miền chủ đề.
* Quá trình thường dẫn đến
* loại bỏ, lập tài liệu và kiểm tra liên tiếp và hiệu chỉnh đúng bản ghi nghi ngờ.
* Kiểm tra xác nhận có thể được tiến hành nhằm đạt tính phù hợp với các chuẩn áp dụng, các quy luật, và quy tắc.
* Các bài toán thuộc làm sạch dữ liệu
* Xử lý giá trị thiếu
* Dữ liệu nhiễu: định danh ngoại lai và làm trơn.
* Chỉnh sửa dữ liệu không nhất quán
* Giải quyết tính dư thừa tạo ra sau tích hợp dữ liệu.
* Mục đích:
* Phòng ngừa liên quan chặt chẽ với thu thập và nhập dữ liệu vào CSDL.
* Tăng cường phòng ngừa lỗi, vẫn/tồn tại sai sót trong bộ dữ liệu lớn (Maletic và Marcus 2000) và không thể bỏ qua việc xác nhận và sửa chữa dữ liệu
* Xử lý giá trị nhiễu:
* Bỏ qua bản ghi có giá trị thiếu: ko hiệu quả khi tỉ lệ bản ghi thiếu lớn, thường làm khi thiếu nhãn phân lớp
* Điền giá trị bằng tay: tẻ nhạt, thiếu khả thi
* Điền giá trị tự động:
* Hằng toàn cục: Một biến chưa biết "unknown"
* Trung bình giá trị thuộc tính các bản ghi hiện có
* Trung bình giá trị thuộc tính các bản ghi cùng lớp
* **Giá trị có khả năng nhất: Cây quyết định hoặc công thức Bayes**
##### b.1. Dữ liệu nhiễu:
* Nhiễu:
* Lỗi ngẫu nhiên
* Biến dạng của một biến đo được
* Giá trị không chính xác
* Lỗi do thiết bị thu thập dữ liệu
* Vấn đề nhập dữ liệu: người dùng hoặc máy có thể sai
* Vấn đề truyền dữ liệu: sai từ thiết bị gửi/nhận/truyền
* Hạn chế của công nghệ: ví dụ, phần mềm có thể xử lý không đúng
* Thiết nhất quán khi đặt tên: cũng một tên song cách viết khác nhau
* Các vấn đề dữ liệu khác yêu cầu làm sạch dữ liệu
* Bội bản ghi
* Dữ liệu không đầy đủ
* Dữ liệu không nhất quán
* Xử lý dữ liệu nhiễu:
* Phương pháp đóng thùng (Binning):
* Sắp dữ liệu tăng và chia “đều” vào các thùng
* Làm trơn: theo trung bình, theo trung tuyến, theo biên…
* Phân cụm (Clustering)
* Phát hiện và loại bỏ ngoại lai (outliers)
* Kết hợp kiểm tra máy tính và con người
* Phát hiện giá trị nghi ngờ để con người kiểm tra (chẳng hạn, đối phó với ngoại lai có thể)
* Hồi quy
* Làm trơn: ghép dữ liệu theo các hàm hồi quy
* Phương pháp đóng thùng:
* **Phân hoạch cân bẳng bề rộng Equal-width** (distance) partitioning:
* Chia miền giá trị: N đoạn dài như nhau: uniform grid
* Miền giá trị từ A (nhỏ nhất) tới B (lớn nhất) ->W = (B –A)/N.
* Đơn giản nhất song bị định hướng theo ngoại lai.
* Không xử lý tốt khi dữ liệu không cân bằng (đều).
* **Phân hoạch cân bằng theo chiều sâu Equal-depth** (frequency) partitioning:
* Chia miền xác định thành N đoạn “đều nhau về số lượng”, các đoạn có xấp xỉ số ví dụ mẫu.
* Khả cỡ dữ liệu: tốt.
* Việc quản lý các thuộc tính lớp: có thể “khôn khéo”.
* Ví dụ về làm trơn dữ liệu: 
* Phân tích cụm:
* 
* Hồi quy:
* 
#### c. Tích hợp và chuyển dạng dữ liệu
* Tích hợp dữ liệu (Data integration):
* Kết hợp dữ liệu từ nhiều nguồn thành một nguồn lưu trữ chung
* Tích hợp sơ đồ
* Tích hợp siêu dữ liệu từ các nguồn khác nhau
* Vấn đề định danh thực thế: xác định thực thể thực tế từ nguồn dữ liệu phức, chẳng hạn, A.cust-id = B.cust-#
* Phát hiện và giải quyết vấn đề thiết nhất quá dữ liệu
* Cùng một thực thể thực sự: giá trị thuộc tính các nguồn khác nhau là khác nhau
* Nguyên nhân: trình bày khác nhau, cỡ khác nhau, chẳng hạn, đơn vị quốc tế khác với Anh quốc
* Nắm bắt dư thừa trong tích hợp dữ liệu:
* Dư thừa dữ liệu: thường có khi tích hợp từ nhiều nguồn khác nhau
* Một thuộc tính có nhiều tên khác nhau ở các CSDL khác nhau
* Một thuộc tính: thuộc tính “nguồn gốc” trong CSDL khác, chẳng hạn, doanh thu hàng năm
* Dữ liệu dư thừa có thể được phát hiện khi phân tích tương quan
* Tích hợp cẩn trọng dữ liệu nguồn phức giúp giảm/tránh dư thừa, thiếu nhất quán và tăng hiệu quả tốc độ và chất lượng
* Chuẩn hóa (Normalization): thu nhỏ vào miền nhỏ, riêng
* Chuẩn hóa min-max
* 
* 
* Chuẩn hóa z-score
* 
* 
* Chuẩn hóa tỷ lệ thập phân
* 
* 
#### d. Rút gọn dữ liệu
* Kho chứa dữ liệu chứa tới hàng TB
* Phân tích/khai phá dữ liệu phức tạp mất nhiều thời gian khi chạy trên tập toàn bộ dữ liệu
* Rút gọn dữ liệu
* Có trình bày gọn tập dữ liệu mà nhỏ hơn nhiều về dung lượng mà sinh ra cùng (hoặc hầu như cùng) kết quả.
* Theo chiều ngang (rút gọn thể hiện: lấy mẫu), theo chiều dọc (rút gọn đặc trưng: lựa chọn và trích xuất), theo giá trị đặc trưng
* **Chiến lược rút gọn dữ liệu**
* **Lấy mẫu**
* **Lựa chọn đặc trưng và trích xuất đặc trưng**
* **Giảm giá trị số hóa** – dữ liệu thành mô hình; **Rời rạc hóa và sinh cây khái niệm**
* **Nén dữ liệu; Tập hợp vào khối dữ liệu**
##### d.1. Rút gọn mẫu (theo chiều ngang)
* **Sampling**
* Cho phép một thuật toán khai phá chạy theo độ phức tạp tựa tuyến tính theo cỡ của DL
* Lựa chọn một tập con trình diễn dữ liệu
* Lấy mẫu ngẫu nhiên đơn giản có hiệu quả rất tồi nếu có DL lệch
* Phát triển các phương pháp lấy mẫu thích nghi
* Lấy mẫu phân tầng:
* Xấp xỉ theo phần trăm của mỗi lớp (hoặc bộ phận nhận diện được theo quan tâm) trong CSDL tổng thể
* Sử dụng kết hợp với dữ liệu lệch
* Lẫy mẫu có thể không rút gọn được CSDL.
* Rút gọn mẫu:
* Simple Random Sampling (SRS)
* SRS with replacement (SRSWR)
* Chọn một phần tử dữ liệu đưa vào mẫu
* Loại bỏ phần tử dữ liệu đó ra khỏi tập dữ liệu
* Lặp tiếp cho đến khi có n phần tử dữ liệu
* Các phần tử dữ liệu giống nhau có thể được chọn nhiều lần
* SRS without replacement (SRSWOR)
* Chọn một phần tử và không bị loại bỏ. Các mẫu DL phân biệt
* Rút gọn phân cấp:
* Dùng cấu trúc đa phân giải với các mức độ khác nhau của rút gọn
* Phân cụm phân cấp thường được thi hành song có khuynh hướng xác định phân vùng DL hớn là “phân cụm”
* Phương pháp tham số thường không tuân theo trình bày phân cấp
* Tích hợp phân cấp
* Một cây chỉ số được chia phân cấp một tập DL thành các vùng bởi miền giá trị của một vài thuộc tính
* Mỗi vùng được coi như một thùng
* Như vậy, cây chỉ số với tích hợp lưu trữ mỗi nút là một sơ đồ phân cấp
##### d.2. Đặc trưng và rút gọn đặc trưng
* Lựa chọn đặc trưng:
* Khái niệm
* Lựa chọn tập nhỏ nhất đặc trưng mà phân bố xác suất các lớp khác nhau cho giá trị gần như phân bổ vốn có các giá trị các đặc trưng
* Kỳ vọng
* Tăng tốc độ thực thi
* Tăng chất lượng mẫu? các đặc trưng “nhiễu”
* Hoặc cả hai mục tiêu trên
* Phương pháp
* Heuristic (# mũ phép chọn) :Chọn tiến/lùi
* Kết hợp chon tiến/lùi lên trước và loại bỏ lạc hậu.
* Rút gọn bằng cây quyết định
* Hai tiếp cận điển hình
* Tiếp cận lọc
* Đầu vào: Không gian tập các tập đặc trưng
* Đầu ra: Tập con đặc trưng tốt nhất
* Phương pháp
* Dò tìm “cải tiến” bộ đặc trưng: Thuật toán tối ưu hóa
* Đánh giá chất lượng mô hình: độc lập với thuật toán học máy
* 
* Tiếp cận bao gói
* Đầu vào: Không gian tập các tập đặc trưng
* Đầu ra: Tập con đặc trưng tốt nhất
* Phương pháp
* Dò tìm “cải tiến” bộ đặc trưng: Thuật toán tối ưu hóa
* Đánh giá chất lượng mô hình: Dùng chính thuật toán học để đánh giá
* 
* Rút gọn đặc trưng theo cây quyết định:
* 
##### d.3. Trích xuất đặc trưng PCA
* Phân tích thành phần chính (Principal Component Analysis)
* Cho N vector dữ liệu k-chiều, tìm c (<= k) vector trực giao tốt nhất để trình diễn dữ liệu.
* Tập dữ liệu gốc được rút gọn thành N vector dữ liệu c chiều: c thành phần chính (chiều được rút gọn).
* Mỗi vector dữ liệu là tổ hợp tuyến tính của các vector thành phần chính.
* **Chỉ áp dụng cho dữ liệu số.**
* Dùng khi số chiều vector lớn.
##### d.4. Tổng hợp khối dữ liệu
* DataCube Aggregation
* Mức thấp nhất của khối dữ liệu
* Tổng hợp dữ liệu thành một cá thể quan tâm
* Chẳng hạn, một khách hàng trong kho dữ liệu gọi điện thoại.
* Các mức phức hợp của tích hợp thành khối dữ liệu
* Giảm thêm kích thước dữ liệu
* Tham khảo mức thích hợp
* Sử dụng trình diễn nhỏ nhất đủ để giải bài toán
* Nên sử dụng dữ liệu khối lập phương khi trả lời câu hỏi tổng hợp thông tin

##### d.5. Nén dữ liệu
* Nén xâu văn bản
* Tồn tại lý thuyết phong phú và thuật toán điển hình
* Mạnh: Không tốn thất điển hình
* Yếu: chỉ các thao tác hạn hẹp mà không mở rộng
* Nén Audio/video
* Nén tổn thất điển hình, với tinh lọc cải tiến
* Vài trường hợp mảnh tín hiệu nhỏ được tái hợp không cần dựng toàn bộ
* Chuỗi thời gian mà không là audio
* Ngắn điển hình và thay đổi chậm theo thời gian
##### d.6. Rút gọn kích thước số
* Phương pháp tham số
* Giả sử dữ liệu phù hợp với mô hình nào đó, ước lượng tham số mô hình, lưu chỉ các tham số, và không lưu dữ liệu (ngoại trừ các ngoại lai có thể có)
* Mô hình tuyến tính loga (Log-linear models): lấy giá trị tại một điểm trong không gian M-chiều như là tích của các không gian con thích hợp
* Phương pháp không tham số
* Không giả thiết mô hình
* Tập hợp chính: biểu đồ (histograms), phân cụm (clustering), lấy mẫu (sampling)

#### e. Rời rạc hóa và sinh kiến trúc khái niệm
* Ba kiểu thuộc tính:
* Định danh — giá trị từ một tập không có thứ tự
* Thứ tự — giá trị từ một tập được sắp
* Liên tục — số thực
* Rời rạc hóa:
* Chia miền thuộc tính liên tục thành các đoạn
* Một vài thuật toán phân lớp chỉ chấp nhận thuộc tính phân loại.
* Rút gọn cỡ DL bằng rời rạc hóa
* Chuẩn bị cho phân tích tiếp theo
* Rời rạc hóa: Rút gọn số lượng giá trị của thuộc tính liên tục bằng cách chia miền giá trị của thuộc tính thành các đoạn. Nhãn đoạn sau đó được dùng để thay thế giá trị thực.
* Phân cấp khái niệm: Rút gọn DL bằng tập hợp và thay thế các khái niệm mức thấp (như giá trị số của thuộc tính tuổi) bằng khái niệm ở mức cao hơn (như trẻ, trung niên, hoặc già)
* Các cách:
* Phân thùng (xem làm trơn khử nhiễu)
* Phân tích sơ đồ (đã giới thiệu)
* Phân tích cụm (đã giới thiệu)
* Rời rạc hóa dựa theo Entropy
* Phân đoạn bằng phân chia tự nhiên
* Rời rạc hóa dựa theo Entropy
* Cho tập ví dụ S, nếu S được chia thành 2 đoạn S1 và S2 dùng biên T, thì entropy sau khi phân đoạn là 
* Biên làm cực tiểu hàm entropy trên tất cả các biên được chọn như một rời rạc hóa nhị phân.
* Quá trình đệ quy tới các vùng cho tới khi đạt điều kiện dừng nào đó, như 
* Thực nghiệm chỉ ra rằng cho phép rút gọn cỡ DL và tăng độ chính xác phân lớp
* Phân đoạn bằng phân chia tự nhiên:
* Quy tắc đơn giản 3-4-5 phân đoạn dữ liệu số thành các đoạn “tự nhiên” tương đối thống nhất:
* Nếu khoảng gồm 3, 6, 7 hoặc 9 lần giá trị ý nghĩa nhất thì chia miền thành 3 đoạn tương đương.
* Nếu khoảng gồm 2, 4, hoặc 8 lần giá trị ý nghĩa nhất thì chia miền thành 4 đoạn tương đương.
* Nếu khoảng gồm 1, 5, hoặc 10 lần giá trị ý nghĩa nhất thì chia miền thành 5 đoạn tương đương.
* Ví dụ: 
* Sinh kiến trúc khái niệm dữ liệu phân loại
* Đặc tả một thứ tự bộ phận giá trị thuộc tính theo mức sơ đồ do người dùng hoặc chuyên gias
* street<city<state<country
* Đặc tả thành cấu trúc phân cấp nhờ nhóm dữ liệu
* {Urbana, Champaign, Chicago}<Illinois
* Đặc tả theo tập các thuộc tính.
* Tự động sắp xếp một phần bằng cách phân tích số lượng các giá trị khác biệt
* Như, street < city <state < country
* Đặc tả một phần thứ tự bộ phận
* Như, chỉ street < city mà không có cái khác
### 4. Thách thức dữ liệu
- Thiếu dữ liệu
- Dữ liệu không đại diện
- Chất lượng dữ liệu kém
- Đặc trưng không liên quan
#### a. Thách thức mô hình:
- Quá khớp DL học:
- Mô hình quá tốt với dữ liệu mẫu (xây dựng mô hình) song cho độ hiệu quả thấp khi sử dụng mô hình do không khái quát tốt
- Overfitting: 
- Giải pháp
- Đơn giản hóa mô hình: (i) giảm tham số mô hình, (ii) giảm số đặc trưng (chiều) dữ liệu, (iii) hạn chế phạm vi mô hình
- Thu thập thêm dữ liệu đào tạo
- Giảm nhiễu dữ liệu (sửa lỗi dữ liệu, xóa ngoại lệ)
- Chính quy hóa mô hình: khống chế siêu tham số
- 
- Không khớp DL học:
- Đối ngẫu với quá khớp: độ chính xác mô hình thấp
- Nâng bậc mô hình: bổ sung tham số
- Nâng cấp làm tốt đặc trưng dữ liệu
- Giảm ràng buộc đối với các tham số mô hình
- Underfitting: 
- Dùng một kỹ thuật
- Giải pháp: Kết hợp nhiều kỹ thuật
- Thiên vị và công bằng trong KPDL
- Thiên vị bị ẩn/bị bỏ qua ở dữ liệu/thuật toán
- Công bằng
- Phát triển các giải pháp cho công bằng
- Thiên vị từ dữ liệu tới thuật toán:
- Đo lường: chọn, dùng và đo lường các đặc trưng
- Bỏ qua biến: bỏ qua biến quan trọng
- Đại diện: Thiếu đa dạng quần thể, thiếu nhóm nhỏ, điểm bất thường
- Tổng hợp: Kết luận sai về cá thể khi quan sát toàn bộ dân số
- Lấy mẫu: (~ đại diện) mẫu không ngẫu nhiên trong các nhóm con
- Sai lầm dữ liệu dài hạn: Dữ liệu thời gian bị phân tích cắt ngang
- Liên kết: Thể hiện sai hành vi thực sự của người dùng trong mạng
- Thiên vị từ thuật toán tới nguòi dùng:
- Thuộc về thuật toán: Do lựa chọn thiết kế TT (sử dụng hàm tối ưu hóa, chính quy hóa, dùng hồi quy trên toàn bộ dữ liệu, v.v.)
- Tương tác người dùng: Giao diện người dùng và hành vi người dùng thiên vị
- Phổ biến: Phổ biến hơn sẽ được thiên vị hơn
- Mới nổi: Thay đổi dân số, ví dụ công cụ tìm kiếm, v.v.
- Đánh giá: Tiêu chuẩn bất đối xứng đánh giá mô hình
- Từ người dùng tới dữ liệu:
- lịch sử: đã tồn tại và các vấn đề kỹ nghệ xã hội
- dân số: độ đo thống kê, nhân khẩu học, v.v.  nhóm mục tiêu
- Tự lựa chọn:
- Xã hội: ảnh hưởng từ người khác
- Hành vi: hành vi khác nhau trên các nền tảng khác nhau
- Thời gian: từ khác biệt theo thời gian dân số và hành vi
- Tạo nội dung: Cấu trúc/từ vựng/ngữ nghĩa, v.v.

## Chương 4: Khai phá luật kết hợp

### 1. Khai phá luật kết hợp (Association rule)
* Bán chéo
* cross-selling
* Bán chéo: bán các mặt hàng bổ sung cho khách hàng hiện tại.
* Sản phẩm thường được mua cùng nhau
* “Mẫu phổ biến”, “luật kết hợp”
* Bán tăng
* up-selling (deep-selling: bán sâu)
* bán các mặt hàng giá cao hơn: nâng cấp – bổ sung tiện ích, v.v.
* khách hàng ưa mẫu mới
* Phát hiện sở thích khách hàng
* Bán sâu
* deep-selling
* bán một mặt hàng với lượng nhiều hơn: nên mua loại gói to hơn, nên mua thêm cho người thân
* Phát hiện sở thích khách hàng
* Cơ sở dữ liệu giao dịch (transaction database)
* Tập toàn bộ các mục $I = \{i_1, i_2, …, i_k\}$ “tất cả các mặt hàng”.
* Một giao dịch $T$ là một tập con của I: $T \subseteq I$. Giao dịch: danh sách các mục (mục: item, mặt hàng) trong một phiếu mua hàng.
* CSDL giao dịch $𝐷=\{𝑇:T\subseteq I \}$, Mỗi giao dịch $T$ có một định danh là $T_{ID}$.
* $A$ là một tập mục $A \subseteq I$ và $T$ là một giao dịch: Gọi $T$ chứa $A$ nếu $A \subseteq T$.
* Tập mục (mẫu) phổ biến (frequent itemset)
* Đỗ hỗ trợ (support) tập mục $A$:$𝑠(𝐴)=|\{𝑇∈𝐷:A \subseteq T\} |$ (giai đoạn đầu)
* Ngày nay $s(𝐴)= \frac{|{𝑇∈𝐷:A \subseteq T}|}{|𝐷|}$ là “xác suất xuất hiện A trong CSDL D”.
* Cho trước độ hỗ trợ tối thiểu $𝑠_𝑜>0$, tập mục $A$ là tập mục phổ biến nếu $s(𝐴)≥𝑠_𝑜$; khi đó A cũng được gọi là một “mẫu phổ biến”
* “các mặt hàng thường được mua cùng nhau”
* Luật kết hợp (association rules)
* 
* Luật mạnh
* 
* Khai phá dữ liệu kết hợp
* Mẫu phổ biến và luật mạnh
#### a. Khai phá mẫu phổ biến và khai phá luật kết hợp
* Nền tảng của nhiều bài toán KPDL bản chất
* Kết hợp, tương quan, nhân quả
* Mẫu tuần tự, kết hợp thời gian hoặc vòng, chu kỳ bộ phận, kết hợp không gian và đa phương tiện
* Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích tụ (nén dữ liệu ngữ nghĩa)
* Ứng dụng rộng rãi
* Ví dụ: Phân tích DL bóng rổ, tiếp thị chéo (cross-marketing), thiết kế catalog, phân tích chiến dịch bán hàng
* Phân tích Web log (click stream), Phân tích chuỗi DNA v.v.
* Khai phá mẫu phổ biến: FIM
* 
* Khai phá luật kết hợp mạnh: SRM
* 
#### b. **Apriori**
* Khái quát: Khai phá luật kết hợp gồm hai bước:
* Tìm mọi tập mục phổ biến: theo min-sup
* Sinh luật mạnh từ tập mục phổ biến
* Nguyên lý tỉa Apriori: Với tập mục không phổ biến thì không cần phải sinh ra/kiểm tra mọi tập bao nó!
* Trong thuật toán, các tên mục $i_1, i_2, … i_n (n = |I|)$ được sắp xếp theo một thứ tự cố định (thường được đánh chỉ số $1, 2, ..., n$).
* Phương pháp: Quy hoạch động theo độ dài tập mục
* 
* 
* 
* 
* Sinh luật kết hợp:
* 
* Tính độ hỗ trợ ứng viên (lệnh 4-8):
* Số lượng ứng viên là rất lớn
* Một giao dịch chứa nhiều ứng viên
* Phương pháp: sử dụng cây băm ứng viên
* Tập các tập mục ứng viên được chứa trong một cây-băm (hash-tree)
* Lá của cây băm chứa một danh sách ứng viên và bộ đếm (độ hỗ trợ hiện thời của ứng viên đó)
* Nút trong chứa bảng băm: theo tập các mục  I
* Hàm tập con: tìm ứng viên trong tập ứng viên
* 

### 2. Các thuật toán khai phá vô hướng luật kết hợp (giá trị lôgic đơn chiều) trong CSDL giao dịch
### 3. Khai phá kiểu đa dạng luật kết hợp/tương quan
### 4. Khai phá kết hợp dựa theo ràng buộc
### 5. Khai phá mẫu dãy