Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 2

MỤC LỤC
1. Giới thiệu ........................................................................................................3
2. Các thuật toán Data Mining của Microsoft.....................................................3
3. Xây dựng các mô hình Data Mining bằng Analysis Services 2000 ...............6
3.1. Nguồn dữ liệu cho mô hình data mining..................................................6
3.2. Tạo mô hình data mining .........................................................................7
3.3. Huấn luyện mô hình data mining.............................................................8
3.4. Duyệt qua nội dung của mô hình data mining .........................................9
3.5. Dùng mô hình data mining thực hiện dự báo .........................................12
4. Kết luận .........................................................................................................15
Phụ lục A: Kết quả thử nghiệm ........................................................................16
A.1. Kết quả thực thi trên thuật toán cây quyết đònh ...................................16
A.1.1. Kết quả thực thi Training khi không có sự liên kết giữa các bảng16
A.1.2. Kết quả thực thi Training khi có sự liên kết giữa các bảng ..........19
A.2. Kết quả thực thi trên thuật toán Clustering (phân lớp).........................21
A.2.1. Kết quả thực thi Training khi không có sự liên kết giữa các bảng21
A.2.2. Kết quả thực thi Training khi có sự liên kết giữa các bảng ..........23
Phụ lục B: Một số thuật ngữ .............................................................................25
Phụ lục C: Chương trình demo ..........................................................................26
Tài liệu tham khảo:...........................................................................................27


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 3

Nghiên cứu công cụ Data Mining trong SQL Server 2000

1. Giới thiệu

Trong môi trường thương mại điện tử ngày nay, lónh vực data mining ngày càng
thu hút nhiều sự quan tâm. Nhờ vào các phương tiện tự động hay bán tự động, data
mining khảo sát và phân tích trên một lượng lớn dữ liệu để rút ra những mẫu và qui
luật có ý nghóa. Các thông tin này giúp các công ty kinh doanh chẳng hạn như hiểu rõ
khách hàng hơn để từ đó có các chiến lược phù hợp hơn nhằm nhằm cải thiện hoạt
động tiếp thò, bán hàng và hỗ trợ khách hàng. Qua nhiều năm hoạt động, các công ty
kinh doanh tích luỹ được các cơ sở dữ liệu (CSDL) rất lớn từ các ứng dụng như Lập kế
hoạch sử dụng nguồn tài nguyên cho hoạt động kinh doanh (Enterprise Resource
Planning (ERP)), Quản lý khách hàng (Client Relationship Management (CRM)), hay
từ các hệ thống điều hành khác. Người ta tin rằng có các giá trò chưa được khai thác
tiềm ẩn bên trong các dữ liệu này. Các kỹ thuật data mining có thể giúp lấy ra những
mẫu như thế.
Gần đây Microsoft đã đưa ra OLE DB cho giao diện lập trình ứng dụng (API) Data
Mining với nhiều data mining provider hàng đầu. API này đònh nghóa một ngôn ngữ
truy vấn data mining dựa trên cú pháp SQL. Các mô hình data mining (Data Mining
Model) được xem như là một dạng đặc biệt của bảng quan hệ. Các tính toán dự báo
được xem như là một dạng đặc biệt của phép kết. Microsoft SQL Server 2000
Analysis Services cung cấp Microsoft data mining provider dựa trên OLE DB cho
chuẩn Data Mining. Provider này gồm hai thuật toán data mining: Microsoft Decision
Trees và Microsoft Clustering.

2. Các thuật toán Data Mining của Microsoft

Hai thuật toán data mining trong SQL Server 2000, Microsoft Decision Trees
(MDT) và Microsoft Clustering, là kết quả của nhiều năm nghiên cứu tại Microsoft
Research. Sau đây là trình bày tóm tắt hai thuật toán này.
Thuật toán Microsoft Decision Trees (cây quyết đònh)
Cây quyết đònh có lẽ là kỹ thuật phổ biến nhất cho việc lập mô hình dự báo.

Bảng sau đây là một tập dữ liệu huấn luyện (training data) được dùng để dự báo credit
risk
Customer
ID

Debt level

Income level Employment type Credit risk

1

High

High

Self-employed

Bad

2

High

High

Salaried

Bad

3


High

Low

Salaried

Bad

4

Low

Low

Salaried

Good

5

Low

Low

Self-employed

Bad

6


Low

High

Self-employed

Good


Nghiên cứu công cụ Data Mining trong SQL Server 2000
7

Low

High

Salaried

Trang 4
Good

Sau đây là một cây quyết đònh được tạo ra từ tập dữ liệu này:

Trong ví dụ này, thuật toán Decision Tree xác đònh thuộc tính quan trọng nhất là Debt
level, do đó rẽ nhánh đầu tiên được thực hiện dựa trên debt level. Node với Debt =
High là node lá (cả ba trường hợp đều là bad credit risk). Node với Debt = Low còn
lẫn lộn (3 trường hợp good credit risk, 1 trường hợp bad credit risk). Tiếp theo,
Employment là thuộc tính quan trọng kế tiếp. Tương tự node với Employment =
Salaried là node lá.

