Đề tài Nghiên cứu kỹ thuật khai phá dữ liệu và ứng dụng trong hệ thống bán sách trực tuyến

1 bít ‘Outlook’ = ‘Overcast’: Info ([4,0]) = entropy (1, 0) = – 1log2(1) – 0log2(0) = 0 bít Do không có log2(0) nên ta quy ước nó bằng 0 ‘Outlook’ = ‘Rainy’: Info ([3,2]) = entropy (3/5, 2/5) = – 3/5log2(3/5) – 2/5log2(2/5) = 0.971 bít Entropy cho phép phân tách trên thuộc tính « Outlook« : Info ([3,2], [4, 0], [2, 3] ) = (5/14) * 0.971 + (4/14) * 0 + (5/14) * 0.971 = 0.693 bít. Lượng thông tin tăng thêm tại một nút được xác định bằng biểu thức : (Thông tin trước khi phân tách) – ( Thông tin sau khi phân tách) Lượng thông tin tăng thêm cho các thuộc tính trong cơ sở dữ liệu thời tiết ở trên : Rõ ràng ban đầu ta sẽ chọn thuộc tính ‘Outlook’  để phân tách. Sau đó làm tương tự ta sẽ được cây quyết định cuối cùng có dạng : Hình 20: Cây quyết định cuối cùng Phương pháp phân tách dựa trên entropy có thể gặp vấn đề khi kết hợp với phương pháp phân tách dựa trên biến đầu vào định tính bằng cách tạo một nhánh riêng rẽ cho mỗi giá trị. Vấn đề ở đây là, việc chia một tập dữ liệu thành quá nhiều các tập con dẫn đến số lượng các lớp tại mỗi nút giảm và do đó entropy cũng giảm theo Cơ sở dữ liệu với trường ID : Bảng 6 : Dữ liệu thời tiết với trường ID ID Code Outlook Temperature Humidity Windy Play? A sunny hot high false No B sunny hot high true No C overcast hot high false Yes D rain mild high false Yes E rain cool normal false Yes F rain cool normal true No G overcast cool normal true Yes H sunny mild high false No I sunny cool normal false Yes J rain mild normal false Yes K sunny mild normal true Yes L overcast mild high true Yes M overcast hot normal false Yes N rain mild high true No Lúc đó phép phân tách trên thuộc tính ID có dạng như hình vẽ ở dưới. Và Entropy của phép phân tách này = 0 (bởi vì mỗi nút lá đều tinh khiết, vì chỉ chứa một mẫu duy nhất) Hình 21: Kết quả phép phân tách trên thuộc tính ID Lúc này độ đo lượng thông tin tăng thêm không phù hợp nữa buộc người ta phải đưa ra một độ đo khác hợp lý hơn để thay thế đó là tỉ lệ tăng thêm thông tin. Tỉ lệ tăng thêm thông tin có giá trị lớn khi dữ liệu được trải đều nhau, có giá trị nhỏ khi dữ liệu thuộc về một nhánh. Thông tin bản chất (Intrinsic information) là entropy của sự phân phối của một trương hợp vào một nhánh: Tỉ lệ thông tin tăng thêm được tính theo biểu thức: Ví dụ: Thông tin bản chất cho trường ID code : Tỉ lệ thông tin thu được : Chọn lọc cây quyết định Chọn lọc là quá trính loại bỏ các nhánh và các lá để làm tăng khả năng thực thi dự báo của cây quyết định. Kết quả của quá trình chọn lọc là một tập cây con của cây quyết định đang phát triển. Điều này nghe có vẻ lạ lùng vì tập con của cây quyết định lại có khả năng dự báo hơn chính cây quyết định đang phát triển. Điều này có thể lý giải như sau, cây quyết định đang phát triển được luyện trên một tập dữ liệu xác định, tập dữ liệu này có thể chứa một số mẫu dị thường do những dữ liệu tạp nhiễu gây ra. Mặc dầu cây quyết định tìm các mẫu chung tại các nút lớn, nhưng nó lại tìm ra các mẫu xác định đối với tập luyện trong các nút nhỏ hơn. Điều dẫn đến tình trạng, tính tổng quan của kết quả tìm được sẽ bị cản trở vì dữ liệu mới không cư xử giống như tập luyện cho tất cả các biến, và điều này nên tránh bằng bất cứ giá nào. Phương pháp luận chọn lọc cây quyết định Chọn lọc có thể được tiếp cận hai phương pháp khác nhau : Chọn lọc trước : Cây quyết định có thể được chọn lọc trong pha xây dựng. Dừng việc phát triển một nhánh nếu thông tin trở nên không đáng tin cậy. Chọn lọc sau : Tiến hành phát triển cây quyết định một cách đầy đủ sau đó tiến hành loại bỏ đi các nhánh hoặc các nút lá không đáng tin cậy. Thực tế đã chứng minh, phương pháp chọ lọc sau có tính ưu việt hơn phương pháp chọn lọc trước, vì vậy sau đây, chúng ta sẽ trình bày hai thuật toán theo phương pháp chọn lọc sau : CART và C5. Thuật toán chọn lọc CART Cây phân loại và hồi quy – CART là một trong những thuật toán cây quyết định nổi tiếng đầu tiên được đưa ra vào năm 1984. Thuật toán CART phát triển cây nhị phân và tiếp tục phân tách cho đến khi vẫn tìm thấy phép phân tách làm tăng độ tinh khiết của tập kết quả. Trong hình dưới đây, ta vẫn thấy có rất nhiều cây con đơn giản hơn, mỗi cây con đó là miêu tả sự cân bằng giữa hai yếu tố: độ phức tạp của mô hình và tỉ lệ phân tách sai đối với tập luyện. Thuật toán CART xác định một tập các cây con đó như là mô hình dự tuyển. Những cây dự tuyển này được áp dụng đối với tập dữ liệu phê chuẩn và cây với tỉ lệ phân chia sai trên tập dữ liệu nhỏ nhất sẽ được chọn là mô hình cuối cùng. Hình 22: Ví dụ về tập cây con đơn giản trong một cây hoàn chỉnh Tạo các cây dự tuyển : Thuật toán nhận ra các cây con thông qua một tiến trình chọn lọc được lặp đi lặp lại. Mục tiêu là tiến hành loại bỏ những nhánh mà cung cấp sức mạnh dự báo ít nhất trên mỗi lá. Để xác định những nút lá này có độ hữu ích ít nhất, CART dựa vào một khái niệm gọi là tỷ lệ điều chỉnh lỗi ( adjusted error rate). Hệ số điều chỉnh lỗi dũng để xác định các nhánh « yếu«  (là những nhánh mà có tỉ lệ phân tách lỗi không đủ nhỏ) và đánh dấu chúng để tiến hành loại bỏ. Công thức xác định tỉ lệ điều chỉnh lỗi được xác định bằng : Tỉ lệ điều chỉnh lỗi (T) = Tỉ lệ lỗi (T) + α * Số lượng nút lá (T) Trong đó: α là hệ số điều chỉnh được tăng lên từng bước để tạo những cây con mới. Khi α = 0, tỉ lệ điều chỉnh lỗi bằng tỉ lệ lỗi. Để bắt đầu tìm cây con đầu tiên, tỉ lệ điều chỉnh lỗi cho tất cả các cây con có chứa nút gốc được đánh giá theo α được tăng theo từng bước. Khi tỉ lệ điều chỉnh lỗi của một cây con nhỏ hơn hoặc bằng tỉ lệ điều chỉnh lỗi của cây đầy đủ, ta tìm được cây dự tuyển đầu tiên α1. Tất cả các nhánh không thuộc α1 bị loại bỏ và tiến trình bắt đầu lại từ đầu. Cây α1 được chọn lọc để tạo thành cây α2 và tiến trình sẽ ngừng khi cây được chọn lọc cho kết quả chỉ chứa nút gốc. Mỗi cây con trong tập kết quả là một dự tuyển cho mô hình cuối cùng. Chú ý: tất cả các dự tuyển đều chứa nút gốc và cây dự tuyển lớn nhất là cây đầy đủ. Chọn cây con dự tuyển tốt nhất.  Nhiệm vụ tiếp theo là chọn ra trong tập các cây dự tuyển một cây con mà làm việc với dữ liệu mới một cách tốt nhất. Tập dữ liệu được dùng với mục đích này gọi là tập phê chuẩn (validation set). Mỗi cây con trong tập dự tuyển được sử dụng để phân loại các bản ghi trong tập phê chuẩn. Cây con nào thực hiện nhiệm vụ này với tỉ lệ lỗi thấp nhất là cây chiến thắng (được chọn). Cây chiến thắng được chọn lọc một cách thích đáng để loại bỏ những ảnh hưởng của việc luyện mô hình một cách quá mức nhưng vẫn giữ được những thông tin cần thiết. Sử dụng tập dữ liệu kiểm tra (test set) để đánh giá cây quyết định cuối cùng. Cây con chiến thắng được chọn dựa vào tỉ lệ lỗi của nó khi áp dụng vào việc phân loại các bản ghi trong tập phê chuẩn. Nhưng trong khi chúng ta hi vọng cây con được chọn sẽ tiếp tục là cây con có tốc độ thực thi tốt nhất khi áp dụng đối với tập dữ liệu khác, thì chính tỉ lệ lỗi mà khiến nó được chọn sẽ cường điệu hóa tính hiệu quả của chúng. Để kiểm tra thực thi của cây con được chọn, nó được áp dụng vào một tập dữ liệu thứ ba chưa được phân loại. Tập dữ liệu này không giao với cả tập dữ liệu luyện và tập dữ liệu phê chuẩn. Tập dữ liệu thứ ba này được gọi là tập kiểm tra. Tỉ lệ lỗi thu được trên tập kiểm tra dùng để dự đoán sự thực thi mong muốn của các luật phân loại áp dụng cho tập dữ liệu chưa được phân loại. Thuật toán chọn lọc C5 C5 là phiên bản gần đây nhất của thuật toán cây quyết định do nhà nghiên cứu người Úc J.Ross Quinlan đưa ra và cải tiến trong nhiều năm. Phiên bản sớm hơn – ID3 được đưa ra vào năm 1986 có ảnh hưởng rất lớn trong lĩnh vực học máy. Và các biến thể của nó đã được dùng rất nhiều trong một số sản phẩm mang tính thương mại về khai phá dữ liệu. Cây quyết định phát triển bởi C5 cũng như cây được phát triển bởi CART (mặc dù khác với CART, C5 đưa ra nhiều cách phân tách trên những biến định tính). Giống như Cart, đầu tiên C5 cũng một cây đầy đủ và sau đó tiến hành chọn lọc nó để tạo một mô hình tin cậy hơn. Tuy nhiên chiến lược chọn lọc của C5 và CART khác nhau. C5 không sử dụng tập dữ liệu phê chuẩn để chọn giữa các cây con một cây con tốt nhất ; tập dữ liệu giống hệt khi phát triển cây quyết định cũng được sử dụng để quyết định cây được chọn lọc như thế nào. Chọn lọc bi quan : C5 tiến hành chọn lọc cây quyết định bằng kiểm tra tỉ lệ lỗi tại mỗi nút và giả sử rằng tỉ lệ lỗi thật sự còn tồi tệ hơn. Nếu tại một nút có N bản ghi, trong đó có E bản ghi không được phân loại một cách chính xác, thì tỉ lệ lỗi lúc đó là E/N. Bây giờ toàn bộ các điểm trên cây quyết định phải tối thiểu hóa tỉ lệ lỗi này, vì vậy thuật toán giả sử rằng là tỉ lệ tốt nhất mà nó có thể thi hành. C5 sử dụng phép loại suy việc lấy mẫu thống kê để đạt tới việc đánh giá tỉ lệ lỗi tồi nhất có thể xảy ra tại một nút lá. Phép loại suy làm việc bằng cách suy nghĩ về dữ liệu tại nút lá như là việc miêu tả kết quả của một loạt các thử nghiệm, mỗi một thử nghiệm trong số chúng có hai kết quả có thể xảy ra. Khi nó xảy ra, các nhà thống kê phải nghiên cứu tình huống cụ thể này. Chọn lọc dựa vào sự ổn định. Thuật toán chọn lọc sử dụng bởi CART và C5 (và rất nhiều các sản phẩm thương mại về data mining) đều gặp phải một vấn đề. Chúng không loại bỏ được một vài nút mà hiển nhiên là thiếu ổn định. Cây quyết định khi được áp dụng vào tập luyện thì kết quả có vẻ rất khả quan, nhưng khi áp dụng nó với tập phê chuẩn thì kết quả có thể rất khác nhau. Một trong những mục đích chính của một mô hình là đưa ra được các dự báo nhất quán đối với tập dữ liệu mới so với tập luyện. Bất kì luật nào không đạt được mục đích này nên bị loại ra khỏi mô hình. Rất nhiều công cụ khai phá dữ liệu cho phép người dùng có thể chọn lọc cây quyết định một cách thủ công. Đây là một công cụ rất hữu ích, nhưng chúng ta mong đợi các phần mềm khai phá dữ liệu có thể cung cấp việc chọn lọc dựa vào độ ổn định một cách tự động như là một tùy chọn Chú ý: Các nút có kích thước nhỏ có thể gây ra vấn để lớn. Một trong những nguyên nhân gây ra mô hình cây quyết định không ổn định là việc cho phép tồn tại các nút có quá ít bản ghi. Hầu hết các công cụ về khai phá dữ liệu đều cho phép thiết lập kích thước tối đa của nút. Kinh nghiệm, nếu một nút có ít hơn 100 bản ghi có thể không ổn định. Thuật toán cây quyết định Microsoft Cây quyết định của Microsoft là thuật toán cây quyết định lai ghép được phát triển bởi nhóm nghiên cứu của Microsoft. Nó hỗ trợ cả hai nhiệm vụ phân loại và hồi quy. Một trong những tính chất khác biệt trong cây quyết định Microsfot là nó có thể áp dụng cho việc phân tích các luật kết hợp. Có hai lý do để đặt tên của toán cây quyết định này là thuật toán cây quyết định Microsoft. Thứ nhất, dựa vào các thiết lập các tham số, cây kết quả có thể rất khác nhau về mặt phân tách các nút và hình dạng của cây. Thứ hai, một mô hình cây có thể chứa rất nhiều cây, có lúc tới hàng trăm cây. Những cây này có thể được liên kết với nhau một cách trực quan thông qua mạng phục thuộc (dependency network) để phân tích sau này. Làm việc với các biến có nhiều trạng thái: Đối với các cây phân loại, số lượng hợp lý các trạng thái của biến đầu vào nên nhỏ hơn 100. Tuy nhiên trong tập dữ liệu thực, không phải mọi trường hợp đều diễn ra đúng như thế, một số thuộc tính có thể có hàng nghìn trạng thái. Một số thuật toán bỏ qua những thuộc tính như thế này, tuy nhiên những thuộc tính này có thể chứa các thông tin hữu ích. Có một số kỹ thuật để giải quyết vấn đề này, ví dụ, nhóm các trạng thái giống nhau lại để làm giảm tống số trạng thái. Phương pháp nhóm này rất chính xác, nhung lại bị hạn chế vì tốn nhiều thời gian bởi vì thuật toán sẽ phải thực hiện thao tác này tại mọi nút. Cây quyết định Microsoft xử lý vấn đề này bằng phương pháp nhóm động. Tại mỗi lần phân tách, thuật toán chỉ quan tâm đến 100 trạng thái, 99 trạng thái phổ biến nhất cộng với một trạng thái miêu tả các trường hợp còn lại. Qua mỗi lần phân tách, các trạng thái phổ biến có thể khác nhau qua các tập con. Dĩ nhiên, ta phải giả sử dựa trên kinh nghiệm rằng các trạng thái phổ biến có ảnh hưởng lớn đến dự báo hơn là các trạng thái ít phổ biến. Chú ý: đối với các thuộc tính dự báo riêng rẽ, số trạng thái nên nhỏ hơn 10. Nếu có quá nhiều trạng thái trong thuộc tính dự báo, ta nên nhóm chúng lại vơi nhau để giảm số trạng thái của thuộc tính dự báo. Tránh việc luyện quá mức Có rất nhiều cách giải quyết các vấn đề đưa ra bởi việc luyện quá mức một cây quyết định. Một số thuật toán chứa hai bước xử lý: phát triển và chọn lọc đã được trình bày ở phần trước. Thuật toán cây quyết định Microsoft không đưa ra bước chọn lọc. Cây được phát triển được điều khiển bởi hai cách: bằng cách sử dụng điểm số Bayesian để có thể tránh phép phân tách khi không đủ dữ liệu để căn chỉnh cho phép phân tách, và một tham số có tên là complexity_Penalty với miền giá trị từ 0 đến 1. Nếu giá trị này được thiết lập cao, càng nhiều ràng buộc được áp dụng trong khi phát triển cây, do đó kích cỡ của cây sẽ nhở hơn. Thuật toán cây quyết định Microsoft còn thêm vào độ ưu tiên (số lượng) tại mỗi nút cho mỗi trạng thái của thuộc tính dự báo. Sử dụng các thuộc tính đầu vào có kiểu giá trị liên tiếp: Thuật toán cây quyết định Microsoft xử lý với các thuộc tính dạng số theo một cách riêng. Đầu tiên nó chia các đầu vào liên tiếp vào n giỏ dựa vào miền giá trị; n là một tham số của hệ thống với giá trị mặc định là 99. Sau đó thuật toán tiến hành tiến trình hợp nhất các giỏ hàng láng giềng dựa vào cùng một độ đo mà ta đã sử dụng đối với các thuộc tính rời rạc như là entropy. Nếu việc hợp nhất hai giỏ lại có thể làm tăng điểm cho phép phân tách thì tiến hành hợp nhất hai giỏ đó lại với nhau. Tiến trình này được tiến hành một cách đệ quy. Cuối cùng ta có được tập các giỏ với điểm của phép phân tách được tối ưu. Điểm số này sau đó được so sánh với các thuộc tính rời rạc hay liên tục khác, và thuộc tính với điểm số cao nhất sẽ được chọn để phân loại. Hồi quy cũng tương tự như nhiệm vụ phân loại, chỉ khác nhau ở chỗ, hồi quy dự báo trên các thuộc tính liên tục. Thuật toán cây quyêt định Micrososft bổ sung chức năng hồi quy trong phiên bản SQL Sever 2005. Phân tích các mối kết hợp với thuật toán cây quyết định Microsoft. Một trong những riêng biệt của thuật toán cây quyết định Microsoft là nó có thể để phân tích các mối kết hợp. Một mô hình khai phá có thể chứa một rừng các cây. Nếu một mô hình chứa một bảng lồng và bảng lồng đó có thể dự báo và tất cả các khóa lồng đều là các thuộc tính có thể dự báo. Thuật toán cây quyết định Microsoft xây dựng cây quyết định cho mỗi khóa, chính xác hơn cho mỗi khóa lồng mà đó là tình chất được chọn lựa. Hình 23: Minh họa về việc sử dụng luật kết hợp trong cây quyết định Sử dụng thuật toán cây quyết định Microsoft cho việc phân tích các mối kết hợp rất thú vị. Các mục chọn được hiể thị theo dạng cây hay dạng mạng phục thuộc. Tuy nhiên cũng có một vài giới hạn đối với công viêc tìm các kết hợp. Bởi vì nó xây dựng cây quyết định cho mỗi mục chọn, do đó sẽ gây tốn phì thời gian và tài nguyên khi số lượng mục chọn là lớn. Các tham số của thuật toán: Complexity_Penalty: được sử dụng để điều khiển sự phát triển của cây quyết định. Nó là một số thực trong khoảng [0, 1]. Minimum_Support: xác định kích thước tối thiểu của mỗi nút lá trên cây. Score_Method: xác định phương pháp đo một phép phân tách cây quyết định trong suốt quá trình phát triển cây. Split_Method: xác định hình dạng của cây quyết định. Maximum_Input_Atribute: là một tham số ngưỡng để chọn đặc trưng. Khi số lượng các thuộc tính dự báo lớn hơn tham số này, việc chọn các đặc trưng được gọi một cách ngầm định để chọn những thuộc tính đầu vào quan trọng nhất. Maximum_Output_Atribute: là một tham số ngưỡng để chọn đặc trưng. Khi số lượng các thuộc tính đầu vào lớn hơn tham số này, việc chọn các đặc trưng được gọi một cách ngầm định để chọn những thuộc tính quan trọng nhất Thuật toán Microsoft Time Series Giới thiệu Một dãy thời gian bao gồm một chuỗi các dữ liệu được thu thập một cách liên tiếp theo trục tăng của thời gian hay theo một trật tự nào đó. Thế giới của chúng ta luôn vận động và biến đổi, rất nhiều các biến thay đổi giá trị của nó theo thời gian. Một dãy có trật tự các giá trị của một biến biến theo thời gian thiết lập một dãy thời gian. Ví dụ, giá cả trong kho của một mặt hàng trong kho hàng của Microsoft là một dãy thời gian. Hình 24: Lịch sử giá của một sản phẩm của Microsoft Nói chung, sự tăng về mặt thời gian trong một dãy thời gian có thể là là rời rạc hoặc liên tục. Chúng ta chỉ quan tâm đến các loại dãy thời gian mà sự tăng về mặt thời gian là rời rạc. Hơn nữa, giá trị theo dõi trong một dãy thời gian có thể là rời rạc hoạc liên tục. Trong hầu hết các tài liệu, người ta sử dụng dãy thời gian để đề cập đến các trường hợp mà các kết quả quan sát là liên tục và sử dụng thuật ngữ chuỗi (sequence) để đề cập đến các trường hợp mà các kết quả quan sát là rời rạc. Mục đích chính của việc thu thập dữ liệu theo thời gian là để dự báo trước, hoặc đưa ra các dự đoán về các giá trị trong tương lai. Ví dụ: trong ngành sản xuất chế tạo, một nhà máy càn dự báo được nhu cầu của khách hàng trong tháng tới để chuẩn bị kế hoạch sản xuất. Giới thiệu về các nguyên lý của thuật toán Microsoft Time Series Thuật toán Microsft Time Series là một thuật toán dự báo mới. Nó là sự lai ghép của kỹ thuật hồi quy tự động và cây quyết định. Chúng ta đặt tên thuật toán này là AutoRegression Tree – ART. Hồi quy tự động Hồi quy tự động là một kỹ thuật trong việc xử lý dãy thời gian. Một quá trình hồi quy tự động là một quá trình mà các giá trị x và thời gian (xt) là một hàm của các giá trị của x tại thời gian trước. Ví dụ: Xt = f (Xt-1, Xt-2, Xt-3, …, Xt-n ) + εt Trong đó xt là một dãy thời gian và n là thứ tự của hồi quy tự động, n thường nhỏ hơn độ dài dãy thời gian. Thành phần cuối cùng ε miêu tả độ nhiễu (noise). Một trong những bước chính của ART là biến đổi các trường hợp đơn (single case) thành các trường hợp đa (multiple case) ở trong nó. Tiến trình này được giải thích như sau : Hình 25: Chuyển đổi các trường hợp đơn (single case) Trong đó, Milk t(0) và Bread (t0) là các cột có thể dự báo, mỗi bản ghi trong bảng phía phải miêu tả một trường hợp. Bởi vì cây quyết định Microsoft hỗ trợ hồi quy do đó ta có thể sử dụng kỹ thuật này để dự đoán các giá trị của , Milk t(0) và Bread (t0). Trong Microsoft Time Series, mặc định, việc biến đổi các trường hợp đơn thành các trường hợp đa dùng 8 giá trị của biến đó theo thời gian về trước để biểu diễn giá trị xt. Một trong những ưu điểm quan trọng của việc biến đổi các trường hợp là tất cả các dãy thời gian trong cùng một mô hình khai phá được biến đổi thành các cột trong cùng một bảng. Trong khi sử dụng kỹ thuật cây quyết định để dự đoán về Milk (t0) và Bread (t0), tất cả các cột khác đều được coi là các cột đầu vào. Nếu có sự liên quan giữa doanh số bán hàng của Bread và Milk, mối quan hệ này sẽ được biểu hiện trong hàm f. Mục đích của các thuật toán dãy thời gian là để tìm ra hàm f. Nếu f là một hàm tuyến tính thì ta có. Xt = a1Xt-1 + a2Xt-2 + a3Xt-3 + ….. + anXt-n + εt Trong đó, ai là các hệ số hồi quy tự động. Mô hình này, được biết đến như là thuật toán hồi quy tự động đơn giản, hay ART được đưa ra và giải quyết đầu tiên bởi Yule năm 1927. Có một số cách để giải quyết đối với các hệ số hồi quy tự động. Phương pháp phổ biến nhất là lấp đầy các hệ số hồi quy tự động bằng việc tối thiểu sự khác nhau bình phương giá trị trung bình giữa các dãy thời gian được mô hình hóa Xnmodel và các dãy thời gian quan sát được Xn. Kết quả của quá trình tối thiểu là một hệ các phương trình tuyến tính cho hệ số an, được biết tới như là các phương trình Yule – Walker. Hệ phương trình này dùng để tính toán ra hệ số hồi quy tự động: Hình 26: Ma trận các biến tương quan (covariance matrix) Sử dụng đau dãy thời gian Trong thuật ngữ của DMX (DataMining eXtensions) – một ngôn ngữ truy vấn khai phá dữ liệu – một dãy thời gian là một trường hợp đơn. Doanh số bán hàng của Pepsi hàng tuần trong một năm thiết lập một trường hợp đơn của dãy thời gian. Một mô hình có thể chứa nhiều dãy thời gian. Ví dụ một mô hình có thể chứa toàn bộ các dãy thời gian của các sản phẩm đồ uống như là Pepsi, bia, nước hoa quả, sữa …. Các dãy (series) không phải luôn luôn độc lập. Doanh số bán Pepsi và nước hoa quả có thể có sự liên quan mật thiết đến nhau. Microsoft Time Series nhận ra sự tương quan chéo giữa các dãy khi chúng tồn tại. Đây là một trong những thuộc tính độc nhất của thuật toán này. Cây hồi quy tự động (AutoRegresson Tree) Thuật toán Microsoft Time Series là một mô hình hồi quy tự động mà hàm f tương ứng với cây hồi quy. Thuật toán này được đặt tên là cây hồi quy tự động (AutoRegression Tree - ART). ART được phát triển bởi ba nhà nghiên cứu thuộc trung tâm nghiên cứu của Microsoft là: Chriss Meek, David Maxwell Chickering và David Heckerman vào năm 2001. Trong ART, hàm f được miêu tả bởi một cây quyết định. Ví dụ : Hình 27: Cây hồi quy với dữ liệu dãy thời gian Tính chu kỳ Hầu hết các dãy thời gian  có các mẫu có tính chu kỳ. Ví dụ: doanh số bán hàng thường đạt doanh số cao nhất trong tháng 12 hay vào quý cuối của năm. Có nhiều kỹ thuật để xử lý tính chu kỳ. Hầu hết các thuật toán « time series «  phân tích dãy dữ liệu và đối xử với tính chu kỳ một cách độc lập. ART xử lý vấn đề này bằng một cách dễ hiểu: trong quá trình chuyển đổi các trường hợp, ART thêm vào các điểm dữ liệu lịch sử dựa vào tham số chu kỳ Periodicity_Hint. Ví dụ: đối với dữ liệu bán hàng theo tháng ở trên, chu kỳ là 12 (do có 12 tháng). ART bao gồm các kết quả đối với Milk (t-12), Milk (t-24), …, Milk (t-8*12), Bread (t-12), Bread (t-24), …, Bread (t-8*12) trong bảng. Một dãy có thể rất nhiều các gợi ý chu kỳ. Khi có nhiều chu kỳ, ART thêm vào một số cột mới trong bảng biến đổi các trường hợp dựa vào tính chu kỳ. Chú ý rằng tham số Periodicity_Hint chỉ là một gợi ý. Nếu nó được cung cấp, và nó đưa ra rằng không có tác động nào tới tính chu kỳ một cách có hiệu quả trong chu kỳ đó, thì thuật toán sẽ hủy bỏ sự phụ thuộc. Nếu nó không được cung cấp, thuật toán Microsoft Time Series có thể tự động kiểm tra tính chu kỳ dựa vào biến đổi Fourier nhanh (FFT) – là một phương pháp có hiệu quả và nổi tiếng để phân tích tần số xuất hiện. Chú ý: sau khi các trường hợp được biến đổi và các dữ liệu điểm có tính chu kỳ được thu thập, phần cốt lõi của ART xử lý giống như cây hồi quy. Các tham số của thuật toán Minimum_Support: được sử dụng để xác định số lượng các trường hợp nhỏ nhất của mỗi nút lá. Complexity_Penalty: được sử dụng để điều khiển sự lớn lên của cây. Nó giá trị trong khoảng từ 0 đến 1. giá trị này càng nhỏ, cây thu được càng lớn. Historical_Model_Count: được sử dụng số lượng các mô hình lịch sử được xây dựng. Historical_Model_Gap: được sử dụng để xác định khoảng thời gian giữa các mô hình lịch sử. Periodicity_Hint: cung cấp gợi ý cho thuật toán về thông tin chu kỳ của dữ liệu. Auto_Detect_Periodicity: nó là một số thực trong khoảng [0, 1] để xác định chu kỳ. Maximum_Series_Value: xác định giới hạn trên của các giá trị được dự báo. Minimum_Series_Value: xác định giới hạn dưới của các giá trị được dự báo. Missing_Value_Substitution: xác định phương thức để lấp đầy các giá trị còn thiếu trong tập dữ liệu lịch sử. Ví dụ về dự báo trong cây hồi quy tự động được xây dựng bằng thuật toán dãy thời gian của Microsoft Hình 28: Ví dụ về dự báo (phần nét đứt thể hiện sự dự báo) ÁP DỤNG MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU VÀO HỆ THỐNG BÁN SÁCH TRỰC TUYẾN Giới thiệu bài toán Mục tiêu Hiện nay, đã có rất nhiều các website bán sách trực tuyến, có thể kể ra như ... Hệ thống mà khóa luận dự định xây dựng là một website bán sách trực tuyến như vậy. Trong mục tiêu muốn giới thiệu việc triển khai, áp dụng kỹ thuật khai phá dữ liệu vào xây dựng các ứng dụng cụ thể, khóa luận xin được tập trung vào một số chức năng tiêu biểu thuộc 3 nhóm bài toán khá điển hình của khai phá dữ liệu đã trình bày ở trên: Chức năng phân loại khách hàng (thuộc nhóm bài toán phân loại). Chức năng gợi ý sách đi kèm (thuộc nhóm bài toán phân tích luật kết hợp). Chức năng lập các báo dự đoán doanh thu của hệ thống trong tương lai và lập báo báo dự đoán số lượng đầu sách sẽ tiêu thụ trong tương lai (thuộc nhóm bài toán dự đoán). Yêu cầu Hệ thống phải phải đáp ứng các yêu cầu sau: Cung cấp các chức năng quản trị chủ đề, đầu sách, khách hàng, đơn hàng (cập nhật, sửa, xóa). Cung cấp chức năng đăng ký cho khách hàng. Dự đoán, phân loại khách hàng ngay từ khi khách hàng đăng ký xong, xem khách hàng này thuộc loại “Thường xuyên” / “Vãng lai”. Sau đây là một nghiệp vụ đơn giản về cách phân loại khách hàng, trong phạm vi đề tài này, khóa luận xin phép không bàn luận nhiều đến tính đúng đắn của nghiệp vụ kinh doanh và bán hàng: Khách hàng “Thường xuyên” là những khách hàng mua sách trung bình lớn hơn hoặc bằng 1 lần / tháng, thời gian được tính từ lúc khách hàng đăng ký là thành viên của hệ thống cho đến thời điểm hiện tại. Trường hợp còn lại được xem là loại khách hàng “Vãng lai”. Khách hàng có thể xem, tìm kiếm, đặt mua sách từ hệ thống. Gợi ý sách kèm theo mỗi khi khách hàng chọn xem chi tiết một cuốn sách. Cung cấp chức năng lập báo cáo dự đoán doanh thu của hệ thống và báo báo dự đoán số lượng đầu sách tiêu thụ trong tương lai. Bảo mật, phân quyền hệ thống ở mức độ đơn giản. Lựa chọn giải pháp Hệ thống được viết trên nền Web sử dụng công cụ VS.NET 2005 và hệ quản trị CSDL là MSSQL Server 2005. MSSQL Server 2005 là một hệ quản trị CSDL rất tốt, rất dễ dàng cho những người phát triển CSDL xây dựng, quản lý và áp dụng kỹ thuật khai phá dữ liệu, và công cụ VS.NET 2005 là một công cụ tiên tiến phát triển ứng dụng web dễ dàng và hiệu quả. Như vậy, môi trường phát triển hệ thống như sau: Máy chủ ứng dụng: WebServer: IIS 6.0 .NET Framework 2.0 Máy chủ CSDL: MSSQL Server 2005 Với công cụ MSSQL Server 2005, khóa luận lựa chọn các thuật toán để xây dựng 3 mô hình khai phá dữ liệu tương ứng với 3 chức năng trên như sau: Chức năng dự đoán, phân loại khách hàng: sử dụng thuật toán cây quyết định của Microsoft. Chức năng gợi ý sách kèm theo: sử dụng thuật toán luật kết hợp của Microsoft. Chức năng lập báo cáo dự đoán thu nhập của hệ thống và báo báo dự đoán số lượng đầu sách tiêu thụ trong tương lai: sử dụng thuật toán chuỗi thời gian của Microsoft. Tóm tắt phân tích và thiết kế Bài toán này được khóa luận cân nhắc và lựa chọn theo cách tiếp cận là hướng cấu trúc. Thông thường, việc phân tích và thiết kế hệ thống của một ứng dụng như này phải trải qua rất nhiều bước. Bao gồm: Xác định mô hình tiến trình nghiệp vụ. Dựa vào các thông tin về các nghiệp vụ của hệ thống để phân tích và xây dựng sơ đồ phân rã chức năng chi tiết từ đó xác định các chức năng cơ sở. Mô hình hóa dữ liệu. Vẽ sơ đồ luồng dữ liệu. Đưa ra ma trận thực thể chức năng. Thiết kế mô hình dữ liệu logic. Chọn hệ quản trị cơ sở dữ liệu. Tạo CSDL vật lý. Tuy nhiên, do tiêu điểm chính của khóa luận này là tập trung vào việc giới thiệu về kỹ thuật khai phá dữ liệu và cách áp dụng, triển khai kỹ thuật khai phá dữ liệu vào một ứng dụng cụ thể, do thời gian và phạm vi của một đề tài tốt nghiệp nên khóa luận không thể đi sâu vào trình bày nhiều thông tin và cụ thể như mong muốn. Thay vào đó, khóa luận xin được phép trình bày luôn mô hình quan hệ thực thể và CSDL vật lý (qua hệ quản trị CSDL MSSQL Server 2005). Hơn thế nữa, khóa luận chỉ xin trình bày những thông tin nhỏ gọn, phù hợp với mục tiêu của đề tài, những thông tin liên quan đến các chức năng khai phá dữ liệu để qua đó, muốn giới thiệu với bạn đọc một số thao tác thủ công, triển khai khai phá dữ liệu qua công cụ MSSQL Server 2005. Mô hình quan hệ thực thể Hình 29: Mô hình quan hệ thực thể đã được lược bỏ và tóm gọn Thiết kế CSDL vật lý với MSSQL Server 2005 Sơ đồ dữ liệu quan hệ Hình 30: Thiết kế CSDL vật lý với Hệ quản trị CSDL MSSQL Server 2005 Thiết kế chi tiết các bảng Bảng ChuDe Hình 31: Thiết kế chi tiết bảng ChuDe Bảng Sach Hình 32: Thiết kế chi tiết bảng Sach Bảng KhachHang Hình 33: Thiết kế chi tiết bảng KhachHang Bảng DonHang Hình 34: Thiết kế chi tiết bảng DonHang Bảng DonHangChiTiet Hình 35: Thiết kế chi tiết bảng DonHangChiTiet Kiến trúc hệ thống Hệ thống được xây dựng theo mô hình 3 lớp: Hình 36: Thiết kế kiến trúc hệ thống Presentation: tầng trình diễn Application Server: máy chủ ứng dụng Database Server: máy chủ CSDL Một cách nhìn khác về kiến trúc hệ thống: Hình 37: Cách nhìn khác về kiến trúc hệ thống Giới thiệu một số kỹ thuật và công nghệ Một số khái niệm cơ bản về mô hình khai phá dữ liệu Mô hình khai phá dữ liệu hay mô hình khai phá có thể được xem như là một bảng quan hệ (bảng thông thường trong CSDL quan hệ). Nó bao gồm các cột khóa chính, các cột dữ liệu vào và các cột dữ liệu có thể dự đoán. Mỗi mô hình được gắn kết với một thuật toán khai phá dữ liệu mà mô hình này được luyện qua. Việc luyện một mô hình có nghĩa là tìm ra những mẫu trong tập luyện bởi việc sử dụng một vài thuật toán khai phá nào đó với các tham số đầu vào thích đáng của các thuật toán. Sau khi được luyện, mô hình khai phá dữ liệu sẽ lưu trữ các mẫu mà thuật toán khai phá dữ liệu vừa khám phá ra về tập luyện. Trong khi các bảng quan hệ là một kho chứa các bản ghi thì một mô hình khai phá dữ liệu sẽ chứa các mẫu. Sau đây là 3 bước cơ bản cho khai phá dữ liệu: Hình 38: 3 bước cơ bản cho khai phá dữ liệu. Tạo mô hình: việc tạo mô hình có thể hiểu đơn giản là tạo một mô hình rỗng, tương tự như cách ta tạo một bảng mới trong CSDL quan hệ. Luyện mô hình: việc luyện mô hình còn có thể gọi là xử lý mô hình. Nó sẽ thực thi các thuật toán khai phá dữ liệu để khám phá ra các tri thức từ tập luyện đưa vào. Sau khi luyện, các mẫu sẽ được lưu trữ trong mô hình khai phá. Mô hình dự đoán: mô hình dự đoán được sử dụng cho việc áp dụng các mẫu trong mô hình khai phá với tập dữ liệu mới được đưa vào, dự đoán giá trị cho các cột có thể dự đoán cho mỗi bản ghi dữ liệu mới đưa vào. DMX Như ở mục trên đã trình bày 3 thao tác cơ bản với mô hình khai phá, chúng ta có thể sử dụng DMX truy vấn tới hệ quản trị CSDL MSSQL Server 2005 này để có thể làm tự động hóa quá trình xây dựng mô hình, luyện và dự đoán, truy vấn ra các thông tin tri thức, hiển thị kết quả trên giao diện người dùng. DMX - Data Mining eXtensions là một ngôn ngữ truy vấn khai phá dữ liệu được định nghĩa trong OLE DB dành cho khai phá dữ liệu, được kế thừa hầu hết các khái niệm quan hệ và cấu trúc của nó dựa trên ngôn ngữ truy vấn SQL. Với vai trò là người phát triển CSDL, thật dễ dàng để học ngôn ngữ này. Ví dụ: Đoạn mã DMX để tạo mô hình khai phá dữ liệu dùng để dự đoán kiểu của thẻ thành viên của một khách hàng, sử dụng thuật toán cây quyết định của Microsoft: Create mining model MemberCard_Prediction ( CustomerId long key, Gender text discrete, Income long continuous, MemberCard text discrete predict, Purchase table ( ProductName text key, Quantitylong continuous ) ) Using Microsoft_Decision_Trees Đoạn mã DMX để luyện mô hình: Insert into MemberCard_Prediction ( CustomerId, Gender, Age, Profession, Income, HouseOwner, MemberCard) OpenRowset(‘sqloledb’, ‘myserver’;’mylogin’;’mypwd’, ‘Select CustomerId, gender, age, profession, income, houseowner, membercard From customers’) Đoạn mã DMX để dự đoán: Select T.CustomerID, T.LastName, M.MemberCard From MemberCard_Prediction Prediction Join OpenRowset(‘Provider=Microsoft.Jet.OLEDB’, ‘data source=c:\customer.mdb’, ‘select * from customers’) as T On MemberCard_Prediction.Gender= T.Gender And MemberCard_Prediction.Age = T.Age And MemberCard_Prediction.Profession = T.Profession And MemberCard_Prediction.Incom = T.Income And MemberCard_Prediction.HouseOwner=T.HouseOwner Where NewCustomer.age > 30 Hình 39:Dự đoán bằng truy vấn kết nối giữa một mô hình khai phá với một bảng. Để có thêm nhiều thông tin hơn về DMX, bạn có thể xem thêm ở một số tài liệu tham khảo của khóa luận. Lập trình khai phá dữ liệu MSSQL Server 2005 với .NET 2.0 ADOMD.NET (ADO.NET – Multidimensional) là một thư viện API dành cho .NET lập trình với dịch vụ phân tích, làm cho việc xây dựng các ứng dụng khai phá dữ liệu ở máy khách trở nên dễ dàng. Hình 40: Sơ đồ phân cấp các đối tượng khai phá dữ liệu trong ADOMD.NET Ví dụ một đoạn mã viết bằng C#.NET và nhúng trong trang ASP.NET để kết nối đến dịch vụ phân tích của hệ quản trị CSDL qua ADOMD.NET: using System; using Microsoft.AnalysisServices.AdomdClient; using System.Data; AdomdConnection con; static bool CreateADOMDConnection() { con = new AdomdConnection(“Data Source=ASServer; Catalog=MovieAssociation; Integrated Security=SSPI”); try { con.Open(); } catch (System.Exception e) { Log(e.Message); return false; } return true; } public bool ExecuteAndFetchSQL(string strCommand) { AdomdCommand cmd = (AdomdCommand) con.CreateCommand(); cmd.Text = strCommand; IDataReader dr = null; try { dr = cmd.ExecuteReader(); } catch(Exception e) { Log(e.Message); return false; } ... //display the result in the listbox while(dr.Read()) { string val = dr.GetString(0); SuggestedList.Items.Add(val); } ... return true; } Xây dựng mô hình khai phá dữ liệu trực quan với MSSQL Server 2005 Sau đây, khóa luận xin trình bày cách xây dựng các mô hình một cách trực quan dựa trên CSDL của bài toán, sử dụng MSSQL Server 2005, với mong muốn mang đến cho bạn đọc một cách nhìn dễ hình dung hơn về kỹ thuật triển khai, áp dụng khai phá dữ liệu cho một bài toán. Đó là: Mô hình khai phá dữ liệu với thuật toán luật kết hợp của Microsoft: phục vụ cho chức năng gợi ý sách mua kèm theo. Mô hình khai phá dữ liệu với thuật toán cây quyết định của Microsoft: phục vụ cho chức năng phân loại khách hàng. Mô hình dự báo về doanh thu và mô hình dự báo về số lượng sách sẽ được bán với thuật toán chuỗi thời gian của Microsoft: phục vụ cho chức năng lập các báo cáo dự đoán. Do các bước xây dựng các mô hình khai phá dựa trên các thuật toán cây quyết định, luật kết hợp, dãy thời gian của Microsoft tương tự nhau, nên khóa luận chỉ trình bày cách xây dựng một mô hình chi tiết, còn các mô hình sau thì chỉ đưa ra kết quả. Xây dựng mô hình khai phá dữ liệu với thuật toán luật kết hợp của Microsoft Bước 1: Sau khi vào màn hình IDE của Microsoft Visual Studio 2005, tạo một Project mới. Chọn kiểu dự án là Business Intelligence Projects, sau đó trên cửa sổ Templates chọn Analysis Services Project, và điền các thông tin về Project ở dưới và nhấn OK. Hình 41: Màn hình NewProject Bước 2: Sau đó chọn Solution Explorer, nháy phải vào Data Sources và chọn New Data Source, sau đó màn hình Connection Manager hiện ra, nhập các thông tin cần thiết và nhấn OK. Hình 42: Màn hình Connection Manager Bước 3: Tiếp đó màn hình Impersonation Information hiện ra, chọn Default, và nhấn Next. Hình 43: Màn hình Impersonation Information Bước 4: Màn hình Completing the Winzard đưa ra các thông tin về Data Source trước khi tạo. Chọn Finish. Hình 44: Màn hình kết thúc tạo Data Source Bước 5: Trong Solution Explorer, nháy phải vào Data Source Views, chọn New Data Source View. Sau đó chọn Data Source và nhấn Next. Hình 45: Màn hình chọn Data Source Bước 6: Trong màn hình Select Tables and Views chọn các bảng hoặc các khung nhìn để tạo mô hình. Ta chọn hai bảng DonHang và DonHangChiTiet. Sau đó nhấn Next. Hình 46: Màn hình Select Tables and Views Bước 7: Sau đó màn hình Completing the Winzard hiện ra và ta chọn Finish để kết thúc quá trình tạo Data Source Views Bước 8: Sau khi tạo Data Source Views ta tiến hành xây dựng cấu trúc khai phá. Nháy phải vào Mining Structures và chọn New Mining Structures. Màn hình Select the Definition Method, nhấn Next. Hình 47: Màn hình Select the Definition Method Bước 9: Tại màn hình Select Data Mining Technique chọn thuật toán để xây dựng mô hình. Ta chọn Microsoft Association Rules, và nhấn Next. Hình 48: Màn hình Select Data Mining Technique Bước 10: Tại màn hình Select Data Source View, chọn Data Source View dùng để xây dựng mô hình, ta chọn Sieu Thi Sach Viet, và nhấn Next. Hình 49: Màn hình Select Data Source View Bước 11: Sau đó ta tiến hành chọn kiểu bảng để xây dưng mô hình tại màn hình Specify Table Types. Ta tích chọn Case tương ứng với bảng DonHang và tích chọn Nested tương ướng với bảng DonHangChiTiet, và nhấn Next. Hình 50: Màn hình Specify Table Types Bước 12: Tại màn hình Specify the Training Data ta tiến hành chọn các thuộc tính khóa, đầu vào và dự đoán của mô hình. Ta chọn MaDonHang là Key, Masach vừa là Nested Key, Input, Predict và nhấn Next. Hình 51: Màn hình Specify the Training Data Bước 13: Hai màn hình tiếp theo đưa ra các thông tin tổng kết về cấu trúc mô hình sắp được xây dựng. Ta chọn Next để kết thúc. Bước 14: Sau khi có mô hình phá ta tiến hành luyện mô hình. Nháy phải vào tên mô hình và chọn Process, và nhấn Next. Hình 52: Màn hình thực thi mô hình Bước 15: Sau đó màn hình thực thi mô hình sẽ hiện ra, ta chọn Run, màn hình kết quả luyện mô hình hiện ra và ta nhấn Close Hình 53: Màn hình Process Progress Bước 16: Kết quả thu được sau khi xây dựng mô hình bao gồm tập mục chọn thường xuyên, các luật. Sau đây là một số hình minh họa. Hình 54: Tập các mục chọn thường xuyên Hình 55: Các luật kết hợp Hình 56: Mạng phụ thuộc của luật kết hợp Kết quả xây dựng mô hình khai phá dữ liệu dựa vào thuật toán cây quyết định của Microsoft. Cây quyết định sau khi được xây dựng và được luyện: Hình 57: Cây quyết định Mô hình khai phá biểu diễn dưới dạng mạng phụ thuộc Hình 58: Mạng phụ thuộc của cây quyết định Kết quả xây dựng mô hình dự báo về doanh thu của Siêu Thị Sách Việt. Hình 59: Màn hình dự báo doanh thu Phần nét đứt thể hiện sự dự báo. Kết quả xây dựng mô hình dự báo về số lượng sách sẽ được bán của Siêu Thị Sách Việt Đồ thị dự báo cho một đầu sách Hình 60: Màn hình dự bao số lượng sách bán với một đầu sách Đồ thị dự báo cho nhiều đầu sách Hình 61: Màn hình dự bao số lượng sách bán với nhiều đầu sách CSDL thử nghiệm Khóa luận đã tiến hành thử nghiệm với số lượng bản ghi như sau: Bảng ChuDe: 25 bản ghi dữ liệu chủ đề. Bảng KhachHang: 100 bản ghi dữ liệu về khách hàng. Bảng Sach: 50 bản ghi sách. Bảng DonHang: 100 bản ghi đơn hàng. Bảng DonHangChiTiet: 1000 bản ghi các dòng hàng. Kết quả thử nghiệm Sau đây, khóa luận xin trình bày 3 kịch bản tương ứng với việc thực thi 3 chức năng có áp dụng khai phá dữ liệu như phần yêu cầu đã nêu: Kịch bản thực hiện chức năng gợi ý sách kèm theo Hình 62: Giao diện trang chủ Khi khách hàng truy cập vào trang web giao diện trang chủ trên sẽ hiện ra. Mặc định các sách hiển thị ở trang chủ là các sách mới. Danh mục sách ở bên trái cho phép khách hàng có thể xem sách theo các chủ đề. Danh mục phía bên phải cho phép khách hàng có thể xem các sách bán chạy nhất, các sách được khách hàng bình chọn cao nhất, các sách giảm giá, .... Ngoài ra, khách hàng có thể sử dụng chức năng tìm kiếm sách. Thông tin các quyến sách sẽ được liệt kê như trên. Hình 63: Giao diện thông tin chi tiết một cuốn sách Khi khách hàng chọn cuốn sách “Luật Doanh Nghiệp” hệ thống sẽ gợi ý những cuốn sách nên mua kèm theo. Trong trường hợp ví dụ này là các cuốn: “205 Câu hỏi – Đáp về luật doanh nghiệp”, “Doanh mục giấy phép kinh doanh, chứng chỉ hành nghề có hiệu lực theo luật doanh nghiệp”, “Các văn bản hướng dẫn thi hành luật doanh nghiệp”. Hình 64: Giao diện giỏ hàng Sau khi khách hàng chọn sách, hệ thống sẽ đưa vào trang giỏ hàng cho phép khách hàng thêm hay bớt các sách muốn mua vào đơn đặt hàng của mình. Kịch bản thực hiện chức năng dự đoán, phân loại khách hàng Hình 65: Giao diện đăng ký thành viên. Khách hàng muốn đặt mua sách tại Siêu Thị Sách Việt cần phải đăng ký thành viên. Sau khi điền các thông tin yêu cầu sẽ tiến hàng đăng ký với hệ thống. Ở đây, khách hàng Tạ Thanh Hùng đã tiến hành đăng ký. Sau khi đăng ký xong, hệ thống sẽ tự động dự đoán khách hàng này trong tương lai sẽ là khách hàng “Thường xuyên” hay chỉ là khách hàng “Vãng lai”, để có chiến lược tiếp tiếp thị, kinh doanh với những loại khách hàng này. Hình 66: Giao diện quản lý khách hàng. Kết quả, khi vào trang quản lý khách hàng, sẽ cho ta thấy ở đây, hệ thống dự đoán khách hàng Tạ Thanh Hùng trong tương lai sẽ là khách hàng “Thường xuyên” của hệ thống. Kịch bản thực hiện chức năng lập báo cáo dự đoán doanh thu của hệ thống và báo báo dự đoán số lượng đầu sách tiêu thụ trong tương lai Hình 67: Giao diện báo cáo dự đoán doanh thu của hệ thống trong 3 tháng tới. Phần quản trị hệ thống, sẽ có mục xem báo cáo, ở đây, người quản trị hệ thống chọn xem báo cáo dự đoán doanh thu của hệ thống trong 3 tháng tới dưới dạng đồ thị. Ở đồ thị trên, trục hoành của đồ thị thể hiện thời gian - với ứng với một đơn vị tỷ lệ là một tháng. Trục tung của đồ thị thể hiện doanh thu của Siêu Thị Sách Việt - ứng với một đơn vị tỷ lệ là 2000 đơn vị doanh thu. Phần nét liền thể hiện doanh thu của Siêu Thị trong quá khứ và hiện tại. Phần nét đứt thể hiện dự đoán về doanh thu của Siêu Thị trong các tháng tiếp theo. Hình 68: Giao diện báo cáo dự đoán số lượng đầu sách “Luật doanh nghiệp” sẽ bán được trong 3 tháng tới. Trên đây là diện báo cáo dự đoán số lượng một đầu sách sẽ bán được trong 3 tháng tới, ở đây ví dụ là đầu sách “Luật doanh nghiệp”. Ở đồ thị trên, trục hoành của đồ thị thể hiện thời gian - với ứng với một đơn vị tỷ lệ là một tháng. Trục tung của đồ thị thể hiện số lượng sách “Luật doanh nghiệp” bán được - ứng với một đơn vị tỷ lệ là 50 đơn vị số lượng. Phần nét liền thể hiện số lượng sách bán được trong quá khứ và hiện tại. Phần nét đứt thể hiện dự đoán về số lượng sách có thể bán được trong các tháng tiếp theo. Hình 69: Giao diện báo cáo dự đoán số phần trăm lượng sách của một số đầu sách sẽ bán được trong tương lai. Ở đồ thị trên, trục hoành của đồ thị thể hiện thời gian - với ứng với một đơn vị tỷ lệ là một tháng. Trục tung của đồ thị thể hiện phần trăm số lượng sách bán được - ứng với một đơn vị tỷ lệ là 50% đơn vị số lượng. Phần nét liền thể hiện phần trăm sách bán được trong quá khứ và hiện tại. Phần nét đứt thể hiện dự đoán về phần trăm sách có thể bán được trong các tháng tiếp theo. Nhận xét và đánh giá chung Do lượng dữ liệu chương trình nhỏ, tính thực tế chưa cao và khóa luận vẫn còn hạn chế về nghiệp vụ kinh doanh do đó chưa thể kiểm định được tốc độ và hiệu suất xử lý của hệ thống, cũng như độ chính xác về các kết quả hệ thống suy luận và dự đoán. Tuy nhiên, theo ý kiến chủ quan, kết quả mà chương trình đã đạt được mục tiêu của khóa luận, có thể được coi là chấp nhận được. Chương trình cần phải phát triển, cải tiến thêm nữa để có thể áp dụng, triển khai vào thực tế. KẾT LUẬN Qua thời gian thực hiện khoá luận này, chúng tôi đã nghiên cứu một số kỹ thuật khai phá dữ liệu theo hướng ứng dụng từ đó áp dụng vào triển khai hệ thống bán sách trực tuyến Mục tiêu đặt ra ở đầu khoá luận đã đạt được thành công, tuy còn ở mức đơn giản: Nắm được các ý tưởng chủ đạo về khai phá dữ liệu. Áp dụng kỹ thuật khai phá dữ liệu trong các chức năng: phân loại khách hàng, gợi ý sách mua kèm theo và lập các báo cáo dự đoán. Áp dụng các công nghệ mới trong việc cài đặt hệ thống, sử dụng ASP.NET tích hợp trong VS.NET 2005 và hệ quản trị cơ sở dữ liệu MSSQL Server 2005. Để hệ thống có thể đưa hệ thống vào vận hành thực sự trên thực tế cần có thêm thời gian và công sức nghiên cứu kiểm thử, hoàn thiện giải pháp và xây dựng phần mềm hoàn chỉnh. Hướng phát triển: Bổ sung và hoàn thiện các dịch vụ để khai thác hệ thống. Cần kiểm định với lượng dữ liệu chương trình lớn, thực tế và bổ xung, nâng cao nghiệp vụ kinh doanh để đạt được một hệ thống có hiệu suất xử lý tốt cũng như độ chính xác về các kết quả hệ thống suy luận và dự đoán. Trong phạm vi của một khoá luận tốt nghiệp, đề tài này không thể tránh khỏi những thiếu sót. Chúng tôi mong nhận được những ý kiến phê bình, đóng góp, sự chỉ bảo chân tình của các thầy cô và các bạn để có thể tiếp tục phát triển đề tài này trong thời gian tới. Một lần nữa chúng tôi xin chân thành cảm ơn công ty Công nghệ Tin học Tinh Vân đã tạo điều kiện cho chúng tôi phát triển đề tài. Cảm ơn các thầy cô giáo bộ môn Công Nghệ Phần Mềm và bộ môn Các Hệ Thống Thông Tin. Đặc biệt, chúng tôi xin gửi lời cảm ơn sâu sắc đến thầy Đỗ Trung Tuấn và thầy Đào Kiến Quốc, hai thầy đã định hướng và trực tiếp giúp đỡ chúng tôi hoàn thành khoá luận này. Chúng tôi xin chân thành cảm ơn! Hà Nội, tháng 6 năm 2006 TÀI LIỆU THAM KHẢO Tài liệu tiếng việt: [1] Đào Kiến Quốc, “Phân tích thiết kế hệ thống thông tin tin học hóa”, NXB Đại Học Quốc Gia Hà Nội, 1998. [2] Trần Mạnh Tuấn, “Xác suất thống kê” (Giáo trình). [3] Đỗ Trung Tuấn, “Cơ sở dữ liệu, Giáo trình dùng cho sinh viên, kỹ sư, cử nhân chuyên nghành công nghệ thông tin”, NXB Giáo dục, 1997. [4] Đỗ Trung Tuấn, Thầy Trần Thọ Châu , “Trí tuệ nhân tạo“ (Bài giảng). [5] Nguyễn Tuệ, “SQL cơ bản” (Giáo trình). [6] Nguyễn Tuệ, “SQL nâng cao” (Giáo trình). [7] Đinh Mạnh Tường, “Nhập môn Trí tuệ nhân tạo”, NXB Khoa học kỹ thuật, 2002 . [8] Nguyễn Văn Vỵ, “Giáo trình phân tích thiết kế hệ thống thông tin” , NXB Đại Học Quốc Gia TP. Hồ Chí Minh, 2004. [9] Nguyễn Văn Vỵ. “Phân tích và thiết kế hệ thống thông tin quản lý”, NXB Thống kê, 2004. Tài liệu tiếng Anh: [1] Nguyễn Hùng Sơn, “Giáo trình Dataming” (Slide). [2] ZhaoHui Tang and Jamie MacLennan, Data Mining with SQL Server 2005 Sep 2005. [3] Wiley.IEEE.Press.DANIEL T. LAROSE Data Mining Methods and Models Jan 2006. [4] (By Laxxus) Data Mining Cookbook - Modeling Data for Marketing, Risk, and Customer Relationship Management (OCR) – 2001. [5] Morgan Kaufmann Publishers - Business Modeling and Data Mining. [6] Kluwer Academic, High Performance Data Mining. [7] Micheal J.A.Berry, Gordon S.Linoff.Data mining technique, 2006. [8] ASP.NET and Webforms. Aftech Limited. [9] Namid R. Nemati and Christopher D. Barko (eds), Idea Group Publishing Organizational Data Mining. [10] John Wang, Idea, Data Mining - Opportunities and Challenges. [11] Ykie Go, Robert Grossman, High Performent data mining Scaling Algorithms, Applications and Systems. [12 ] LinG.MWL, Elsevier.Oracle.Database.10g.Data.Warehousing. [13] Larissa T. Moss, Shaku Atre, Business Intelligence Roadmap The Complete Project Lifecycle for Decision Support Applications. [14] Lipo Wang, Xiuju, Fu, Springer Data Mining with Computational Intelligence Sep 2005. [15]Data.Mining.Practical.Machine.Learning.Tools.and.Techniques.Second.Edition.Jun.2005, Morgan.Kaufmann. [16] Mark Last, Abraham Kendel &Horst Bunke, Wordware Publishing Advanced SQL Functions in Oracle 10g Jan 2006. [17] Reitman-Olson J., William B. I., Gruenenfelder T. A general user interface for creating and displaying tree-structures, hierarchies, decision trees, and nested menus, Human factors and interactive computer systems New York, 1984. [18] Vessey I., Weber R. Structured tools and conditional logic: an empirical investigation, Communications of the ACM 29(1), 1986. [19] Hewett R., Leuchner J. Restructuring decision tables for elucidation of knowledge. Data & Knowledge Engineering 46(3), 2003. PHỤ LỤC Giải thích một số thuật ngữ chuyên ngành Thuật ngữ Chú giải Ad targeting Bài toán lựa chọn ảnh quảng cáo nào sẽ xuất hiện đối với mỗi loại khách hàng Aggregation Tập hợp Analyze the state transitions Phân tích sự chuyển của các trạng thái API - Application Program Interface Giao diện lập trình ứng dụng ART - AutoRegression Tree Cây hồi quy tự động Association analisys rule algorithm Thuật toán phân tích luật kết hợp Candidate Dự tuyển Case  Trường hợp Churn analysis Phân tích xem loại khác hàng nào có khả năng cao nhất sẽ chuyển sang dùng sản phẩm dịch vụ của đối thủ cạnh tranh của công ty Classification Phân loại Clustering Phân cụm Conditional pattern-base Cơ sở mẫu có điểu kiện Confidence Độ tin cậy Credit card fraud detection kiểm tra phát hiện thẻ tín dụng giả mạo Customer Relationship Management (CRM) Hệ thống quản lý khách hang Data archaeology Khảo cổ dữ liệu Data Mining Khai phá dữ liệu Data dredging Nạo vét dữ liệu Data Flow Luồng dữ liệu Data warehouse Kho dữ liệu Data/Pattern analysis Phân tích dữ liệu/Mẫu Deccision trees algorthm Thuật toán cây quyết định Deviation Analysis Phân tích độ lệch Forecasting Dự đoán Frequent Itemset Tập các mục chọn thường xuyên Generalization Tổng quát hoá Grouping Nhóm Hash Tree Cây băm Importance Độ quan trọng Inexplicable Rules Các luật không thể giải thích Information Gain Lượng thông tin thu được Information gain ratio Tỉ lệ thông tin thu được Inrelevent data Dữ liệu không nhất quán Item Mục chọn Itemset Tập các mục chọn Knowlegde Discovery in Databases – KDD Khám phá tri thức trong cơ sở dữ liệu Knowlegde extraction Trích lọc dữ liệu Knowlegde mining from Databases Khai phá tri thức từ cơ sở dữ liệu Market basket analysis Phân tích giỏ hàng Microsoft Time Series algorythm Thuật toán Microsoft Time Series Missing value handling Dữ liệu bị thiếu Model Mô hình Naitive Bayes Thuật toán Naitive Bayes Neural networks algorithm Thuật toán mạng nơron Normalization Chuẩn hoá Online Analytical Processing – OLAP Tiến trình phân tích trực tuyến Online transaction processing (OLTP) database Cơ sở dữ liệu tiến trình giao dịch trực tuyến Optimized Tối ưu hóa original – data Dữ liệu nguyên thuỷ Outlier detection Phát hiện điểm biên Parten Mẫu Prefix-tree Tiếp đầu ngữ Purity Độ tinh khiết Reduction in variace Giảm bớt sự dao động Regression Hồi quy Removing outliers Loại bỏ các điểm biên Requent retraining Huấn luyện lại thường xuyên Segmentation Phân đoạn Sequence Chuỗi Sequence Analysis Phân tích chuỗi Subset Function Hàm tìm tập con Supervised learning Học có quan sát Support Tần suất Training set Tập huấn luyện Transaction Giao tác Trivial Rules Các luật tầm thường Unspervised learning Học không có giám sát Web logs Công cụ lưu trữ thông tin trên web