Khai phá dữ liệu là gì?

Report





Khai phá dữ liệu là gì?
Khai phá dữ liệu và kho dữ liệu.
Khai phá dữ liệu và khai phá tri thức.
Mục tiêu của khai phá dữ liệu và khai phá tri thức.
Một số loại khai phá tri thức dùng cho khai phá dữ
liệu.

Là quá trình khám phá (rút trích) các tri thức mới
và các tri thức có ích ở dạng tiềm ẩn trong lượng
lớn dữ liệu được lưu trữ trong các CSDL, kho dữ
liệu….

Mục tiêu của kho dữ liệu là hỗ trợ trong quá trình ra
quyết định.

Khai phá dữ liệu được dùng kết hợp với kho dữ liệu giúp
cho quá trình ra quyết định được chắc chắn hơn.

Khai phá dữ liệu có thể được ứng dụng trong hoạt động
của cơ sở dữ liệu nhưng để có hiệu quả hơn thì nó
được dử dụng với kho dữ liệu.

Những ứng dụng của khai phá dữ liệu được suy nghĩ
trước trong quá trình thiết kế kho dữ liệu.

Khai phá dữ liệu là một bước của quá trình khai phá tri
thức (Knowledge Discovery Process).

Tiến trình khai phá dữ liệu (KDD: Knowledge Discovery
in Database) bao gồm 6 giai đoạn:
Chọn dữ liệu (data selection).
Làm sạch dữ liệu (data cleaning).
Làm giàu dữ liệu (enrichment).
Chuyển đổi dữ liệu hoặc mã hóa (data transformation or
encoding ).
5. Khai phá dữ liệu (data mining).
6. Báo cáo và trình bày dữ liệu khai thác
1.
2.
3.
4.






Ví dụ: Để duy trì thông tin của cửa hàng chuyên bán lẻ hàng tiêu dùng.
Thông tin khách hàng gồm: Tên, zip code, số điện thoại, ngày giao
dịch, mã item(item code), giá, số lượng và tổng số lượng hàng mua.
Chọn item là những item đặc biệt, hay những loại item thuộc vùng miền
của quốc gia.
Làm sạch dữ liệu: sẽ loại bỏ những số điện thoại có mã vùng sai, hoặc
những zip code không hợp lệ.
Làm giàu thông tin: thêm vào mỗi record những thông tin : tuổi, thu
nhập,mức độ tin cậy.
Chuyển đổi dữ liệu: việc nhóm các sản phẩm theo các loại như : audio,
video, camera, thiế bị điện tử,…
Khai thác dữ liệu áp dụng những luật và mẫu:
◦ Luật kết hợp: khi người dùng mua sản phẩm x sẽ có nhu cầu mua
sản phẩm Y.
◦ Mẫu liên tục: nếu người dùng mua một máy camera trong vòng 6
tháng người đó sẽ có nhu cầu mua một số đồ phụ tùng thay thế.
◦ Phân loại dựa trên cây: thẻ tín dụng khách hàng, tiền mặt khách
hàng…
Envalution of Rule
Data Mining
Transformation
Cleansing Pre-processing
Preparation
Knowledge
Pattern
Discovery
Selection
Transformed
Data
Gathering
Cleansed
Preprocessed
Target
Data
Data
Preparated

Dự đoán – Sử dụng một vài biến để dự báo giá trị chưa
biết hoặc giá trị tương lai của các biến khác.
◦ Ví dụ: những mẫu về sóng địa chấn và động đất được dự đoán
với xác xuất cao.

Sự nhận dạng- các mẫu dữ liệu có thể được sử dụng để
xác định sự tồn tại của một mục, sự kiện, hoặc một hoạt
động.
◦ Ví dụ: xác định sự tồn tại của một gen trong chuỗi DNA.

Sự phân lớp- khai phá dữ liệu có thể phân vùng dữ liệu
dựa phát hiện ra mô tả của vài lớp đã được xác định và
phân loại dữ liệu vào trong các lớp đó.
◦ Ví dụ: khách hàng trong siêu thị có thể phân thành: những khách
hàng thường xuyên, những khách hàng thường mua giảm giá,
những khách không thường xuyên mua hàng…

Tối ưu hóa- một trong những mục tiêu cuối cùng của
khai phá dữ liệu là có thể tối ưu hóa việc sử dụng các
nguồn tài nguyên hạn chế như: thời gian, không gian,
tiền bạc, hoặc nguyên vật liệu.

Tri thức( Knowledge) được phân loại theo tri thức qui
nạp và diễn dịch.

Tri thức qui nạp (Inductive knowledge): khám phá các
mẫu và các luật mới từ dữ liệu sẵn có.