Trên đây chỉ là một ví dụ nhỏ dựa vào dữ liệu tổng hợp, nhưng nó cho thấy cây quyết
đònh có thể dùng các thuộc tính có liên quan để dự báo credit risk. Khi phạm vi của
vấn đề được mở rộng thì sẽ gây khó khăn cho việc rút ra các luật một cách thủ công.
Thuật toán có thể chạy trên hàng trăm thuộc tính và hàng triệu record để đưa ra cây
quyết đònh mô tả các luật dự báo credit risk.
Có nhiều thuật toán khác nhau với các phương pháp rẽ nhánh khác nhau được dùng để
xây dựng cây quyết đònh. Microsoft Decision Tree là cây phân lớp theo xác suất
(Probabilistic Classification Tree). Nó rất giống với C4.5, nhưng mặc đònh dùng
Bayesian score làm tiêu chuẫn rẽ nhánh thay vì Entropy.
Thuật toán Microsoft Clustering
Clustering nghóa là tìm các nhóm (hay cluster) trong tập dữ liệu gồm các tập
con có các record tương tự nhau. Nó khác với mô hình dự báo ở chỗ nó không có
thuộc tính đích trong tập dữ liệu. Thuật toán clustering quyết đònh thuộc tính “ẩn” mới
này bằng cách khảo sát tập dữ liệu. Có nhiều phương pháp phân nhóm dữ liệu. Các
thuật toán phổ biến như K-Means, các phương pháp khối liên kết nhiều tầng, và lập
mô hình pha trộn bằng cách dùng thuật toán Expectation-Maximization (EM) để liên


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 5

kết các mô hình pha trộn theo xác suất tới tập dữ liệu. Các record của tập dữ liệu có
thể thuộc về các cluster khác nhau tuỳ thuộc vào cách thiết lập giới hạn.
Xét một CSDL nhân viên, trong đó mỗi nhân viên gồm ba thuộc tính: age, salary, và
vested amount. Người sử dụng muốn có một bảng về độ tuổi trung bình của các nhân
viên có vested amount trong khoảng 100K-200K, 200K-400K, và 400K-1000K và có
lương trong khoảng 50K-100K, 100K-200K, 200K-300K. Đây là loại dữ liệu ba chiều.
Các record của dữ liệu n-chiều có thể được xem như là các điểm trong không gian nchiều. Chẳng hạn, các record dạng (age, salary) có thể được xem như các điểm trong
không gian 2-chiều, với chiều age và chiều salary. Hình 3a và 3b minh hoạ hai cách

biểu diễn cho ví dụ này.

Việc tìm các cluster trong không gian nhiều chiều (4 chiều hay lớn hơn) thì rất phức
tạp đối với con người. Nếu chỉ đơn giản biểu diễn dữ liệu bằng các điểm thì sẽ không
giúp ích gì nhiều. Tuy nhiên, các thuật toán clustering tự động tìm các cluster như thế
trong tập dữ liệu. Mỗi cluster được thể hiện bởi phân bố của chính nó.
Thuật toán Microsoft Clustering có cơ sở là thuật toán Expectation and Maximization
(EM). Thuật toán này lặp đi lặp lại giữa hai bước. Trong bước đầu tiên, gọi là bước E
hay “Expectation”, thành phần cluster của mỗi trường hợp được tính ra. Trong bước
thứ hai, gọi là bước M hay “Maximization”, các thông số (parameter) của các mô hình
được ước lượng lại dựa vào các thành phần cluster này. EM tương tự với K-Means, với
các bước chính sau đây:
1. Thiết lập các phương tiện khởi tạo
2. Gán các trường hợp cho mỗi phương tiện bằng cách sử dụng một vài độ đo
khoảng cách
3. Tính ra các phương tiện mới dựa vào các thành viên của mỗi cluster
4. Thiết lập các biên cho vùng chứa mới dựa vào các phương tiện mới
5. Lặp lại chu kỳ cho đến khi hội tụ.
EM khác với K-Means ở nhiều khía cạnh. Điểm khác biệt chủ yếu là EM không xác
đònh biên rõ ràng giữa các cluster. Một trường hợp được gán cho mỗi cluster với một


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 6

xác suất nào đó. Sau đây là minh hoạ một vài lần lặp của thuật toán EM cho tập dữ
liệu một chiều. Giả sử dữ liệu trong mỗi cluster có phân bố Gauss. Các phương tiện
của mỗi cluster được hoán đổi nhau sau mỗi lần lặp.


