Bài giảng Nhập môn Khai phá dữ liệu

Các vấn đề chính trong KPDL

Một số ứng dụng điển hình

Công nghệ KPDL điển hình

Kiểu mẫu được khai phá

Kiểu dữ liệu trong KPDL KPDL và xử lý CSDL truyền thống Khái niệm KPDL và phát hiện tri thức trong CSDL Nhu cầu của khai phá dữ liệu (KPDL)

Nội dung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI 09-2015 PGS. TS. HÀ QUANG THỤY

PHÁ DỮ LIỆU CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ KHAI

BÀI GIẢNG NHẬP MÔN KHAI PHÁ DỮ LIỆU

03/02/17

 Phiên bản 18 tháng: rút ngắn chu kỳ thời gian

 Chi phí sản xuất mạch bán dẫn với cùng tính năng giảm một nửa sau hai năm

năm

 Số lượng bán dẫn tích hợp trong một chíp sẽ tăng gấp đôi sau khoảng hai

 “Phương ngôn 2x

circuits, Electronics, 38 (8), April 19, 1965. Một quan sát và dự báo

 Gordon E. Moore (1965). Cramming more components onto integrated

 Xuất xứ

Bùng nổ dữ liệu: Luật Moore

 Phát hiện tri thức từ dữ liệu  Kinh tế tri thức

 Ngành kinh tế định hướng dữ liệu

 Thể hiện  Lý do xã hội  Lý do công nghệ  Sự bùng nổ dữ liệu

1. Nhu cầu về khai phá dữ liệu

03/02/17

Conference (ISSCC), February 2003.

h, accessed January 9, 2008.)

the International Solid-State Circuits

www.intel.com/technology/mooreslaw/?iid=searc

Speaking of extending Moore’s Law at

by Intel Innovation,

Chairman Emeritus

the Board

(Source: Intel Web site Moore’s Law: Made Real

end to creativity”. Gordon Moore, Intel

straightforward...There is certainly no

chip double about every two years.

“Another

decade

probably

Moore’s Law: Transistor densities on a single

Luật Moore: Bộ xử lý Intel

và công nghệ mạng (truyền dẫn dữ liệu)

 Tác động tới sự phát triển công nghệ cơ sở dữ liệu (tổ chức và quản lý dữ liệu)  Bùng nổ về năng lực xử lý tính toán và lưu trữ dữ liệu.

năm qua (trang tiếp theo).

 Định luật Moore với công nghiệp phần cứng máy tính: bộ xử lý Intel trong 40  Công nghệ bán dẫn là nền tảng của công nghiệp điện tử.

 Thúc đẩy công nghệ xử lý, lưu giữ và truyền dẫn dữ liệu

công nghệ tiên tiến, Acorn Technologies, Inc. (http://acorntech.com/) đôi vai của chuỗi các nhà phân phối sản phẩm”. Daniel Grupp, Giám đốc PT làm. Nếu bị tụt sau định luật Moore, không có gì để mua, và gánh nặng đè lên Moore, thị trường không thể hấp thụ hết các sản phẩm mới, và kỹ sư bị mất việc là có tính bền vững khi tuân theo định luật Moore… Nếu đánh bại định luật  “toàn bộ chu trình thiết kế, phát triển, sản xuất, phân phối và bán hàng được coi

Giám đốc điều hành Tập đoàn Intel Nó cũng là cách sử dụng sáng tạo mạch bán dẫn”. Paul S. Otellini, Chủ tịch và nó vẫn còn hiệu lực tốt tại Intel… Định luật Moore không chỉ là mạch bán dẫn.  “Định luật Moore vẫn tạo khả năng cơ bản cho sự phát triển của chúng tôi, và  Mô hình cơ bản cho ngành công nghiệp mạch bán dẫn

 Dẫn dắt ngành công nghệ bán dẫn

Luật Moore & công nghiệp điện tử

03/02/17

 Bắt đầu hoạt động 2016. Sau 5 ngày sẽ có 140 TB

 Large Synoptic Survey Telescope

 Kính viễn vọng kế tiếp

 Vài tuần đầu tiên: thu thập dữ liệu thiên văn học = toàn bộ

 Làm việc từ 2000

 Kính viễn vọng đầu tiên

hơn 120.000 quasar

 Đã tạo bản đồ 3-chiều có chứa hơn 930.000 thiên hà và  http://www.sdss.org/  Sloan Digital Sky Survey

 Một ví dụ điển hình: SDSS  Mọi lĩnh vực Quản lý, Thương mại, Khoa học…  Thiết bị số hóa đa dạng

 Năng lực số hóa

Thiết bị thu thập – lưu trữ dữ liệu

Giá trị, cách đọc các bội và ước điển hình

Hệ thống ước và bội đơn vị đo

trong quá khứ. Sau 10 năm: 140 TB

03/02/17

và Phân tích dữ liệu mở rộng (có KPDL)

 Tiến hóa công nghệ CSDL [HKP11]: Hệ CSDL mở rộng

Tiến hóa Công nghệ CSDL: năm 2011

KDL & KPDL, Hệ CSDL dựa trên Web

 Tiến hóa công nghệ CSDL [HK0106]: Hệ CSDL mở rộng,

Tiến hóa Công nghệ CSDL: năm 2006

03/02/17

 Nguồn: http://www.worldwidewebsize.com/

trang Web được đánh chỉ số (04/09/2013)

 13 tỷ rưỡi trang web được đánh chỉ số (ngày 23/01/2011). Ít nhất có 4,2 tỷ

 Web

 2010: 20.396 PB/tháng, 2009-2014: tăng trung bình hàng năm 34%

 Nguồn: Sách trắng CISCO 2010

 Tổng lượng giao vận IP trên mạng

Bùng nổ dữ liệu: Công nghệ mạng

 dung lượng CSDL YouTube tăng gấp đôi sau mỗi chu kỳ 5 tháng  Sau hai năm: hàng trăm triệu video

 YouTube

 http://www.nersc.gov/news/annual_reports/annrep0809/annrep0809.pdf  tháng 3/2010: khoảng 460 TB  National Energy Research Scientific Computing Center: NERSC quốc gia Mỹ

 Trung tâm tính toán khoa học nghiên cứu năng lượng

 Tốp 10 CSDL lớn nhất

Công nghệ CSDL: Một số CSDL lớn

Data Centre for Climate bản ghi viễn thông; Google: 90 triệu tìm kiếm/ngày; AT&T: 310TB; World xem hàng ngày; ChoicePoint: 75 lần Trái đất – Mặt trăng; Sprint: 70.000 sách, 55 triệu người dùng, 40TB; YouTube: hàng trăm triệu clip được 100 “hồ sơ: thống kê dân số, bản đồ…” hàng tháng; Amazon: 250 nghìn  Library of Congress: 125 triệu mục; Central Intelligence Agency (CIA):  http://top-10-list.org/2010/02/16/top-10-largest-databases-list/ (04/9/13)

03/02/17

 Đạt 35 ZB vào năm 2020

 Độ dốc tăng càng cao

 Dung lượng tổng thể tăng

 0,5 xu Mỹ/1 GB vào năm 2009 giảm tới 0,02 xu Mỹ /1 GB vào năm 2020

 Chiều hướng giá tạo mới dữ liệu giảm dần

 Giá tạo dữ liệu ngày càng rẻ hơn

 Nguồn: IDC Digital Universe Study, sponsored by EMC, May 2010

Bùng nổ dữ liệu: Giá thành và thể hiện

Universe Study, sponsored by EMC, May 2010

 2010: 900 EB do người dùng tạo (trong 1260 EB tổng thể). Nguồn: IDC Digital  Mạng xã hội Facebook chứa tới 40 tỷ ảnh  Hệ thống trực tuyến người dùng, Mạng xã hội…  Phần tạo mới dữ liệu của người dùng ngày càng tăng

 Mở rộng tác nhân tạo dữ liệu

Bùng nổ dữ liệu: Tác nhân tạo mới

03/02/17

quản lý”. http://www.economist.com/node/15557443?story_id=15557443

có giá trị kinh tế, cung cấp những hiểu biết mới vào khoa học và tạo ra lợi ích từ

Được quản lý tốt, dữ liệu như vậy có thể được sử dụng để mở khóa các nguồn mới

xu hướng kinh doanh, ngăn ngừa bệnh tật, chống tội phạm …

khả năng làm được nhiều việc mà trước đây không thể thực hiện được: nhận ra các

“Thông tin từ khan hiếm tới dư dật. Điều đó mang lại lợi ích mới to lớn… tạo nên



 Kenneth Cukier,

thập kỷ gần đây” [HK0106].

vực làm cho nó trở nên khó khăn để nắm bắt những tiến bộ phi thường trong vài hóa, trí tuệ nhân tạo, và học máy đang đóng góp cho lĩnh vực này. Bề rộng của lĩnh cứu cơ sở dữ liệu. Các nhà nghiên cứu trong lĩnh vực bao gồm thống kê, trực quan Đây là một trong những lĩnh vực năng động và thú vị nhất của cộng đồng nghiên dẫn các dị thường. động tóm tắt nó, tự động phát hiện và mô tả các xu hướng trong nó, và tự động chỉ Vì vậy, chúng ta phải tìm cách tự động phân tích dữ liệu, tự động phân loại nó, tự xét dữ liệu như vậy. Sự chú ý của con người đã trở thành nguồn tài nguyên quý giá. dữ liệu tài chính, và các dữ liệu tiếp thị. Con người không có đủ thời gian để xem  “Chúng ta đang ngập trong dữ liệu khoa học, dữ liệu y tế, dữ liệu nhân khẩu học,

 Jim Gray, chuyên gia của Microsoft, giải thưởng Turing 1998

Nhu cầu thu nhận tri thức từ dữ liệu

 Nguồn: IDC Digital Universe Study, sponsored by EMC, May 2010.  Lực lượng nhân lực CNTT tăng 1,4 lần  Dung lượng thông tin tăng 67 lần, đối tượng dữ liệu tăng 67 lần  Bùng nổ dữ liệu với tăng trưởng nhận lực CNTT

Nhu cầu nắm bắt dữ liệu

03/02/17

Economic Growth, IBM Corporation, 2006

Jim Spohrer (2006). A Next Frontier in Education, Employment, Innovation, and

 Quản lý: tác động tới toàn bộ quy trình thi hành dịch vụ

 Kỹ nghệ: tri thức  dịch vụ

 Khoa học: dữ liệu & thông tin  tri thức

 Dịch vụ: dữ liệu & thông tin  tri thức  giá trị mới

 Đơn vị trao đổi trong kinh tế và xã hội là dịch vụ  Mọi nền kinh tế là 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ụ.

 Kinh tế dịch vụ

Kinh tế dịch vụ: Từ dữ liệu tới giá trị

Lao động dịch vụ vượt lao động nông nghiệp (2006).

 Sử dụng tri thức là động lực chủ chốt cho tăng trưởng kinh tế  Tri thức là tài nguyên cơ bản

 Kinh tế tri thức

Kinh tế tri thức

Productivity (The World Bank. Korea as a Knowledge Economy, 2006) Hàn Quốc gấp đôi so với đóng góp của lao động và vốn. TFP: Total Factor  Hình vẽ: Năm 2003, đóng góp của tri thức cho tăng GDP/đầu người của

03/02/17

 Data Mining là một bước trong quá trình KDD

 KDD và KPDL: tên gọi lẫn lộn? theo hai tác giả|Khai phá dữ liệu

liệu ẩn, chưa biết và hữu dụng tiiềm năng) từ một tập hợp lớn dữ

 Trích chọn các mẫu hoặc tri thức hấp dẫn (không tầm thường,

 Knowledge discovery from databases

2. Khái niệm KDD và KPDL

v%e1%bb%81-c%c6%a1-h%e1%bb%99i-trong-nganh-th%e1%bb%91ng-ke-va-khmt/ http://www.procul.org/blog/2009/07/03/t%e1%ba%a3n-m%e1%ba%a1n- (và

của Nguyễn

KHMT)

Xuân

Long

ngày

03/7/2009.  Tham khảo bài trao đổi “Tản mạn về cơ hội trong ngành Thống kê

nhân” dữ liệu. Mỹ có chuẩn quy định chức năng

lập trình + nhà thống kê + “nghệ

 Người phân tích dữ liệu: người  CIO và chuyên gia phân tích dữ liệu có vai trò ngày càng cao

 Nhân lực khoa học dữ liệu

 Tổng hợp của Kenneth Cukier

phân tích dữ liệu

 vài năm gần đây các tập đoàn lớn chi khoảng 15 tỷ US$ mua công ty  Tăng 10% hàng năm, gần gấp đôi kinh doanh phần mềm nói chung  Đáng giá hơn 100 tỷ US$ vào năm 2010  “Chúng ta nhập trong dữ liệu mà đói khát tri thức”  Ngành công nghiệp quản lý và phân tích dữ liệu

Ngành kinh tế định hướng dữ liệu

03/02/17

 Sử dụng tri thức phát hiện được

 Trực quan hóa, chuyển dạng, loại bỏ các mẫu dư thừa, v.v.

 Đánh giá mẫu và trình diễn tri thức

 Bước KPDL: tìm mẫu hấp dẫn

 Chọn (các) thuật toán KPDL

 Tóm tắt, phân lớp, hồi quy, kết hợp, phân cụm.

 Chọn lựa chức năng (hàm) KPDL

 Tìm các đặc trưng hữu dụng, rút gọn chiều/biến, tìm các đại diện bất biến.

 Thu gọn và chuyển đổi dữ liệu  Chuẩn bị dữ liệu và tiền xử lý: (huy động tới 60% công sức!)  Khởi tạo một tập dữ liệu đích: chọn lựa dữ liệu

 Tri thức sẵn có liên quan và mục tiêu của ứng dụng

 Học từ miền ứng dụng

Các bước trong quá trình KDD

and Data Mining 1996: 1-34 Data Mining to Knowledge Discovery: An Overview, Advances in Knowledge Discovery [FPS96] Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth (1996). From

Quá trình KDD [FPS96]

Đánh giá và

03/02/17

(1998). A Perspective on Data Mining, Technical Reporrt, Northern Arizona University.

 [CCG98] Kenneth Collier, Bernard Carey, Ellen Grusy, Curt Marjaniemi, Donald Sautter

 Lặp kiểu vòng đời phát triển phần mềm

 Kết quả thi hành được: xác định tập kết quả thi hành được dựa trên các mô

 Định hướng kinh doanh: Xác định 1-3 câu hỏi hoặc mục đích hỗ trợ đích KDD

 Một mô hình cải tiến quá trình KDD

Mô hình quá trình KDD lặp [CCG98]

 Hệ chuyên gia hoặc chương trình học máy/thống kê nhỏ  Xử lý truy vấn suy diễn.

 Phân biệt: Phải chăng mọi thứ là DM?

 …  Thông minh doanh nghiệp (business intelligence -BI)  Phân tích/xử lý mẫu/dữ liệu (data/pattern analysis/processing)  khai quật/nạo vét dữ liệu (data archaeology/ dredging),  thu hoạch thông tin (information harvesting),  phát hiện thông tin (information discovery),  chiết lọc tri thức (knowledge extraction),

 Các tên thay thế

Các khái niệm liên quan

hình được đánh giá

03/02/17

622-634. [Oha09]

process for business intelligence, Industrial Management & Data Systems, 2008. 108(5):

Wang, H. and S. Wang (2008). A knowledge management approach to data mining

Mô hình tích hợp DM-BI [WW08]

 Nguồn: http://www.crisp-dm.org/Process/index.htm (13/02/2011)  CRISP-DM 2.0 SIG WORKSHOP, LONDON, 18/01/2007  Thi hành chỉ sau khi tham chiếu kết quả với “hiểu kinh doanh” for Data Mining). “Hiểu kinh doanh”: hiểu bài toán và đánh giá

 Các pha trong mô hình quy trình CRISP-DM (Cross-Industry Standard Process

 Quy trình chuẩn tham chiếu công nghiệp KPDL

Mô hình CRISP-DM 2000

Chu trình phát triển tri thức thông qua khai phá dữ liệu

03/02/17

Khoa học dữ liệu

về lối sống của họ…? " hành vi không mong muốn? Có cách nào để cho mọi người phản hồi • "Làm thế nào chúng ta có thể sử dụng thông tin để tác động tới các

• Van der Aalst

is not welldefined as an academic subject.

• Data science is an emerging field in industry, and as yet, it

Khoa học dữ liệu

máy móc, nâng cao hiệu quả chúng, và ngăn chặn trục trặc ?“ • Làm thế nào sử dụng toàn bộ thông tin đó để cải thiện quy trình và

03/02/17

 Nếu a*THUNHẬP + b*NỢ < 0

mẫu có giá trị hơn.

không cho vay nợ. huống vay tốt lại bị đưa vào vùng xuống do bao gói thêm các tình lớn hơn) thì độ chân thực giảm

phải (biến THUNHẬP nhận giá trị mẫu "THUNHẬP < $t“ dịch sang  Chẳng hạn, đường biên xác định

hoặc toàn bộ) MC. không gian đo được (bộ phận ngữ biểu diễn mẫu L tới một ánh xạ một biểu thức thuộc ngôn giá trị (chân thực) là một hàm C  Tính "có giá trị" : một độ đo tính có

Tính có giá trị

chân thực nào đấy. trị đối với các dữ liệu mới theo độ  Mẫu được phát hiện: phải có giá

(mô hình chứa một biến THUNHẬP)  Chẳng hạn, biểu thức "THUNHẬP < $t"

 Mẫu: biểu thức E trong ngôn ngữ L 

FE. hơn so với việc liệt kê các sự kiện thuộc F. E được gọi là mẫu nếu nó đơn giản tập con FE tương ứng các sự kiện trong

 Trong KDD: ngôn ngữ L để biểu diễn

 Mẫu

 KDD:phải gồm rất nhiều trường hợp



vào tập sự kiện F, các tập con các sự kiện (dữ liệu) thuộc

 Dữ liệu (tập dữ liệu)

Dữ liệu và Mẫu

kiện). tập F gồm hữu hạn các trường hợp (sự

03/02/17

dẫn I(E,F,C,N,U,S) > i.

người sử dụng nào đó, chỉ ra được một ngưỡng i  Mi mà độ hấp

 Tri thức: Một mẫu E  L được gọi là tri thức nếu như đối với một lớp

 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.

một không gian đo được Mi.

 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

giá trị, mới, hữu ích và dễ hiểu.

 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í

 Tồn tại một số độ đo dễ hiểu:  Khó đo được một cách chính xác: "có thể hiểu được“  dễ hiểu.  KDD: mẫu mà con người hiểu chúng dễ dàng hơn các dữ liệu nền.

 Tính hiểu được: Mẫu phải hiểu được

Tính hiểu được, tính hấp dẫn và tri thức

bộ) MS: s = S(E,F). thức E trong L tới một không gian đo được có thứ tự (bộ phận /toàn  Giả định rằng tính hiểu được là đo được bằng một hàm S ánh xạ biểu dễ dàng để con người nhận thức được theo một tác động nào đó).  Sắp xếp từ cú pháp (tức là cỡ của mẫu theo bit) tới ngữ nghĩa (tức là

quyết định được trình bày trong Hình 1.3. sự tăng lãi của nhà băng (tính theo đơn vị tiền tệ) kết hợp với quy tắc  Ví dụ, trong tập dữ liệu vay nợ, hàm này có thể là sự tăng hy vọng theo

 Hàm U ánh xạ các biểu thức trong L tới một không gian đo có thứ tự động hữu dụng và được đo bởi một hàm tiện ích.

 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

(bộ phận hoặc toàn bộ) MU: u = U (E,F).

 Tổng quát, điều này có thể được đo bằng một hàm N(E,F) hoặc là

độ đo về tính mới hoặc là độ đo kỳ vọng.

 hoặc tri thức: tri thức mới quan hệ như thế nào với các tri thức đã

có.

 sự thay đổi trong dữ liệu: so sánh giá trị hiện tại với giá trị quá khứ

 Tính mới có thể đo được : ít nhất là hệ thống đang được xem xét.

 Tính mới: Mẫu phải là mới trong một miền xem xét nào đó,

Tính mới và hữu dụng tiềm năng

hoặc giá trị kỳ vọng

03/02/17

analytic processing - OLAP).

•

nhận dữ liệu đa chiều do xử lý phân tích trực tuyến (on-line Hiển thị mọi cổ phiếu trong CSDL với mệnh giá tăng ? ghi

•

định thống kê (stastical decision suppport system - DSS) tháng trước ? ghi nhận thống kê do hệ thống hỗ trợ quyết Có bao nhiêu nhà đầu tư nước ngoài mua cổ phiếu X trong

•

transaction processing – OLTP). ghi nhận riêng lẻ do xử lý giao dịch trực tuyến (on-line Hãy hiển thị số tiền Ông Smith trong ngày 5 tháng Giêng ?

Cần có một giả thiết “đầy đủ” về tri thức miền phức tạp!

3. Khai phá dữ liệu và quản trị CSDL

Kiến trúc điển hình hệ thống KPDL

Câu hỏi thuộc hệ quản trị CSDL (DBMS)

03/02/17

Hệ thống CSDL và Hệ thống KPDL

 Những người mua sản phẩm Y có đặc trưng gì ?

không trả được nợ của họ ?  Trong tháng tiếp theo, sẽ có bao nhiêu đoàn viên công đoàn

 Hy vọng gì về cổ phiếu X trong tuần tiếp theo ?

 Tỷ giá US$ - DMark có đặc trưng gì ?

 Các cổ phiếu tăng giá có đặc trưng gì ?

cho hệ thống  Cải tiến (nâng cấp) miền tri thức ! Giả thiết tri thức “đầy đủ” không còn có tính cốt lõi, cần bổ sung tri thức

Khái niệm KPDL: câu hỏi DMS

Câu hỏi thuộc hệ thống khai phá dữ liệu (DMS)

03/02/17

 CSDL Text & WWW

 Dữ liệu không đồng nhất và thừa kế

 Dữ liệu đa phương tiện

 Dữ liệu dòng  Dữ liệu chuỗi thời gian  Dữ liệu không gian và thời gian  CSDL quan hệ-đối tượng

 CSDL mở rộng và kho chứa thông tin  CSDL giao dịch  Kho dữ liệu  CSDL quan hệ

4. KPDL: các kiểu dữ liệu

Bài viết, Files, Nhà cung cấp thông tin, Hệ thống CSDL, OLTP Nguồn dữ liệu OLAP, MDA

(DBA) CSDL trị Quản

Kho DL(Data Warehouses) / KDL chuyên đề (Data Marts)

Phân tích thống kê, Truy vấn và Trả lời Khai thác DL (Data Exploration)

phân tích dữ liệu Chuyên gia

Information Discovery KPDL

Visualization Techniques

tích kinh doanh Chuyên gia phân

Trình diễn DL

Người dùng cuối

doanh Hỗ trợ quyết định kinh Chiều tăng bản chất để

KPDL và Thông minh kinh doanh

quyết định Tạo

03/02/17

database-data-mined.htm http://www.kdnuggets.com/polls/2009/largest-

-miner-salary.html http://www.kdnuggets.com/polls/2010/data

http://www.kdnuggets.com/polls/2010/data-types-analyzed.html Kích thước dữ liệu và lương KPDL

http://www.kdnuggets.com/polls/2010/data-types-analyzed.html Kiểu dữ liệu được phân tích/khai phá

03/02/17



Trees: Theory and Applications. World Scientific Publishing.

 L. Rokach and O. Maimon (2015). Data Mining with Decision

Phân cấp phương pháp KPDL

 Phân tích định hướng mẫu, các bài toán khác  Phát hiện biến đổi và độ lệch  Mô hình phụ thuộc  Hồi quy  Phân cụm  Phân lớp  Quan hệ kết hợp  Mô tả khái niệm

 Các bài toán điển hình

 KPDL dự đoán: phân lớp, hồi quy…  KPDL mô tả: tóm tắt, phân cụm, luật kết hợp…

 Chức năng chung

5. KPDL: Kiểu mẫu được khai phá

03/02/17

 Dự đoán giá trị số chưa biết hoặc đã mất

 Trình diễn: cây quyết định, luật phân lớp, mạng nơron

ô tô dựa theo tiêu tốn xăng

 Chẳng hạn, phân lớp quốc gia dựa theo khí hậu, hoặc phân lớp

niệm cho các lớp hoặc khái niệm để dự đoán trong tương lai  Xây dựng các mô hình (chức năng) để mô tả và phân biệt khái

 Phân lớp và Dự báo

Các bài toán KPDL: Chức năng KPDL

 Quan hệ nội dung trang web với mối quan tâm người dùng  Phát hiện quan hệ ngữ nghĩa

 Ví dụ, trong khai phá dữ liệu Web  Luật kết hợp: XY  Diaper  Beer [0.5%, 75%]  Quan hệ kết hợp giữa các biến dữ liệu: Tương quan và nhân quả)

 Quan hệ kết hợp

 Tóm tắt văn bản  Kỳ vọng, phương sai

 Bài toán mô tả điển hình: Tóm tắt (tìm mô tả cô đọng)

phản, chẳng hạn, các vùng khô so sánh với ướt

 Tổng quát hóa, tóm tắt, phát hiện đặc trưng ràng buộc, tương  Tìm các đặc trưng và tính chất của khái niệm

 Mô tả khái niệm: Đặc trưng và phân biệt

KPDL: Sơ đồ phân loại (Chức năng)

03/02/17

 Phát hiện biến đổi và độ lệch <> tiền xử lý

trị chuẩn, cung cấp tri thức về sự 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á

 Phát hiện biến đổi và độ lệch phân tích các sự kiện hiếm

 Nhiễu hoặc ngoại lệ? Không phải! Hữu dụng để phát hiện gian lận, toàn bộ dữ liệu. Ví dụ, sử dụng kỳ vọng mẫu và phương sai mẫu  Bất thường: đối tượng dữ liệu không tuân theo hành vi chung của

 Phân tích bất thường

 Cực đại tương tự nội bộ cụm & cực tiểu tương tự giữa các cụm

các nhà để tìm mẫu phân bố

 Nhãn lớp chưa biết: Nhóm dữ liệu thành các lớp mới: phân cụm

 Phân tích cụm

KPDL: Sơ đồ phân loại chức năng (2)

 Tính tương tự

dữ liệu miền ứng dụng. hiện được mẫu phân bố "cụm" (lớp mới) để phát  nhóm dữ liệu thành các

 Phân cụm

lớp đã biết liệu vào một trong một số  học một hàm ánh xạ dữ

báo tiếp hiện lớp/khái niệm cho dự hàm dự báo để mô tả/phát  xây dựng/mô tả mô hình/

 Phân lớp

KPDL: Sơ đồ phân loại (Chức năng)

03/02/17

thống kê

 Phân tích định hướng mẫu khác hoặc phân tích

 Phân tích dựa trên tương tự  Khai phá mẫu tuần tự, phân tích chu kỳ  Xu hướng và độ lệch: phân tích hồi quy

 Phân tích xu hướng và tiến hóa

KPDL: Sơ đồ phân loại (Chức năng)

trị số

 mức định lượng: tính phụ thuộc khi sử dụng việc đo tính theo giá

 biến là phụ thuộc bộ phận vào các biến khác  dạng đồ thị  mức cấu trúc:

có ý nghĩa giữa các biến

 xây dựng mô hình phụ thuộc: tìm một mô hình mô tả sự phụ thuộc

 Mô hình phụ thuộc

tập biến độc lập.

 dự đoán giá trị của một/một số biến phụ thuộc vào giá trị của một  điển hình trong phân tích thống kê và dự báo

biến theo một số biến khác

 học một hàm ánh xạ dữ liệu nhằm xác định giá trị thực của một

 Hồi quy

KPDL: Sơ đồ phân loại (Chức năng)

03/02/17

 Bán lẻ, viễn thông, ngân hàng, phân tích gian lận, KPDL sinh học, phân

 Ứng dụng phù hợp

hóa, ….

 Định hướng CSDL, KDL (OLAP), học máy, thống kê, trực quan

 Kỹ thuật được dùng

 Các chức năng phức/tích hợp và KPDL các mức phức hợp

lệch, phân tích bất thường,…

 Đặc trưng, phân biệt, kết hợp, phân lớp, phân cụm, xu hướng/độ

 Tri thức được khai phá

đồng nahats, kế thừa, WWW cực, không gian, chuỗi thời gian, văn bản, đa phương tiện, không

 Quan hệ, KDL, giao dịch, dòng, hướng đối tượng/quan hệ, tích

 Dữ liệu được khai phá

Khung nhìn đa chiều của KPDL

 Kiểu miền ứng dụng

 Kiểu kỹ thuật được dùng

 Kiểu tri thức cần phát hiện

 Kiểu dữ liệu được KP

 Phân loại theo khung nhìn

KPDL: Sơ đồ phân loại (2)

tích thị trường chứng khoán, KP văn bản, KP Web, …

03/02/17

 Sinh ra chỉ các mẫu hấp dẫn—tối ưu hóa câu hỏi khai phá

không hấp dẫn.

 Đầu tiên tìm tổng thể tất cả các mẫu sau đó lọc bỏ các mẫu

 Tiếp cận

 Hệ thống KPDL có khả năng tìm ra đúng các mẫu hấp dẫn?

 Tìm chỉ các mẫu hấp dẫn: Về tính tối ưu

 Kết hợp <> phan lớp <> phân cụm

 Tìm kiếm mày mò (heuristic) <> tìm kiếm đầy đủ

 Hệ thống KHDL có khả năng tìm mọi mẫu hấp dẫn?  Tìm được mọi mẫu hấp dẫn: Về tính đầy đủ

Tìm được tất cả và chỉ các mẫu hấp dẫn?

chẳng hạn, sự không chờ đón, tính mới mẻ, tác động được...  Chủ quan: dựa trên sự tin tưởng của người dùng đối với dữ liệu,

 Khách quan: dựa trên thống kê và cấu trúc của mẫu, chẳng hạn,

 Độ đo hấp dẫn khách quan và chủ quan

dộ hỗ trợ, độ tin cậy, …

 Mẫu là hấp dẫn nếu dễ hiểu, có giá trị theo dữ liệu mới/kiểm tra

 Độ đo hấp dẫn

giả thiết mà người dùng tìm kiếm để xác thực. với độ chắc chắn, hữu dụng tiềm năng, mới lạ hoặc xác nhận các

 Tiếp cận gợi ý: KPDL hướng người dùng, dựa trên câu hỏi, đều hấp dẫn

 KPDL có thể sinh ra tới hàng nghìn mẫu: Không phải tất cả

Mọi mẫu khai phá được đều hấp dẫn?

hướng đích

03/02/17

Hội tụ của nhiều ngành phức [HKP11]

KPDL: Các công nghệ chính

Hội tụ của nhiều ngành phức [HK0106]

6. KPDL: Các công nghệ chính

03/02/17

 Tham khảo thêm từ Nguyễn Xuân Long

 Về thuật ngữ: KPDL: biến ra/biến mục tiêu, thuật toán khai phá

thủ tục thống kê, biến giải thích, quan sát... dữ liệu, thuộc tính/đặc trưng, bản ghi... XLDLTK: biến phụ thuộc,

dữ liệu kiểm tra) được công bố dưới dạng chuẩn. độc lập nhau. Một số trường hợp: hai tập dữ liệu này (hoặc tập

cần "đại diện" cho toàn bộ dữ liệu trong miền ứng dụng và cần Bài toán học KPDL đòi hỏi tập dữ liệu học/tập dữ liệu kiểm tra tham số mô hình không phụ thuộc vào cách chọn tập dữ liệu học. kết quả phải phù hợp với tập toàn bộ dữ liệu -> cần đảm bảo các  Bài toán học khai phá dữ liệu: mô hình chưa có trước. Mô hình

 Phân biệt giữa bài toán thống kê và bài toán khai phá dữ liệu

Thống kê toán học với KPDL

quan tâm đặc biệt.

 Các phương pháp KPDL dựa theo thống kê nhận được sự

khung cảnh phát hiện tri thức tổng thể. biệt đối với mô hình dữ liệu và nắm bắt nhiễu trong một  Hệ thống KDD thường gắn kết với các thủ tục thống kê đặc

Data Analysis) cũng như dự báo [Fied97, HD03].

 Đặc biệt như phân tích dữ liệu thăm dò (EDA: Exploratory

 Nhiều điểm chung giữa KPDL với thống kê:

Thống kê toán học với KPDL

kê có đúng trên toàn bộ dữ liệu quan sát được hay không. được có phù hợp với giả thiết thống kê hay không/ giả thiết thống tập dữ liệu quan sát được. Cần kiểm tra xem tập dữ liệu quan sát  Bài toán kiểm định giả thiết thống kê: cho trước một giả thiết +

03/02/17

 KPDL văn bản, web, phương tiện xã hội liên quan mật thiết với tìm

kiếm thông tin.

quan trọng

 Tìm kiếm thông tin với KPDL

chính trong tập tài liệu, từng tài liệu … bổ sung thuộc tính dữ liệu  Kết hợp mô hình tìm kiếm với kỹ thuật KPDL tìm thấy các chủ đề

dưới dạng từ khóa/cụm từ khóa mà không phải cấu trúc phức tạp  Hai giả thiết: (i) Dữ liệu tìm kiếm là không cấu trúc; (ii) Truy vấn

 Tìm kiếm tài liệu hoặc tìm kiếm thông tin trong tài liệu theo một truy



vấn. Tài liệu: văn bản, đa phương tiện, web…

 Tìm kiếm thông tin

Tìm kiếm thông tin với KPDL

Information Retrieval. “Truy hồi thông tin”

 Học tích cực (Active learning) có thể gọi

(interactive learning) có tương tác với người dùng. là học tương tác

 Học bán giám sát (semi-supervised learning) sử dụng cả ví dụ có

nhãn và ví dụ không có nhãn

 Học không giám sát (unsupervised learning) là đồng nghĩa với phân

cụm (clustering),

 Học giám sát (supervised learning) là đồng nghĩa với phân lớp  Nhiều nội dung đã được trình bày tại mục trước

 Một số nội dung học máy với khai phá dữ liệu

 Học máy là lĩnh vực nghiên cứu phát triển nhanh



(classification)

 Cách máy tính có thể học (nâng cao năng lực) dựa trên dữ liệu.  Machine Learning

 Học máy

Học máy với KPDL

tay trên thư thông qua một tập ví dụ”. ra quyết định thông minh dựa trên dữ liệu, ví dụ, “học được chữ viết Các chương trình máy tính tự động học được các mẫu phức tạp và

03/02/17

 Thông tin tóm tắt thống kê (xu hướng trung tâm dữ liệu và biến đổi)

 Báo cáo tóm tắt đa chiều

 Cung cấp thông tin tóm tắt

 Dự báo các nhân tố sẽ thu hút khách hàng mới

 Định danh các sản phẩm tốt nhất tới khách hàng (khác nhau)

 Phân tích yêu cầu khách hàng

 Kiểu của khách hàng mua sản phẩm gì (phân cụm và phân lớp)

 Hồ sơ khách hàng

 Quan hệ kết hợp/đồng quan hệ giữa bán hàng và sự báo dựa theo quan

 Phân tích thị trường chéo

 Xác định các mẫu mua hàng theo thời gian

hệ kết hợp

 Tìm cụm các mô hình khách hàng cùng đặc trưng: sự quan tâm, mức thu

 Tiếp thị định hướng

nhập, thói quen chi tiêu...

 Nguồn dữ liệu có từ đâu ?

Phân tích và quản lý thị trường

 Phân tích DNA và dữ liệu sinh học

 Khai phá dữ liệu dòng

 Khai phá Text (nhóm mới, email, tài liệu) và khai phá Web

 Ứng dụng khác

 Phát hiện gian lận và phát hiện mẫu bất thường (ngoại lai)

phân tích cạnh tranh

 Dự báo, duy trì khách hàng, cải thiện bảo lãnh, kiểm soát chất lượng,

 Phân tích và quản lý rủi ro

quen mua hàng, bán hàng chéo, phân đoạn thị trường

 Tiếp thị định hướng, quản lý quan hệ khách hàng (CRM), phân tích thói

 Phân tích và quản lý thị trường

 Phân tích dữ liệu và hỗ trợ quyết định

7. Ứng dụng cơ bản của KPDL

của khách hàng, các nghiên cứu phong cách sống (công cộng) bổ sung  Giao dịch thẻ tín dụng, thẻ thành viên, phiếu giảm giá, các phàn nàn

03/02/17

Enhancement of Business Processes, Springer.

WMP Van der Aalst (2011). Process Mining: Discovery, Conformance and

Phân tích kinh doanh: Khai phá quy trình

 Khởi tạo chiến lược giá trong thị trường cạnh tranh cao  Nhóm khách hàng thành các lớp và định giá dựa theo lớp khách  Theo dõi đối thủ cạnh tranh và định hướng thị trường

 Cạnh tranh

 Tóm tắt và so sánh các nguồn lực và chi tiêu

 Lên kế hoạch tài nguyên

tích xu hướng…)

 Phân tích lát cắt ngang và chuỗi thời gian (tỷ số tài chính, phân  Phân tích yêu cầu ngẫu nhiên để đánh giá tài sản  Phân tích và dự báo dòng tiền mặt

 Lên kế hoạch tài chính và đánh giá tài sản

Phân tích doanh nghiệp & Quản lý rủi ro

03/02/17

với sự trợ giúp của KPDL

 JPL và Palomar Observatory khám phá 22 chuẩn tinh (quasar)

 Thiên văn học

và Miami Heat

hỗ trợ và lỗi) để đưa tới lợi thế cạnh trang cho New York Knicks

 IBM Advanced Scout phân tích thống kế môn NBA (chặn bóng,

 Thể thao

tiếp thị Web, cải thiệ cách tổ chức Website … đãi khách hàng và các trang hành vi, phân tích tính hiệu quả của Web đối với các trang liên quan tới thị trường để khám phá ưu  Trợ giúp IBM áp dụng các thuật toán KPDL biên bản truy nhập

 Khai phá web và khai phá phương tiện xã hội

Ứng dụng khác

 Chống khủng bố

 Các nhà phân tích ước lượng rằng 38% giảm bán lẻ là do nhân viên

 Công nghiệp bán lẻ

không trung thực

 Mô hình cuộc gọi: đích cuộc gọi, độ dài, thời điểm trong ngày hoặc

 Viến thông: cuộc gọi gian lận

 Xét nghiệm không cần thiết hoặc tương quan

 Bệnh nghề nghiệp, nhóm bác sỹ, và nhóm chỉ dẫn

 Bảo hiểm y tế  Rửa tiền: giao dịch tiền tệ đáng ngờ  Bảo hiểm tự động: vòng xung đột thông.

 Ứng dụng: Chăm sóc sức khỏe, bán lẻ, dịch vụ thẻ tín dụng, viễn

 Tiếp cận: Phân cụm & xây dựng mô hình gian lận, phân tích bất thường

Phát hiện gian lận và khai phá mẫu hiếm

tuần. Phân tích mẫu lệch một dạng chuẩn dự kiến

03/02/17



Future Directions in Computer Science

 Danh sách tài liệu tham khảo



http://www.kdnuggets.com/

 Một số tham khảo khác



Journals: IEEE Trans. visualization and computer graphics, etc.

 Conference proceedings: CHI, ACM-SIGGraph, etc.



Visualization



Journals: Annals of statistics, etc.

 Conferences: Joint Stat. Meeting, etc.



Statistics



Journals: Machine Learning, Artificial Intelligence, etc.

 Conferences: Machine learning (ML), AAAI, IJCAI, COLT (Learning Theory), etc.



AI & Machine Learning



Journals: ACM-TODS, IEEE-TKDE, JIIS, J. ACM, etc.

 Conferences: ACM-SIGMOD, ACM-PODS, VLDB, IEEE-ICDE, EDBT, ICDT, DASFAA

 Database systems (SIGMOD: CD ROM)



Journal: Data Mining and Knowledge Discovery, KDD Explorations

 Conferences: ACM-SIGKDD, IEEE-ICDM, SIAM-DM, PKDD, PAKDD, etc.

 Data mining and KDD (SIGKDD: CDROM)

Nguồn chỉ dẫn về KPDL

8. Vấn đề chính trong KPDL

03/02/17

 Data Analysts earn on average $86K (11% higher than $76K in 2014).

because more people entered the market).

 Data Scientists earn on average $122K (9% lower than $135K in 2014, probably

in 2014).

 Data Science Managers earn average salary around $177K (11% higher than $165K

A regional breakdown in the US/Canada shows that :

compensated.html http://www.kdnuggets.com/2015/03/salary-analytics-data-science-poll-well-

http://www.kdnuggets.com/2015/09/free-data-science-books.html

03/02/17

KPDL: tốp 20 từ khóa hàng đầu



PAKDD (1997), PKDD (1997), SIAM-Data Mining (2001), (IEEE) ICDM (2001), etc.

 More conferences on data mining

http://www.researcherid.com/

 1998 ACM SIGKDD, SIGKDD’1999-2001 conferences, and SIGKDD



Journal of Data Mining and Knowledge Discovery (1997)

Explorations

 1995-1998 International Conferences on Knowledge Discovery in Databases

and R. Uthurusamy, 1996)



Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth,

 1991-1994 Workshops on Knowledge Discovery in Databases



Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991)