Tri thức được biễu diễn nhiều dạng: không có cấu trúc,
có cấu trúc( cây quyết định, mạng ngữ nghĩa, mạng
nơron), dạng luật, mệnh đề logic.

Tri thức được khai phá trong quá trình khai thác dữ liệu
có thể mô tả 5 cách:
Luật kết hợp- mối tương quan về sự hiện diện việc thiết
lập các bộ thông qua sắp xếp các giá trị khác nhau cho
các biến khác nhau.
1.
◦
Ví dụ: Khi một khách nữ mua một túi xách tay, cô ấy cũng thích
mua giày.
Hệ thống phân loại- mục tiêu từ các sự việc hoặc các
giao dịch tạo ra hệ thống các lớp.
2.
◦
Ví dụ: Về con người có thể chia làm 5 nhóm dựa theo mức độ
tin cậy theo những sự giao dịch trước đó.
3.
◦
4.
◦
5.
◦
Mẫu liên tục- chuỗi những hành động hoặc sự việc.
Ví dụ: nếu bệnh nhân trải qua ca phẫu thuật tim dành cho khối
động mạch và chứng phình mạch và sau đó lại phát triển sang
tăng lượng ure trong máu sau 1 năm phẫu thuật, bệnh nhân đó có
thể sẽ phải chịu quả thận hư trong vòng 6 tháng tới.
Chuỗi mẫu thời gian- sự tương tự có thể được tìm thấy
trong với mốc của chuỗi thời gian.
Ví dụ: mẫu về sức gió hệ mặt trời có thể dùng dự đoán sự thay
đổi khí hậu ở trái đất.
Sự phân loại và sự phân đoạn- phân chia mật độ dân số của
các sự kiện hay các item tương tự yếu tố.
Ví dụ: Người trưởng thành ở Mỹ chia thành năm loại từ “thích
mua” cho đến “ không thích mua” sản phẩm mới.

Luật kết hợp.

Các thuật toán cơ bản dựa trên luật kết hợp.

Luật kết hợp nằm trong Hệ phân cấp.

Mối kết hợp phủ định.

Cân nhắc việc bổ sung các luật kết hợp.




Khai thác luật kết hợp là một tiến trình quan trọng trong
khai thác dữ liệu, mục đích của nó là tìm ra các luật tiềm
ẩn trong CSDL.
Luật kết hợp dựa trên hình thức X => Y. Trong đó
X = {x1, x2, …., xn} và Y = {y1, y2, …, ym} , xi, yj là những
hạng mục(item) riêng biệt cho tất cả i, j.
Đó là mối kết hợp nếu một khách hàng mua X, người đó
cũng sẽ có mua Y. Hình thức LHS (left-hand side), RHS
(righthand side).
Thiết lập LHS  RHS được gọi là tập các hạng mục
(itemset).

Các phương pháp cần quan tâm:
1. Độ phổ biến (prevalence)- luật LHS => RHS là phần
trăm giao dịch giữa tất cả các hạng mục trong mối
kết hợp.
2. Độ tin cậy (strenght)- luật LHS => RHS là % (phân
số) của tất cả giao dịch chứa các hạng mục trong
LHS và cả hạng mục trong RHS.

Độ tin cậy ước tính là độ phổ biến (LHS  RHS) / hỗ
trợ(LHS) .

Ví dụ:
Tid
101
203
305
792

time
6:35
7:38
8:05
8:40
Items
milk, bread cookies, juice
milk, juice
milk, eggs
bread, cookies, coffee
Xem xét 2 luật milk=> juice và bread =>juice.
◦
◦
◦
◦
Độ phổ biến {milk, juice} is 50%
Độ phổ biến {bread, juice} is 25%
Độ tin cậy của milk  juice is 66.7%
Độ tin cậy của Bread  juice is 50%

Mục tiêu luật kết hợp là phát sinh ra các luật có thể vượt
qua ngưỡng của mức hỗ trợ.

Vấn đề của luật kết hợp vì vậy cũng được chia làm 2
vấn đề phụ:
◦ Phát sinh các hạng mục vượt qua ngưỡng. Những hạng mục đó
được gọi là hạng mục lớn.
◦ Đối với mỗi hạng mục lớn, tất cả luật có độ tin tưởng nhỏ được
phát sinh sau:
 Để có hạng mục lớn X và Y  X, sao cho Z= X-Y; khi đó nếu mức hỗ trợ (X)/
mức phổ biến(Y)  độ tin cậy nhỏ nhất, luật Z => Y (i.e X - Y =>Y) là luật hợp
lệ.