Hầu hết các thuật toán Clustering đều phải đọc tất cả các con trỏ dữ liệu vào bộ nhớ,
điều này có thể gây ra các vấn đề nghiêm trọng về khả năng tải của bộ nhớ khi xử lý
một tập dữ liệu lớn. Để giải quyết vấn đề này, thuật toán Microsoft Clustering dùng
một phạm vi cơ sở, ở đó chọn lựa lưu trữ các phần CSDL quan trọng và tóm tắt các
phần khác. Tư tưởng chủ đạo là đọc dữ liệu vào các vùng nhớ theo từng khối và dựa
vào mô hình data mining đã được cập nhật để gom các trường hợp gần nhau dựa vào
phân bố Gauss, vì thế các trường hợp đó được nén lại. Thuật toán Microsoft Clustering
chỉ cần một lần duyệt qua dữ liệu thô.

3. Xây dựng các mô hình Data Mining bằng Analysis Services 2000
3.1. Nguồn dữ liệu cho mô hình data mining
Xét câu hỏi: hãy chỉ ra các khách hàng có nhiều nguy cơ rời bỏ ngân hàng nhất
dựa trên thông tin của khách hàng, thông tin giao dòch của họ với ngân hàng.
Để trả lời câu hỏi này, các bảng CSDL quan hệ sau đây được dùng đến:
- Bảng Customer: chứa các thông tin về khách hàng của ngân hàng bao
gồm: age (tuổi của khách hàng), income (thu nhập), educational level
(trình độ học vấn), house value (giá trò nhà), loan (nợ),…
- Bảng Purchases: chứa các thông tin giao dòch của khách hàng bao gồm:
checking accounts (tài khoản vãng lai), money market savings (tiền gởi
tiết kiệm), …


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 7

Mô hình quan hệ cho hai bảng này như sau:

3.2. Tạo mô hình data mining
Khi tạo một mô hình data mining (DMM), bạn phải đònh nghóa cấu trúc và các

thuộc tính cho mô hình. Để đònh nghiã một DMM mới trong Microsolf OLE DB for
Data Mining API, dùng lệnh CREATE DATA MINING MODEL. Tương tự như lệnh
CREATE TABLE, lệnh tạo mô hình này chỉ đònh nghóa cấu trúc và các thuộc tính của
nó, chứ hoàn toàn không có dữ liệu. Cũng tương tự như thế, lệnh này đònh nghóa khoá,
cột, thuật toán được dùng và các tham số dùng cho việc huấn luyện DMM sau này.
Cú pháp đònh nghóa mô hình data mining:
CREATE MINING MODEL <tên mô hình> (<đònh nghóa các cột>) USING vụ>[(<các tham số dòch vụ>)]
Tuy nhiên, do các cột của DMM yêu cầu các thông tin đặc thù, nên có một số mở
rộng được đưa vào cú pháp SQL chuẩn. Sau đây là một ví dụ áp dụng cho cấu trúc
bảng được mô tả ở trên:
CREATE MINING MODEL [Model_MDT_Churn_Prediction]
([Customer Id] LONG KEY,
[Income] DOUBLE CONTINUOUS ,
[Other Income] DOUBLE CONTINUOUS ,
[Loan] DOUBLE CONTINUOUS ,
[Age] DOUBLE CONTINUOUS ,
[Region Name] TEXT DISCRETE ,
[Home Years] DOUBLE CONTINUOUS ,
[House Value] DOUBLE CONTINUOUS ,
[Education Level] TEXT DISCRETE ,
[Home Type] TEXT DISCRETE ,
[Churn Yes No] TEXT DISCRETE PREDICT)
USING Microsoft_Decision_Trees


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 8

Các từ khoá LONG, DOUBLE và TEXT đònh nghóa kiểu dữ liệu của cột. Tuy
nhiên có một vài mở rộng so với SQL chuẩn. Từ khoá KEY chỉ đònh cột (các cột) làm
khoá. Hai từ khoá CONTINUOUS (liên tục) và DISCRETE (rời rạc) là hai giá trò có
thể có cho các cột nội dung. Từ khoá PREDICT chỉ đònh cột kết quả dự báo.
Chú ý: bạn cũng có thể tạo mô hình data mining từ Analysis Manager, khi đó lệnh
CREATE MINING MODEL được phát sinh tự động.
3.3. Huấn luyện mô hình data mining
Sau khi tạo mô hình data mining, bước tiếp theo là huấn luyện mô hình. Huấn
luyện mô hình nghóa là chạy mô hình trên dữ liệu dùng để huấn luyện (training data)
bằng cách dùng một thuật toán đặc thù nào đó. Đây là bước tốn nhiều thời gian nhất.
Thuật toán có thể lặp lại một vài lần trên tập dữ liệu huấn luyện để tìm ra các mẫu ẩn
bên trong tập dữ liệu này. OLE DB for Data Mining API che giấu các phức tạp của
việc huấn luyện mô hình bằng cách cung cấp lệnh INSERT như là lệnh dùng để huấn
luyện. Mặc dù có một lượng dữ liệu khổng lồ được đưa vào mô hình data mining trong
giai đoạn này, nhưng nó không lưu trữ bất kỳ dữ liệu nào, thay vào đó nó lưu trữ các
mẫu của chúng. Khi mô hình đã được huấn luyện, ứng dụng khách có thể duyệt qua
nội dung của mô hình và thực hiện các truy vấn trên tập dữ liệu mới này.
Cú pháp của lệnh INSERT:
INSERT [INTO] <tên mô hình>
[ <các cột được ánh xạ của mô hình > ]
<truy vấn dữ liệu nguồn>


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 9