and Data Mining (KDD’95-98)

 1989 IJCAI Workshop on Knowledge Discovery in Databases (Piatetsky-

Sơ lược cộng đồng KPDL

Shapiro)

03/02/17

 Khai phá nhận định: Opinion Mining / Sentiment Mining

con người là một trong những nguyên nhân chính.

 Đồng thuận với Hội đồng liên chính phủ về Biến đổi khí hậu: hoạt động của

động của con người là nguyên nhân duy nhất của thay đổi khí hậu.

 Khí hậu rất phức tạp và các nhà khoa học không phải là tuyên bố rằng hoạt

hoạt động của con người, một số đáng kể số người nghi ngờ.

 Gần 50% độc giả KDnuggets tin rằng thay đổi khí hậu hiện nay phần lớn là do

Nguyên nhân gây biến đổi khí hậu:

Trang web KDD; KPDL & biến đổi khí hậu

Các chủ đề liên quan KPDL là thời sự !

03/02/17

 Một tổng hợp về các bài học KPDL thành công, thất bại

Statistical Analysis and Data Mining, Elsevier, 2009. [NEM09] Robert Nisbet, John Elder, and Gary Miner (2009). Handbook of

 Quá trình học qua nhiều chu kỳ, cần “chạy đua với thực tiễn” (mô hình

mở rộng khách hàng ban đầu chưa phải đã tối ưu).

 Nắm bắt và duy trì các dòng thông tin tích lũy (chẳng hạn, mô hình kết

quả từ một loạt chiến dịch tiếp thị)

tiền lớn). hưởng sóng ngầm mạnh (Giảm các nợ khoản khó đòi từ 10% còn 9,8% có số  Hoặc gián tiếp tạo ra đòn bẩy cao khi tác động vào quá trình sống còn có ảnh

(như Mô hình mở rộng khách hàng qua tiếp thị và bán hàng)

 Hoặc trực tiếp nhận được “trái cây treo thấp” (“low-hanging fruit”) dễ thu lượm

 Cần có kỳ vọng về một lợi ích đáng kể về kết quả KPDL  Sơ bộ về một số yêu cầu để dự án KPDL thành công

Một số yêu cầu ban đầu

 Bảo đảm bí mật dữ liệu, toàn vẹn và tính riêng tư  KPDL đặc tả miền ứng dụng và KPDL vô hình

 Áp dụng và chỉ số xã hội

 Khai thác tương tác tri thức ở các cấp độ trừu tượng

 Biểu diễn và trực quan kết quả KPDL

 Ngôn ngữ hỏi KPDL và khai phá “ngẫu hứng”

 Tương tác người dùng

 Kết hợp các tri thức được khám phá với tri thức hiện có: tổng hợp tri thức

 Tính song song, phân tán và phương pháp KP gia tăng

 Xử lý dữ liệu nhiễu và dữ liệu không đầy đủ

 Kết hợp tri thức miền: ontology

 Đánh giá mẫu: bài toán về tính hấp dẫn

 Hiệu năng: Hiệu suất, tính hiệu quả, và tính mở rộng

 Khai phá các kiểu tri thức khác nhau từ dữ liệu hỗn tạp như sinh học, dòng, web…

 Phương pháp luận khai phá

Vấn đề chính trong KPDL

hợp tốt giữ người phân tích và người kinh doanh tích hợp dữ liệu, phân tích mô hình hóa, lập và trình diễn báo cáo. Kết  Cần có một đội dự án thi hành các kỹ năng theo yêu cầu: chọn dữ liệu,

03/02/17

Chương 2. Bài toán phát hiện tri thức

 Một số nội dung liên quan

 Bài toán phát hiện tri thức từ dữ liệu

 Cơ sở của phát hiện tri thức từ dữ liệu

 Quản lý tri thức

 Công nghệ tri thức

Chapter 2: Phát hiện tri thức từ dữ liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI 09-2014 PGS. TS. HÀ QUANG THỤY

CHƯƠNG 2. PHÁT HIỆN TRI THỨC TỪ DỮ LIỆU

BÀI GIẢNG NHẬP MÔN KHAI PHÁ DỮ LIỆU

Chương 2. Bài toán phát hiện tri thức

 Hệ thống phát hiện tri thức

 Hệ thống tác nghiệp, điều hành

 Vai trò bản chất của CNTT trong kinh tế

 Nhận đinh về luận điểm của CARR

 “CNTT không quan trọng”: IT does not matter !

 Luận điểm của CARR

điển) và đầu tư CNTT

 Căn cứ: Thống kê hiệu quả kinh tế (theo lý thuyết kinh tế cổ

 Nghịch lý hiệu quả của CNTT

Vai trò của CNTT

 Nội dung cơ bản của công nghệ tri thức  Khái niệm công nghệ tri thức

 Cơ bản về Công nghệ tri thức đại học, phần mềm

 Các yếu tố đầu vào cốt lõi của kinh tế tri thức: R&D, giáo dục  Bốn cột trụ của nền kinh tế tri thức  Khái niệm kinh tế tri thức

 Kinh tế tri thức

 Bản chất vai trò của CNTT trong kinh tế  Luận điểm của CARR  Nghịch lý về tính hiệu quả của CNTT

 Vai trò của CNTT trong kinh tế Nhầm lẫn tai hại: “hạ tầng CNTT” với bản thân “CNTT”

nghe/tin-tuc/35_280229/cong_nghe_thong_tin_la_ha_tang_cua_ha_tang.htm “xác định CNTT giữ vai trò là hạ tầng của hạ tầng quốc gia” http://vnmedia.vn/VN/cong-  Công nghệ thông tin là hạ tầng của hạ tầng ?

Công nghệ tri thức

quả“ (1987) “chúng ta nhìn thấy máy tính ở mọi nơi ngoại trừ trong thống kê hiệu  Robert Solow, nhà kinh tế được giải thưởng Nobel, có nhận định

Chương 2. Bài toán phát hiện tri thức

1990s

3.1

2.20%

1980s

0.3

2.75%

1970s

0.05

2.95%

1960s

0.003

4.50%

Giai đoạn

tính (%GNP) Chi phí cho máy

năm Tăng GNP hàng

Sự không tương quan trong tăng GNP

Toàn nền kinh tế Mỹ: nghịch lý hiệu quả

Management Research, June, 1994 (in Japanese) Assessment , Published in Communications of the ACM, December, 1993; and Japan Erik Brynjolfsson. The Productivity Paradox of Information Technology: Review and

 Sự vỡ mộng, thâm chí làm thất vọng với công nghệ gia tăng một mạng công nghệ lớn nhất mà loài người từng có" (Snow, 1966),

 Cho một hứa hẹn khổng lồ của IT tới mở ra trong “cuộc cách

 Hiệu quả, đặc biệt trong khu vực dịch vụ có vẻ đình trệ.

không hầu hết thời gian" (Economist, 1990). cách hiển nhiên: “Không, máy tính không làm tăng hiệu quả, ít nhất

 Năng lực máy tính được đưa vào kinh tế Mỹ đã tăng hơn bậc hai

biết vẫn còn rất hạn chế.

 Mối quan hệ giữa IT và hiệu quả: nhiều tranh luận song hiểu thống kê

 “Nghịch lý hiệu quả“: Một xung đột của kỳ vọng với

Nghịch lý hiệu quả

về độ lớn từ năm 1970

Chương 2. Bài toán phát hiện tri thức

tài chính

(trục hoành) với thu hồi vốn (trục tung) tại các công ty

 Có quan hệ “tỷ lệ thuận” giữa đầu tư CNTT/nhân viên

Nghịch lý hiệu quả: mức công ty tài chính

 http://www.strassmann.com/pubs/cf/cf970603.html vốn: đầu tư CNTT lãng phí ? Thu hồi vốn chậm ?

 Phải: Có 90,6 % số công ty giá thành CNTT lớn hơn giá thu hồi

với thu hồi vốn (trục tung): tỷ lệ đầu tư nhiều cũng như ít !

 Trái: Không có quan hệ giữa đầu tư CNTT/nhân viên (trục hoành)

Nghịch lý hiệu quả: mức công ty

Chương 2. Bài toán phát hiện tri thức

 Thuộc 100 người có tên được nhắc đến nhiều nhất !

SloanManagementReview, Spring 2005: 67-73.

 Nicholas G. Carr. The end of corporate computing, MIT

chiến lược của CNTT !

đưa ra ba quy tắc hướng dẫn cho tương lai: phủ nhận vai trò

khắc đầu tư vào CNTT và quản lý các hệ thống của họ. Carr

chóng biến mất, nhiều công ty cần có một cái nhìn nghiêm

 Với các cơ hội đạt được lợi thế chiến lược từ CNTT đã nhanh

quan trọng hơn các lợi thế mà nó cung cấp. không quan trọng cho chiến lược, rủi ro nó tạo ra trở thành  Khi một tài nguyên trở thành bản chất để cạnh tranh nhưng

đổi đáng kể ! đã giảm. Cách tiếp cận đầu tư và quản lý CNTT cần phải thay  CNTT xuất hiện khắp nơi và tầm quan trọng chiến lược của nó 2003: 41-49

 Nicholas G. Carr. IT does'n matter! HBR at Large, May

Luận điểm của G. Carr: IT does'n matter !

 Công thức tính hiệu quả kinh tế

 Sai lầm trong quản lý đầu tư CNTT: Ph/pháp phân tích lỗi thời.

Cty này đầu tư – công ty khác hưởng lợi

 Tính phân phối lại tài nguyên thông tin “sản phẩm công cộng”:  Đầu tư CNTT có độ trễ phát huy hiệu quả 2-3 năm Biến đầu vào, biến đầu ra và đo lường các biến này .

 Lỗi đo lường từ công thức tính hiệu quả của kinh tế cổ điển:

 E. Brynjolfsson [Bryn93]: không là nghịch lý hiệu quả

Phân tích nghịch lý hiệu quả

Chương 2. Bài toán phát hiện tri thức

anh sẽ được giải quyết”.

thuốc bách bệnh “Mua công nghệ này đi và các vần đề của

cụ, các nhà cung cấp công nghệ lại nhằm tới nó như một

Nhẽ ra phải giúp các công ty hiểu rằng IT chỉ là một công

một đền đáp như được kỳ vọng một vụ nổ vũ trụ, là khởi đầu dựa theo IT hiếm khi tạo ra Một điều chúng ta học được từ những năm 1990, nó như

June 2003 Thomas A. Stewart (2003). Does IT Matter ? An HBR Debate, Harvard Bussiness Review,

anh sẽ được giải quyết”. thuốc bách bệnh “Mua công nghệ này đi và các vần đề của cụ, các nhà cung cấp công nghệ lại nhằm tới nó như một Nhẽ ra phải giúp các công ty hiểu rằng IT chỉ là một công

một đền đáp như được kỳ vọng một vụ nổ vũ trụ, là khởi đầu dựa theo IT hiếm khi tạo ra Một điều chúng ta học được từ những năm 1990, nó như

Chương 2. Bài toán phát hiện tri thức

chất chung.

dụng lôgíc về công nghệ mà còn bằng áp dụng lôgic về bản

IT bắt buộc hỗ trợ kinh doanh – không chỉ bằng áp

IT luôn luôn quan trọng – là vấn đề trong mọi quan niệm.

thách thức hơn so với theo đuổi lợi thế cạnh tranh ? quản lý và kiểm soát rủi ro về kinh phí ít hứa hẹn hoặc nên buồn rầu ? Phải chăng là vì các bài toán lãnh đạo như Nhưng tại sao Carr lại khuyến cáo các nhà quản lý IT sẽ trở chịu đựng được là IT đã trở thành một loại hàng hóa. cách thức các công ty nên phản ứng với thực tế không thể Tôi đồng tình nhiều với khuyến cáo của Nicholas Carr về

lại ! may, tất cả minh chứng đều ngược mọi người có thế tăng lên. Không Chúc Carr đúng vì điều bất lợi của

thông tin. chức sẽ thay đổi rất nhanh để cạnh tranh trong thời đại trong các thập niên tiếp theo. Gói kỹ năng cần trong một tổ và CIO (người đứng đầu về TT) sẽ quan trọng chưa từng có Công việc của CTO (người đứng đầu bộ phận công nghệ)

Chương 2. Bài toán phát hiện tri thức

Kinh tế CNTT và kinh tế Internet

talk.php?talk=123. Communicating I.T. Value, http://www.strassmann.com/talks/one- [Strass07] and

(2007), Measuring

Strassmann

Paul thông thường.

 Hơn mức thông thường khi mà tri thức của nhân viên hơn mức

nghiệp hơn mức thông thường,

 Hơn mức thông thường khi mà hiệu quả thông tin của doanh

lường được,

 Hơn hay kém hơn so với mức thông thường khi có hiệu quả đo

doanh nghiệp đồng hạng:

Paul A. Strassmann [Strass07]: chi tiêu CNTT so với các

Định hướng quản lý đầu tư CNTT

trong nhóm 20 nền kinh tế (G-20) đạt 2300 tỷ đô la Mỹ, chiếm 4,1% GDP - Theo The Boston Consulting Group, kinh tế Internet (the Internet economy) 19, 2012. Internet Economy in the G-20: The $4.2 Trillion Growth Opportunity, March Lundmark, James O'Day, John Pineda, and Paul Zwillenberg (2012).The 1200 tỷ US$). David Dean, Sebastian DiGrande, Dominic Field, Andreas - Kinh tế CNTT 2011: trên 4200 tỷ US$ (Software + Services chiếm 29% đạt

Chương 2. Bài toán phát hiện tri thức



that – Knowing how). Ví dụ tri thức ẩn  tri thức hiện: ngành CNPM