Hiện nay các thuật toán tìm các hạng mục lớn được
thiết kế để làm những việc sau:
1.
Kiểm tra mức độ hỗ trợ của hạng mục có chiều dài là 1, gọi là 1itemsets, bằng cách quét toàn bộ cơ sở dữ liệu. Bỏ qua những thành
phần có mức hỗ trợ thắp hơn so yêu cầu.
2.
Mở rộng 1-itemsets thành 2-itemsets bằng cách thêm vào một item
cho mỗi phần, để tạo ra các ứng viên hạng mục có chiều dài là 2
.Kiểm tra mức hỗ trợ của các ứng viên hạng mục bằng cách quét vào
cơ sở dữ liệu và loại ra những hạng mục không đáp ứng độ phổ biến.
3.
Lặp lại bước trên; tới bước k, các tập ứng cử viên được xác định dựa
vào các tập mục lớn đã xác định tại vòng k – 1.
4. Quá trình xác định các tập mục sẽ kết thúc khi không xác định
được thêm tập mục lớn nào nữa.

Một số thuật toán thường gặp:
◦
◦
◦
◦
Thuật toán Apriori.
Thuật toán Sampling.
Thuật toán cây Frequent-pattern.
Thuật toán Phân vùng.


Đó là những loại kết hợp đặc biệt được chú ý vì những lí
do đặc biệt.
Những mối kết hợp xảy ra trong hệ thống cấp bậc của
những mẫu tin. Điển hình, nó có thể chia các mẫu tin
trong đó hệ phân cấp độc lập dựa trên tính chất tự nhiên
của miền giá trị.
◦ Ví dụ: thức ăn trong siêu thị những hạng mục trong cùng một
tầng hay quần áo trong một tiệm đồ thể thao đều có thể được
phân loại theo lớp hoặc phân lớp.

Vấn đề đây là khai thác mối kết hợp phủ định thì khó
hơn so với khai thác mối kết hợp ngẫu nhiên.

Một phủ định mối kết hợp được hiểu :”60% khách hàng
mua khoai tây chiên mà không mua nước uống” .(Ở đây,
60% tương ứng với độ tin cậy dành cho luật phủ định
mối kết hợp.)

Đối với nguồn dữ liệu rất lớn, một cách để khai thác hiệu
quả đó là lấy theo mẫu.

Nếu mẫu tiêu biểu thể hiện được tất cả các đặc tính
trong dữ liệu gốc, khi đó hầu hết các luật có thể được
thiết lập dựa trên dữ liệu mẫu đó. Một trong số thuật
toán đề xuất tìm ra dữ liệu mẫu là nguyên tắc phân loại,
nguyên tắc kết hợp hoặc các mô hình dữ liệu tuần tự,. v.v.

Đây là tiến trình có tìm ẩn nguy cơ khi khám phá một số
hạng mục sai( hạng mục lớn thì thật sự không lớn) cách
tốt nhất bỏ qua các phủ định sai ở một số hạng mục lớn
và tương ứng một số luật kết hợp.

Khám phá luật kết hợp trong cơ sở dữ liệu thực
rắc rối do các yếu tố:
◦ Trong một số trường hợp tập hợp con của các hạng mục thì vô cùng
lớn, và số lượng của các giao tác là rất cao.

Hoạt động của các cơ sở dữ liệu cửa hàng bán lẻ tập hợp thông tin trao đổi
của các quốc gia lên đến hàng chục triệu mỗi ngày.
◦ Các giao tác biểu thị tính thay đổi trong các nhân tố liên quan vị trí địa lí
và các mùa, làm mẫu phức tạp.
◦ Mẫu của các phân lớp tồn tại dạng đa chiều. Do đó, việc điều khiển tiến
trình khai thác với miền tri thức, đặc biệt những luật phủ định, thì cực kì
khó.
◦ Đặc trưng của dữ liệu là có thể thay đổi; vấn đề quan trọng tồn tại việc
bỏ qua, không đúng, trùng lắp, được xem như là dữ liệu thừa ở nhiều
quốc gia.

Ví dụ:
◦ Việc kiểm tra dữ liệu là mẫu máu với thuộc tính như hemoglobin, đếm tế
bào máu đỏ, tế bào màu trắng, tỉ lệ đường trong máu, ure, tuổi của bệnh
nhân, và vân vân. Mỗi thuộc tính có thể chia thành loại, và sự có mặt của
thuộc tính với một giá trị khác nhau có thể được cho là một mẫu.
◦ Vì vậy, nếu thuộc tính hemoglobin được chia loại: 0-5, 6-7, 8-9,10-12,1314 và trên 14, khi đó chúng sẽ tương ứng là những mẫu H1, H2, H3,…,
H7. Một giá trị hemoglobin của bệnh nhân sẽ một trong 7 mẫu có sẵn
trên.

similar documents