Ví dụ: Huấn luyện cho mô hình Model_MDT_Churn_ Prediction được tạo ra ở

trên.

INSERT INTO [Model_MDT_Churn_ Prediction]
(SKIP, [Income], [Other Income], [Loan], [Age], [Region Name], [Home
Years], [House Value], [Education Level], [Home Type], [Churn Yes No])
OPENROWSET(‘SQLOLEDB’, ’…’, SELECT DISTINCT [CustomerID],
[Income], [OtherIncome], [Loan], [Age], [RegionName], [HomeYears],
[HouseValue], [EducationLevel], [HomeType], [Churn_Yes_No] FROM
Customers)
3.4. Duyệt qua nội dung của mô hình data mining
Khi mô hình đã được huấn luyện, từ Analysis Manager bạn có thể duyệt qua
nội dung mô hình dùng tree browser. Trong browser này, nội dung hiển thò dạng đồ
hoạ, và cho phép lướt qua các phần nội dung khác nhau. Nội dung của một DMM là
tập các luật, các công thức, các phân lớp, các phân bố, các node, hay bất kỳ thông tin
nào khác có nguồn gốc từ một tập dữ liệu đặc biệt bằng cách dùng kỹ thuật data
mining.
Tuỳ theo kỹ thuật data mining được dùng khi tạo DMM mà loại nội dung có thể khác
nhau giữa các mô hình. Nội dung DMM của một cây quyết đònh sẽ khác với nội dung
DMM của clustering.
Duyệt qua nội dung của mô hình có thể cung cấp các kiến thức quan trọng bên trong
dữ liệu. Trong nhiều trường hợp, nó cho phép các nhà phân tích dữ liệu hiểu được các
mẫu và các qui luật và dự đoán các đặc điểm của dữ liệu mới.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 10

Sau đây là mẫu được tìm thấy bởi thuật toán Decision Trees chạy trên tập dữ liệu
huấn luyện:

Ta cũng có thể duyệt qua tất cả các trường hợp có thể có của mô hình. Xét một mô

hình DMM với các cột như sau: Gender (giới tính), Age (tuổi) và HairColor (màu tóc).
Sau khi mô hình này được huấn luyện, cột Gender sẽ có các trạng thái (giá trò)
“Male” (nam), “Female” (nữ), “Missing” (không biết). Đối với cột HairColor, DMM
nhìn thấy và ghi nhớ các giá trò “Black”, “Gray”, và “Missing”. Đối với cột Age, mặc
dù DMM thấy tất cả các giá trò liên tục của nó, nhưng không ghi nhớ từng giá trò phân
biệt mà chỉ ghi nhớ các giá trò minimum (nhỏ nhất), mean (trung bình), maximum (lớn
nhất).
Giả sử mô hình được xây dựng để dự báo cột HairColor từ một tập dữ liệu 100 người,
nội dung của DMM có thể như sau:


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 11

Câu truy vấn:
SELECT *, PredictProbability(HairColor) FROM HairColorPredictDMM
Có kết quả như sau:
Gender

Age

HairColor

P(HairColor)

Male

2

Black

.667

Male

2

Gray

.267

Male

2

NULL

.067

Male

91

Black

.300

Male

91

Gray

.625

Male

91

NULL

.075

Male

45

Black

.667

Male

45

Gray

.267

Male

45

NULL

.067

Male

NULL

Black

.600

Male

NULL

Gray

.350

Male

NULL

NULL

.05

Female

2

Black

.933

Female

2

Gray

.067

Female

2

NULL

.000

Female

91

Black

.300

Female

91

Gray

.625

Female

91

NULL

.075

Female

45

Black

.933

Female

45

Gray

.067


Nghiên cứu công cụ Data Mining trong SQL Server 2000
Gender

Age

HairColor

P(HairColor)

Female

45

NULL

.000

Female

NULL

Black

.600

Female

NULL

Gray

.350

Female

NULL

NULL

.05

NULL

2

Black

.800

NULL

2

Gray

.167

NULL

2

NULL

.033

NULL

91

Black

.300

NULL

91

Gray

.625

NULL

91

NULL

.075

NULL

45

Black

.800

NULL

45

Gray

.167

NULL

45

NULL

.033

NULL

NULL

Black

.600

NULL

NULL

Gray

.350

NULL

NULL

NULL

.05

Trang 12