Subjective knowledge), tri thức biết – tri thức hành động (Knowing

thức chủ quan – tri

thức khách quan (Objective knowledge –



tri thức hiện – tri thức ẩn (Explicit knowledge – Tacit knowledge), tri

Phân loại tri thức

động thực tiễn

 Hình thức thu nhân tri thức: giáo dục, kinh nghiệm qua hoạt

 Khai phá dữ liệu: mẫu có độ hấp dẫn vượt qua ngưỡng  Ở đây: Compact Oxford English Dictionary  Nội dung khái niệm còn phụ thuộc vào từng lĩnh vực:

một hiện tượng mà thu nhận được nhờ kinh nghiệm  nhận thức và hiểu biết tường minh về một sự việc hoặc  tổng hợp những gì mà con người biết rõ

người thu nhận được qua kinh nghiệm hoặc giáo dục  sự hiểu biết tinh thông cùng với các kỹ năng mà con

 Từ điển Compact Oxford English Dictionary

 Khái niệm

Tri thức

2. Tri thức và kinh tế tri thức

dẻo và động, "know where“, "know when“: tri thức quan trọng cho một nền kinh tế mềm "know how“: tri thức về kỹ năng và kinh nghiệm thực tiễn. "know who“: tri thức về ai và họ làm được gì, "know why“: tri thức về thế giới, xã hội và trí tuệ con người, "know what“: tri thức về sự vật, sự kiện, hiện tượng

Chương 2. Bài toán phát hiện tri thức

theo tương tác động, trong một xoắn ốc tri thức.

Trong công ty sáng tạo tri thức, bốn mô hình chuyển đổi tri thức làm việc

 Chủ quan hóa (Internalization) là quá trình bao chứa các tri thức rõ ràng vào

những kinh nghiệm của những người khác, gián tiếp. tri thức ẩn. Điều này tạo điều kiện thuận lợi nếu cá nhân có thể lại trải nghiệm

 Thông tin có trong CSDL

tri thức rõ mới (KDD) có thể được xử lý để tạo

 Kết

Chuyển hóa tri thức

là thoại. các cuộc họp qua điện họ bằng cách chuyển đổi và kết hợp tri thức rõ của vậy, các cá nhân thay đổi từ các nguồn khác nhau. Vì bằng cách kết hợp tri thức quá trình tạo ra tri thức rõ (Combination/mixing) hợp / trộn

khó khăn nhất. ra tri thức, nhưng cũng là nhất liên quan đến việc tạo là hoạt động quan trọng  Ngoại diên hóa tri thức ẩn

 Ngoại

là và các mô hình. phép ẩn dụ, tương tự hóa nhóm) bằng cách sử dụng truyền giữa các cá nhân và tương đối dễ dàng lây hình thức, dễ tiếp cận, thànhtri thức hiện (tri thức trình chuyển đổi tri thức ẩn (Externalization) quá hóa

Chuyển hóa tri thức

diên dụng ngôn ngữ. Bắt chước được coi là một phương tiện đào tạo xã hội. chức). Một cá nhân có thể tiếp thu tri thức ẩn của cá nhân khác mà không cần sử tri thức tiềm ẩn, cá nhân hóa sâu sắc và trình bày khuếch tán trong phạm vi tổ ẩn (tri thức của cá nhân bao gồm nhận định, sự hiểu biết, niềm tin và trực giác,  Xã hội hóa (Socialization): quá trình chia sẻ kinh nghiệm và do đó tạo ra tri thức

Chương 2. Bài toán phát hiện tri thức

doanh nghiệp



thực hiện các biện pháp điều khiển quá trình tiến hóa tri thức

bộ



tạo điều kiện thuận lợi cho trao đổi và phát triển tri thức nội

- Doanh nghiệp là một thực thể bảo vệ tri thức:

 

văn hóa và một mô hình của tinh thần san sẻ. Tạo ra tri thức: cung cấp một ý thức cộng đồng, một bản sắc Tich hợp tri thức phân tán của tập cá nhân - Doanh nghiệp là một thực thể sáng tạo tri thức: tính chất chuyên môn ngành nghề trình độ cao

  Môi trường văn hóa doanh nghiệp cộng đồng đơn nhất thu nhận & chuyển giao tri thức:

- Doanh nghiệp là một thực thể tích hợp tri thức, một

Tri thức doanh nghiệp: tiếp cận kinh tế

Chuyển đổi tri thức trong doanh nghiệp

Chương 2. Bài toán phát hiện tri thức

[WB06].

 Hai định nghĩa trên là tương tự nhau: ở đây sử dụng định nghĩa

tầng thông tin hữu hiệu và truy nhập được.

là tri thức, năng lực trí tuệ, một thiết chế xã hội cho một hạ  [UN00] nền kinh tế mà các yếu tố then chốt cho sự phát triển

dụng một cách hiệu quả cho tăng trưởng kinh tế. thức được yêu cầu, được phát sinh, được phổ biến và được vận chốt cho tăng trưởng kinh tế. Trong nền kinh tế tri thức, tri  [WB06] nềnkinhtếmà việcsửdụngtrithứclàđộnglựcchủ  Knowledge Economy/Knowledge-Based Economy

Khái niệm

Kinh tế tri thức



“Tự phát” –> “tự giác” nghiệp Thói quen: một bộ phận quan trọng trong văn hóa doanh

 trợ sự tương tác linh hoạt trong doanh nghiệp

- Các thói quen được hình thành trong doanh nghiệp hỗ

đề quá phức tạp hoặc quan trọng và bất thường. Nên và chỉ nên sử dụng các quy trình chuẩn đối với các vấn

 vào sản phẩm trình tiến hành các bưước tham gia của các chuyên gia - Chuẩn hóa hoạt động mức doanh nghiệp qua ư quá

chuyển hóa tri thức ẩn thành tri thức hiện

- Các quy tắc tưương tác giữa các cá nhân tạo điều kiện

Cơ chế tích hợp tri thức doanh nghiệp

Chương 2. Bài toán phát hiện tri thức

phổ biến và xử lý thông tin và tri thức

information infrastructure) là phương tiện hiệu quả để truyền thông,

 Một hạ tầng thông tin hiện đại và đầy đủ (a modern and adequate

học tập suốt đời. cách tân tri thức cũng như để đảm bảo xã hội học tập và hoạt động Hạ tầng thông tin hiện đại và đầy đủ đảm bảo hoạt động thu nhận,

innovation system)

 Một hệ thống cách tân hướng tri thức hiệu quả (a effective Bốn cột trụ của một nền kinh tế tri thức

Kinh tế tri thức: đặc trưng

không ngừng cách tân tri thức, phát huy sáng kiến mang tính xã hội. phát triển của nền kinh tế tri thức. Trong nền kinh tế tri thức, hoạt động liên tục được thay thế bằng tri thức mới - tiến bộ phù hợp với trình độ tổ chức khác , trong đó, tri thức khi mà đã trở nên lỗi thời - lạc hậu cần tập đoàn, trung tâm nghiên cứu, trường đại học, các chuyên gia và các Nền kinh tế tri thức cần là một nền kinh tế cách tân hiệu quả của các

 Một lực lượng lao động được giáo dục và lành nghề (An

thức của nền kinh tế. học tập suốt đời cũng là các yếu tố đảm bảo tăng cường tiềm năng tri chọn nhằm thể hiện tiềm năng nói trên. Xã hội học tập và hoạt động lực trong nền kinh tế. Các thông số về giáo dục và sáng tạo được lựa Cột trụ này bao gồm các yếu tố về năng lực tri thức của nguồn nhân educated and skilled labor force)

 Một thiết chế xã hội pháp quyền và khuyến khích kinh tế (An

Bốn cột trụ của một nền kinh tế tri thức

Kinh tế tri thức: đặc trưng

phát kiến, phổ biến và sử dụng các tri thức đang có. khích phân phối hiệu quả tài nguyên, kích thích cách tân và thúc đẩy Cột trụ này bao gồm các chính sách và thể chế kinh tế tốt, khuyến economic incentive and institutional regime)

Chương 2. Bài toán phát hiện tri thức

tri thức của Ngân hàng thế giới (KAM) được đổi mới theo thời gian

đang được nghiên cứu đề xuất, chẳng hạn hệ thống đo lường kinh tế

thống kê quốc dân truyền thống.

chưa có cách thức thống kê tri thức tương tự như cách thức

 Việc lên sơ đồ cho đầu vào của bộ tạo tri thức là rất khó khăn vì

Việc chọn các tiêu chí trong hệ thống đánh giá kinh tế tri thức vẫn

dịch các đầu vào của nguồn tạo tri thức thành đầu ra tri thức.

 Không có một công thức hoặc một cách làm ổn định để chuyển Bốn nguyên tắc [Oec96]

Kinh tế tri thức: đo lường

 Tổng hợp các tiêu chí

 Đo lường từng tiêu chí

 Hệ thống tiêu chí

 Đang trong quá trình hình thành và cải tiến:

 Thông qua hệ thống tiêu chí: Đầu ra của kinh tế tri thức

 [OEC96] xác định 4 khó khăn nguyên tắc (trang sau)

tưởng”. thức về tăng trưởng kinh tế không hoàn toàn rõ ràng như ta vẫn  [Ram08] nhận định “người ta ngày càng nhận thức rõ hơn rằng tri

dung 4 cột trụ [OEC96, RF99, CD05]

 Là một công việc khó khăn: Từ chính Khái niệm tri thức và nội

Kinh tế tri thức: đo lường

Ví dụ, đầu tư cho khoa học – công nghệ <=> kinh tế tri thức kinh tế ? công thức định lượng đúng tuyệt đối hệ thống các tiêu chí thể hiện được tiềm năng tạo ra tri thức cho nền thức hay cách làm nói trên. tính phức tạp của quá trình nhận thức cho nên không thể có một công

Chương 2. Bài toán phát hiện tri thức

- hệ thống đo lường kinh tế tri thức phổ biến: có KAM của WB

- đề xuất một mô hình đánh giá kinh tế tri thức của một quốc gia

thống đánh giá điển hình.

- phân tích nội dung, điểm mạnh và điểm hạn chế của một số hệ

kinh tế tri thức của một quốc gia.

Yogesh Malhotra [Mal03] trình bày hệ thống về mô hình đánh giá

 Đo lường tri thức thông qua học tập  Đo lường mạng tri thức  Đo lường tri thức của đầu ra  Đo lường kho tri thức và tri thức trong kho.  Đo lường tri thức của đầu vào. Các bài toán cần giải quyết [OEC96]

Kinh tế tri thức: đo lường

kho tri thức. sung mạng vào kho tri thức và sự lạc hậu của các phần tử trong  Chưa văn bản hóa được việc tạo tri thức mới mà không phải bổ

(hợp các phần tử tri thức thành thành phần bản chất duy nhất).  Thiếu tri thức về một hệ thống định giá có tính phương pháp luận Bốn nguyên tắc [OEC96]

Kinh tế tri thức: đo lường

quốc gia vẫn chưa có tính phương pháp luận hoàn toàn. hợp các giá trị đó thành giá trị “đo” mức độ kinh tế tri thức của một Chẳng hạn, hệ thống KAM, việc “đo” cho từng tiêu chí cũng như tổng “tri thức” của một nền kinh tế. Thành phần bản chất duy nhất được dùng để làm giá trị đo mức độ

Chương 2. Bài toán phát hiện tri thức

tin và tri thức

phương tiện hiệu quả để truyền thông, phổ biến và xử lý thông

 Cột trụ Hạ tầng thông tin hiện đại và đầy đủ đảm bảo hệ thống

thức mới cho nhu cầu địa phương

dòng tăng trưởng tri thức tổng thể, đồng hóa và làm phù hợp tri

chức khác nhằm đảm bảo sự tiến hóa tri thức, chuyển đổi thành

trung tâm nghiên cứu, trường đại học, các chuyên gia và các tổ  Cột trụ Hệ thống cách tân được thi hành trong các tập đoàn,

training services, in Services (%), Local availability of specialized research and tiếp tới kinh tế dịch vụ, chẳng hạn như các tiêu chí Employment  Hệ thống KAM chứa một số tiêu chí có nội dung liên quan trực

2008, KAM-2009) tiếng Anh là Institutions (KAM-2005) và Governance (KAM-  Tiêu đề Điều hành chính quyền được chuyển từ các tiêu đề

Một số giải thích

Đo lường kinh tế tri thức: KAM

 2005: 80 tiêu chí; 2008: 83 tiêu chí; 2009: 109 tiêu chí  Đang được cải tiến  Chi tiết hóa 4 cột trụ bằng hệ thống tiêu chí

 Đo lường điển hình KTTT

KAM - Knowledge Assessment Methodology [CD05]

Đo lường kinh tế tri thức: KAM

Chương 2. Bài toán phát hiện tri thức

Bài toán phát hiẹn tri thức 34

ảnh chụp.

tập tin văn bản, hình ảnh, băng hình, cảm biến, và các bức

 Chuyên gia, sách hướng dẫn, phim ảnh, sách, cơ sở dữ liệu,

 Một số nguồn tri thức

chủ quan)

thức văn bản hóa là mục tiêu (dù có thể được diễn giải một cách

phim… Tri thức không văn bản hóa có trong tâm trí con người. Tri  Tri thức văn bản hóa có trong sách vở, đĩa máy tính, báo cáo,

cơ sở tri thức.

 Biểu diễn tri thức liên quan đến việc tổ chức các tri thức trong các

toán neuron. Sử dụng 3 kỹ thuật: quy nạp, lập luận dựa trên trường hợp, tính đã văn bản hóa và chưa văn bản hóa và chuyển nó vào máy tính.  Thu nhận tri thức là việc khai thác tri thức từ nguồn (chuyên gia)

 Một số khái niệm

Cơ bản về công nghệ tri thức

Bài toán phát hiẹn tri thức 33

 Metaknowledge: YKYN, YDYK, YKYD, YDYD

file đầy đủ. So sánh với metadata (dữ liệu về dữ liệu): dữ liệu mô tả xác định những tri thức có liên quan, và khi nào tri thức là chưa để sử dụng tri thức trong các tình huống cụ thể, làm thế nào để  Metaknowledge: tri thức về tri thức. Một số ví dụ: làm thế nào

 Một số khái niệm liên quan

luận, và thiết kế các công cụ giải thích.

 thu nhận tri thức, biểu diễn tri thức, xây dựng một cơ chế suy

 Bốn bước thi hành

diễn tri thức, và xây dựng cơ chế suy luận và giải thích.

 Công nghệ tri thức là một quá trình bao gồm thu nhận và biểu

 Khái niệm công nghệ tri thức

Cơ bản về công nghệ tri thức

Chương 2. Bài toán phát hiện tri thức

 OK - Organizational Knowledge: Tri thức của tổ chức



 VKC - Validated Knowledge Claim: Yêu cầu tri thức hợp lệ

 UKC - Unvalidated Knowledge Claim: Yêu cầu tri thức không hợp lệ

 CKC - Codified Knowledge Claim: Yêu cầu tri thức hệ thống hóa

ra giá trị lớn nhất của nó. nói chung - các công ty phải sử dụng chiến lược khác nhau để nhận một tổ chức, sau đó tại nhiều tổ chức, và cuối cùng cho công chúng  Khi nó trở nên truy cập vào nhiều hơn và nhiều người - đầu tiên trong

gian: khởi tạo, huy động, phổ biến, trở thành hàng hóa

 Tri thức tiến bộ thông qua bốn giai đoạn là nó phát triển theo thời

2. Quản lý tri thức trong tổ chức

IKC - Invalidated Knowledge Claim: Yêu cầu tri thức hết hiệu lực IK - Invalidated Knowledge: Tri thức hết hiệu lực

Chương 2. Bài toán phát hiện tri thức

Bài toán phát hiẹn tri thức 38

dụng mô hình.

dựng mô hình và kiểm định giả thuyết  Đánh giá mô hình  Sử

 Từ dữ liệu  phát hiện quan hệ  phát triển giả thuyết  Xây

 Tiếp cận khai phá dữ liệu

kiểm định (chứng minh) giả thuyết. Ngô Bảo Châu: Bổ đề cơ bản

 Từ lý thuyết (hệ toán mệnh đề)  phát triển các giả thuyết 

 Tiếp cận truyền thống

Tiếp cận truyền thống và tiếp cận KPDL

được những gì HP biết, chúng tôi sẽ có ba lần lợi nhuận"

 Cựu giám đốc điều hành HP, Lew Platt đã từng nói, "Nếu HP biết  Hầu hết kỹ thuật khai phá dữ liệu chuyển hóa DKYK  YKYK.

3. Chuyển đổi meta-knowledge

Chương 2. Bài toán phát hiện tri thức

 Mô hình năm 1998

Mô hình vòng khai phá dữ liệu DN’98

Bài toán phát hiẹn tri thức 39

 Ví dụ: Chương 3 sách Data Mining: Methods and Tools, 1998.

 Khi nào nên khai phá dữ liệu

toán công nghệ. “kinh doanh”, bài toán “chiến lược” mà không phải

là bài  Khai phá dữ liệu và phát hiện tri thức trong CSDL là bài toán

 Nội dung cơ bản của KDD và DM

4. Bài toán phát hiện tri thức

Chương 2. Bài toán phát hiện tri thức

 Nguồn: http://www.crisp-dm.org/Process/index.htm (13/02/2011)

 CRISP-DM 2.0 SIG WORKSHOP, LONDON, 18/01/2007

 Thi hành chỉ sau khi tham chiếu kết quả với “hiểu kinh doanh”

toán và đánh giá

Standard Process for Data Mining). “Hiểu kinh doanh”: hiểu bài

 Các pha trong mô hình quy trình CRISP-DM (Cross-Industry

CRISP-DM Chuẩn công nghiệp khai phá dữ liệu

kinh doanh. liệu để xác định các quan hệ và mẫu thực sự liên quan tới mục tiêu • Chuyên gia miền ứng dụng làm việc với chuyên gia khai phá dữ • Trích chọn quan hệ và mẫu từ tập dữ liệu kinh doanh,

liệu xác nhận bộ công cụ là thích hợp nhất với mục tiêu kinh doanh, • Chuyên gia miền ứng dụng làm việc với chuyên gia khai phá dữ

mục tiêu kinh doanh, được khảo sát và thích hợp với công cụ phát hiện tri thức phù hợp • Khởi tạo dữ liệu sao cho năng lực tính toán làm chủ được dữ liệu

nghiệm trong hệ thống phát hiện tri thức,

• Định danh các chuyên gia miền lĩnh vực làm việc với nhóm thực • Khởi tạo tập dữ liệu mẫu chứa mọi thông tin liên quan,

mục tiêu kinh doanh đã được xác định,

• Định danh dữ liệu doanh nghiệp chứa thông tin liên quan tới các

kinh doanh để nghiên cứu có tính tập trung,

• Xác định mục tiêu kinh doanh. Bắt đầu với nhiều nhất ba mục tiêu

Mô hình vòng khai phá dữ liệu DN’98

Chương 2. Bài toán phát hiện tri thức

 thực hiện nhiều lần và không theo một thứ tự quy định.

công cụ mô hình hóa. tính cũng như chuyển đổi, và làm sạch dữ liệu cho các  gồm các hoạt động lập bảng, ghi lại và lựa chọn thuộc

cuối làm đầu vào cho công cụ mô hình hóa.

 gồm mọi các hoạt động nhằm xây dựng các tập dữ liệu

• Chuẩn bị dữ liệu (Data preparation)

CRISP-DM Chuẩn công nghiệp khai phá dữ liệu

khai phá dữ liệu, mục tiêu và kế hoạch thực hiện. hồi, phối hợp với nội dung hiểu kinh doanh  làm rõ bài toán hiểu dữ liệu  phân tích dữ liệu để hiểu dữ liệu có thể phản  Tri thức kinh doanh từ giai đoạn hiểu kinh doanh định hướng con dữ liệu thú vị nhằm hình thành giả thuyết cho thông tin ẩn.  khám phá hiểu biết ban đầu tới tập dữ liệu /phát hiện các tập

liệu, xác định các vấn đề chất lượng dữ liệu,

 Với một tập dữ liệu ban đầu: tiến hành hoạt động “làm quen” dữ

• Hiểu dữ liệu (Data understanding)

tiêu.

 một kế hoạch sơ bộ được thiết kế để đạt được các mục  một định nghĩa bài toán khai thác dữ liệu

tri thức này thành

 chuyển đổi  tập trung vào hiểu biết mục tiêu/yêu cầu từ góc độ kinh doanh

• Hiểu kinh doanh (Business understanding)

CRISP-DM Chuẩn công nghiệp khai phá dữ liệu

Chương 2. Bài toán phát hiện tri thức

 Một mô hình KDD năm 2000 [Nac00]

Một mô hình khai phá dữ liệu DN’00

đúng cách thức. rằng mô hình kết quả đạt được các mục tiêu kinh doanh theo được thực hiện để xây dựng mô hình  niềm tin chắc chắn  Đánh giá mô hình kết quả kỹ lưỡng và xem xét các bước đã

theo góc độ phân tích dữ liệu.

 Tìm ra (một số) mô hình kết quả với mục tiêu chất lượng cao

• Đánh giá (Evaluation)

nhằm đạt được mô hình có kết quả tối ưu.

 thực hiện lặp một số lần mô hình hóa và chuẩn bị dữ liệu  Một số kỹ thuật được sử dụng  Xác định tham số mô hình nhằm đạt tới giá trị tối ưu.  Các kỹ thuật mô hình khác nhau được lựa chọn và áp dụng.

• Mô hình hóa (Modeling)

CRISP-DM Chuẩn công nghiệp khai phá dữ liệu

Chương 2. Bài toán phát hiện tri thức

[HF09]

 Mô hình phát triển tri thức hướng thông minh doanh nghiệp, 2009

Một mô hình KPDL hướng BI

Management & Data Systems, 2008. 108(5): 622-634. [Oha09] to data mining process

for business

intelligence,

Industrial  Wang, H. and S. Wang (2008). A knowledge management approach

Mô hình KPDL và mô hình kinh doanh’08

Chương 2. Bài toán phát hiện tri thức

 Mô hình quá trình khai phá dữ liệu hướng miền ứng dụng [CYZ10]

Mô hình KPDL hướng ứng dụng

 Mô hình quá trình C-KDD [Pan10]

Tương tác người-máy trong KPDL’10

Chương 2. Bài toán phát hiện tri thức

chuyển giao cho người kinh doanh).

(tổng hợp phát hiện cuối cùng thành báo cáo ra quyết định sẽ được

P13. Cung cấp tri thức và báo cáo tổng hợp để ra quyết định thông minh

P12. Triển khai (triển khai các kết quả vào các ngành kinh doanh);

P11. Xem xét lại các giai đoạn từ P1 có thể được đòi hỏi;

quả ban đầu);

P10. Hậu xử lý kết quả (hậu phân tích hoặc hậu khai phá dữ liệu các kết

P9. Thực hiện qua lại giữa P7 và P8;

suất bằng cách áp dụng phương pháp hiệu quả hơn). theo quan điểm cả về kỹ thuật và kinh doanh, và tăng cường hiệu P8. Đo lường và nâng cao khả năng hành động (đánh giá tính thú vị P07. Khai phá chuyên sâu về kết quả chung ban đầu khi áp dụng;

ứng dụng theo phương thức quay lui và xem xét; thông qua phân tích ràng buộc và tương tác với các chuyên gia miền P7. Là hoàn toàn hợp lý khi mỗi giai đoạn từ P1 có thể được lặp đi lặp lại

các phát hiện ban đầu);

P6. Phân tích và đánh giá kết quả chung ban đầu (phân tích /đánh giá

Mô hình KPDL hướng ứng dụng

dụng khai phá đa bước, khai phá kết hợp); cách sử dụng nhiều mô hình hiệu quả tiết lộ cốt lõi của vấn đề, hoặc P05. Mô hình hóa chuyên sâu (áp dụng mô hình hóa chuyên sâu bằng

và phương pháp thích hợp để đạt được các mục tiêu trên);

P5. Lựa chọn phương pháp và mô hình hóa (lựa chọn được các mô hình

hoặc chuẩn bị dữ liệu chẳng hạn như xử lý dữ liệu mất tích và riêng tư); P4. Tiền xử lý dữ liệu (trích chọn, chuyển đổi và tải dữ liệu, nói riêng,

hợp hoặc xây dựng để đạt được các mục tiêu); nghĩa mục tiêu khai phá dữ liệu, và các đặc trưng được lựa chọn phù P3. Định nghĩa các mục tiêu phân tích, và xây dựng đặc trưng (định

trên, từ dữ liệu, miền ứng dụng, tính thú vị và cách phân bố);

P2. Phân tích ràng buộc (định danh ràng buộc xung quanh các vấn đề ở

của nó và những thách thức ...);

P1. Hiểu vấn đề (định danh và xác định các vấn đề, bao gồm cả phạm vi

Mô hình KPDL hướng ứng dụng

Chương 2. Bài toán phát hiện tri thức

Bài toán phát hiẹn tri thức 53

 Vai trò của người sử dụng.

 Dữ liệu học, dữ liệu kiểm tra.

 Vai trò dữ liệu mẫu

 Kết hợp giải pháp

 Không có thuật toán “tốt nhất” cho mọi bài toán khai phá dữ liệu.

 Lựa chọn thuật toán

 Độ đo là nội dung nghiên cứu trong KPDL

từng phương pháp, luật kết hợp (độ hỗ trợ + độ tin cậy)… giá (chính xác + hồi tưởng, chính xác + lỗi), phân cụm: đo theo  Mỗi bài toán KPDL thường đi kèm độ đo: phân lớp có độ đo đánh

 Tri thức  “mẫu có giá trị”

 Đô đo “tri thức”

5. Một số vấn đề liên quan

 Rời rạc và sinh kiến trúc khái niệm

 Rút gọn dữ liệu

 Tích hợp và chuyển dạng dữ liệu

 Làm sạch dữ liệu

 Vai trò của tiền xử lý dữ liệu

 Tiền xử lý dữ liệu

 Đánh giá và lập hồ sơ DL  Trực quan hóa DL  Mô tả thống kê cơ bản của DL  Thu thập dữ liệu  Độ đo tương tự và không tương tự của DL  Đối tượng DL và kiểu thuộc tính  Vai trò của hiểu dữ liệu

 Hiểu dữ liệu

Chương 3: Tiền xử lý dữ liệu

VÀ TIỀN XỬ LÝ DỮ LIỆU CHƯƠNG 3. HIỂU DỮ LIỆU

KHAI PHÁ DỮ LIỆU

Bài giảng môn học

[HF09]: Hiểu dữ liệu và hiểu thương mại điện tử

 Mô hình phát triển tri thức hướng thông minh doanh nghiệp, 2009

một mô hình KPDL hướng BI 3.1.1. Vai trò của hiểu dữ liệu:

 Đánh giá và lập hồ sơ DL

 Trực quan hóa DL

 Mô tả thống kê cơ bản của DL

 Thu thập dữ liệu

 Độ đo tương tự và không tương tự

 Đối tượng dữ liệu và kiểu thuộc tính

 Vai trò của hiểu dữ liệu

Hiểu dữ liệu

Phiên bản 2011 nhấn mạnh Hiểu dữ liệu !

 Thay đổi đáng kể từ phiên bản 2006 tới phiên bản 2011:

Hiểu dữ liệu qua hai phiên bản sách

Bước P3 “Hiểu dữ liệu”, Bước P4 “Tiền xử lý dữ liệu”

 Mô hình quá trình khai phá dữ liệu hướng miền ứng dụng [CYZ10]:

Một mô hình KPDL hướng ứng dụng Vai trò của hiểu dữ liệu:

 Tập trung và phân tán

 Phân bố

 Mẫu phụ thuộc quy mô

 Phân tích

 Chỉ mang tính hiện diện

 Thưa

 Tai họa của kích thước lớn

 Kích thước

Đặc trưng quan trọng của DL có cấu trúc



Dữ liệu Video



Dữ liệu ảnh, DL không gian: bản đồ

 Không gian, ảnh và đa phương tiện:

5 4

Coke, Diaper, Milk Beer, Bread, Diaper, Milk



Dữ liệu dãy gene



3 2

Beer, Coke, Diaper, Milk Beer, Bread



Dữ liệu dãy: dãy giao dịch Dữ liệu thời gian: chuỗi thời gian

Bread, Coke, Milk



Dữ liệu Video: dãy các ảnh

TID

Items

 Thứ tự



Cấu trúc phân tử

 Mạng xã hội và mạng thông tin

 World Wide Web

 Đồ thị và mạng



Dữ liệu giao dịch



vector tần số từ … Dữ liệu tài liệu: Tài liệu văn bản dùng

chéo…

 Ma trận DL, chẳng hạn, ma trận số, bảng



Bản ghi quan hệ

 Bản ghi

3.1.2. Kiểu tập dữ liệu

 Cỡ tỷ lệ

 Cỡ khoảng

 Số: định lượng

 Nhị phân

 Đinh danh

 Kiểu:

 Ví dụ, ChisoKH, tên, địa chỉ tượng DL. biểu diễn một thuộc tính/đặc trưng của một đối trưng_features, biến_variables): một trường DL  Thuộc tính_Attribute (hoặc chiều_dimension, đặc

Thuộc tính

 Dòng CSDL -> đối tượng DL; cột ->thuộc tính.

 Đối tượng DL được mô tả bằng các thuộc tính (attributes)

điểm DL (data points), đối tượng (objects), bộ (tuples).

 Tên khác: mẫu (samples ), ví dụ (examples), thể hiện (instances),

 CSDL đại học: sinh viên, giáo sư, môn học

 CSDL y tế: bệnh nhân, điều trị

 CSDL bán hàng: Khách hàng, mục lưu, doanh số

 Ví dụ:

thể.

 Mỗi đối tượng dữ liệu (data object) trình bày một thực

 Tập DL được tạo nên từ các đối tượng DL.

Đối tượng dữ liệu

tổng số đếm được, số lượng tiền

 Ví dụ, nhiệt độ theo Kelvin, độ dài đếm được,

đo lường (10 K˚ là hai lần cao hơn 5 K˚).

 Các giá trị là một thứ bậc của độ đo so với đơn vị

 zero-point vốn có

 Tỷ lệ

 Không làm điểm “true zero-point”

 Chẳng hạn, nhiệt độ theo C˚hoặcF˚, ngày lịch

 Các giá trị có thứ tự

thước

 Được đo theo kích thước các đơn vị cùng kích

 Khoảng  Số lượng (nguyên hay giá trị thực)

Kiểu thuộc tính số

 Size = {small, medium, large}, grades, army rankings

trị liên kết: không được biết

 Các giá trị có thứ tự mang nghĩa (xếp hạng) nhưng độ lớn các giá

 Có thứ tự

dương tính HIV)

 Quy ước: gán 1 cho kết quả quan trọng nhất (chẳng hạn,  Chẳng hạn, kiểm tra y tế (tích cực/tiêu cực)

 Nhị phân phi ĐX: kết quả không quan trọng như nhau.

 Chẳng hạn, giới tính

 Nhị phân đối xứng: Cả hai kết quả quan trọng như nhau  Thuộc tính định danh hai trạng thái (0 và 1)

 Nhị phân

số ID (ID numbers), mã zip bưu điện (zip codes)

 Tình trạng hôn nhân (marital status), nghề nghiệp (occupation),  Hair_color = {auburn, black, blond, brown, grey, red, white}

 Định danh: lớp, trạng thái, hoặc “tên đồ vật”

Kiểu thuộc tính

 Gần-Proximity chỉ dẫn tới tương tự hoặc phân biệt

 Giới hạn trên tùy

 Phân biệt tối thiểu là 0

 Càng thấp khi các đối tượng càng giống nhau

 Độ đo bằng số cho biết hai đối tượng khác nhau ra sao

 Phân biệt-Dissimilarity (như khoảng cách)

 Thường thuộc đoạn [0,1]

 Giá trí càng cao khi hai đối tượng càng giống nhau

 Độ đo bằng số cho biết hai đối tượng giống nhau ra sao

 Tương tự

3.1.4. Tương tự và phân biệt

động

 Thuộc tính liên tục được trình bày phổ biến như biến dấu phảy

hạn chữ số

 Thực tế, giá trị thực chỉ tính và trình bảng bằng sử dụng một hữu

 Như nhiệt độ, chiều cao, trong lượng

 Có rất nhiều các giá trị thuộc tính

 Thuộc tính liên tục

rạc

 Lưu ý: Thuộc tính nhị phân là trường hợp riêng của thuộc tính rời  Đôi lúc trình bày như các biến nguyên

tập tài liệu

 Chẳng hạn, mã zip, nghề nghiệp haowcj tập ácc từ trong một

 Chỉ có một tập hữu hạn hoặc hữu hạn đếm được các giá trị

 Thuộc tính rời rạc

Thuộc tính rời rạc và liên tục

thái định danh

 Tạo một TT nhị phân mới cho mỗi từ M trạng

 Phương pháp 2: Dùng lượng lớn TT nhị phân

)



 m: lượng đối sánh, p: tổng số lượng biến

 Phương pháp 1: Đối sánh đơn giản

thuộc tính nhị phân) như “red, yellow, blue, green” (tổng quát hóa  Có thể đưa ra 2 hoặc nhiều hơn các trạng thái,

Đo khảng cách thuộc tính định danh

nd (

)1,

nd (

)2,

...

: )2,3(

: 0

: d(3,1

)

 Chế độ đơn  Ma trận tam giác ghi khoảng cách

       

       

d(2,1) 0

 n điểm DL nhưng chi

 Ma trận phân biệt

...

 Hai chế độ  n điểm DL có p chiều

        

        

n1x ... i1x ... 11x

...

nfx ... ifx ... 1fx

npx ... ipx ... 1px

...

 Ma trân DL

Ma trận DL và ma trận phân biệt





(

jim

mary

)

75.0





(

jack

jim

)

67.0





(

jack

mary

)

33.0



 Cho giá trị Y và P là 1, và giá trị N là 0:

 Các thuộc tính còn lại: nhị phân phi đối xứng  Giới tính: thuộc tính nhị phân đối xứng

Y Y Y

P N N

N N N

N P N

N N N

N Jim M P Mary F P Jack M Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4

 Ví dụ

Phân biệt giữa các biến nhị phân

 Chú ý: Hệ số Jaccard giống độ “gắn kết” (coherence):

các biến nhị phân không ĐX):

 Hệ số Jaccard (đo tương tự cho

phân không đối xứng:

 Đo khoảng cách các biến nhị

phân đối xứng:

 Đo khoảng cách các biến nhị

 Bảng kề cho dữ liệu nhị phân

Object i

Đo khoảng cách các thuộc tính nhị phân

Object j

4.24

5.39

2.24

5.1

3.61

(với khoảng cách Ơcơlit)

Ma trận phân biệt

Ma trận DL

Ví dụ: Ma trận DL và ma trận phân biệt

chuẩn

 Dùng độ lệch tuyệt đố trung bình là mạnh mẽ hơn so với độ lệch

 Độ chuẩn hóa (z-score):



s  mx

 ...



nf x

2 x

trong đó











2 x

 ...

nf x

(xn m  1 xn (|1  Một cách khác: Tính độ lệch tuyệt đối trung bình

 Âm (-) khi DL thô nhỏ thua kỳ vọng, “+” khi lớn hơn above  Khoảng cách giữa DL thô và kỳ vọng theo đơn vị độ lệch chuẩn

tập số, σ: độ lệch chuẩn

 X: DL thô sẽ được chuẩn hóa, μ: trung bình mẫu (kỳ vọng_ của

 Z-score:

 

 x

Chuẩn hóa DL số

các vector

 Là sự khác biệt cực đại giữa các thành phần (thuộc tính) của

 h  . Khoảng cách “supremum” (chuẩn Lmax, chuẩn L) j 1









jid ),(

 ...

i x

)| 2

i 1 x  h = 2: Khoảng cách Ơcơlit - Euclidean (chuẩn L2)

j 1







jid

 |),(

i 1 x

i x

 ...

i p x

của hai vector nhị phân

 Chẳng hạn, khoảng cách Hamming: số lượng bit khác nhau

 h = 1: khoảng cách Manhattan (khối thành thị, chuẩn L1)

KC Minkowski: các trường hợp đặc biệt

 Một KC bảo đảm 3 tính chất trên là một metric

 d(i, j)  d(i, k) + d(k, j) (Bất đẳng thức tam giác)

 d(i, j) = d(j, i) (đối xứng)

 d(i, j) > 0 nếu i ≠ j, và d(i, i) = 0 (xác định dương)

 Tính chất

chuẩn L-h) tượng DL p-chiều, và h là bậc (KC này còn được gọi là

với i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là hai đối

 KC Minkowski: Một độ đo khoảng cách điển hình

Khoảng cách DL số: KC Minkowski

cỡ-khoảng

 Tính toán độ phân biệt sử dụng phương pháp với biến







thành biến f :

 Ánh xạ phạm vi biến vào [0, 1] khi thay thể đối tượng I  Thay xif bằng hạng của nó

if r 

,...,1{

}

 Có thể coi cỡ-khoảng

 Thứ tự là quan trọng, chẳng hạn như “hạng”

 Một biến có thứ tự có thể rời rạc hoặc liên tục

Biến có thứ tự

5 0

1 5 0

3 2 3 0

x4 x3 x2 x1 L

Supremum

5.39 0

1 5.1 0

4.24 2.24 3.61 0

x4 x3 x2 x1 L2

Euclidean (L2)

7 0

1 6 0

x4 x3 x2 x1 L

6 3 5 0 x1

x2 Manhattan (L1)

Ma trận phân biệt

Ví dụ: KC Minkowski

với  chỉ tích vector vô hướng, ||d||: độ dài vector d

cos(d1,d2) = (d1  d2) /||d1|| ||d2|| ,

 Độ đo Cosine: d1 và d2: hai two vector (như vector tần suất từ), thì

...

 Ứng dụng: truy hồi thông tin, phân cấp sinh học, ánh xạ đặc trưng gene,  Đối tượng vector khác: đặc trưng gene trong chuỗi phân tử, …

nhận tần số của các phần tử (như từ khóa, n-gram) hoặc cụm từ

 Một tài liệu có thể được trình bày bằng hàng nghìn thuộc tính, mỗi ghi

Độ tương tự cosine



 Cho zif như cỡ-khoảng  Tính toán hạng rif và



zif



M r

dij

 f là thứ bậc  f là số: sử dụng khoảng cách đã chuẩn hóa (f) = 1 ngược lại

(f) = 0 nếu xif = xjf , hoặc dij  f là nhị phân hay định danh:



jid ),(



f ij 1   p ( f  f 1 ij  d p (

)

) ij (

)

của chúng

 Có thể sử dụng công thức trọng số để kết hợp tác động

số, thứ tự

 Định danh, nhị phân đối xứng, nhị phân phi đối xứng,

 Một CSDL chứa mọt kiểu thuộc tính

Thuộc tính có kiểu pha trộn

xứng, không bảo đảm bất đẳng thức tam giác

 Phân kỳ KL : không là độ đo khoảng cách, không là metric: phi đối

 Dạng liên tục:

một lý thuyết, mô hình, mô tả, hoặc xấp xỉ p(x)

(phân bố “true”) khi dùng một mã dựa trên q(x), được biểu diễn như

 Phân kỳ KL đo số kỳ vọng các bit yêu cầu thêm để mã hóa ví dụ từ p(x)

 Dạng rời rạc: q(x) được dùng để xấp xỉ p(x)

 DKL(p(x), q(x)): phân kỳ của q(x) từ p(x), đo độ mất mát thông tin khi

thông tin, và thông tin để phân biệt

 Từ lý thuyết thông tin: liên quan chặt với entropy tương đối, phân kỳ trên cùng biến x

 Phân kỳ Kullback-Leibler (KD) : Do sự khách biệt hai phân bố xác suất

So sánh hai phân bố XS: Phân kỳ KL

cos(d1,d2 ) = 0.94

= 4.12

||d2||= (3*3+0*0+2*2+0*0+1*1+1*1+0*0+1*1+0*0+1*1)0.5=(17)0.5

= 6.481

||d1||= (5*5+0*0+3*3+0*0+2*2+0*0+0*0+2*2+0*0+0*0)0.5=(42)0.5 d1d2= 5*3+0*0+3*2+0*0+2*1+0*1+0*1+2*1+0*0+0*1 = 25

d2 = (3, 0, 2, 0, 1, 1, 0, 1, 0, 1) d1 = (5, 0, 3, 0, 2, 0, 0, 2, 0, 0)

 Ví dụ: Tìm độ tương tự giữa hai tài liệu 1 và 2.

ở đây  chỉ tích vô hướng, ||d|: độ dài vector d

 cos(d1, d2) = (d1  d2) /||d1|| ||d2|| ,

Ví dụ: Đô tương tự Cosine

 Tạo điều kiện quản trị dữ liệu tốt hơn để đáp ứng mối quan

 Rút gọn sự tăng không cần thiết của dữ liệu

 Hỗ trợ việc quản lý và bảo quản dữ liệu tập trung hóa

tâm đúng đắn

 Loại bỏ ràng buộc không gian/thời gian khi di chuyển khối

 Kết nối mức thấp để truy nhập trực tiếp CSDL

 Ngôn ngữ hỏi bậc cao truy nhập trực tiếp CSDL

 Trích chọn dữ liệu theo câu hỏi từ CSDL tới tập tin phẳng Data Acquisition:

 Cách thu thập dữ liệu cần thiết để mô hình hóa

3.1.4. Thu thập dữ liệu

 DKL(P’,Q’) có thể tính toán được  Q′ : (a : 5/9 − ϵ/3, b : 3/9 − ϵ/3, c : ϵ, d : 1/9 − ϵ/3).  P′ : (a : 3/5 − ϵ/3, b : 1/5 − ϵ/3, c : 1/5 − ϵ/3, d : ϵ)  Làm trơn, bổ sung ký hiệu thiếu cho mỗi phân bố với xác suất ϵ

= {a, b, c, d}

 Tập mẫu được quan sát trong P, SP = {a, b, c}, SQ = {a, b, d}, SU  Đưa vào một hằng số rất nhỏ ϵ,: chẳng hạn, ϵ = 10−3

 Ví dụ: P : (a : 3/5, b : 1/5, c : 1/5). Q : (a : 5/9, b : 3/9, d : 1/9)

năng của cái không nhìn thấy: làm trơn (smoothing ) là cần thiết

 Thực tế: P và Q được cung cấp từ phân bố tần suất, không xem xét khả

0), thì hai phân bố là khác biệt tuyệt đối e là khả năng (p(e) > 0), và dự báo q là không thể tuyệt đối (q(e) =  Khi p = 0 nhưng q != 0, DKL(p, q) được định nghĩa là ∞: một sự kiện  limq→0 q log q = 0  Xem xét p =0 hoặc q = 0  Dựa trên công thức, DKL(P,Q) ≥ 0 và DKL(P,Q) = 0  P = Q.

Cách tính PK KL

lượng lớn dữ liệu

 Cung cấp kỹ thuật đồ họa biểu diễn tần số giá trị của một biến

 Lược đồ (Histograms)

 Phân bố tần suất giá trị của các biến

 Bảng tần suất (Frequency tables)

 Min, Q1, Median, Q3, Max

interquartile range (IQR): Q3-Q1

 Q1=25%, Q2=50%, Q3=75% |yD: miny x|/|yD|=k%  [Min, Max]: giá trị k% là giá trị x sao cho

 Độ đo phân tán

 Giá trị nhỏ nhất và Giá trị lớn nhất

 Cực tiểu (Minimum) và Cực đại (Maximum)

 Phân bố dữ liệu xung quanh kỳ vọng  Độ lệch chuẩn (Standard deviation)

Một số độ đo thống kê

bimodal, trimodal, v.v.

 Mode: Tập con dữ liệu xuất hiện với tần số cao nhất. unimodal,

 Trung vị

 Xu hướng trung tâm của tập dữ liệu

 Giá trị kỳ vọng (mean)

3.1.5 . Mô tả thống kê cơ bản của dữ liệu

3.1.6. Mô tả dữ liệu: trực quan hóa

cần kiểm tra là giá trị ngoại lai Q1-1.5*IQR, Q1, Median, Q3, Q3+1.5*IQR nếu nằm ngoài Min, Q1, Median, Q3, Max

Biểu diễn giá trị dữ liệu

 Rời rạc hóa và sinh kiến trúc khái niệm

 Rút gọn dữ liệu

 Tích hợp và chuyển dạng dữ liệu

 Làm sạch dữ liệu

 Vai trò của Tiền xử lý dữ liệu

3.2. Tiền xử lý dữ liệu

 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

 Bất cứ dữ liệu đáng ngờ, như mã thiếu (miscodes), dữ liệu học, dữ liệu  Số lượng và phân bố các khoảng trong trong mọi trường hợp  Các ngoại lai tiềm năng bất kỳ  Tâm của dữ liệu

 Lập hồ sơ dữ liệu (cơ sở căn cứ: phân bố dữ liệu)

test, hoặc chỉ đơn giản dữ liệu rác

 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ữ  Mô tả dữ liệu sẽ làm hiện rõ một số vấn đề

liệu chất lượng kém.

 Định vị một vấn đề trong dữ liệu cần giải quyết: Tìm ra và quyết định

 Đánh giá dữ liệu

3.1.7. Đánh giá và lập hồ sơ dữ liệu

cách nắm bắt vấn đề

IEEE Data Engineering Bulletin, 23(4): 3-13, 2000.

[RD00] Erhard Rahm, Hong Hai Do (2000). Data Cleaning: Problems and Current Approaches,

- (Dữ liệu chồng chéo, mâu thuẫn và không nhất quán) không nhất quán tích hợp và

- (Mô hình dữ liệu và thiết kế sơ đồ không đồng nhất) xung đột tên, cấu trúc

- (Lỗi nhập dữ liệu) sai chính tả, dư thừa/sao, giá trị mâu thuẫn…

- (Thiếu lược đồ toàn vẹn, thiết kế sơ đồ sơ sài) đơn trị, toàn vẹn tham chiếu…

Các vấn đề về chất lượng dữ liệu [RD00]

sử dụng trong điều hành, ra quyết định, và lập kế hoạch  Dữ liệu có chất lượng cao nếu như phù hợp với mục đích

chọn, làm sạch và chuyển đổi dữ liệu —Bill Inmon .  Phân lớn công việc xây dựng một kho dữ liệu là trích

lượng

 Kho dữ liệu cần tích hợp nhất quán của dữ liệu chất

chính xác, thậm chí gây hiểu nhầm.

 Chẳng hạn, dữ liệu bội hay thiếu là nguyên nhân thống không  Quyết định chất lượng phải dựa trên dữ liệu chất lượng

 Không có dữ liệu tốt, không thể có kết quả khai phá tốt!

3.2.1. Vai trò của tiền xử lý

thời gian

biệt với dữ liệu số

 Bộ phận của rút gọn dữ liệu nhưng có độ quan trọng riêng, đặc

 Rời rạc dữ liệu

hoặc tương tự kết quả phân tích

 Thu được trình bày thu gọn về kích thước những sản xuất cùng

 Rút gọn dữ liệu

 Chuẩn hóa và tổng hợp

 Chuyển dạng dữ liệu

 Tích hợp CSDL, khối dữ liệu hoặc tập tin phức

 Tích hợp dữ liệu

ngoại lai, và khử tính không nhất quán

 Điền giá trị thiếu, làm trơn dữ liệu nhiễu, định danh hoặc xóa

 Làm sạch dữ liệu

Các bài toán chính trong tiền XL DL

(accessibility). diễn (representational), và tiếp cận được

 Bản chất (intrinsic), ngữ cảnh (contextual), trình

 Phân loại bề rộng (Broad categories):

 Tiếp cận được (Accessibility)  Biểu diễn được (Interpretability)  Giá trị gia tăng (Value added)  Độ tin cậy (Believability)  Tính kịp thời (Timeliness)  Tính nhất quán (Consistency)  Tính đầy đủ (Completeness)  Độ chính xác (Accuracy)  Khung đa chiều cấp nhận tốt:

Độ đo đa chiều chất lượng dữ liệu

 Cách thức tạo biến mới: Data Derivation

 Giá trị: Data Discretization

 Biến: Dimensionality Reduction

 Bản ghi : Data Sampling

 Cách thức rút gọn dữ liệu để dùng: Data Reduction

 Data Abstraction

 Cách thức nắm bắt dữ liệu thời gian/chuỗi thời gian:

 Data Filtering

 Xử lý dữ liệu ngoại lai và không mong muốn khác:

 Data Weighting and Balancing  Trọng số của các trường hợp:

 Data Imputation

 Cách thức nắm bắt giá trị thiếu:

 Data Transformation  Cách thức diễn giải dữ liệu:

 Data Cleaning

 Cách thức làm sạch dữ liệu:

Một số bài toán cụ thể

Các thành phần của tiền xử lý dữ liệu (Bảng 2.1)

 Giải quyết tính dư thừa tạo ra sau tích hợp dữ liệu.

 Chỉnh sửa dữ liệu không nhất quán

 Dữ liệu nhiễu: định danh ngoại lai và làm trơn.

 Xử lý giá trị thiếu

 Các bài toán thuộc làm sạch dữ liệu



 Vai trò quan trọng chữa dữ liệu (Maletic và Marcus 2000) và không thể bỏ qua việc xác nhận và sửa  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  Phòng ngừa liên quan chặt chẽ với thu thập và nhập dữ liệu vào CSDL.  hai vấn đề cốt lõi để cải thiện chất lượng - phòng ngừa và chỉnh sửa quản lý dữ liệu (nắm giữ, số hóa, lưu trữ, phân tích, trình bày và sử dụng).  Nguyên lý chất lượng dữ liệu cần được áp dụng ở mọi giai đoạn quá trình

Làm sạch dữ liệu

“là bài toán “number one” trong kho dữ liệu”—DCI khảo sát “là một trong ba bài toán lớn nhất của kho dữ liệu”—Ralph Kimball

 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.

 Quá trình thường dẫn đến

 đánh giá dữ liệu của các chuyên gia miền chủ đề.

ngờ. 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

 xem xét dữ liệu để xác định ngoại lai (địa lý, thống kê, thời gian hay môi

 kiểm tra định dạng, tính đầy đủ, tính hợp lý, miền giới hạn,

 Quá trình bao gồm

 nâng cao chất lượng dữ liệu.

 chỉnh sửa các sai sót và thiếu sót được phát hiện

 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

 Là quá trình

3.2.2. Làm sạch dữ liệu

trường) hoặc các lỗi khác,

 Dữ liệu không nhất quán

 Dữ liệu không đầy đủ

 Bội bản ghi

 Các vấn đề dữ liệu khác yêu cầu làm sạch dữ liệu

 Thiết nhất quán khi đặt tên: cũng một tên song cách viết khác nhau

 Hạn chế của công nghệ: ví dụ, phần mềm có thể xử lý không đúng  Vấn đề truyền dữ liệu: sai từ thiết bị gửi/nhận/truyền  Vấn đề nhập dữ liệu: người dùng hoặc máy có thể sai  Lỗi do thiết bị thu thập dữ liệu

 Giá trị không chính xác

 Biến dạng của một biến đo được  Lỗi ngẫu nhiên

 Nhiễu:

Dữ liệu nhiễu

 Giá trị có khả năng nhất: dựa trên suy luận như công thức Bayes hoặc  Trung bình giá trị thuộc tính các bản ghi cùng lớp: tinh hơn  Trung bình giá trị thuộc tính các bản ghi hiện có

cây quyết định

 Hằng toàn cục: chẳng hạn như“chưa biết - unknown”, có phải một lớp

 Điền giá trị tự động:



mới

 Điền giá trị thiếu bằng tay:

 không hiểu quả khi tỷ lệ số lượng giá trị thiếu lớn (bán giám sát)  Thường làm khi thiếu nhãn phân lớp (giả sử bài toán phân lớp)

 Bỏ qua bản ghi có giá trị thiếu:

3.2.3. Xử lý thiếu giá trị

tính khả thi tẻ nhạt

 Việc quản lý các thuộc tính lớp: có thể “khôn khéo”.

 Khả cỡ dữ liệu: tốt.

lượng”, các đoạn có xấp xỉ số ví dụ mẫu.

 Chia miền xác định thành N đoạn “đều nhau về số

(frequency) partitioning:

 Phân hoạch cân bằng theo chiều sâu Equal-depth

 Không xử lý tốt khi dữ liệu không cân bằng (đều).  Đơn giản nhất song bị định hướng theo ngoại lai.

A)/N.

 Miền giá trị từ A (nhỏ nhất) tới B (lớn nhất) ->W = (B –  Chia miền giá trị: N đoạn dài như nhau: uniform grid partitioning:

 Phân hoạch cân bẳng bề rộng Equal-width (distance)

P/pháp rời rạc hóa đơn giản: Xếp thùng (Binning)

 Làm trơn: ghép dữ liệu theo các hàm hồi quy

 Hồi quy

hạn, đối phó với ngoại lai có thể)

 Phát hiện giá trị nghi ngờ để con người kiểm tra (chẳng

 Kết hợp kiểm tra máy tính và con người

 Phát hiện và loại bỏ ngoại lai (outliers)

 Phân cụm (Clustering)

biên…

 Làm trơn: theo trung bình, theo trung tuyến, theo  Sắp dữ liệu tăng và chia “đều” vào các thùng

 Phương pháp đóng thùng (Binning):

Xử lý dữ liệu nhiễu

Thuật toán phân cụm: Chương 6.

Làm trơn phần tử trong cụm theo đại diện.

Cụm: Các phần tử trong cụm là “tương tự nhau”

Phân tích cụm (Cluster Analysis)

- Bin 3: 26, 26, 26, 34 - Bin 2: 21, 21, 25, 25 - Bin 1: 4, 4, 4, 15 * Làm trơn thùng theo biên: - Bin 3: 29, 29, 29, 29 - Bin 2: 23, 23, 23, 23 - Bin 1: 9, 9, 9, 9

* Làm trơn thùng theo trung bình:

- Bin 3: 26, 28, 29, 34 - Bin 2: 21, 21, 24, 25 - Bin 1: 4, 8, 9, 15

* Chia thùng theo chiều sâu: * Dữ liệu được xếp theo giá: 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34

P/pháp xếp thùng làm trơn dữ liệu (Data Smoothing)

chẳng hạn, đơn vị quốc tế khác với Anh quốc

 Nguyên nhân: trình bày khác nhau, cỡ khác nhau,

khác nhau là khác nhau

 Cùng một thực thể thực sự: giá trị thuộc tính các nguồn

 Phát hiện và giải quyết vấn đề thiết nhất quá dữ liệu

nguồn dữ liệu phức, chẳng hạn, A.cust-id  B.cust-#

 Vấn đề định danh thực thế: xác định thực thể thực tế từ  Tích hợp sieu dữ liệu từ các nguồn khác nhau

 Tích hợp sơ đồ

trữ chung

 Kết hợp dữ liệu từ nhiều nguồn thành một nguồn lưu

 Tích hợp dữ liệu (Data integration):

3.3.4. Tích hợp dữ liệu

Y1’

y = x + 1

Hồi quy (Regression)

Nguồn dữ liệu đơn: mức thể hiện (Ví dụ)

Nguồn dữ liệu đơn: mức sơ đồ (Ví dụ)

lượng

dư thừa, thiếu nhất quán và tăng hiệu quả tốc độ và chất

 Tích hợp cẩn trọng dữ liệu nguồn phức giúp giảm/tránh

tương quan

 Dữ liệu dư thừa có thể được phát hiện khi phân tích

khác, chẳng hạn, doanh thu hàng năm

 Một thuộc tính: thuộc tính “nguồn gốc” trong CSDL

khác nhau

 Một thuộc tính có nhiều tên khác nhau ở các CSDL

khác nhau

 Dư thừa dữ liệu: thường có khi tích hợp từ nhiều nguồn

Nắm bắt dư thừa trong tích hợp dữ liệu

Nguồn dữ liệu phức: sơ đồ/thể hiện (Ví dụ)

j : số nguyên nhỏ nhất mà Max(| |)<1

'

 Chuẩn hóa tỷ lệ thập phân

dev



stand  v

_ mean







(

new

max

new

min

)

new

min

 Chuẩn hóa z-score max min  v

 min

 Chuẩn hóa min-max

Chuyển đổi dữ liệu: Chuẩn hóa

 Thuộc tính mới được xây dựng từ các thuộc tính đã có

 Xây dựng thuộc tính/đặc trưng

 Chuẩn hóa tỷ lệ thập phân

 Chuẩn hóa z-score

 Chuẩn hóa min-max

 Chuẩn hóa (Normalization): thu nhỏ vào miền nhỏ, riêng

 Tổng quát hóa (Generalization): leo kiến trúc khái niệm

 Tổng hợp (Aggregation): tóm tắt, xây dựng khối dữ liệu

 Làm trơn (Smoothing): loại bỏ nhiễu từ dữ liệu

Chuyển dạng dữ liệu

tổng hợp thông tin

 Nên sử dụng dữ liệu khối lập phương khi trả lời câu hỏi

 Sử dụng trình diễn nhỏ nhất đủ để giải bài toán

 Tham khảo mức thích hợp

 Giảm thêm kích thước dữ liệu

 Các mức phức hợp của tích hợp thành khối dữ liệu

điện thoại.

 Chẳng hạn, một khách hàng trong kho dữ liệu cuộc gọi

 Tổng hợp dữ liệu thành một cá thể quan tâm

 Mức thấp nhất của khối dữ liệu

Kết hợp khối dữ liệu: DataCube Aggregation

 Rời rạc hóa và sinh cây khái niệm  Giảm tính số hóa – dữ liệu thành mô hình  Nén dữ liệu  Giảm đa chiều – loại bỏ thuộc tính không quan trọng  Tập hợp khối dữ liệu

 Chiến lược rút gọn dữ liệu

lượng mà sinh ra cùng (hoặc hầu như cùng) kết quả.

 Có được trình bày gọn của tập dữ liệu mà nhỏ hơn nhiều về khối

 Rút gọn dữ liệu

tập toàn bộ dữ liệu

 Phân tích/khai phá dữ liệu phức mất thời gian rất dài khi chạy trên

 Kho dữ liệu chứa tới hàng TB

Chiến lược rút gọn dữ liệu

Class 1

Class 2

A1?

A6?

A4 ?

{A1, A2, A3, A4, A5, A6} Tập thuộc tính khởi tạo:

Ví dụ rút gọn cây quyết định

 Rút gọn câu qyuyết định  Kết hợp chon chuyển tiếp và loại bỏ lạc hậu.  Khôn ngoan chọn chuyển tiếp từ phía trước

 Phương pháp Heuristic (có lực lượng mũ # phép chọn):

hiểu dữ liệu

 Rút gọn # của các mẫu trong tập mẫu dễ dàng hơn để

các đặc trưng các lớp này gần như phân bổ vốn có đã cho giá trị của suất của các lớp khác nhau cho giá trị khi cho giá trị của

 Lựa chọn tập nhỏ nhất các đặc trưng mà phân bố xác

 Rút gọn đặc trưng (như., lựa chọn tập con thuộc tính):

Rút gọn chiều

> Tập thuộc tinh rút gọn: {A1, A4, A6}

Phân lớp cây quyết định

 Xem Chương 5  Các lá là các nhãn, hoặc các lớp.

đỉnh trong

 Các nhánh tương ứng với kết quả kiểm tra tại  Đỉnh trong là một hàm test  Đồ thị dạng cây

Phân lớp cây quyết định

 Sử dụng loại bỏ đặc trưng và tùy chọn

 Nhánh cận và phạm vi tối ưu:

 Kết hợp lựa chọn và loại bỏ tốt nhất

 Loại bỏ lặp các đặc trưng tồi nhất

 Loại bỏ đặc trưng khôn ngoan từng bước:

chọn tốt nhất trước đó, ...

 Tiếp đó, chọn tốt nhất tiếp theo theo điều kiện đã  Các thuộc tính đơn tốt nhất được chọn đầu tiên  Lựa chọn đặc trưng khôn ngoan từng bước tốt nhất:

trưng: chọn từ kiểm thử điển hình.

 Các đặc trưng tốt nhất theo giả thiết độc lập đặc

 Một vài phương pháp chọn đặc trưng heuristic:  Có 2d tập con đặc trưng từ d đặc trưng

Phương pháp chọn đặc trưng Heuristic

chưa được gán nhãn

 Sử dụng cây quyết định: phân lớp các đối tượng

những đối tượng mới nhánh rườm rà tăng độ chính xác khi phân lớp

 Phương pháp bottom-up: xác định và loại bỏ những

 Cắt tỉa cây (pruning)

 Phương pháp top-down  Xây dựng cây quyết định  Xây dựng cây quyết định:

Phân lớp cây quyết định

Approximated

Original Data

lossless

Original Data

Data Compressed

Nén dữ liệu (Data Compression)

 Ngắn điển hình và thay đổi chậm theo thời gian

 Chuỗi thời gian mà không là audio

cần dựng toàn bộ

 Vài trường hợp mảnh tín hiệu nhỏ được tái hợp không  Nén tổn thất điển hình, với tinh lọc cải tiến

 Nén Audio/video

 Yếu: chỉ các thao tác hạn hẹp mà không mở rộng  Mạnh: Không tốn thất điển hình  Tồn tại lý thuyết phong phú và thuật toán điển hình

 Nén xâu văn bản

Nén dữ liệu (Data Compression)

Low Pass High Pass

 Image

DWT cho nén ảnh

Haar2

Daubechie4

 Áp dụng đệ quy hai chức năng đến độ dài mong muốn

 Áp dụng cho các cặp DL, kết quả theo 2 tập DL độ dài L/2

 Mỗi phép biến đổi có 2 chức năng: làm mịn, tách biệt

khi cần)

 Độ dài, L, buộc là số nguyên lũy thừa 2 (đệm thêm các chữ số 0,

 Phương pháp:

tổn thất tốt hơn, bản địa hóa trong không gian

 Tương tự như biến đổi rời rạc Fourier (DFT), nhưng nén

 Xấp xỉ nén: chỉ lưu một mảnh nhỏ các hệ số sóng lớn nhất

XL tín hiệu tuyến tính, phân tích đa giải pháp

 Biến dạng sóng rời rạc (Discrete wavelet transform:DWT):

Chuyển dạng sóng (Wavelet Transformation)

Phân tích thành phần chính (PCA)

 Dùng khi số chiều vector lớn.

 Chỉ áp dụng cho dữ liệu số.

thành phần chính.

 Mỗi vector dữ liệu là tổ hợp tuyến tính của các vector

chiều: c thành phần chính (chiều được rút gọn).

 Tập dữ liệu gốc được rút gọn thành N vector dữ liệu c

giao tốt nhất để trình diễn dữ liệu.

 Cho N vector dữ liệu k-chiều, tìm c (<= k) vector trực

Phân tích PCA (Principal Component Analysis )

100

xác suất đa chiều

 Mô hình tuyến tính loga: rời rạc hóa xấp xỉ các phân bố

như ột hàm tuyến tính của vector đặc trưng đa chiều

 Hồ quy đa chiều: Cho một biến đích Y được mô hình hóa

khớp với đường

 Thường dùng phương pháp bình phương tối thiểu để

đường thẳng

 Hồ quy tuyến tính: DL được mô hình hóa phù hợp với 1

Mô hình hồi quy tuyến tính và logarit

(clustering), lấy mẫu (sampling)

 Tập hợp chính: biểu đồ (histograms), phân cụm

 Không giả thiết mô hình

 Phương pháp không tham số

các không gian con thích hợp tại một điểm trong không gian M-chiều như là tích của  Mô hình tuyến tính loga (Log-linear models): lấy giá trị

liệu (ngoại trừ các ngoại lai có thể có) tham số mô hình, lưu chỉ các tham số, và không lưu dữ  Giả sử dữ liệu phù hợp với mô hình nào đó, ước lượng

 Phương pháp tham số

Rút gọn kích thước số

101

10000

30000

50000

70000

90000

lượng tử hóa.

 Có quan hệ tới bài toán

dùng quy hoạch động

ưu hóa theo 1 chiều khi

 Có thể được dựng tối (tổng) của mỗi thùng thùng và giữ trunh bình

 Phân dữ liệu vào các

phổ biến

 Kỹ thuật rút gọn dữ liệu

Lược đồ (Histograms)

 Xác suất: p(a, b, c, d) = ab acad bcd

tích của các bảng bậc thấp hơn

 Bảng đa chiều của xác suất tích nối được xấp xỉ bởi

 Mô hình tuyến tính loga:

trên.

 Nhiều hàm không tuyến tính được chuyển dạng như

 Hồi quy đa chiều: Y = b0 + b1 X1 + b2 X2.

Y1, Y2, …, X1, X2, ….

 Sử dụng chiến lược BP tối thiếu tới các giá trị đã biết

xỉ qua dữ liệu đã nắm bắt được.

 Hai tham số,  và  đặc trưng cho đường và được xấp

 Hồi quy tuyến tính: Y =  +  X

Phân tích mô hình hồi quy tuyến tính và logarit

102

 Lẫy mẫu có thể không rút gọn được CSDL.

 Sử dụng kết hợp với dữ liệu lệch

nhận diện được theo quan tâm) trong CSDL tổng thể

 Xấp xỉ theo phần trăm của mỗi lớp (hoặc bộ phận

 Lấy mẫu phân tầng:

 Phát triển các phương pháp lấy mẫu thích nghi

DL lệch

 Lấy mẫu ngẫu nhiên đơn giản có hiệu quả rất tồi nếu có

 Lựa chọn một tập con trình diễn dữ liệu

tựa tuyến tính theo cỡ của DL

 Cho phép một thuật toán khai phá chạy theo độ phức tạp

Rút gọn mẫu (Sampling)

toán phân cụm

 Tồn tài nhiều lựa chọn cho xác định phân cụm và thuật

trúc cây chỉ số đa chiều

 Có thể phân cụm phân cấp và được lưu trữ trong cấu

không chứa dữ liệu “bẩn”

 Có thể rất hiệu quả nếu DL là được phân cụm mà

của cụm

 Phân tập DL thành các cụm, và chỉ cần lưu trữ đại diện

Phân cụm

103

Raw Data

Mẫu cụm/phân tầng

Rút gọn mẫu (Sampling)

 Ví dụ: Chọn mẫu 2 (n) phần tử từ tập 4 dữ liệu

 Chọn một phần tử và không bị loại bỏ. Các mẫu DL phân biệt

 SRS without replacement (SRSWOR)

 Các phần tử dữ liệu giống nhau có thể được chọn nhiều lần

 Lặp tiếp cho đến khi có n phần tử dữ liệu

 Loại bỏ phần tử dữ liệu đó ra khỏi tập dữ liệu

 Chọn một phần tử dữ liệu đưa vào mẫu  SRS with replacement (SRSWR)

 Simple Random Sampling (SRS)

Rút gọn mẫu (Sampling)

104

 Chuẩn bị cho phân tích tiếp theo

 Rút gọn cỡ DL bằng rời rạc hóa

phân loại.

 Một vài thuật toán phân lớp chỉ chấp nhận thuộc tính  Chia miền thuộc tính liên tục thành các đoạn

 Rời rạc hóa:

 Liên tục — số thực  Thứ tự — giá trị từ một tập được sắp  Định danh — giá trị từ một tập không có thứ tự

 Ba kiểu thuộc tính:

Rời rạc hóa

đồ phân cấp

 Như vậy, cây chỉ số với tích hợp lưu trữ mỗi nút là một sơ  Mỗi vùng được coi như một thùng

vùng bởi miền giá trị của một vài thuộc tính

 Một cây chỉ số được chia phân cấp một tập DL thành các

 Tích hợp phân cấp

phân cấp

 Phương pháp tham số thường không tuân theo trình bày

hướng xác định phân vùng DL hớn là “phân cụm”

 Phân cụm phân cấp thường được thi hành song có khuynh

rút gọn

 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ấp

105

 Phân đoạn bằng phân chia tự nhiên

 Rời rạc hóa dựa theo Entropy

 Phân tích cụm (đã giới thiệu)

 Phân tích sơ đồ (đã giới thiệu)

 Phân thùng (xem làm trơn khử nhiễu)

Rời rạc hóa & kiến trúc khái niệm DL số

già) khái niệm ở mức cao hơn (như trẻ, trung niên, hoặc mức thấp (như giá trị số của thuộc tính tuổi) bằng  Rút gọn DL bằng tập hợp và thay thế các khái niệm

 Phân cấp khái niệm

Nhãn đoạn sau đó được dùng để thay thế giá trị thực. cách chia miền giá trị của thuộc tính thành các đoạn.  Rút gọn số lượng giá trị của thuộc tính liên tục bằng

 Rời rạc hóa

Rời rạc hóa và kiến trúc khái niệm

106

 Nếu phủ 1, 5, hoặc 10 giá trị phân biệt thì chia thành 5.

 Nếu phủ 2, 4, hoặc 8 giá trị phân biệt thì chia thành 4.

3 đoạn tương đương.

 Nếu 3, 6, 7 hoặc 9 giá trị khác biệt thì chia miền thành

 Hướng tới số giá trị khác biệt ở vùng quan trọng nhất

thành các đoạn tương đối thống nhất, “tự nhiên”.

 Quy tắc đơn giản 3-4-5 được dùng để phân đoạn dữ liệu số

Phân đoạn bằng phân hoạch tự nhiên

độ chính xác phân lớp

 Thực nghiệm chỉ ra rằng cho phép rút gọn cỡ DL và tăng





( ) Ent S

( , ) E T S

dừng nào đó, như

 Quá trình đệ quy tới các vùng cho tới khi đạt điều kiện

chọn như một rời rạc hóa nhị phân.

 Biên làm cực tiểu hàm entropy trên tất cả các biên được





( , E S T

Ent

1 )

)

(

)

S | | S 2

S | | S 1 | | dùng biên T, thì entropy sau khi phân đoạn là

 Cho tập ví dụ S, nếu S được chia thành 2 đoạn S1 và S2

Rời rạc hóa dựa trên Entropy

107

 Như, chỉ street < city mà không có cái khác

 Đặc tả một phần thứ tự bộ phận

 Như, street < city

lượng các giá trị khác biệt

 Tự động sắp xếp một phần bằng cách phân tích số

 Đặc tả theo tập các thuộc tính.

 {Urbana, Champaign, Chicago}

 Đặc tả thành cấu trúc phân cấp nhờ nhóm dữ liệu

 street

 Đặc tả một thứ tự bộ phận giá trị thuộc tính theo mức

Sinh kiến trúc khái niệm cho dữ liẹu phân loại

0) (-$100 -

$1,000) ($800 -

$2,000) ($1,800 -

$1,800) ($1,600 -

$800) ($600 -

$5,000) ($4,000 -

-$100) (-$200 -

$600) ($400 -

$1,600) ($1,400 -

$4,000) ($3,000 -

-$200) (-$300 -

$1,400) ($1,200 -

$400) ($200 -

$3,000) ($2,000 -

-$300) (-$400 -

$1,200) ($1,000 -

$200) (0 -

(-$400 - 0)

(0 - $1,000)

($1,000 - $2, 000)

($2,000 - $5, 000)

Step 4:

(-$4000 -$5,000)

(0 -$ 1,000)

($1,000 - $2,000)

(-$1,000 - 0)

Step 3:

(-$1,000 - $2,000)

msd=1,000

Low=-$1,000

High=$2,000

Step 2:

Min Low (i.e, 5%-tile)

High(i.e, 95%-0 tile) Max

Step 1:

-$351

-$159

profit

$1,838

$4,700

count

Ví dụ luật 3-4-5

108

street

674,339 giá trị phân biệt

city

3567 giá trị phân biệt

province_or_ state

65 giá trị phân biệt

country

15 giá trị phân biệt

 Lưu ý: Ngoài trừ, các ngày trong tuần, tháng, quý, năm

phân cấp thấp nhất

 Thuộc tính có giá trị phân biệt nhất được đặt ở cấp độ tính của tập DL đã cho trên phân tích số lượng các giá trị phân biệt theo thuộc  Một vài kiến trúc khái niệm có thể được sinh tự động dựa

Sinh kiến trúc khái niệm tự động

109

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

Dựa theo “Data Mining: Concepts and Techniques”

Chapter 6. Mining Association Rules in Large Databases

©Jiawei Han and Micheline Kamber

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

 Khai phá luật kết hợp (Association rule)

 Các thuật toán khai phá vô hướng luật kết hợp (giá trị

www.cs.uiuc.edu/~hanj

 Khai phá kiểu đa dạng luật kết hợp/tương quan

 Khai phá kết hợp dựa theo ràng buộc

 Khai phá mẫu dãy

110

lôgic đơn chiều) trong CSDL giao dịch

Khái niệm cơ sở: Tập phổ biến và luật kết hợp

Một số ví dụ về “luật kết hợp” (associate rule) • “98% khách hàng mà mua tạp chí thể thao thì đều mua các tạp chí về ôtô” sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ôtô”

Khái niệm cơ sở: Tập phổ biến và luật kết hợp

Renáta Iváncsy, István Vajk (2006). Frequent Pattern Mining in Web Log Data,

[IV06] Acta Polytechnica Hungarica, 3(1):77-90, 2006

111

• “60% khách hàng mà mua bia tại siêu thị thì đều mua bỉm trẻ em” sự kết hợp giữa “bia” với “bỉm trẻ em” • “Có tới 70% người truy nhập Web vào địa chỉ Url 1 thì cũng vào địa chỉ Url 2 trong một phiên truy nhập web”  sự kết hợp giữa “Url 1” với “Url 2”. Khai phá dữ liệu sử dụng Web (Dữ liệu từ file log của các site, chẳng hạn được MS cung cấp). • Các Url có gắn với nhãn “lớp” là các đặc trưng thì có luật kết hợp liên quan giữa các lớp Url này.

Khái niệm cơ sở: Tập phổ biến và luật kết hợp

Cơ sở dữ liệu giao dịch (transaction database)

• 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. Giao dịch T là một tập mục.

• Tập toàn bộ các mục I = {i1, i2, …, ik} “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  I. Mỗi giao dịch T có một định danh là TID. • A là một tập mục A  I và T là một giao dịch: Gọi T chứa A nếu A  T.

• Gọi A  B là một “luật kết hợp” nếu A  I, B  I và AB=. • Luật kết hợp A  B có độ hỗ trợ (support) s trong CSDL giao dịch D nếu trong D có s% các giao dịch T chứa AB: chính là xác suất P(AB). Tập mục A có P(A)  s>0 (với s cho trước) được gọi là tập phổ biến (frequent set). Luật kết hợp A  B có độ tin cậy (confidence) c trong CSDL D nếu như trong D có c% các giao dịch T chứa A thì cũng chứa B: chính là xác suất P(B|A).

= P(AB)

: 1  s (A  B)  0 : 1  c (A  B)  0

• Support (A  B) • Confidence (A  B) = P(B|A) • Luật A  B được gọi là đảm bảo độ hỗ trợ s trong D nếu s(A  B)  s. Luật AB được gọi là đảm bảo độ tin cậy c trong D nếu c(A  B)  c. Tập mạnh.

Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp

 Tập mục I={i1, …, ik}. CSDL giao dịch

D = {d  I}

Transaction-id

Items bought

A, B, C

 A, B  I, AB=: AB là luật kết hợp  Bài toán tìm luật kết hợp.

A, C

A, D

Cho trước độ hỗ trợ tối thiểu s>0, độ tin cậy tối thiếu c>0. Hãy tìm mọi luật kết hợp mạnh XY.

B, E, F

Customer buys both

• Luật kết hợp

Customer buys diaper

Giả sử min_support = 50%, min_conf = 50%:

niệm luật kết hợp với khái niệm phụ thuộc hàm.

Customer buys beer

 Các tính chất Armstrong ở đây.

112

A  C (50%, 66.7%) C  A (50%, 100%)  Hãy trình bày các nhận xét về khái

Một ví dụ tìm luật kết hợp

Transaction-id

Items bought

A, B, C

A, C

Frequent pattern

Support

A, D

{A}

75%

B, E, F

{B}

50%

{C}

50%

{A, C}

50%

For rule A  C:

support = support({A}{C}) = 50% confidence = support({A}{C})/support({A}) =

66.6%

Khai niệm khai phá kết hợp

113

Min. support 50% Min. confidence 50%

Khái niệm khai phá luật kết hợp

 Khai phá luật kết hợp:

 Tìm tất cả mẫu phổ biến, kết hợp, tương quan, hoặc cấu trú nhan-quả trong tập các mục hoặc đối tượng trong CSDL quan hệ hoặc các kho chứa thông tin khác.

 Mẫu phổ biến (Frequent pattern): là mẫu (tập mục, dãy mục…) mà xuất hiện phổ biến trong 1 CSDL [AIS93]  Động lực: tìm mẫu chính quy (regularities pattern) trong DL  Các mặt hàng nào được mua cùng nhau? — Bia và bỉm

 Mặt hàng nào sẽ được mua sau khi mua một PC ?  Kiểu DNA nào nhạy cảm với thuộc mới này?  Có khả năng tự động phân lớp Web hay không ?

Mẫu phổ biến và khai phá luật kết hợp là một bài toán bản chất của khai phá DL

 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ộ

(diapers)?!

 Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích

phận, kết hợp không gian và đa phương tiện

 Ứng dụng rộng rãi

 Ví dụ: Phân tích DL bóng rổ, tiếp thị chéo (cross-

tụ (nén dữ liệu ngữ nghĩa)

 Phân tích Web log (click stream), Phân tích chuỗi DNA v.v.

114

marketing), thiết kế catalog, phân tích chiến dịch bán hàng

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

 Khai phá luật kết hợp (Association rule)

 Các thuật toán khai phá vô hướng luật kết hợp (giá trị

 Khai phá kiểu đa dạng luật kết hợp/tương quan

 Khai phá kết hợp dựa theo ràng buộc

 Khai phá mẫu dãy

Apriori: Một tiếp cận sinh ứng viên và kiểm tra

 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

 Mọi tập con của tập mục phổ biến cũng là tập mục phổ biến

 Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} cũng vậy: Mọi

giao dịch chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}.  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ó!

 Phương pháp:

 Sinh các tập mục ứng viên dài (k+1) từ các tập mục phổ biến có độ

dài k (Độ dài tập mục là số phần tử của nó),

 Kiểm tra các tập ứng viên theo CSDL

 Các nghiên cứu hiệu năng chứng tỏ tính hiệu quả và khả năng mở rộng

của thuật toán

 Agrawal & Srikant 1994, Mannila, và cộng sự 1994

115

lôgic đơn chiều) trong CSDL giao dịch

Thuật toán Apriori

Trên cơ sở tính chất (nguyên lý tỉa) Apriori, thuật toán hoạt động theo quy tắc quy hoạch động

• Từ các tập Fi = {ci| ci tập phổ biến, |ci| = i} gồm mọi tập mục phổ biến có độ dài i với 1  i  k,

• đi tìm tập Fk+1 gồm mọi tập mục phổ biến có độ dài k+1.

Thuật toán Apriori

116

Trong thuật toán, các tên mục i1, i2, … in (n = |I|) được sắp xếp theo một thứ tự cố định (thường được đánh chỉ số 1, 2, ..., n).

Thuật toán Apriori: Thủ tục con Apriori-gen

Trong mỗi bước k, thuật toán Apriori đều phải duyệt CSDL D. Khởi động, duyệt D để có được F1. Các bước k sau đó, duyệt D để tính số lượng giao dịch t thoả từng ứng viên c của Ck+1: mỗi giao dịch t chỉ xem xét một lần cho mọi ứng viên c thuộc Ck+1.

Thủ tục con Apriori-gen sinh tập phổ biến: tư tưởng

Thủ tục con Apriori-gen

117

Một ví dụ thuật toán Apriori (s=0.5)

Itemset

sup

Itemset

sup

{A}

Tid

Items

{B}

A, C, D

{C}

Database TDB L1 C1

B, C, E

{D}

{E}

A, B, C, E

{E}

B, E

1st scan

Itemset

{A, B}

{A, C}

{A, E}

{B, C}

Itemset {A, C} {B, C} {B, E} {C, E}

sup 2 2 3 2

Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}