Câu truy vấn:
SELECT Age, PredictProbability(HairColor) FROM HairColorPredictDMM
WHERE Gender = 'Male' and HairColor = 'Black'
Có kết quả như sau:

Gender

Age

HairColor

P(HairColor)

Male

2

Black

.667

Male

91

Black

.300

Male

45

Black

.667

Male

NULL

Black

.600

3.5. Dùng mô hình data mining thực hiện dự báo
Sau khi được huấn luyện, mô hình có thể được dùng để thực hiện các dự báo
trên các tập dữ liệu mới.
Trong OLE DB for Data Mining API, lệnh dùng để thực hiện dự báo là lệnh
SELECT. Lệnh này thực hiện kết một mô hình data mining với một bảng input mới.
Phép kết đặc biệt này được gọi là PREDICTION JOIN.
Cú pháp tổng quát của lệnh SELECT:
SELECT [FLATTENED] <SELECT-expressions>
FROM <tên mô hình> PREDICTION JOIN <truy vấn dữ liệu nguồn> ON <điều kiện kết>


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 13

[WHERE <WHERE-expression>]
Mệnh đề <truy vấn dữ liệu nguồn>: chỉ đònh tập dữ liệu mới có các thuộc tính được
dự báo bằng cách kết hợp tập này với tri thức trong mô hình DMM.
PREDICTION JOIN: các trường hợp thực tế từ <truy vấn dữ liệu nguồn> được kết
hợp với tập các trường hợp có thể có từ mô hình <tên mô hình> thông qua phép toán

PREDICTION JOIN. Sự kết hợp của các trường hợp trong dữ liệu nguồn với tất cả các
trường hợp có thể có thông qua PREDICTION JOIN về mặt ngữ nghóa khác với phép
kết trong CSDL quan hệ chuẩn, vì lý do đơn giản sau đây:
- Các trường hợp trong DMM không thể hiện tất cả các giá trò có thể có của một thuộc
tính (cột) có kiểu dạng CONTINUOUS, tuy nhiên một PREDICTION JOIN phải kết
hợp một giá trò continuous chính xác của một trường hợp trong dữ liệu nguồn với các
giá trò phân bố trong DMM. Với ví dụ tập của tất các trường hợp có thể có nêu trên,
lệnh sau đây trả về không có record nào bởi vì các trường hợp có thể có trong DMM
có cột Age chỉ chứa các giá trò “Minimum”, “Mean”, “Maximum”, và “Missing” ứng
với (2, 45, 91, “Missing”):
SELECT * FROM GenderPredictDMM WHERE Gender = 'Male' AND Age = 30
Tuy nhiên, một PREDICTION JOIN sử dụng cây quyết đònh được mô tả cho mô hình
này tìm thấy một phân bố trên HairColor cho phái nam 30 tuổi như sau: Black = .667,
Grey = .267, Missing = .067.
- Các trường hợp của DMM thể hiện đầy đủ các giá trò có thể có cho một cột được
dùng để dự báo, trong khi người thực hiện dự báo thường mong đợi một giá trò đơn “tốt
nhất”. Xét câu truy vấn sau:
SELECT * FROM GenderPredictDMM WHERE Gender = 'Male' AND Age = 45
Kết quả như sau:
Gender

Age

HairColor

Male

45

Black

Male

45

Gray

Male

45

NULL

- PREDICTION JOIN có thể cần có một vài ràng buộc và giả đònh khi gặp các giá trò
không xác đònh được (missing) trong trường hợp nguồn. Một PREDICTION JOIN giữa
một mô hình đơn giản và một trường hợp mà trong đó age là 30, gender không biết, sẽ
cho kết quả của HairColor là “Black” với xác suất là 80%.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 14

Tổng quát, PREDICTION JOIN sẽ chọn một trường hợp từ tập dữ liệu input, và dựa
vào điều kiện mô tả trong mệnh đề ON để tìm tập các trường hợp tương ứng trong
DMM.
Mệnh đề <SELECT-expressions> : là một tập các phát biểu phân cách bởi dấu
phẩy, một phát biểu có thể là một cột đơn giản dùng để tham chiếu, hay chứa các
chức năng dự báo. Các cột có thể được tham chiếu từ DMM hay từ truy vấn dữ liệu
nguồn.

ON và Điều kiện kết: mỗi dòng trong tập các trường hợp có thể có của DMM là duy
nhất, nên nó có thể được kết với các dòng trong truy vấn nguồn của các trường hợp
thực sự thông qua mệnh đề <điều kiện kết> của từ khoá ON. Điều kiện kết sẽ kết hợp
các cột trong DMM với các cột trong truy vấn nguồn. Điều kiện kết có một phát biểu
“=” cho các cột được kết, và các phát biểu được nối với nhau qua từ khoá AND trong
trường có nhiều cột kết.
Mệnh đề WHERE : giới hạn các trường hợp trả về từ truy vấn dự báo.
Ví dụ: Hãy dự báo các khách hàng có nhiều nguy cơ rời bỏ ngân hàng nhất (=80%)
dựa trên thông tin của khách hàng:
SELECT FLATTENED
[T1].[CustomerID], [T1].[Income], T1.[OtherIncome], [T1].[Loan], [T1].[Age],
[T1].[RegionName], [T1].[HomeYears], [T1].[HouseValue], [T1].[EducationLevel],
[T1].[HomeType], [T1].[Churn_Yes_No])
FROM