sup 1 2 1 2 3 2

{B, E}

{C, E}

Itemset

C2 C2 2nd scan L2

{B, C, E}

Itemset {B, C, E}

sup 2

Chi tiết quan trọng của Apriori

 Cách thức sinh các ứng viên:

 Bước 1: Tự kết nối Lk  Step 2: Cắt tỉa

 Cách thức đếm hỗ trợ cho mỗi ứng viên.

 Ví dụ thủ tục con sinh ứng viên

 L3={abc, abd, acd, ace, bcd}  Tự kết nối: L3*L3

 abcd từ abc và abd

 acde từ acd và ace

 Tỉa:

 acde là bỏ đi vì ade không thuộc L3

 C4={abcd}

118

L3 C3 3rd scan

Ví dụ: D, min_sup*|D| = 2 (C4 = )

Sinh luật kết hợp

Việc sinh luật kết hợp gồm hai bước

 Với mỗi tập phổ biến W tìm được hãy sinh ra mọi tập

con thực sự X khác rỗng của nó.

 Với mỗi tập phố biến W và tập con X khác rỗng thực sự của nó: sinh luật X  (W – X) nếu P(W-X|X)  c.

Như ví dụ đã nêu có L3 = {{I1, I2, I3}, {I1, I2, I5}}

Với độ tin cậy tối thiểu 70%, xét tập mục phổ biến {I1,

I2, I5} có 3 luật như dưới đây:

119

Cách thức tính độ hỗ trợ của ứng viên

 Tính độ hỗ trợ ứng viên (lệnh 4-8) vấn đề cần quan tâm

 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:

 Tập mục ứng viên được chứa trong một cây-băm

 Lá của cây băm chứa một danh sách ứng viên và bộ

(hash-tree)

 Nút trong chứa bảng băm

 Hàm tập con: tìm ứng viên trong tập ứng viên

Tính độ hỗ trợ của ứng viên

 Tập các ứng viên Ck được lưu trữ trong một cây-băm.

 Gốc của cây băm ở độ sâu 1. Lá chứa một danh sách tập mục thuộc Ck.  Nút trong chứa một bảng băm (chắng hạn mod N): mỗi ô trỏ tới một nút khác

(Nút ở độ sâu d trỏ tới các nút ở độ sâu d+1).  Khi khởi tạo: gôc là nút lá với danh sách rỗng.  Xây dựng cây băm - thêm một tập mục c:

 bắt đầu từ gốc đi xuống theo cây cho đến khi gặp một lá.  Tại một nút trong độ sâu d:

 quyết định theo nhánh nào: áp dụng hàm băm tới mục thứ d của tập mục này.  Khi số lượng tập mục tại một lá vượt quá ngưỡng quy định, lá được chuyển thành