[Model_MDT_Churn_Prediction] AS [M1]
PREDICTION JOIN
OPENROWSET('SQLOLEDB', ’…;data source=D:\customer.mdb',
SELECT DISTINCT [CustomerID], [Income], [OtherIncome], [Loan],
[Age], [RegionName], [HomeYears], [HouseValue], [EducationLevel],
[HomeType], [Churn_Yes_No] FROM Customers)
AS [T1]
ON
[M1]. [Customer Id]= [T1]. [CustomerID]
WHERE PredictProbability([M1]. [Churn_Yes_No]) > 0.8.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 15

4. Kết luận

Data mining đang nhanh chóng trở thành một kỹ thuật phân tích được sử dụng
rộng rãi. Báo cáo này mô tả hai thuật toán data mining trong SQL Server 2000
Analysis Services: Microsoft Decision Trees (MDT) và Microsoft Clustering. Báo cáo
cũng đưa ra cách xây dựng các mô hình data mining giúp giải quyết các vấn đề trong
kinh doanh. Các kết quả thực nghiệm trong huấn luyện các mô hình data mining, dùng
cả hai thuật toán với các thiết lập các thông số khác nhau được trình bày trong phụ lục
A. Các kết quả này chứng tỏ hai thuật toán này thực thi rất nhanh và có thể áp dụng
trên các tập dữ liệu lớn. Chẳng hạn, thuật toán Microsoft Decision Trees tốn khoảng
100 phút để huấn luyện một mô hình data ming với 10 triệu trường hợp và 25 thuộc
tính.
Với SQL Server 2000 Analysis Services, data mining không còn là đặc quyền của các
nhà thống kê. Người sử dụng không cần biết đến các phức tạp của các thuật toán data
mining. Mỗi người phát triển CSDL đều có khả năng tạo và huấn luyện các mô hình
data mining và nhúng các tính năng nâng cao vào các ứng dụng của họ.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 16

Phụ lục A: Kết quả thử nghiệm
Sau đây nhóm xin trình bày về quá trình chạy thử nghiệm khi dùng hai thuật
toán cây quyết đònh và thuật toán clustering. Việc hiểu rõ về tác động của các yếu tố
tới thời gian thực thi thuật toán sẽ giúp các nhà phát triển có một sự lựa chọn mô hình
tối ưu nhất, giảm thiểu thời gian thực thi trên máy.
Khi thực thi thuật toán, các yêu tố sau đây sẽ ảnh hưởng tới thời gian thực thi:
- Số các trường hợp.

- Số lượng các thuộc tính.
- Số các trạng thái (giá trò).
- Số các trạng thái của thuộc tính liên kết .
- Sự thưa thớt của bảng (sparseness of the table).
- Số lượng phân lớp trong thuật toán phân lớp.
Trong các thử nghiệm sau, một thông số sẽ được thay đổi, các thông số khác được giữ
nguyên. Thời gian thực hiên sẽ cho chúng ta biết về tác động của yếu tố thay đổi đó
tới quá trình thực thi thuật toán.
A.1. Kết quả thực thi trên thuật toán cây quyết đònh

A.1.1. Kết quả thực thi Training khi không có sự liên kết giữa các bảng
Thường thì sau khi chuẩn bò dữ liệu, các dữ liệu này nằm trên một bảng. Và
các dự đoán thường dựa trên bảng này.

Tác động của số lượng các thuộc tính tham gia dự đoán (input Attributes)
Các thông số
Training cases
Predictable Attribute
Input Attributes
Number of states

Số lượng
1 000 000.
1
Varying :10, 20, 50, 100, 200
25


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 17

Nhận xét :
- Thời gian thực thi tăng tuyến tính khi số lượng thuộc tính tăng.
- Thời gian thực thi khá nhanh : 130 phút cho 1 triệu trường hợp với 200 thuộc tính.

Tác động của kích thước dữ liệu ( số các trường hợp) .
Các thông số
Training cases
Predictable Attribute
Input Attributes
Number of states

Số lượng
Varying :10 000 đến 10 triệu.
1
20
25


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 18

Nhận xét :
- Thời gian thực thi tăng tuyến tính khi số lượng các trường hợp tăng.
- Thời gian thực thi khá nhanh : 20 giây cho 10 000 trường hợp và100 phút cho 20
triệu trường hợp.

Tác động của số lượng các trạng thái của thuộc tính tham gia dự đoán.

Các thông số
Training cases
Predictable Attribute
Input Attributes
Number of states

Số lượng
1 triệu.
1
20
Varying : 2,5,10,25,50

Nhận xét :
- Thời gian thực thi tăng tuyến tính khi số lượng các trạng thái nhỏ hơn 10.
- Khi số lượng các trạng thái tăng, thuật toán sẽ khó khăn trong việc xác đònh dữ
liệu hữu dụng khi tạo cây. Khi đó chiều cao của cây giảm và dẫn đến thời gian
training giảm.

Tác động của số lượng các thuộc tính cần phải dự đoán ( Predictable
Attributes)
Các thông số
Training cases
Predictable Attribute
Input Attributes
Number of states

Số lượng
1 triệu.
Varying :1,2,4,16,32.
40

25


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 19

Nhận xét: thời gian thực thi tăng hơi mạnh hơn tuyến tính tuỳ thuộc vào số lượng các
thuộc tính dự đoán. Nguyên do là khi có nhiều hơn một thuộc tính cần dự đoán thì việc
tạo cây có thể làm song song.

A.1.2. Kết quả thực thi Training khi có sự liên kết giữa các bảng
Bảng kết hợp là một khái niệm mới được giới thiệu trong OLE DB cho Data
mining. Đây là một đặc tính khá mạnh, nó cho phép trả lời nhiều câu hỏi dự đoán
phức tạp. Ví dụ như câu hỏi liệt kê các sản phẩm khác có thể hấp dẫn khách hàng dựa
vào các sản phẩm mà họ đã mua. Nếu không có khái niệm bảng kết hợp thì việc phân
tích dữ liệu cho câu hỏi này là rất khó khăn.

Tác động của số lượng các trạng thái của thuộc tính trong bảng kết hợp
Các thông số
Case table
Training cases
Predictable Attribute
Input Attributes
Number of states
Nested table
Input Attributes
Number of states ( banking product)
Products perchased per Custommer

Số lượng
200 000.
1
5
25
5
Varying: 100 đến 1000

0 Ỉ50


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 20

Nhận xét :
- Thời gian thực thi mất nhiều thời gian hơn khi không có bảng kết hợp.
- Khi số lượng sản phẩm tăng trên 255 thì thời gian bắt đầu giảm. Nguyên do là khi
đó thuật toán sử dụng kỹ thuật lựa chọn đặc điểm để lọc ra những thông tin quan
trọng nhất, còn những sản phẩm còn lại thì dùng mô hình lề (marginal model).
- Khi số lượng các gía trò khoá của bảng kết hợp nhiều hơn, và khi mức độ giao dòch
của khách hàng vẫn duy trì như cũ thì các trò của khoá của bảng kết hợp phân bố
thưa hơn. Do đó, có ít mẫu liên quan cho mỗi khoá. Cây trở nên nhỏ hơn, và thời
gian training giảm.

Tác động của số lượng sản phẩm mà khách hàng mua.
Các thông số
Case table
Training cases
Predictable Attribute

Input Attributes
Number of states
Nested table
Input Attributes
Number of states ( banking product)
Products perchased per Custommer

Số lượng
200 000.
1
5
25
5
1000
10 Ỉ50


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 21

Nhận xét: thời gian thực thi tăng tuyến tính.

Tác động của số lượng các trường hợp trong bảng chính.
Các thông số

Số lượng

Case table

Training cases
Predictable Attribute
Input Attributes
Number of states

Varying 10 000 Ỉ 200 000.
1
5
25

Nested table

Input Attributes
Number of states ( banking product)
Products perchased per Custommer

5
20
25

Nhận xét : thời gian thực thi tăng tuyến tính.
A.2. Kết quả thực thi trên thuật toán Clustering (phân lớp)

A.2.1. Kết quả thực thi Training khi không có sự liên kết giữa các bảng
Tác động của số lượng các phân lớp (Number of clusters)


Nghiên cứu công cụ Data Mining trong SQL Server 2000
Các thông số
Training cases

Predictable Attribute
Input Attributes
Number of states
Identifiable clusters

Trang 22

Số lượng
1 000 000.
1
20
20
5,10,20

Nhận xét: thời gian thực thi gần tuyến tính.

Thực hiện tương tự đối với:
Tác động của số lượng các thuộc tính tham gia dự đoán
Các thông số
Training cases
Predictable Attribute
Input Attributes
Number of states
Identifiable clusters

Số lượng
1 000 000.
1
20
20

10

Nhận xét :
- Thời gian thực thi tăng tuyến tính. Với một triệu trường hợp, tốn khoảng 230 phút
với 50 thuộc tính input.
- Đối với các biến liên tục thì tốn nhiều thời gian training hơn so với các biến rời
rạc. Nguyên do là các tính toán lân cận cho các biến liên tục thì phức tạp hơn so
với các biến rời rạc.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 23

Tác động của kích thước dữ liệu ( số các trường hợp) .
Các thông số
Training cases
Predictable Attribute
Input Attributes
Number of states
Identifiable clusters