một nút trong và phân chia danh sách các tập mục như hàm băm.

 Tính độ hỗ trợ: tìm tất cả các ứng viên thuộc giao dịch t:

 Nếu ở nút gốc: băm vào mỗi mục trong t.  Nếu ở một lá: tìm các tập mục ở lá này thuộc t và bổ sung chỉ dẫn các tập mục

này tới tập trả lời.

 Nếu ở nút trong và đã đạt được nó bằng cách băm mục i, trên từng mục đứng sau

i trong t và áp dụng đệ quy thủ tục này sang nút trong thùng tương ứng.

120

đếm (độ hỗ trợ hiện thời)

Ví dụ: Tính hỗ trợ các ứng viên

Hàm tập con

3,6,9

1,4,7

Có tập các ứng viên độ dài 3 là 124, 125, 136, 145, 159, 234, 345, 356, 357, 367, 368, 457, 458, 567, 689

2,5,8

1, 4, 7 đi sang trái; 2, 5, 8 dừng ở giữa; 3, 6, 9 đi sang phải

124 125 136

Thêm 145 vượt qua ngưỡng, đưa 4 tập này sang nút con trái. Vì 4 tập này đều vượt qua ngưỡng nên tách thành 145; 124, 125; 136

Thêm 159 bổ sung vào nút giữa cây con trái

Thêm 234 bổ sung vào nút giữa cây mẹ

2 3 4 5 6 7

1 4 5

3 4 5

1 3 6

3 6 7 3 6 8

3 5 6 3 5 7 6 8 9

1 5 9

Thêm 345 bổ sung vào nút phải cây mẹ; sau đó tách cây con phải 345; 356, 357; 367, 368

1 2 4 4 5 7

1 2 5 4 5 8

Ví dụ: Tính hỗ trợ các ứng viên

Hàm tập con

3,6,9

1,4,7

Giao dịch t=1 2 3 5 6

2,5,8

1, 4, 7 đi sang trái; 2, 5, 8 dừng ở giữa; 3, 6, 9 đi sang phải

1 + 2 3 5 6

1 3 + 5 6

2 3 4 5 6 7

1 4 5

3 4 5

1 3 6

3 6 7 3 6 8

1 2 + 3 5 6

3 5 6 3 5 7 6 8 9

1 5 9

1 2 4 4 5 7

1 2 5 4 5 8

12356 sang trái; 2356 ở giữa; 356 sang phải Trái: 12356 trái; 2356 ở giữa; 356 sang phải; … Bộ đếm của ba ứng viên 125, 136, 356 được tăng thêm 1 với giao dịch t-12356

121

Thi hành hiệu quả thuật toán Apriori trong SQL

 Khó có thể có một hiệu quả tốt nếu chỉ tiếp cận thuần

 Sử dụng các mở rộng quan hệ - đối tượng như UDFs,

SQL (SQL-92)

 Nhận được các thứ tự tăng quan trọng  Xem bài: S. Sarawagi, S. Thomas, and R. Agrawal. Integrating

association rule mining with relational database systems: Alternatives and implications. In SIGMOD’98

Thách thức khai phá mẫu phổ biến

 Thách thức

 Duyệt nhiều lần CSDL giao dịch

 Lượng các ứng viên rất lớn

 Tẻ nhạt việc tính toán độ hỗ trợ

 Cải tiến Apriori: tư tưởng chung  Giảm số lần duyệt CSDL giao dịch

 Rút gọn số lượng các ứng viên

 Giảm nhẹ tính độ hỗ trợ của các ứng viên

122

BLOBs, hàm bảng v.v.

DIC (Đếm tập mục động): Rút số lượng duyệt CSDL

ABCD

ABC ABD ACD BCD

 Xây dựng dàn tập mục  Khi mà A và D được xác định là phổ biến thì việc tính toán cho AD được bắt đầu  Khi mọi tập con độ dài 2 của BCD được xác định là phổ biến: việc tính toán cho BCD được bắt đầu.

AB AC BC AD BD CD

Transactions

C D

Apriori

1-itemsets 2-itemsets …

{} Itemset lattice

1-itemsets 2-items

DIC

3-items

S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD’97

Giải pháp Phân hoạch (Partition): Duyệt CSDL chỉ hai lần

 Mọi tập mục là phổ biến tiềm năng trong CSDL bắt buộc phải phổ biến ít nhất một vùng của DB  Scan 1: Phân chia CSDL và tìm các mẫu cục bộ  Scan 2: Hợp nhất các mẫu phổ biến tổng thể  A. Savasere, E. Omiecinski, and S. Navathe. An

efficient algorithm for mining association in large databases. In VLDB’95

123

Ví dụ về mẫu phổ biến

 Chọn một mẫu của CSDL gốc, khai phá mẫu phổ biến nội

 Duyệt CSDL một lần để kiểm tra các tập mục phổ biến tìm thấy trong ví dụ, chỉ có các bao (borders) đóng của các mẫu phổ biến được kiểm tra  Ví dụ: kiểm tra abcd thay cho ab, ac, …, v.v.

 Duyệt CSDL một lần nữa để tìm các mẫu phổ biến bị mất

bộ mẫu khi dùng Apriori

H. Toivonen. Sampling large databases for association rules. In VLDB’96

DHP: Rút gọn số lượng các ứng viên

 Một k-tập mục mà bộ đếm trong lô băm tương ứng dưới

(bỏ qua)

J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining

association rules. In SIGMOD’95

124

ngưỡng (=3) thì không thể là tập mục phổ biến  Ứng viên: a, b, c, d, e  Điểm vào băm: {ab, ad, ae} {bd, be, de} …  1-tập mục phổ biến: a, b, d, e  ab không là một ứng viên 2-tập mục nếu tống bộ đếm trong lô băm {ab, ad, ae} là dưới ngưỡng hỗ trợ. Mọi giao dịch có chứa a đều ở lô băm {ab, ad, ae}.

Eclat/MaxEclat và VIPER: Thăm dò dạng dữ liệu theo chiều ngang

 Dùng danh sách tid của giáo dịch trong một tập mục

 Nén danh sách tid

 Tập mục A: t1, t2, t3, sup(A)=3

 Tập mục B: t2, t3, t4, sup(B)=3

 Tập mục AB: t2, t3, sup(AB)=2

 Thao tác chính: lấy giao của các danh sách tid  M. Zaki et al. New algorithms for fast discovery of association rules. In KDD’97

 P. Shenoy et al. Turbo-charging vertical mining of large databases. In

SIGMOD’00

Thắt cổ chai của khai phá mẫu phổ biến

 Duyệt CSDL nhiều là tốn kém  KP mẫu dài cần nhiều bước để duyệt và sinh

nhiều ứng viên  Để tìm các tập mục phổ biến i1i2…i100

0) = 2100-1 =

 # duyệt: 100  # ứng viên: (100

1) + (100

2) + … + (1

 Thắt cổ chai: sinh ứng viên và kiểm tra  Tránh sinh ứng viên?

125

1.27*1030 !

KP mẫu phổ biến không cần sinh ƯV

 Dùng các mục phổ biến để tăng độ dài mẫu từ các

mẫu ngắn hơn

 “abc” là một mẫu phổ biến

 Nhận mọi giao dịch có “abc”: DB|abc (DB đã

luôn có abc: “có điều kiện”)

 “d” là một mục phổ biến trong DB|abc  abcd

là một mẫu phổ biến

Xây dựng cây FP từ một CSDL giao dịch

(ordered) frequent items

min_support = 3

TID 100 200 300 400 500

Items bought {f, a, c, d, g, i, m, p} {a, b, c, f, l, m, o} {b, f, h, j, o, w} {b, c, k, s, p} {a, f, c, e, l, p, m, n}

{f, c, a, m, p} {f, c, a, b, m} {f, b} {c, b, p} {f, c, a, m, p}

1. Duyệt CSDL một lần, tìm các

{}

Header Table

f:4

c:1

1-tập mục phổ biến (mẫu mục đơn). Loại các mục có độ hỗ trợ < minsup. Xếp các mục phổ biến theo thứ tự giảm dần về độ hỗ trợ (bậc): Tạo f-list. Tạo cây FP với gốc nhãn {}

c:3

b:1

a:3

p:1

Item frequency head f c a b m p

4 4 3 3 3 3

2. Duyệt CSDL lần nữa: Với mỗi giao dịch t: xâu các mục phổ biến theo thứ tự như 2 và biểu diễn dưới dạng [p|P] với p là mục đầu, còn P là xâu mục còn lại; Gọi insert_tree ([p|P]), T)

m:2

b:1

3. Tìm tập phổ biến trên cây FP

p:2 m:1

126

F-list=f-c-a-b-m-p

Xây dựng cây FP

Xây dựng cây FP: chèn một xâu vào cây

127

Lợi ích của cấu trúc FP-tree

 Tính đầy đủ

 Duy trì tính đầy đủ thông tin để khai phá mẫu phổ biến  Không phá vỡ mẫu dài bới bất kỳ giao dich

 Tính cô đọng

 Giảm các thông tin không liên quan: mục không phổ

 Sắp mục theo tần số giảm: xuất hiện càng nhiều thì

biến bỏ đi

 Không lớn hơn so với CSDL thông thường

Tìm tập phổ biến từ cấu trúc FP-tree

128

cành hiệu quả

Mẫu cực đại (Max-patterns)

2) + …

 Mẫu phổ biến {a1, …, a100}  (100

1) + (100

0) = 2100-1 = 1.27*1030 frequent sub-

+ (1 0 patterns!

 Mẫu cực đại: Mẫu phổ biến mà không là tập con

thực sự của mẫu phổ biến khác  BCDE, ACD là mẫu cực đại  BCD không là mẫu cực đại

Tid Items

10 A,B,C,D,E 20 B,C,D,E,

Min_sup=2

Tập mục phổ biến cực đại

Một tập mục cực đại (Maximal Intemset) là tập mục phổ biến không là tập con thực sự của một tập mục phổ biến khác

Maximal Itemsets

Infrequent Itemsets

Border

129

30 A,C,D,F

Tập mục đóng

 Tập mục đóng là tập mục mà không là tập con thực sự

 X đóng: Y  X  s(Y) < s(X)

Itemset Support

TID 1 2 3 4 5

Items {A,B} {B,C,D} {A,B,C,D} {A,B,D} {A,B,C,D}

Itemset Support {A,B,C} {A,B,D} {A,C,D} {B,C,D} {A,B,C,D}

2 3 2 3 2

{A} {B} {C} {D} {A,B} {A,C} {A,D} {B,C} {B,D} {C,D}

4 5 3 4 4 2 3 3 4 3

Phân biệt tập mục cực đại với tập mục đóng

Transaction Ids

null

TID

Items

124

123

245

345

ABC

1234 C

ABCD

BCE

124

123

ACDE

ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

ABCD

ABCE

ABDE

ACDE

BCDE

Not supported by any transactions

ABCDE

130

của một tập mục có cùng độ hỗ trợ

Tập mục cực đại với tập phổ biến đóng

null

Minimum support = 2

Closed but not maximal

124

123

245

345

1234 C

Closed and maximal

124

123

ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

ABCD

ABCE

ABDE

ACDE

BCDE

# Closed = 9 # Maximal = 4

ABCDE

Tập mục cực đại với tập mục đóng

131

Tập mục cực đại với tập mục đóng

R. Bayardo. Efficiently mining long patterns from databases. SIGMOD’98 J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets", DMKD'00

132

Mohammed Javeed Zaki, Ching-Jiu Hsiao: CHARM: An Efficient Algorithm for Closed Itemset Mining. SDM 2002

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

 Khai phá luật kết hợp (Association rule)

 Các thuật toán khai phá vô hướng luật kết hợp (giá trị

 Khai phá kiểu đa dạng luật kết hợp/tương quan

 Khai phá kết hợp dựa theo ràng buộc

 Khai phá mẫu dãy

Luật kết hợp đa mức

 Các mục có thể phân cấp  Đặt hỗ trợ linh hoạt: Mục cấp thấp hơn là kỳ vọng có độ

lôgic đơn chiều) trong CSDL giao dịch

 CSDL giao dịch có thể được mã hóa theo chiều và mức  Thăm dò KP đa mức chia sẻ

uniform support

hỗ trợ thấp hơn.

Level 1 min_sup = 5%

Milk [support = 10%]

Level 2 min_sup = 3%

Skim Milk [support = 4%]

2% Milk [support = 6%]

Level 2 min_sup = 5%

133

reduced support

Kết hợp đa chiều



Luật đơn chiều (viết theo dạng quan hệ (đối tượng, giá trị)):

buys(X, “milk”)  buys(X, “bread”)



Luật đa chiều:  2 chiều / thuộc tính

 Luật kết hợp liên chiều (không có thuộc tính lặp)

age(X,”19-25”)  occupation(X,“student”)  buys(X,“coke”)

 Luật KH chiều-kết hợp (lai/hybrid) (lặp thuộc tính)

age(X,”19-25”)  buys(X, “popcorn”)  buys(X, “coke”)

 Thuộc tính phân lớp

 Tìm số lượng các giá trị khả năng không được sắp

 Thuộc tính định lượng

 Số, thứ tự ngầm định trong miền giá trị

Kết hợp đa mức: Rút gọn lọc

 Trong luật phân cấp, một luật có thể dư thừa do đã có

 Ví dụ

 milk  wheat bread [support = 8%, confidence = 70%]  2% milk  wheat bread [support = 2%, confidence = 72%]

 Nói rằng: luật đầu tiên là tổ tiên luật thứ hai.

 Một luật là dư thừa nếu độ hỗ trợ của nó là khít với giá trị

quan hệ giữa “tổ tiên” của các mục.

134

“mong muốn”, dựa theo tổ tiên của luật.

Luật kết hợp định lượng

 Thuộc tính số là sự rời rạc hóa động d

 Độ tin cậy hoặc độ cô đọng của luật là cực đại

 Luật kết hợp định lượng 2-D: Aquan1  Aquan2  Acat  Phân cụm các luật kết hợp Liền kề nhau từ các luật Tổng quát dựa trên Lưới 2-D

 Ví dụ age(X,”30-34”)  income(X,”24K - 48K”)

 buys(X,”high resolution TV”)

Khai phá luật KH dựa theo khoảng cách

 Phương pháp đóng thùng không nắm bắt được ngữ nghĩa

Equi-depth (depth 2) [7,20] [22,50] [51,53]

Distance- based [7,7] [20,22] [50,53]

Price($) 7 20 22 50 51 53

Equi-width (width $10) [0,10] [11,20] [21,30] [31,40] [41,50] [51,60]

 Phân vùng dựa trên khoảng cách, rời rạc có ý nghĩa hơn

của dữ liệu khoảng

135

khi xem xét :  Mật độ/ số điểm trong một khoảng  Tính “gần gũi” của các điểm trong một khoảng

Độ đo hấp dẫn: Tương quan (nâng cao)

 play basketball  eat cereal [40%, 66.7%] là lạc

 Phần trăm chung của sinh viên ăn ngũ cốc là 75% cao hơn so với

66.7%.

 play basketball  not eat cereal [20%, 33.3%] là chính xác hơn, do

độ hỗ trợ và tin cậy thấp hơn

 Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao)

Basketball

Not basketball

Sum (row)

Cereal

2000

1750

3750

Not cereal

1000

250

1250



corr BA ,

 BAP ( ) BPAP )()(

Sum(col.)

3000

2000

5000

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

 Khai phá luật kết hợp (Association rule)

 Các thuật toán khai phá vô hướng luật kết hợp (giá trị

 Khai phá kiểu đa dạng luật kết hợp/tương quan

 Khai phá kết hợp dựa theo ràng buộc

 Khai phá mẫu dãy

136

lôgic đơn chiều) trong CSDL giao dịch

KPDL dựa trên ràng buộc

 Tìm tất cả các mẫu trong CSDL tự động? — phi hiện thực!

 Mẫu có thể quá nhiều mà không mục đích!

 KPDL nên là quá trình tương tác

 Người dùng trực tiếp xác định KPDL gì khi dùng ngôn

 KP dựa theo ràng buộc

 Linh hoạt người dùng: cung cấp ràng buộc trên cái mà

ngữ hỏi KPDL (hoặc giao diện đồ họa)

 Tối ưu hệ thống: thăm dò các ràng buộc để hiệu quả

Ràng buộc trong KPDL

 Ràng buộc kiểu tri thức:

 classification, association, etc.  Ràng buộc dữ liệu — dùng câu hỏi kiếu SQL

 Tìm các cặp sản phẩn mua cùng nhau trong Vancouver

KP: KP dựa theo ràng buộc

 Ràng buộc chiều/cấp

 Liên quan tới vùng, giá, loại hàng, lớp khách hàng

 Ràng buộc luật (mẫu)

 Mua hàng nhỏ (price < $10) nhanh hơn mua hàng lớn

vào Dec.’00

 Luật mạng: min_support  3%, min_confidence 

(sum > $200)  Ràng buộc hấp dẫn

137

60%

KP ràng buộc <> tìm kiếm dựa theo ràng buộc

 KP ràng buộc <> tìm/lập luận dựa theo ràng buộc

 Cả hai hướng tới rút gọn không gian tìm kiếm  Tìm mọi mẫu bảm đảm ràng buộc <> tìm một vài (một_ câu trả lời của tìm dựa theo ràng buộc trong AI (TTNT)

 Cố tìm theo ràng buộc <> tìm kiếm heuristic  Tích hợp hai cái cho một bài toán tìm kiếm thú vị

 KP ràng buộc <> quá trình hỏi trong hệ CSDL quan hệ

 Quá trình hỏi trong CSDL quan hệ đòi hỏi tìm tất cả  KP mẫu ràng buộc chung một triết lý tương tựng như cố

gắng chọn về chiều sâu của câu hỏi

 Cho một câu hỏi KP Mấu phổ biến với một tập ràng buộc C, thì thuật

toán nên là  Mạnh mẽ: chỉ tìm các tập phố biến bảo đảm ràng buộc C  đầy đủ: Tìm tất cả tập phổ biến bảo đảm ràng buộc C

 Giải pháp “thơ ngây/hồn nhiên” (naïve)

 Tìm tất cát tập PB sau đó kiểm tra ràng buộc

 Tiếp cận hiệu quả hơn

 Phân tích tính chất các ràng buộc một cách toàn diện  Khai thác chúng sâu sắc có thể nhất trong tính toán mẫu

KP mấu phổ biến ràng buộc: vấn đề tố ưu hóa câu hỏi

138

PB.

Không đơn điêu trong KP theo ràng buộc

TDB (min_sup=2)

TID

Transaction

 Chống đơn điệu (Anti-monotonicity)

a, b, c, d, f

b, c, d, f, g, h

a, c, d, e, f

c, e, f, g

 Một tập mục S vi phạmràng buộc, mọi tập lớn hơn nó cũng vi phạm  sum(S.Price)  v là chống đơn điệu  sum(S.Price)  v là không chống đơn

Item Profit

 Ví dụ. C: range(S.profit)  15 là chống

-20

điệu

 Tập mục ab vi phạm C

-30

 Cũng vậy mọi tập chứa ab

-10

Ràng buộc nào là chống đơn điệu

Ràng buộc

Chống đơn điệu

v  S S  V

yes

S  V min(S)  v

yes

min(S)  v max(S)  v

yes

max(S)  v count(S)  v

yes

count(S)  v

yes

sum(S)  v ( a  S, a  0 ) sum(S)  v ( a  S, a  0 )

yes

range(S)  v range(S)  v

convertible

avg(S)  v,   { , ,  } support(S)  

yes

support(S)  

139

đơn điệu

Tính đơn điệu trong KP luật dựa theo ràng buộc

TDB (min_sup=2)

 Tính đơn điệu

TID

Transaction

a, b, c, d, f

b, c, d, f, g, h

a, c, d, e, f

 Khi một tập mục S thỏa mãnràng buộc, thì mọi tập lớn hơn của nó cũng thỏa mãn

c, e, f, g

Item Profit

 sum(S.Price)  v là đơn điệu  min(S.Price)  v là đơn điệu

-20

 Ví dụ. C: range(S.profit)  15

 Tập mục ab đảm bảo C

-30

 Cũng vậy mọi tập chứa ab

-10

Ràng buộc đơn điệu

Đơn điệu

yes

Ràng buộc v  S S  V

yes

S  V min(S)  v

yes

min(S)  v max(S)  v

yes

max(S)  v count(S)  v

count(S)  v

yes

sum(S)  v ( a  S, a  0 ) sum(S)  v ( a  S, a  0 )

yes

range(S)  v range(S)  v

yes

convertible

avg(S)  v,   { , ,  } support(S)  

support(S)  

yes

140

Tính cô đọng

 Tính cô đọng:

 Cho A1, là tập mục bảo đảm một ràng buộc cô đọng C, thì mọi S bảm đảm C là dựa trên A1, chằng hạn., S chứa một tập con thuộc A1

 Tư tưởng: Bỏ qua xem xét CSDL giao dịch, có chăng một tập mục S bảo đảm ràng buộc C có thể được xác định dựa theo việc chọn các mục

 min(S.Price)  v là cô đọng  sum(S.Price)  v không cô đọng

 Tối ưu hóa: Nếu C là cô đọng có thể đẩy đếm trước

Ràng buộc cô đọng

Cô đọng

yes

Ràng buộc v  S S  V

yes

S  V min(S)  v

yes

min(S)  v max(S)  v

yes

max(S)  v count(S)  v

weakly

count(S)  v

weakly

sum(S)  v ( a  S, a  0 ) sum(S)  v ( a  S, a  0 )

range(S)  v range(S)  v

avg(S)  v,   { , ,  } support(S)  

support(S)  

141

Thuật toán Apriori— Ví dụ

itemset sup.

L1 C1

{1} {2} {3} {5}

2 3 3 3

{1} {2} {3} {4} {5}

2 3 3 1 3

Scan D

Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5

itemset sup

{1 3} {2 3} {2 5} {3 5}

2 2 3 2

itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

1 2 1 2 3 2

C2 C2 Scan D L2

itemset {2 3 5}

itemset sup {2 3 5}

Thuật toán Naïve: Apriori +ràng buộc

itemset sup.

L3 C3 Scan D

L1 C1

{1} {2} {3} {5}

2 3 3 3

{1} {2} {3} {4} {5}

2 3 3 1 3

Scan D

Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5

itemset sup

{1 3} {2 3} {2 5} {3 5}

2 2 3 2

itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

1 2 1 2 3 2

Constraint:

C2 C2 Scan D L2

itemset {2 3 5}

Sum{S.price < 5}

itemset sup {2 3 5}

142

L3 C3 Scan D

Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu

itemset sup.

L1 C1

{1} {2} {3} {5}

2 3 3 3

{1} {2} {3} {4} {5}

2 3 3 1 3

Scan D

Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5

itemset sup

{1 3} {2 3} {2 5} {3 5}

2 2 3 2

itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

1 2 1 2 3 2

Constraint:

C2 C2 Scan D L2

itemset {2 3 5}

Sum{S.price < 5}

itemset sup {2 3 5}

Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu

itemset sup.

L3 C3 Scan D

L1 C1

{1} {2} {3} {5}

2 3 3 3

{1} {2} {3} {4} {5}

2 3 3 1 3

Scan D

Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5

itemset sup

{1 3} {2 3} {2 5} {3 5}

2 2 3 2

itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}

1 2 1 2 3 2

Constraint:

C2 C2 Scan D L2

itemset {2 3 5}

min{S.price <= 1 }

itemset sup {2 3 5}

143

L3 C3 Scan D

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

 Khai phá luật kết hợp (Association rule)

 Các thuật toán khai phá vô hướng luật kết hợp (giá trị

 Khai phá kiểu đa dạng luật kết hợp/tương quan

 Khai phá kết hợp dựa theo ràng buộc

 Khai phá mẫu dãy

CSDL tuần tự và Phân tích mẫu tuần tự

Phần mềm phân tích chuỗi thời gian EidoSearch: Trợ giúp đánh dấu mẫu dữ liệu hấp dẫn và EidoSearch đi tìm mọi mẫu tương tự từ quá khứ và hiện tại, phân tích kết quả tìm kiếm này, và chỉ ra xu hướng gì sẽ xảy ra. Gait-CAD Matlab toolbox: trực quan hóa và phân tích chuỗi thời gian, bao gồm phân lớp, hồi quy, và phân cụm. Giấy phép GNU-GPL. Miningco: chương trình mã nguồn mở tự động tìm ra mẫu và quan hệ trong weblogs và các bộ dữ liệu khác. SAS Enterprise Miner XAffinity (TM): xác định mối quan hệ thân hoặc mẫu trong giao dịch và dòng dữ liệu nháy phím http://www.kdnuggets.com/software/sequence.html

144

lôgic đơn chiều) trong CSDL giao dịch

CSDL TT và PT MTT (2)

 CSDL giao dịch, CSDL chuỗi thời gian <> CSDL tuần tự

 Mấu PB <> mấu TT (PB)

 Ứng dụng của KP Mấu TT

 Tuần tự mua của khách hàng:

 Đầu tiên mua máy tính, sau đó CD-ROM, và sau đó là máy

ảnh số, trong vòng 3 tháng.

 Phẫu thuật y tế, thảm họa tự nhiên (động đất…), quá trình KH

và kỹ nghệ, chứng khoán và thị trường….

 Mẫu gọi điện thoại, dòng click tại Weblogs

 Dãy DNA và cấu trúc gene

Khái niệm KP mấu TT

 Cho một tập các dãy, tìm tập đầy đủ các dãy con

phổ biến

dãy TT : < (ef) (ab) (df) c b >

SID

sequence

Một phần tử chứa một tập mục. Tập mục trong một phần tử là không thứ tự , và viết chúng theo ABC.

<(ad)c(bc)(ae)>

<(ef)(ab)(df)cb>

CSDL dãy TT

là dãy con của

145

Cho độ hỗ trợ min_sup =2, <(ab)c> là mẫu tuần tự sequential pattern

Một số chủ đề khai phá dữ liệu nóng

146

Phân lớp học bán giám sát Phân lớp học giám sát Giới thiệu phân lớp

Nội dung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI 9-2015 PGS. TS. HÀ QUANG THỤY

CHƯƠNG 5. PHÂN LỚP

BÀI GIẢNG NHẬP MÔN KHAI PHÁ DỮ LIỆU

03/02/17

147

 d  D \ Dexam : xác định lớp của d.

 Pha 2: Sử dụng bộ phân lớp

 Chọn mô hình có chất lượng nhất

 Dtest : đánh giá mô hình phân lớp (các độ đo hiệu quả)

 Dtrain : xây dựng mô hình phân lớp (xác định tham số mô hình)

diện” cho miền ứng dụng

 Tách Dexam thành Dtrain (2/3) + Dtest (1/3). Dtrain và Dtest “tính đại

 Pha 1: Dạy bộ phân lớp

 Mô hình: Luật phân lớp, cây quyết định, công thức toán học…  Xây dựng ánh xạ (mô hình) phân lớp trên: Dạy bộ phân lớp.

Dexam được gọi là tập ví dụ mẫu.

 Có tập ví dụ Dexam=D1+D2+ …+ Dk với Di={dDexam: dCi}  Cho ánh xạ (chưa biết) từ miền D sang tập lớp C  Cho trước tập lớp C = {C1, C2, …, Ck}

 Xây dựng mô hình: Tìm mô tả cho tập lớp đã có

Phân lớp: Quá trình hai pha

 d  D \ Dexam : xác định lớp của đối tượng d

 Sử dụng mô hình

 Mô hình phân lớp: ánh xạ từ D sang C

 Đầu ra

 Tập ví dụ Dexam đại diện cho tập D  Tập ví dụ Dexam = D1+D2+ …+ Dk với Di={dDexam: d thuộc Ci}  Tập các lớp C1, C2, …, Ck mỗi dữ liệu d thuộc một lớp Ci  Tập dữ liệu D = {di}

 Đầu vào

Bài toán phân lớp

03/02/17

148

Phân lớp: Quá trình hai pha

Married

80K

Yes

Single

40K

Married

80K

Yes

Married

150K

Yes

Single

40K

Married

150K

Yes

Married

50K

Yes

Married

50K

Yes

Single

75K

Married

80K

Yes

Single

40K

Married

150K

Yes

Single

75K

Married

50K

Yes

Single

75K

Ví dụ phân lớp: Bài toán cho vay

Tid Refund Marital Status Taxable Income Cheat

03/02/17

149

– Phân cấp: Lớp này là con của lớp kia

– Đa nhãn: Một đối tượng thuộc một hoặc nhiều lớp

lớp Đơn nhãn: Một đối tượng chỉ thuộc duy nhất một

– Phân lớp đơn nhãn/đa nhãn/phân cấp

Đa lớp: số lượng lớp > 2 Nhị phân: hai lớp

(|C| > 2) (|C| = 2)

– Phân lớp nhị phân/đa lớp

Các loại phân lớp

15 No

Large

67K

14 No

Small

95K

13 Yes

Large

110K

12 Yes

Medium

80K

11 No

Small

55K

Tid Attrib1

Attrib2

Attrib3 Class

Model Apply

10 No

Small

90K

Yes

Medium

75K

Small

85K

Yes

Large

220K

Model Learn

Medium

60K

Large

95K

Yes

Medium

120K

Small

70K

Medium

100K

Yes

Large

125K

Tid Attrib1

Attrib2

Attrib3 Class

Phân lớp: Quá trình hai pha

03/02/17

150







- Độ hồi tưởng , độ chính xác , các độ đo F1 và F

- FN: số ví dụ âm N mà thuật toán (F) phân lớp cho dương P

• FP: số ví dụ dương P mà thuật toán (F) phân lớp cho giá trị N • TN: số ví dụ âm N mà thuật toán phân đúng (T) giá trị âm N P • TP: số ví dụ dương P mà thuật toán phân đúng (T) giá trị negatives), FP (false positives), FN (false negatives) – Sử dụng các ký hiệu TP (true positives), TN (true

đúng/F sai. : còn gọi là ma trận nhầm lẫn

– Giá trị thực: P dương / N âm; Giá trị qua phân lớp: T – Theo dữ liệu test

Đánh giá phân lớp nhị phân

đối giữa các mô hình có tính cạnh tranh? Câu hỏi: Làm thế nào để so sánh hiệu quả tương

– Phương pháp so sánh mô hình

tin cậy? Câu hỏi: Làm thế nào để có được ước tính đáng

– Độ đo để đánh giá hiệu quả

của một mô hình? Câu hỏi: Làm thế nào để đánh giá được hiệu quả

– Các phương pháp đánh giá hiệu quả

Các vấn đề đánh giá mô hình

03/02/17

151

liệu

–

f1 thể hiện việc đánh giá nhạy cảm với giá dữ

Được coi là rất chính xác ! accurary=0.9991; error rate = 9/10000 = 0.0009

– Theo phương án (accurary, error rate) có

= 1/10=0.1; =1/1=1; f1 = 2*0.1/(0.1+1.0)= 0.18

– Theo phương án (precision, recall) có dụ lớp 1 (chính xác: TP) thử: mô hình dự đoán cả 9999 ví dụ là lớp 0 và 1 ví – Tập test có 9990 ví dụ lớp 0 và 10 ví dụ lớp 1. Kiểm

So sánh hai phương án

Lớp = 0

Lớp thực sự

Lớp = 1

f01 f11 Lớp = 1

f00 f10 Lớp = 0

Lớp dự báo

– Ma trận nhầm lẫn

độ chính xác (accuracy) và hệ số lỗi (Error rate) – Phương án khác đánh giá mô hình nhị phân theo

Đánh giá phân lớp nhị phân

03/02/17

152



Re

thuộc lớp Ci:

toán phân lớp cho giá trị đúng trên tổng số ví dụ dương thực sự

 Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được thuật



FN i

 TP

phân lớp vào lớp Ci : toán phân lớp cho giá trị đúng trên tổng số ví dụ được thuật toán  Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật

 Tương tự bộ phân lớp hai lớp (nhị phân)

Đánh giá phân lớp đa lớp

FPi

TNi

lớp Ci Không thuộc

lớp phân lớp đa Giá trị qua bộ

TPi

FNi

Thuộc lớp Ci

lớp Ci Không thuộc

Lớp Ci

Giá trị thực

(như bảng dưới đây) liệu thuộc Dtest nhận được các đại lượng TPi, TFi, FPi, FNi – Đối với mỗi lớp Ci , cho thực hiện thuật toán với các dữ - Bài toán ban đầu: C gồm có k lớp

Đánh giá phân lớp đa lớp

03/02/17

153

 Một số phương pháp khác

Neural Networks

 Các phương pháp mạng nơron

Memory based reasoning

 Lập luận dưa trên ghi nhớ

Support Vector Machines  Các phương pháp máy vector hỗ trợ

Naïve Bayes and Bayesian Belief Networks

 Các phương pháp Bayes «ngây thơ» và mạng tin cậy Bayes

Rule-based Methods  Các phương pháp dựa trên luật

Decision Tree based Methods  Các phương pháp cây quyết định

Các kỹ thuật phân lớp





)

c TN



)





  c  K







(1 

 1 c c TP



c 



 M

 M

(1 c TP  K 1  c  c  1

K 1  c  1

trung bình lớn-macroaveraging M và M vi trung bình-microaveraging (được ưa chuộng)  và 

- Đánh giá theo các độ đo

với lớp Ci.

- Các giá trị i và i : độ hồi phục và độ chính xác đối

Đánh giá phân lớp đa lớp

03/02/17

154

cho bản ghi

Kết luận: Gán giá trị NO (không gian lận) vào trường Cheat

Ví dụ cây quyết định và sử dụng

 Kiểm tra từ gốc theo các điều kiện

 Sử dụng cây quyết định

 Một số thuật toán phổ biến: Hunt, họ ID3+C4.5+C5.x

tương ứng với một tập các ví dụ học. Gốc: toàn bộ dữ liệu học  Phương châm: “chia để trị”, “chia nhỏ và chế ngự”. Mỗi nút

 Xây dựng cây quyết định  Ví dụ: xem trang tiếp theo

không có cung ra.

 Lá hoặc nút kết thúc: giá trị lớp; có chính xác một cung vào + cung ra (gắn với điều kiện kiểm tra giá trị thuộc tính của nút)  Nút trong: tên thuộc tính; có chính xác một cung vào và một số  Gốc: tên thuộc tính; không có cung vào + không/một số cung ra

 Cây quyết định  Mô hình phân lớp là cây quyết định

Phân lớp cây quyết định

03/02/17

155

xem xét vơi u tiếp theo. Thực hiện thuật toán với từng nút con u của t.

cung nối t tới u là miền giá trị A theo phân hoạch, tập con nói trên được

2.3. Mỗi tập con theo phân hoạch của Dt tương ứng với một nút con u của t:

2.2. Tạo phân hoạch Dt theo tập giá trị của A thành các tập con

2.1. Chọn 1 thuộc tính A để phân hoạch Dt và gán nhãn nút t là A

2: Nếu Dt chứa các ví dụ thuộc nhiều lớp thì

và được gán nhãn y.

1: Nếu mọi ví dụ trong Dt đều thuộc vào một lớp y thì nút t là một lá

 Nội dung

 Xác định nhãn nút t và các cung ra (nếu có) của t

 Output

 Cho tập nhãn lớp (giá trị lớp) y1, y1, … yk. (k lớp)  Cho tập các ví dụ học Dt.  Cho nút t trên cây quyết định đang được xem xét

 Input

bắt đầu từ gốc

 Thuật toán dựng cây quyết định sớm nhất, đệ quy theo nút của cây,

Dựng cây quyết định: thuật toán Hunt

Yes

Yes 1

then Class AI = No. If System=1 and Timetable=0

then Class AI = Yes. If System=1 and Timetable=1

Process

Timetable

then Class AI = No. If System=0 and Process=1

then Class AI = Yes. If System=0 and Process=0

System

Timetable (Phân tích miền ứng dụng)

 Dựa vào các từ khóa có trong văn bản: System, Process,  Phân lớp văn bản vào lớp AI : trí tuệ nhân tạo

Ví dụ cây quyết định phân lớp văn bản

03/02/17

156

Thuật toán cây quyết định ID3

Giải thích

Ví dụ: thuật toán Hunt

Status với phân hoạch Married và hai giá trị kia… và Yes nên áp dụng bước 2. Chọn thuộc tính Marital gán No (Don’t cheat). Nút phải có 7 bản ghi có cả No 3 bản ghi cùng thuộc lớp Cheat=No (Bước 1) nên là lá - Xét hai nút con của gốc từ trái sang phải. Nút trái có Refund = Yes và 7 bản ghi có Refund = No trị Yes, No. Chia thành hai tập gồm 3 bản ghi có -Thực hiện bước 2: chọn thuộc tính Refund có hai giá - Xuất phát từ gốc với 10 bản ghi

03/02/17

157

Gini=0.000

Gini=0.278

Gini=0.444

Gini=0.500

 Ví dụ: Bốn trường hợp

 Gini (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy nhất.

phân biệt giữa các lớp

ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, không có  Gini (t) lớn nhất = 1-1/nc (với nc là số các lớp tại nút t): khi các bản

Trong đó p(j|t) là tần suất liên quan của lớp j tại nút t

 1



Gini

t 1)(

jp (





 t 2)|

 Công thức tính độ đo Gini cho nút t:  Đo tính hỗn tạp của một tập ví dụ mẫu

 Độ đo Gini  Tồn tại một số độ đo: Gini, Information gain…  Bước 4.1. chọn thuộc tính A tốt nhất gán cho nút t.

Chọn thuộc tính: Độ đo Gini

cải thiện chất lượng không phụ thuộc các thuộc tính hiện có; (iii) nếu phân chia không ngưỡng cho trước, (ii) test khi-bình phương cho thấy phân bố lớp  Ràng buộc dừng phân chia khác: (i) số lượng dữ liệu nhỏ thua  Tất cả các dữ liệu có giá trị “tương tự nhau”  Tất cả các dữ liệu thuộc về cùng một lớp

 Khi nào thì dừng phân chia (bước 2)

 Theo một số độ đo  Cách xác định cách chia tốt nhất  Cách xác định điều kiện kiểm tra thuộc tính

 Xác định cách phân chia tập dữ liệu

 Vấn đề cần giải quyết

tối ưu hóa chiến lược xác định

 Phân chia tập dữ liệu dựa trên việc kiểm tra các thuộc tính làm

 Chiến lược tham lam Rút gọn cây

03/02/17

158

Don’t Cheat

Cheat / Don’t Cheat

Status cho gốc cây quyết định !

Divorced

Married

Single,

của Marital Status (3/10) nên chọn Marital

Status

Income bằng nhau (24/70) và lớn hơn Gini

Marital



Như vậy, Gini của Refund và Taxable



Gini

)(

(







2)|

7/10*(24/49) = 24/70



3/10 * (0) + 7/10 * (1-(3/7)2 – (4/7)2) =

split



GINI

)(



theo Gini, kết quả 2 thùng và 80K là mốc) chia khoảng (tồn tại một số phương pháp  Taxable Income: thuộc tính liên tục cần

– (3/6) 2) = 6/10 * ½ = 3/10

 Marital Status: 4/10 * 0 + 6/10 * (1- (3/6) 2

(4/7)2) = 7/10*(24/49) = 24/70

 Refund: 3/10 * (0) + 7/10 * (1-(3/7)2 –

và Taxable Income (<80K,  80K). Marital Status (Single&Divorced, Married)  Tính toán GINI cho Refund (Yes, No), Chia tập theo độ đo Gini: Ví dụ

 .ni là số lượng bản ghi tại nút con I (của nút t).  n là số bản ghi của tập bản ghi tại nút t, trong đó

 1

split



GINI

)( i



n i n

lượng của việc chia tính bằng

 Khi một nút t được phân hoạch thành k phần (k nút con của t) thì chất  Dùng trong các thuật toán CART, SLIQ, SPRINT

Chia tập theo độ đo Gini

03/02/17

159

 Áp dụng: Tự tiến hành

tập con

 Dùng GainRatio để khắc phục xu hướng chọn phân hoạch nhiều



SplitINFO



SplitINFO

log





GainRATIO

chia

Gain

 Cải tiến

 Hạn chế: Xu hướng chọn phân hoạch chia thành nhiều tập con C4.5 là một trong 10 thuật toán KPDL phố biến nhất. Gain đạt lớn nhất. Độ đo giảm entropy sau khi phân hoạch: chọn thuộc tính làm cho hoạch, ni là số lượng bản ghi trong tập con thứ i. Trong đó, n là số lượng bản ghi tại nút t, k là số tập con trong phân

 1

chia





Gain

entropy

)( t

entropy

)( i



n i n

 Độ đo Information Gain Chọn thuộc tính: Information Gain

 Tính toán entropy (t) cho một nút tương tự như Gini (t)

 Lấy loga cơ số 2 thay cho loga tự nhiên

nhất.

 Entropy (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy

có phân biệt giữa các lớp bản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, không  Entropy (t) lớn nhất = log (nc) (với nc là số các lớp tại nút t): khi các

độ không đồng nhất tại nút t. Trong đó p(j|t) là tần suất liên quan của lớp j tại nút t

 Công thức tính entropy nút t:



Entropy

)( t

( jp

log)| t

( jp

)| t

 Entropy

 Dùng cho các thuật toán ID3, họ C4.5  Thông tin thu được sau khi phân hoạch tập ví dụ

 Độ đo Information Gain Chọn thuộc tính: Information Gain

03/02/17

160

 Ví dụ:C4.5Rule

hình cây quyết định, mô hình mạng nơ ron, …

 Trích xuất luật từ mô hình phân lớp dữ liệu khác, chẳng hạn, mô

 Gián tiếp

4. Lặp các bước 2-3 cho đến khi gặp điều kiện dừng 3. Xóa mọi bản ghi “bảo đảm” bởi luật vừa được học 2. Mở rộng luật bằng hàm Học_một_luật 1. Bắt đầu từ một tập rỗng

 Trích xuất luật trực tiếp từ dữ liệu  Ví dụ: RIPPER, CN2, Holte’s 1R  Trích xuất luật trực tiếp từ dữ liệu

 Trực tiếp

 Trực tiếp và gián tiếp

 Giới thiệu Xây dựng luật phân lớp

 Khi đó, vế phải của luật cũng được áp dụng cho thể hiện. tính của r đáp ứng điều kiện của luật.  Một luật được gọi là “bảo đảm” thể hiện r (bản ghi) nếu các thuộc

 Sử dụng luật

(Refund = “No”)  (Marital Status = “Married”)  Cheat = “No” Refund = ‘Yes”  Cheat = “No”

 Ví dụ

y là nhãn lớp (còn gọi là kết quả của luật: RHS bên phải). kiện của luật: LHS bên trái) <điều kiện> là sự kết nối các thuộc tính (còn gọi là tiên đề/điều Trong đó:

 Luật: <điều kiện>  y

 Luật

 Phân lớp các bản ghi dựa vào tập các luật “kiểu” if … then

 Giới thiệu Phân lớp dựa trên luật

03/02/17

161

 n 1: số trường hợp sai được đảm

bảo bởi R1

 P1: số thể hiện đúng được bảo

đảm bởi R1

 n0: số thể hiện sai được đảm bảo

bởi R0

hai R0 và R1

với t: số thể hiện đúng đảm bảo cả n1)) - log (p0 / (p0 + n0))]

 Gain (R0, R1) = t [log (p1 / (p1 +

thêm liên kết)

 R1: {A} => lớp (quy tắc sau khi  R0: {} => lớp (luật khởi động)

lợi ích thông tin FAIL

 Bổ sung các liên kết làm cực đại  Bắt đầu từ một luật rỗng: {}  lớp  Thuật toán RIPPER Mở rộng luật: một số phương án

 Xác định kết quả luật theo đa số của các bản ghi đảm bảo luật  Bổ sung các liên kết làm cực tiểu entropy: {A}, {A, B}…  Khởi đầu bằng liên kết rỗng: {}

 Thuật toán CN2

 Tìm đặc trưng điển hình cho từng lớp  Thống kê các đặc trưng cho ví dụ

 Sử dụng thống kê

Mở rộng luật: một số phương án

đảm bởi R0 p0: số thể hiện đúng được bảo

03/02/17

162

một tập luật (giá trị chuẩn, g=0.5)

 g : tham số đếm sự hiện diện của các thuộc tính dư thừa trong

 Độ dài mô tả = L(lỗi) + g* L(mô hình)

 Tính toán độ dài mô tả của mỗi tập con

 Mỗi tập con là một tập các luật với cùng một kết quả (lớp)

luật (thứ tự lớp)

 Thay thế sắp xếp theo luật bằng sắp xếp theo tập con của

 Lặp lại cho đến khi không cải thiện được lỗi tổng thể  Loại bỏ các r’ có lỗi thấp hơn r  So sánh tỷ lệ lỗi r so với các r’

cách bỏ đi một liên kết

 Xem xét luật thay thế r’: A’ → y, trong đó A’ nhận được từ A bằng

 Với mỗi luật, r: A → y  Trích xuất luật từ cây quyết định chưa cắt tỉa

Sinh luật gián tiếp: C4.5rules

Liệt kê các đường đi từ gốc Tập luật

Luật phân lớp: từ cây quyết định

03/02/17

163

Birds

Reptiles

Yes

()  Mammals

(Can Fly=Yes,Give Birth=No)  Birds

Fly?

 Reptiles

Fishes

Amphibians

Can

(Give Birth=No, Can Fly=No, Live In Water=No)

Sometimes

(Have Legs=No)  Reptiles

(Live in Water=Yes)  Fishes

Yes

RIPPER:

( )  Amphibians

Mammals

Water? Live In

(Give Birth=No, Can Fly=No, Live in Water=No)  Reptiles

(Give Birth=Yes)  Mammals

Yes

(Give Birth=No, Live in Water=Yes)  Fishes

(Give Birth=No, Can Fly=Yes)  Birds

Birth? Give

C4.5rules:

C4.5rules: Ví dụ

no yes no no no no no yes no no

eagle dolphin owl platypus gila monster salamander eel porcupine penguin turtle leopard shark yes cat yes no pigeon yes bat no komodo no frog yes whale no salmon no python yes human

yes no yes yes yes yes yes no yes yes no no yes no yes yes no yes yes no

yes no yes no no no no no no no no no yes yes no no no no no no

no no no yes

Name

Give Birth

Lay Eggs

Can Fly

yes no no yes yes no yes no yes no sometimes yes yes no yes no sometimes yes sometimes yes yes no yes no yes no yes no yes no sometimes yes yes yes no no Live in Water Have Legs

birds mammals birds mammals reptiles amphibians fishes mammals birds reptiles fishes mammals birds mammals reptiles amphibians mammals fishes reptiles mammals Class

C4.5rules: Ví dụ

03/02/17

164

http://www.cs.uu.nl/docs/vakken/dm/dmhc13.pdf

(Chapter

5: Classification: Alternative

Techniques),

Addison Wesley,

2005,

Pang-Ning Tan, Michael Steinbach, Vipin Kumar.

Introduction to Data Mining

)(

20/1



SMP

(

)

0002



MPMSP

)

(

)

/15.0

50000

viêm màng não ?

 Một bệnh nhân bị cứng cổ hỏi xác suất anh/cô ta bị

 Xác suất một bệnh nhân bị cứng cổ S là 1/20  Xác suất một bệnh nhân bị viêm màng não M là 1/50.000

50%

 Bệnh nhân viêm màng não có triệu chứng cứng cổ S|M:

 Một bác sỹ biết

Định lý Bayes: Ví dụ

 Vấn đề: làm thế nào để tính P(x|c)?  P(c): tần suất xuất hiện của các tài liệu thuộc lớp c

P(x|c).P(c) lớn nhất

 Tìm c sao cho P(c|x) lớn nhất Tìm c sao cho  P(x) bằng nhau cho tất cả các lớp

P(c|x) = P(x|c).P(c)/P(x)

 Định lý Bayes:



CAP

(

)



ACP

)

(

)

) CP ( CAP ( , AP ( ) CAP , (

Hai biến cố A và C  Xác suất có điều kiện  Khung xác suất để xây dựng bộ phân lớp

 Giới thiệu

Phân lớp Bayes

03/02/17

165



inT



(

 ),

(

)

| xcp

) xTpTxcp

trí của nó trong đối tượng: tính trong đối tượng độc lập với ngữ cảnh và vị  giả thiết độc lập: xác suất xuất hiện của thuộc

 Giả thiết Naïve Bayes:

Phân lớp Naïve Bayes

5: Classification: Alternative

Techniques),

Addison Wesley,

http://www.cs.uu.nl/docs/vakken/dm/dmhc13.pdf (Chapter Pang-Ning Tan, Michael Steinbach, Vipin Kumar.

2005, Introduction to Data Mining

học?

 Có thể tính xác suất P(C|A1, A2, …, An) từ dữ liệu  Tìm lớp c để cực đại xác suất P(C|A1, A2, …, An)  Cần dự báo nhãn c …, An)

 Cho một bản ghi với các giá trị thuộc tính (A1, A2,

ngẫu nhiên.

 Các thuộc tính (bao gồm nhãn lớp) là các biến

Phân lớp Bayes

03/02/17

166

của X: nhãn nhiều nhất trong k-láng giềng gần nhất

- Dùng nhãn lớp của k-láng giềng gần nhất để xác định nhãn lớp

- Tìm k dữ liệu thuộc D gần X nhất

- Tính khoảng cách (độ tương tự) từ X tới tất cả dữ liệu thuộc D

 Phân lớp đối tượng mới Xc được biểu diễn

- Một số k > 0 (láng giềng gần nhất - Một đo đo khoảng cách (Ơcơlit) hoặc tương tự (như trên) - Một tập D các đối tượng dữ liệu biểu diễn bản ghi các đặc trưng

 Cho trước

l Y

  X

l 2



)Y,X(Sm

)Y,X(Cos

l l Y*X



Phân lớp k-NN

TF (fj| X): số lần đặc trưng fj xuất hiện trong X

thì X  C!

 1

j  VF

i *)C(p

f(p(

i )C|



f(TF

)X,

  n

)X|C(P

 Nếu P(C|X) > C  Tính xác suất hậu nghiệm

j  VF

*)C(p

f(p(

)C|



 Cho dữ liệu X mới

f(TF

)X,

 1



(

l , Cj

)





j CfP

(

)



(

j , Cf

)

n TF

 Xác suất một đặc trưng fj thuộc lớp C:  p(Ci) = Mi/M, M= ||Dlearn||, Mi = ||Y  Dlearn / Y Ci||  Trên tập ví dụ học Dlearn  Tính xác suất tiên nghiệm

 Tập lớp C= {C1, C2, …, Cn} với mỗi Ci một ngưỡng i > 0  Tập từ vựng V = {f1, f2, …, f||V||}  Tập ví dụ Dexam = Dlearn + Dtest

 Cho Phân lớp Naïve Bayes

03/02/17

167

số chiều lớn (như các vector biểu diễn văn bản).

 SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có

SVM): được Corters và Vapnik giới thiệu vào năm 1995.  Thuật toán máy vector hỗ trợ (Support Vector Machine –

Thuật toán SVM

3-NN: Chọn lớp “+”: láng giềng có nhãn “+” là nhiều nhất có tổng khoảng cách gần nhất 2-NN: Chọn lớp “-”: hai nhãn có số lượng như nhau, chọn nhãn 1-NN: Chọn lớp “-”: láng giềng có nhãn “-” là nhiều nhất

 Ba trường hợp như hình vẽ

(a ) 1 -nea rest ne igh bo r

(b ) 2 -ne arest ne igh bo r

Phân lớp k-NN: Ví dụ

03/02/17

168

Thuật toán SVM

 Thuộc lớp âm nếu f(d) < 0

 Thuộc lớp dương nếu f(d) > 0

 f(d) = αSVM .d + b

 Phân lớp một tài liệu mới: xác định dấu của

liệu thành hai miền.

 Tìm một siêu phẳng: αSVM .d + b phân chia dữ

 Ci Є {-1,1} xác định dữ liệu dương hay âm

 Tập dữ liệu học: D= {(Xi, Ci), i=1,…n}

Thuật toán SVM

03/02/17

169

 Phân lớp bán giám sát trong NLP

 Các phương án học bán giám sát phân lớp

 Một số cách tiếp cận cơ bản

 Nội dung phân lớp bán giám sát

 Tại sao học bán giám sát

 Khái niệm sơ bộ

 Giới thiệu phân lớp bán giám sát

Phân lớp bán giám sát



1,...., i    1

(4)   i

1,....,

i b

 Thỏa mãn:

C

(3)

    0   i  c d . 2  1

 Cực tiểu:



 Nếu dữ liệu học không tách rời tuyến tính: thêm biến {ξ1… ξn}:  ( 2 )

1,....,

  i

  

  

 Thỏa mãn:



(1)

2  . 1

2 1

 Cực tiểu:

   =  

    

 Nếu dữ liệu học là tách rời tuyến tính:

Thuật toán SVM

03/02/17

170

liệu tuân theo. mô hình đã có theo tự nhiên hoặc giả thiết dữ (mô hình / đặc trưng/ nhân / hàm tương tự)   Ánh xạ gán nhãn có liên quan mô hình dữ liệu  chẳng hạn, nghịch lý “hiệu quả như nhau” trong biểu diễn văn bản nhãn trên dữ liệu

 Biểu diễn dữ liệu chưa mô tả hết ánh xạ gán

Cơ sở của học bán giám sát

 Tạo ra bộ phân lớp tốt hơn so với chỉ dùng học giám sát: học nhãn

 Học bán giám sát: dùng cả ví dụ có nhãn và ví dụ chưa gắn

 Có sẵn  có điều kiện tiến hành tự động gắn nhãn



xử lý văn bản: trang web vô cùng lớn, ngày càng được mở rộng xử lý tiếng nói: bài nói nhiều, xây dựng tài nguyên đòi hỏi công phu

 Dễ thu thập  nhiều

 ví dụ chưa gắn nhãn

 Tự động: như tự động sinh corpus song hiệu quả chưa cao  Thủ công: khó khăn  chuyên gia  tốn thời gian, tiền

 ví dụ gắn nhãn

nhãn) là tập các cặp (tập thuộc tính, nhãn)

 Học giám sát: tập ví dụ học đã được gán nhãn (ví dụ gắn  Học bán giám sát là gì ? Xiaojin Zhu [1] FQA

Sơ bộ về học bán giám sát

bán giám sát đòi hỏi điều kiện về dung lượng khối lượng

03/02/17

171

 …

 Khó nâng cấp học giám sát đã có: dùng self-traning

 Đã sử dụng SVM thì mở rộng TSVM

 Nếu hai điểm tương tự hướng tới một lớp: dựa trên đồ thị

 Đặc trưng phân thành hai phần riêng rẽ: co-training

 Lớp  phân cụm tốt: dùng EM với mô hình sinh trộn.

 Một số định hướng lựa chọn

hình phù hợp cấu trúc dữ liệu: khó kiểm nghiệm

 Đòi hỏi các giả thiết mô hình mạnh. Giả thiết mô

 So sánh các phương pháp

 ...  Dựa trên đồ thị  TSVM  Co-training  Self-training  EM với mô hình trộn sinh điển hình

 Các phương pháp học bán giám sát Phương pháp học bán giám sát

dùng phương pháp khác

 “Tồi” khi dùng phương pháp này song lại “tốt” khi

cách

 phương pháp dựa theo đồ thị với trọng số cạnh là khoảng  mô hình quá trinh Gauxơ với nhiễu phân lớp bằng không  Information Regularization (quy tắc hóa thông tin)  Transductive SVM (máy hỗ trợ vector lan truyền) định: tránh miền có mật độ cao:

 Một số phương pháp cần điều kiện về miền quyết

quả

 Nếu giả thiết mô hình không phù hợp  giảm hiệu

 Dữ liệu chưa nhãn không luôn luôn hiệu quả

Hiệu lực của học bán giám sát

03/02/17

172

của phân bố tới các thành phần

cho tới một hoán đối vị trí các thành phần  tính khả tách

 Cho họ phân bố {p} là đồng nhất nếu 1  2 thì p1 p2

 Là tính chất cần có của mô hình

 Tính đồng nhất

nhãn cho mỗi thành phần

 Lý tưởng hóa tính "Đồng nhất": chỉ cần một đối tượng có

phần, trộn đồng nhất. Miền tài liệu được phân thành các thành  Với số lượng nhiều dữ liệu chưa nhãn cho P(x|y) mô hình  Mô hình có dạng p(x,y) = p(y)*p(x|y)  Mô hình sớm nhất, phát triển lâu nhất

 Sơ bộ

Mô hình sinh: Thuật toán EM

Quy nạp: có thể liên quan tới dữ liệu chưa có.

 Lan truyền để thu hẹp lại cho quy nạp: học chỉ dữ liệu sẵn.

 Có cả lan truyền hoặc quy nạp.  “học dữ liệu phân lớp/có nhãn bộ phận”.  “học dữ liệu nhãn/không nhãn,  dùng ví dụ có / không có nhãn,

 “Bán giám sát”  Đa dạng về cách gọi. Hạn chế bài toán phân lớp.

 Phân biệt “học lan truyền” với “học bán giám sát”

 Có dữ liệu không nhãn: nhận được xác suất p(x)

 Nhiều phương pháp là phân biệt: TSVM, quy tắc hóa thông tin,  Mô hình trộn với EM mở rộng thêm self-training  Mô hình sinh có tham số chung phân bố kết nối p(x, y)  Giả thiết dưới dạng p(y|x) còn dữ liệu chưa có nhãn p(x)

 Mô tả chung liệu có nhãn

 Hoặc biến dạng hoặc thay đổi thứ tự giả thiết thu nhờ chỉ dữ

 Dùng dữ liệu chưa gán nhãn Phương pháp học bán giám sát

quá trình Gauxơ, dựa theo đồ thị

03/02/17

173

10: end for

9: end for

i+1

8: M-bước: xác định c,t dùng công thức (*) để xây dựng mô hình 7: for mỗi lớp c và từ khóa t do 6: end for 5: E-bước: dùng phân lớp Bayes thứ nhất xác định P(c|d,i) 4: for mỗi tài liệu d  DU do 3: for i = 0, 1, 2, . . . cho đến khi kết quả đảm bảo do 2: dùng DK xây dựng mô hình ban đầu 0

và M-bước

1: Cố định tập tài liệu không nhãn DU  D \ DK dùng trong E-bước

 Nội dung thuật toán

Mô hình sinh: Thuật toán EM

 DK: tập ví dụ có nhãn trong D (|DK| << |D|)  D: tập ví dụ đã có (có nhẵn /chưa có nhãn)

 Ký hiệu

 Khi mô hình trộn chính xác

 Miền áp dụng

 Cực đại EM địa phương

thành đa chiều thay cho đơn chiều chia thành các tiêu đề con thì nên mô hình hóa  Chú ý cấu trúc tốt mô hình trộn: nếu tiêu đề được không nhãn sẽ làm tăng độ chính xác phân lớp

 Giả thiết mô hình trộn là chính xác  dữ liệu

 Tính xác thực của mô hình Mô hình sinh: Thuật toán EM

03/02/17

174

Fisher để phân lớp

 Các ví dụ có nhãn được chuyển đổi thành vector

 Nhân là gốc của mô hình sinh

 Phương pháp nhân là một phương pháp điển hình

 Phương pháp nhân Fisher cho học phân biệt  Nhãn cụm (nhãn dữ liệu có nhãn) làm nhãn dữ liẹu khác  Mô hình phân cụm phù hợp dữ liệu

 Độ chính xác phân cụm cao

 dành tập Dtest để đánh giá  cả dữ liệu có nhãn và không có nhãn  Sử dụng phân cụm cho toàn bộ ví dụ

 Phân cụm - và - Nhãn

Mô hình sinh: Thuật toán khác

 Chọn điểm bắt đầu bằng học tích cực

cơ bản khác

 Thuật toán nhân là Bayes naive: có thể chọn thuật toán

 Một số vấn đề khác cần lưu ý: đo hồi tưởng, chính xác, F1...

 "Kết quả đảm bảo yêu cầu": đánh giá theo các độ thì khai thác dữ liệu không nhãn không hiệu quả  Nếu cực trị địa phương khác xa cực trị toàn cục  Phạm vi áp dụng: mô hình trộn chính xác

 Một số vấn đề với EM

Mô hình sinh: Thuật toán EM

03/02/17

175

 Tiêu đề văn bản  Nội dung văn bản

 Ví dụ, các trang web  Một dữ liệu có hai khung nhìn

 Tư tưởng Co-Training

 Thường được áp dụng cho các bài toán NLP  Thủ tục "bootstrapping"

Vấn đề tập U' có "độ tin cậy cao nhất"

U – U’U L + U’ L

Tìm tập con U’  U có độ tin cậy cao nhất: Sử dụng h để phân lớp dữ liệu trong tập U Huấn luyện bộ phân lớp giám sát h trên tập L

Lặp (cho đến khi U = )

U : Tập các dữ liệu chưa gán nhãn L : Tập các dữ liệu gán nhãn.

Gọi

 Nội dung

 EM địa phương là dạng đặc biệt của seft-training

 Là kỹ thuật phổ biến trong SSL

 Giới thiệu

Self-Training

03/02/17

176

 Bộ phân lớp thành phần rất quan trọng

 Số các mẫu thêm vào sau mỗi vòng lặp

 Kích cỡ tập dữ liệu chưa gán nhãn

 Kích cỡ tập dữ liệu gán nhãn

 Cơ sở tăng hiệu quả co-training: thiết lập tham số

 Quá nhiều: không thu lợi từ co-training  Quá ít: không hỗ trợ co-training training

 Tập dữ liệu gán nhãn có ảnh hưởng lớn đến co-

 Một số lưu ý

 hoặc số vòng lặp đạt tới ngưỡng được xác định trước  hoặc tập dữ liệu chưa gán nhãn là rỗng

 Điều kiện dừng

Co-Training

 Mô hình thuật toán

Co-Training

03/02/17

177

thiết dữ liệu tuân theo. tự)  mô hình đã có theo tự nhiên hoặc giả liệu (mô hình / đặc trưng/ nhân / hàm tương

 Ánh xạ gán nhãn có liên quan mô hình dữ

như nhau” trong biểu diễn văn bản) nhãn trên dữ liệu (chẳng hạn, nghịch lý “hiệu quả  Biểu diễn dữ liệu chưa mô tả hết ánh xạ gán

Mô hình đồ thị

 Quá trình Gauxơ)

p(x) ra khỏi miền dầy đặc

 Khi p(x) và p(y|x) không tương thích  đưa

trực tiếp

 Phương pháp phân biệt làm việc trên p(y|x)

 Transductive SVMs (S3VMs)

Chặn thay đổi miền dày đặc

03/02/17

178

Hai tiết từ 9h00-10h50 KSE 11h50, PH 212 nhà E3  Các phương pháp dựa trên luật

GĐ 103 nhà G2 9h00 ngày Thứ Hai 13/10/2014 Japan DataSection: Social Media Ming

 Buổi trình bày DataSection

Ngày 10/10/2014

03/02/17

179

Đánh giá phân cụm

Gán nhãn cụm

Phân cụm dựa trên mô hình

Phân cụm dựa trên mật độ

Phân cụm phân cấp Phân cụm phẳng Một số độ đo cơ bản cho phân cụm Giới thiệu bài toán phân cụm

and Applications. CRC Press 2014. Charu C. Aggarwal, Chandan K. Reddy (Eds., 2014). Data Clustering: Algorithms

Nội dung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI 9-2014 PGS. TS. HÀ QUANG THỤY

CHƯƠNG 6. PHÂN CỤM DỮ LiỆU

BÀI GIẢNG KHAI PHÁ DỮ LIỆU

03/02/17

180

 Tăng: Dữ liệu tiếp tục được bổ sung trong quá trình phân cụm

 Lô: Tại thời điểm phân cụm, toàn bộ dữ liệu đã có

 Phân cụm theo lô và phân cụm tăng

 Phân cấp: Các cụm dữ liệu có quan hệ phân cấp cha- con

 Phẳng: Các cụm dữ liệu không giao nhau

 Phân cụm phẳng và phân cụm phân cấp

cụm

 Xác suất: Danh sách cụm và xác suất một dữ liệu thuộc vào các  Đơn định: Mỗi dữ liệu thuộc duy nhất một cụm

 Phân cụm đơn định và phân cụm xác suất

 Vùng: Danh sách cụm và vùng dữ liệu thuộc cụm  Mô hình: Kết quả là mô hình biểu diễn các cụm dữ liệu  Phân cụm mô hình và phân cụm phân vùng

Sơ bộ tiếp cận phân cụm

 Số lượng cụm cho trước, số lượng cụm không cho trước  Khai thác thông tin bổ sung  Xây dựng độ đo tương tự

 Một số nội dung liên quan

 Đưa ra một số độ đo “tương tự” theo biểu diễn dữ liệu  Khai thác “cách chọn lựa” của người dùng

 Tiên đề phân cụm: Nếu người dùng lựa chọn một đối tượng d thì họ

 Đo “tương tự” (gần) nhau ?

 Dữ liệu hai cụm: “không tương tự” nhau (xa nhau)  Các dữ liệu trong một cụm: “tương tự” nhau (gần nhau)

 Phân các dữ liệu thuộc D thành các cụm  Tập dữ liệu D = {di}

 Bài toán 1. Giới thiệu bài toán phân cụm

cũng lựa chọn các đối tượng cùng cụm với d

03/02/17

181

 FCM (Fuzzy CMEANS),…

 Sử dụng hàm mờ từ các đối tượng tới các cụm

 Giả thiết: không có phân cụm “cứng” cho dữ liệu và đối tượng có thể

 Phân cụm mờ

 MCLUST…

 Xác định mô hình tốt nhất phù hợp với dữ liệu

 Giải thiết: Tồn tại một số mô hình dữ liệu cho phân cụm

 Phân cụm dựa theo mô hình

 STING, CLIQUE, WaweCluster…  Tạo phân cấp ô lưới theo một số tiêu chí: số lượng đối tượng trong ô  Sử dụng lưới các ô cùng cỡ: tuy nhiên cụm là các “ô” phân cấp

 Phân cụm dựa theo lưới

 DBSCAN, OPTICS…  Hàm liên kết: Xác định cụm là lân cận phần tử chính  Hàm mật độ: Tìm các phần tử chính tại nơi có mật độ cao

 Phân cụm dựa theo mật độ Các phương pháp phân cụm

 CHAMELEON, BIRRCH và CURE, …  HAC: Hierarchical agglomerative clustering  Độ đo tương tự / khoảng cách theo các tiêu chí tương ứng

 Xây dựng hợp (tách) dần các cụm tạo cấu trúc phân cấp và đánh giá

 Phân cụm phân cấp

 Hạn chế: Không điều chỉnh được lỗi  K-mean, k-mediod, CLARANS, …  Độ đo tương tự / khoảng cách  Tiếp cận: từ dưới lên (gộp dần), từ trên xuống (chia dần)

thuộc một số cụm

 Xây dựng từng bước phân hoạch các cụm và đánh giá chúng theo các

 Phân cụm phân vùng (phân cụm phẳng)

tiêu chí tương ứng

 Phân vùng, phân cấp, dựa theo mật độ, dựa theo lưới, dựa theo mô

 Các phương pháp phổ biến

Các phương pháp phân cụm

hình, và phân cụm mờ

03/02/17

182

=(1+1)/(2+1+1)=0.5 D(Nam, Vân)

 Lập ma trận khác biệt cho

a=2, b=1, c=1, d=3  Ví dụ, cặp (Nam, Vân): từng cặp đối tượng.

 Quy về giá trị nhị phân:

M/F, Y/N, N/P

 CSDL xét nghiệm bệnh  Ví dụ về độ khác biệt

Một số độ đo cơ bản

nhân

 Tính xác định dương, tính đối

xứng, tính bất đẳng thức tam giác

 Giá trị thực: Khoảng cách

Manhattan, Euclide, Mincowski

 Thuộc tính nhị phân: đối cứng,  Đối ngẫu độ đo tương đồng

 Độ đo khác biệt

giống nhau) hoặc dạng đơn giản (q thuộc tính  Giá trị rời rạc: hoặc tương tự trên không đối xứng

 Giá trị thực : độ đo cosin hai

vector

 Giá trị nhị phân: Ma trận kề, độ đo  Biểu diễn: vector n chiều

 Độ đo tương đồng 2. Một số độ đo cơ bản

trị thành nhị phân, độ đo Jaccard  Giá trị rời rạc [0,m]: Chuyển m giá Jaccard

03/02/17

183

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

 Tính lại ci mới: bước 2.1 khởi động (tổng, bộ đếm); bước 2.2

 Tính được độ tương tự của d với các ci.

 Với mỗi vòng lặp: duyệt CSDL trên đĩa 1 lần

 Toàn bộ dữ liệu quá lớn: không thể ở bộ nhớ trong

 Thi hành k-mean với dữ liệu trên đĩa

 Thực tế: số lần lặp  50

 Trong bước 2: các trọng tâm có thể không thuộc S

 Một số lưu ý (tiếp) và ví dụ

a. Thuât toán K-mean gán cứng

 Có thể dùng độ đo khoảng cách thay cho độ đo tương tự  Vấn đề chọn tập đại diện ban đầu ở bước Khởi động

 Giá trị mục tiêu đủ nhỏ  Khống chế số lần lặp  Điều kiện dừng cưỡng bức  Sau bước 2 không có sự thay đổi cụm

 Điều kiện dừng  Một số lưu ý

3. Thuât toán K-mean gán cứng

cộng và tăng bộ đếm; bước 2.3 chỉ thực hiện k phép chia.

03/02/17

184

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

cầu (các thành phần con không ellip/cầu hóa)

 Không thích hợp với các tập dữ liệu không siêu-ellip hoặc siêu

 Nhạy cảm với mẫu ban đầu: cần phương pháp chọn mẫu thô tốt

ngoại lệ thực tế, ngoại lệ do quan sát sai (làm sạch dữ liệu)

 Nhạy cảm với ngoại lệ (cách xa so với đại đa số dữ liệu còn lại):

 Cần cho trước k : số cụm  Phải “tính trung bình được”: dữ liệu phân lớp thì dựa theo tần số

 Nhược điểm

 Thường cho tối ưu cục bộ. Tối ưu toàn cục rất khó tìm  Một thuật toán phân cụm phổ biến nhất

là số phần tử

 Hiệu quả về thời gian: tuyến tính O(tkn), t số lần lặp, k số cụm, n  Đơn giản, dễ sử dụng

 Ưu điểm

Thuât toán K-mean

 Tinh chỉnh C dần với tỷ lệ học  (learning rate)

 Định hướng

 Tập k “đại diện cụm” C làm cực tiểu lỗi “lượng tử”

 Output

 Tập dữ liệu D (cho trước)  Số nguyên k > 0: số cụm biết trước

 Input Thuât toán K-mean mềm

03/02/17

185

 PAM: Partition Around Mediods  Hàm mục tiêu  Biến thể của K-mean: thay trọng tâm bằng một phần tử của D

 K-mediod

b. Thuât toán PAM (K-mediod)

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

Phải: Không thích hợp với bộ dữ liệu không siêu ellip/cầu hóa Trái: Nhạy cảm với chọn mẫu ban đầu

Thuât toán K-mean

03/02/17

186

 Điều kiện |G| < k có thể thay thế bằng |G|=1

 G là tập các cụm trong phân cụm

 Giải thích

a. Phân cụm phân cấp từ dưới lên

 Tinh chỉnh: Từ cụ thể tới khái quát  Lưu ý: k là một tham số  “tìm k tốt nhất”

phương án phân cụm theo các giá trị k khác nhau

 Đặc điểm: Không cho trước số lượng cụm k, cho phép đưa ra các

 Sơ bộ về thuật toán

 Độ tương tự trung bình giữa hai dữ liệu thuộc hai cum  Độ tương tự cực tiểu giữa hai dữ liệu thuộc hai cum: complete-link  Độ tương tự cực đại giữa hai dữ liệu thuộc hai cụm: single-link  Độ tương tự giữa hai đại diện

 Độ tương tư giữa hai cụm  Độ tương tự hai tài liệu

 Một số độ đo phân biệt cụm  HAC: Hierarchical agglomerative clustering

4. Phân cụm phân cấp

03/02/17

187

 Dưới: Độ tương tự cực đại (Single-link) tạo cụm chuỗi dòng

độ tương tự cực tiểu (complete-link) có tính cầu hơn so với cực đại

 Trên: Hoạt động thuật toán khác nhau theo các độ đo khác nhau:

 Ảnh hưởng của các độ đo

HAC với các độ đo khác nhau

 Chọn phân cụm theo “ngưỡng” về độ tương tự  Cho phép với mọi k  Hoạt động HAC

Phân cụm phân cấp từ dưới lên

03/02/17

188

BIRCH: Năm độ đo khoảng cách

 Thuật toán xây dựng cây  Hai tham số: bề rộng b và ngưỡng t  Một cây cân bằng

 Cây đặc trưng phân cụm CF Tree

 <3, (9,10), (29,38)>. Khi ghép cụm không tính lại các tổng liêu; SS : vector tổng bình phương các thành phần các đối tượng  CF = , n: số phần tử, LS: vector tổng các thành phần dữ

 Đặc trưng phân cụm CF: tóm tắt của cụm

 Khái niệm liên quan

 Tính bất động: Gán không đổi đối tượng –> cụm  Tính khả cỡ: Làm việc với tập dữ liệu lớn Hierarchies

 Balanced Iterative Reducing Clustering Using

b. Phân cụm phân cấp BIRCH

03/02/17

189

Clustering Method for Very Large Databases, SIGMOD Conference 1996: 103-114

Tian Zhang, Raghu Ramakrishnan, Miron Livny (1996). BIRCH: An Efficient Data

 Tinh chỉnh việc trộn:  Biến đổi đường đi tới lá khi bổ sung phần tử mới

 Xác định lá thích hợp: Duyệt từ gốc xuống một cách đệ quy để tới nút

 Chèn một “cụm” a vào cây  Cây ban đầu rỗng Chèn vào CF Tree và BIRCH

trang bộ nhớ tham số P kích thước không gian dữ liệu và định bằng số chiều  Cỡ của nút được xác

ngưỡng T cụm mà đảm bảo nhất L đặc trưng phân lá có nhiều

 Mỗi nút

nhiều nhất là B cành  Mỗi nút không là lá có

Cây đặc trưng phân cụm CF Tree

chia lá cũ Nếu không, tạo nút mới cho a; nếu không đủ bộ nhớ cho lá mới thì cần không (chưa vượt ngưỡng); nếu có thì đặc trưng CF của L1 bổ sung;  Biến đổi lá: Nếu gặp lá L1 gần a nhất, kiểm tra xem L1 có “hấp thụ“ a con gần a nhất theo 1 trong 5 khoảng cách nói trên

03/02/17

190

 Cụm hình dạng bất thường rất khó biểu diễn

 Dữ liệu phân cụm ellip/cầu hóa: đại diện cụm cho biểu diễn tốt

 Lưu ý

 Tần số xuất hiện các giá trị đặc trưng cho từng cụm

 Dùng cho dữ liệu phân loại

 Theo mô hình tần số

 Chạy thuật toán phân lớp để tìm ra biểu diễn cụm  Chỉ số cụm như nhãn lớp

 Theo mô hình phân lớp

 Cụm không ellip/cầu hóa: không tốt  Tính bán kính và độ lệch chuẩn để xác định phạm vi của cụm  Đại diện cụm làm tâm

 Theo đại diện cụm

 Các phương pháp biểu diễn điển dình 7. Biểu diễn cụm và gán nhãn

 Phân cụm cực đại kỳ vọng: khởi tạo, tính giá trị kỳ vọng, cực đại hóa kỳ vọng  Phân cụm cực đại kỳ vọng, phân cụm khái niệm, học máy mạng nơron  Làm phù hợp phân bố cụm với mô hình toán học

 Phân cụm phân cấp dựa trên mô hình

 Đạt được nếu có dãy mà mỗi cái sau là đạt được trực tiếp từ cái trước

neighborhood của q.

 P đạt được trực tiếp theo mật độ từ q nếu q là đối tượng lõi và p thuộc #-  | #-neighborhood| > MinPts gọi đối tượng lõi  #-neighborhood: vùng lân cận bán kính #  Density-Based Spatial Clustering of Application with Noise

 Phân cụm dựa trên mật độ DBSCAN

 RObust Clustering using linKs: xử lý dữ liệu rời rạc, quyết định “gần” theo

 Phân cụm phân cấp ROCK

 Thêm vào S các phần tử có d > 0  Đối ngẫu phân cụm phân cấp từ trên xuống: phần tử khác biệt -> cụm khác biệt S,

 Phân cụm phân cấp từ trên xuống DIANA

 Nghiên cứu giáo trình Các thuật toán phân cụm khác

tập phần tử láng giềng sim (p, q) > >0.

03/02/17

191

Retrieval, Cambridge University Press. 2008.

Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze,

Introduction to Information

 centroid: các từ khóa có tần số cao nhất

 Ba phương pháp chọn nhãn cụm đối với 3 cụm là cụm 4 (622 tài liệu),

 Ví dụ

Ví dụ: Gán nhãn cụm văn bản

 Chon đặc trưng của dữ liệu trong cụm gần trọng tâm nhất

 Tiêu đề

 Dùng các đặc trưng tần số cao tại trọng tâm cụm

 Hướng “trọng tâm” cụm

 N: Tổng số dữ liệu  N00 : số dữ liệu không chứa t không thuộc cụm C  N01 : số dữ liệu không chứa t thuộc cụm C  N10 : số dữ liệu chứa t không thuộc cụm C  N11 : số dữ liệu chứa t thuộc cụm C  Nxy (x có đặc trưng t, y dữ liệu thuộc C)  Chọn đặc trưng tương quan cụm

 Phân biệt các cụm (MU) Gán nhãn cụm

liệu gần trọng tâm nhất. information (MU): thông tin liên quan phân biệt các cụm; title: tiêu đề tài trong trọng tâm; mutual đầu tiên của bộ Reuters-RCV1 cụm 9 (1017 tài liệu), cụm 10 (1259 tài liệu) khi phân cụm 10000 tài liệu

03/02/17

192

 Phân ly theo trọng tâm

 Một số phương pháp điển hình

 Lấy độ tương tự cực tiểu (complete link), cực đại (single link)  Cực tiểu hóa tổng độ tương tự các cặp cụm khác nhau  Cực đại hóa tổng độ tương tự nội tại của các cụm

 Độ phân biệt các cụm Đánh giá theo độ đo tương tự

đo F và đánh giá theo các độ đo này

 Tính các độ đo: entropy, tinh khiết, chính xác, hồi tưởng, độ  Xây dựng ma trận nhầm lẫn khi phân lớp  Học bộ phân lớp đa lớp (cụm)  Coi mỗi cụm là một lớp

 Dùng thuật toán phân lớp

 Phân ly theo trọng tâm  Độ phân biệt giữa các cụm

 Đánh giá theo các độ đo tương tự/khoảng cách

 Đọc các dữ liệu trong cụm  Luật từ cây quyết định  Nghiên cứu trọng tâm và miền phủ

 Người dùng kiểm tra

 Một số phương pháp điển hình

 Chưa biết các cụm thực sự

 Đánh giá chất lượng phân cụm là khó khăn 8. Đánh giá phân cụm

03/02/17

193

Ví dụ

 Ngoại tuyến  Trực tuyến