Số lượng
10 000,25 000, 50 000, 75 000, 100 000, 1 triệu.
1
20
50
10

Nhận xét :

- Thời gian thực thi tăng tuyến tính.
- Tốn 100 phút cho một triệu trường hợp và 910 phút cho 10 triệu trường hợp. Thuật
toán Microsoft Clustering thì chậm hơn khoảng 8 lần so với thuật toán MDT trong
trường hợp này.

Thực hiện tương tự đối với Tác động của số lượng các trạng thái của thuộc
tính tham gia dự đoán.
A.2.2. Kết quả thực thi Training khi có sự liên kết giữa các bảng
Tác động của số lượng các trạng thái của thuộc tính trong bảng kết hợp
Các thông số
Case table
Training cases
Predictable Attribute
Input Attributes
Number of states
Nested table
Input Attributes
Number of states ( banking product)
Products perchased per Custommer

Số lượng
200 000.
1
5
20
5
Varying: 100 đến 1000
25

Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 24

Nhận xét :
- Thời gian training giảm khi số lượng các trạng thái tăng. Có hai lý do dẫn đến kết
quả này. Thứ nhất, thuật toán lựa chọn thuộc tính ngăn cản số thuộc tính tăng vượt
quá 255. Thư hai, khi số thuộc tính giảm, mật độ phân bố của dữ liệu thấp. Kết
quả là có không đủ mẫu cho thuật toán để xác đònh các cluster tạo thành, do đó
thuật toán dùng ít lần lặp hơn.
- Số các thuộc tính input càng lúc càng giảm là do sự chọn lựa đặc điểm. Một vài
thuộc tính được nhóm lại với nhau là do sự phân bố thưa thớt của dữ liệu.

Thực hiện tương tự đối với:
Tác động của số lượng sản phẩm mà khách hàng mua
Tác động của số lượng các trường hợp trong bảng chính.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 25

Phụ lục B: Một số thuật ngữ
Phần này giới thiệu ngắn gọn một số thuật ngữ data mining. Các thuật ngữ này
được giới thiệu trong Microsoft OLE DB for Data Mining specification.
Data Mining Model (mô hình data mining):
Một data mining model thì tương tự với một bảng quan hệ. Nó chứa các cột
khoá, các cột input, và các cột dự báo. Một mô hình được gắn với một thuật toán data
mining. Sau giai đoạn huấn luyện, mô hình data mining lưu trữ các mẫu được khám
phá bởi thuật toán data mining trên tập dữ liệu dùng cho việc huấn luyện. Một mô

hình data mining có thể được xem như là một “bảng thực sự” chứa các dòng ứng cho
mỗi kết hợp có thể có của các giá trò phân biệt trên từng cột của mô hình. Khi đã được
huấn luyện, mô hình có thể được dùng cho việc dự báo.
Columns (cột):
Một cột trong mô hình data mining thì tương tự với một cột trong một bảng
quan hệ, còn được gọi là “biến” hay “thuộc tính”. Có ba loại cột khác nhau trong mô
hình data mining: cột input, cột dự báo, hay cột input và dự báo. Mô hình data mining
sử dụng tập các thuộc tính input của trường hợp để dự báo các thuộc tính output. Trong
báo cáo này, cột và thuộc tính được dùng như nhau.
States (trạng thái):
Mỗi thuộc tính có thể có một tập các giá trò có thể có của nó. Các giá trò này
được gọi là trạng thái của thuộc tính.
Cases (trường hợp):
Data mining liên quan đến việc phân tích các trường hợp. Một trường hợp là
một thực thể thông tin cơ bản. Một trường hợp có thể là đơn giản, chẳng hạn khi phân
tích loan risk của khách hàng, thông tin khách hàng là một trường hợp. Một trường
hợp có thể phức tạp hơn, chẳng hạn mô hình data mining có thể dự báo danh sách các
sản phẩm khách hàng sẽ mua dựa vào thông tin khách hàng và thông tin giao dòch của
họ. Mô hình này kết kết hợp thông tin khách hàng với danh sách các sản phẩm mà họ
mua. Loại trường hợp này được gọi là trường hợp kết hợp (nested case). Trong báo
cáo này, thuật ngữ “kích thước mẫu” (sample size) được dùng để chỉ số các trường
hợp.
Case Tables (bảng trường hợp) và Nested Tables (bảng kết hợp):
Bảng trường hợp là bảng chứa thông tin trường hợp liên quan với phần dữ liệu
không được kết hợp. Bảng kếp hợp là là bảng chứa thông tin liên quan đến phần dữ
liệu được kết hợp.


Nghiên cứu công cụ Data Mining trong SQL Server 2000

Trang 26

Phụ lục C: Chương trình demo
- Chương trình demo có thể download tại:
/>Chương trình này có kích thước là 32 MB, được xuất bản tháng 9-2002.
- Đóa mềm đính kèm lưu file word của báo cáo này.