Đề tài Kỹ thuật khám phá tri thức - Khai phá dữ liệu

 

MỤC LỤC

 

MỞ ĐẦU .1 CHƯƠNG I : GIỚI THIỆU CHUNG.1

1.1. Sự cần thiết của việc nghiến cứu quy trình khám phá tri thức – khai phá dữ liệu.2 1.2. Mục đích nghiên cứu của đề tài. .2 1.3. Phạm vi nghiên cứu của đề tài . .2 1.4. Cách thiết kế các phần nội dung chính trong bản thuyết minh.3

CHƯƠNG II : TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC – KHAI PHÁ

DỮ LIỆU

2.1. Thế nào là Khám phá tri thức - Khai phá dữ liệu.4 2.2. Sự cần thiết của Khám phá tri thức.5 2.3. Khám phá tri thức và các lĩnh vực liên quan.6 2.4 Thế nào là khai phá dữ liệu.7 2.5. Định nghĩa Khai phá dữ liệu.7

CHƯƠNG III : NGHIÊN CỨU QUY TRÌNH KHÁM PHÁ TRI THỨC

3.1. Các giai đoạn của quá trình Khám phá tri thức.10 3. 2. Nhiệm vụ của quá trình Khám phá tri thức.12 3.3. Quy trình Khám phá tri thức.14 3.4. Hướng tiếp cận và kỹ thuật chính trong Khai phá dữ liệu.15

3.4.1.Các dạng dữ liệu có thể khai phá.15 3.4.2.Các phương pháp,kĩ thuật chính trong khai phá dữ liệu.16

3.4.2.1. Phân lớp và dự đoán (Classification & Prediction).17 3.4.2.2. Phân tích luật kết hợp (Association Rules).19 3.4.2.3. Khai thác mẫu tuần tự (Sequential / Temporal patterns).20 3.4.2.4. Phân nhóm- đoạn (Clustering / Segmentation).20 3.4.2.5. Hồi quy (Regression).21 3.4.2.6. Tổng hợp hóa (Summarization).22 3.4.2.7. Mô hình hóa sự phụ thuộc (dependency modeling) .22 3.4.2.8. Phát hiện sự biến đổi và độ lệch (Change and deviation detection).22

3.4.3. Những vấn đề khó khăn trong Khai phá dữ liệu.

3.4.3.1. Vấn đề về CSDL.23

3.4.3.1.1. CSDL lớn.23 3.4.3.1.2. Số chiều dữ liệu lớn.23 3.4.3.1.3. Dữ liệu thay đổi liên tục.24

3.4.3.1.4. Các thuộc tính dữ liệu không phù hợp.24

3.4.3.1.5. Dữ liệu bị thiếu không đầy đủ.24

3.4.3.1.6. Dữ liệu bị nhiễu và không chắc chắn.24

3.4.3.1.7. Mối quan hệ phức tạp giữa các thuộc tính.25

3.4.3.2. Các vấn đề khác.25

3.4.3.2.1. Vấn đề Overfitting.25

3.4.3.2.2. Khả năng biểu đạt của mẫu.26

3.4.3.2.3. Khả năng tương tác với người sử dụng.26

3.4.3.2.4. Khả năng tích hợp với các hệ thống khác.26

3.5. So sánh Khai phá dữ liệu với một số phương pháp cổ điển.26 3.6. Hướng nghiên cứu và việc ứng dụng của Khai phá dữ liệu hiện nay.27 3.7. ứng dụng của Khai phá dữ liệu - Khám phá tri thức.28

CHƯƠNG IV : ỨNG DỤNG QUY TRÌNH KHÁM PHÁ TRI THỨC VÀO VIỆC PHÂN TÍCH CSDL CHƯNG KHOÁN (CSDL CHUỖI THỜI GIAN)

4.1. Các khái niệm về CSDL chuỗi thời gian.30

4.2. CSDL thị trường chứng khoán:.30

4.3 Các đặc điểm của CSDL chứng khoán.31

4.4 Tiền xử lý dữ liệu chuỗi thời gian.32

4.5 Chỉ số xu hướng tổng quát .35

4.6 Phân loại trạng thái của hệ thống nhiễu loạn – tích lũy thông tin thống kê.36

4.7. Dự báo trạng thái của hệ thống nhiễu loạn. .38

KẾT LUẬN

1. Kết quả đạt được.41 2. Hướng nghiên cứu tiếp theo.41

 

doc46 trang | Chia sẻ: netpro | Lượt xem: 3876 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Đề tài Kỹ thuật khám phá tri thức - Khai phá dữ liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
hỉ số chứng khoán ... Cơ sở dữ liệu đa phương tiện (Multimedia database): là dạng dữ liệu âm thanh (audio), hình ảnh (video), Text & WWW, ... Dạng dữ liệu này đang rất phong phú, đa dạng và được phổ biến rộng rãi nhất là trên internet. 3.4.2. Các phương pháp, kỹ thuật chính trong Khai phá dữ liệu. Bởi vì Khai phá dữ liệu và Khám phá tri thức là một lĩnh vực tương đối mới, do vậy có nhiều các tác giả đã đưa ra các nghiên cứu về phương pháp, kỹ thuật Khai phá dữ liệu theo các cách khác nhau như: Đối với Fayyad, các kỹ thuật Khai phá dữ liệu như: Mô hình dự báo (Predictive Modeling), Phân nhóm (Clustering), Tổng hợp hóa (Summarization), Mô hình sự phụ thuộc (Dependency Modeling), Phát hiện sự biến đổi và độ lệch (Change and deviation detection).[5] Đối với Goebel & Gruenwald, các kỹ thuật Khai phá dữ liệu như: Các mô hình thống kê (Statistical Models), Mạng nơron (Neural Networks), cây quyết định (Decision Trees), Quy nạp luật (Rule Induction), mạng Bayesian tin cậy (Bayesian Belief Networks), các thuật toán về lập trình Gen (Genetic algorithms), tập mờ (Fuzzy Sets), tập thô (Rough Sets).[4] Đối với Aggarwal & Yu, các kỹ thuật Khai phá dữ liệu gồm: Luật kết hợp (Association rules), Phân nhóm (Clustering), Phân lớp (Classification). Tựu chung lại, các kỹ thuật Khai phá dữ liệu thực chất không có gì mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như học máy, nhận dạng, thống kê (hồi quy, phân loại, phân nhóm), các mô hình đồ thị, các mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia,… Tuy nhiên, với sự kết hợp tài tình của Khai phá dữ liệu, kỹ thuật này có ưu thế hơn hẳn các phương pháp trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học cũng như áp dụng vào thực tiễn và nó có thể được chia làm 2 nhóm chính sau: Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Nhóm kỹ thuật này gồm các phương pháp: phân nhóm (Clustering), tổng hợp hóa (Summerization), Phát hiện sự biến đổi và độ lệch (Change and deviation detection), phân tích luật kết hợp (Association Rules), ... Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Nhóm kỹ thuật này gồm các phương pháp: phân lớp (Classification), hồi quy (Regression), ... 3.4.2.1. Phân lớp và dự đoán (Classification & Prediction): Là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được biết trước đó. Mục tiêu của việc phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp hay nói cách khác là dự đoán nhãn lớp cho các mẫu dữ liệu. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng luật theo các cách sau: “Nếu các thuộc tính dự báo của một mục thỏa mãn điều kiện của các tiền đề thì mục đó nằm trong lớp chỉ ra trong kết luận”. Ví dụ : phân lớp loại cước hoặc loại dịch vụ dựa trên số máy bị gọi của cuộc gọi, phân lớp khu vực dựa trên số máy chủ gọi, phân lớp giờ cao điểm, thấp điểm dựa trên giờ bắt đầu đàm thoại, ... Phân lớp là một lĩnh vực rất quan trọng trong khai phá dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu. Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát (supervised learning) khác với phân nhóm dữ liệu là học không có giám sát (unsupervised learning). Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: Cây quyết định (Decision Tree), K-Láng giềng gần nhất (k-Nearest Neighbor), Mạng Nơron (Neural networks), Giải thuật di truyền (Genetic algorithms), Mạng Bayesian (Bayesian networks), Tập mờ và tập thô (Rough and Fuzzy Sets). a) Cây quyết định (Decision Tree). Các kỹ thuật phân lớp sử dụng cây quyết định để phân tách các dữ liệu cho đến khi mỗi phần chứa đựng hầu hết các mẫu từ một lớp đặc trưng, kết quả của quá trình sẽ cho ra một cây quyết định. Điểm phân tách trong cây quyết định là một nút (không phải là nút lá) sẽ sử dụng một số điều kiện để quyết định dữ liệu sẽ được phân tách như thế nào. Các nút cuối cùng trong cây quyết định chứa đựng các bộ mẫu giống nhau. Lợi thế của cây quyết định là các thuật toán chạy khá nhanh, với kết quả khá tốt và có thể giải thích được rõ ràng. Tuy nhiên, bất lợi mà các thuật toán của cây quyết định có thể gặp phải đó là chúng có thể tìm ra các điểm tới hạn cục bộ, đưa ra các kết quả không đúng. b)K-láng giềng gần nhất (k-Nearest Neighbor). Thuật toán này tìm ra các láng giềng gần nhất của mẫu thử nghiệm và quy về các nhãn lớp của chúng dựa trên các nhãn đa số, điều đó có nghĩa là các mẫu được quy về cùng lớp khi chúng là lân cận của nhau. Kỹ thuật này cho rằng vị trí trong không gian đặc trưng hàm ý một quan hệ họ hàng gần gũi ở giữa các nhãn lớp. Lợi thế của các thuật toán K-Láng giềng gần nhất là dễ thực thi, và kết quả mà nó đem lại khả năng dễ dàng giải thích. Nhưng một điểm bất lợi là các thuật toán này đưa ra các mô hình rất lớn với một tập dữ liệu nhỏ. c) Mạng nơron (Neural networks). Mạng nơron là mạng được mô phỏng theo bộ não của con người. Đó là một cấu trúc dữ liệu của các hàm với một hoặc nhiều trọng số đầu vào, với kết quả đầu ra là một nhãn các lớp. Từng phần riêng biệt của dữ liệu được đưa vào mạng nơron và các hàm - các trọng số trong mạng nơron bị thay đổi (học - huấn luyện) tùy theo tỷ lệ lỗi của đầu ra. Phương pháp này thường đưa đến một khoảng thời gian huấn luyện dài ngay cả khi tập dữ liệu nhỏ. Lợi thế của mạng nơron là đưa đến các kết quả khá chính xác, nhưng bất lợi của nó là thường đòi hỏi thời gian huấn luyện dài và đưa ra các kết quả khó hiểu, cứng nhắc, bị bao bọc trong một hộp đen, khó giải thích tường minh. d) Giải thuật di truyền (Genetic algorithms). Các giải thuật di truyền được sử dụng để đưa ra công thức giả thuyết về sự phụ thuộc giữa các biến. Đối với một giải thuật di truyền phải sử dụng các giải pháp như cạnh tranh, lựa chọn và kết hợp giữa các tập hợp cá thể. Lợi thế của Giải thuật di truyền là thường đưa đến các kết quả kiểm tra khá chính xác, nhưng bất lợi của nó là kết quả có được thông qua việc lập trình tiến hóa và các kết quả cũng thường cứng nhắc, khó hiểu. e) Mạng Bayesian (Bayesian networks) Trong mạng Mạng Bayesian sử dụng các đồ thị có hướng, không có chu trình để miêu tả sự phân lớp có thể được. Các đồ thị này cũng có thể được sử dụng để miêu tả các tri thức chuyên gia. Các nút miêu tả các biến thuộc tính và các trạng thái (sự kiện) và mỗi một cạnh miêu tả khả năng sự phụ thuộc giữa chúng. Kết hợp với mỗi nút là các lớp cục bộ có thể và các cung được vẽ từ nút nguyên nhân đến nút bị ảnh hưởng. Khai phá dữ liệu trong mạng Bayesian bao gồm việc sử dụng đầu vào các tri thức chuyên gia và sau đó sử dụng một CSDL để cập nhật, lọc và cải tiến tri thức đó trong mạng. Các đồ thị mới có thể là kết quả từ các cải tiến này và nguyên nhân của các mối quan hệ giữa các nút kết quả có thể được giải thích một cách dễ dàng. Lợi thế của mạng Bayesian là thường đưa ra các kết quả dễ hiểu, nhưng bất lợi của nó là cần thu thập được các tri thức chuyên gia truyền thống. f) Tập mờ và tập thô (Rough and Fuzzy Sets) Lý thuyết về tập mờ và tập thô dựa trên một sơ sở toán học không chắc chắn. Đối với các mô hình tập thô, một giới hạn trên và giới hạn dưới sẽ được xác định. Một tập thô định nghĩa một lớp C là một xấp xỉ bởi hai tập. Tập cận dưới (lower) của C bao gồm tất cả các mẫu dữ liệu, mà dựa vào tri thức của các mẫu dữ liệu có thể quyết định một mẫu bất kỳ thuộc phân lớp C một cách rõ ràng. Tập cận trên của C bao gồm tất cả các mẫu với giá trị của thuộc tính được mô tả không thể thuộc vào phân lớp C. Mô hình tập mờ không dốc về cực đại cục bộ bằng các thuật toán cây quyết định, và cũng giống như mô hình tập thô, chúng dùng để đối phó với những điều không chắc chắn tốt hơn bất kỳ một thuật toán nào khác. 3.4.2.2. Phân tích luật kết hợp (Association Rules): Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật Khai phá dữ liệu là tập luật kết hợp tìm được. Chẳng hạn: phân tích CSDL bán hàng nhận được thông tin về những khách hàng mua máy tính có khuynh hướng mua phần mềm quản lý tài chính trong cùng lần mua được miêu tả trong luật kết hợp sau: “Máy tính => Phần mềm quản lý tài chính” [Độ hỗ trợ: 2%, độ tin cậy: 60%] Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật. Chúng tương ứng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Độ hỗ trợ 2% có nghĩa là 2% của tất cả các tác vụ đã phân tích chỉ ra rằng máy tính và phần mềm quản lý tài chính là đã được mua cùng nhau. Còn độ tin cậy 60% có nghĩa là 60% các khách hàng mua máy tính cũng mua phần mềm. Khai phá luật kết hợp được thực hiện qua 2 bước: Bước 1: tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác định qua tính độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu. Bước 2: sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Luật kết hợp có khả năng ứng dụng trong nhiều lĩnh vực khác nhau như kinh doanh, y học, tài chính, thị trường chứng khoán, phân tích quyết định, phân tích thị trường, … Tuy luật kết hợp là một dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ gia quyết định. Tìm kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực Khai phá dữ liệu. 3.4.2.3. Khai thác mẫu tuần tự (Sequential / Temporal patterns): Tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo cao. 3.4.2.4. Phân nhóm- đoạn (Clustering / Segmentation): Mục tiêu chính của việc phân nhóm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các nhóm sao cho mức độ tương tự giữa các đối tượng trong cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các nhóm khác nhau là nhỏ nhất. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau và số lượng các nhóm là chưa biết trước. Một đối tượng có thể vừa thuộc nhóm này, nhưng cũng có thể vừa thuộc nhóm khác. Không giống như phân lớp dữ liệu, phân nhóm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân nhóm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này bạn sẽ không thể biết kết quả các nhóm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các nhóm thu được. Phân nhóm còn được gọi là học không có giám sát (unsupervised learning). Phân nhóm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web, … Ngoài ra phân nhóm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán Khai phá dữ liệu khác. Theo Gray & Orlowska thì các thuật toán phân nhóm bao gồm một trong hai dạng thức điển hình sau: - Phân nhóm theo thứ bậc (Hierarchical clustering): Các thuật toán này định dạng tập dữ liệu bằng cách lặp đi lặp lại việc nối hoặc phân chia những nhóm đã tồn tại vào trong các nhóm mới. Lợi ích của việc phân nhóm theo thứ bậc là sinh ra các luật rõ ràng từ dữ liệu mà không cần giám sát. Nhưng bất lợi của nó là các thuật toán phân nhóm theo vùng thực thi tốt hơn so với việc phân theo thứ bậc. - Phân nhóm theo vùng (Partition-clustering): Các thuật toán này sẽ phân tách tập dữ liệu bằng một con số nhóm xác định bằng việc lặp đi lặp lại việc lựa chọn các điểm tiêu biểu cho mỗi một nhóm, xác định sự phân chia dữ liệu dựa trên những điểm đặc trưng này và đánh giá các vùng thông qua khoảng cách hoặc tiêu chuẩn mô hình cơ bản. Các kỹ thuật đo khoảng cách tìm ra k-cách (k-way) phân chia tốt nhất, vì vậy các trường hợp nằm trong mỗi một khối thuộc một vùng sẽ gần nhau hơn (về khoảng cách) so với các trường hợp trong các vùng khác khác. Các kỹ thuật về mô hình cơ bản tìm sự thích hợp nhất cho một mô hình giả thiết đối với mỗi nhóm. Có thể các phép đo được sử dụng để độ thích hợp của mô hình đối với một nhóm. 3.4.2.5. Hồi quy (Regression). Phân tích hồi qui (regression analysis) là một công cụ mà nhiều người biết. Dạng đơn giản nhất, xây dựng một mô hình dự đoán để liên kết một biến dự đoán X (predictor variable), với một biến trả lờI Y (response variable), thông qua một mối liên hệ dạng Y=aX + b. Ví dụ, chúng ta muốn xây dựng một mô hình cho phép dự đoán mức tiết kiệm của một người khi cho biết thu nhập của họ. Rõ ràng là mô hình có thể sẽ không là hoàn hảo, nhưng do mức tiết kiệm tăng cùng với mức thu nhập, vì vậy mô hình có thể là mô tả thô (rough characterization). Đối chiếu với các bước liệt kê ở trên, chúng ta có kịch bản sau: Biểu diễn là một mô hình mà biến trả lời, mức tiết kiệm, là phụ thuộc tuyến tính với biến dự đoán, mức thu nhập, Hàm cho điểm đuợc sử dụng chung nhất trong tình huống này là tổng các bình phương sự khác nhau (sum of squared discrepancies) giữa mức tiết kiệm dự đoán của mô hình và mức tiết kiệm quan sát trong dữ liệu. Tổng này càng nhỏ thì mô hình càng phù hợp với dữ liệu, Giải thuật tối ưu là không phứp tạp trong trường hợp hồi qui tuyến tính: a và b có thể được tính toán như các hàm tường minh của các giá trị quan sát của các biến mức tiết kiệm và mức thu nhập. Trừ khi tập dữ liệu là lớn, một vài vấn đề quản lý dữ liệu nảy sinh với các giải thuật hồi qui. Các tổng số của dữ liệu (tổng số, tổng các bình phương, tổng của các tích các giá trị X và Y) dễ dàng được thực hiện một cách hiệu quả để cuối cùng ước lượng a và b. Chỉ cần một lần duyệt CSDL sẽ sinh ra các ước lượng của a và b. Trong Khai phá dữ liệu, hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng hạn như hồi quy tuyến tính. Tuy nhiên phương pháp mô hình hóa cũng có thể được sử dụng như Cây quyết định. ứng dụng của hồi quy là rất nhiều, ví dụ: Dự đoán số lượng sinh vật phát quang hiện thời trong khu rừng bằng cách dò tìm vi sóng của các thiết bị cảm biến từ xa, ước lượng xác suất người bệnh có thể chết bằng cách kiểm tra các triệu chứng bệnh lý, dự báo nhu cầu của người dùng đối với một sản phẩm, ... 3.4.2.6. Tổng hợp hóa (Summarization). Là công việc liên quan đến các phương pháp tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật mô tả khái niệm và tổng hợp hóa thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. Cần lưu ý rằng luật dạng này có khác biệt so với luật phân lớp. Luật phát hiện đặc trưng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó. 3.4.2.7. Mô hình hóa sự phụ thuộc (dependency modeling). Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo hai mức. Mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị), trong đó, các biến phụ thuộc bộ phận vào các biến khác. Và mức định lượng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này thường được biểu thị dưới dạng theo luật “nếu - thì” - nếu tiền đề đúng thì kết luận đúng. Về nguyên tắc, cả tiền đề và kết luận đều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề thường là nhóm các giá trị thuộc tính và kết luận chỉ là một thuộc tính. Hơn nữa, hệ thống có thể phát hiện các luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do người dùng chỉ ra trong kết luận. Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy Bayes. Đó là đồ thị có hướng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết phụ thuộc giữa các nút đó. 3.4.2.8. Phát hiện sự biến đổi và độ lệch (Change and deviation detection). Nhiệm vụ này tập chung vào khám phá hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu thời gian. Độ lệch theo nhóm là sự khác nhau của dữ liệu trong hai tập con dữ liệu, ở đây xét cả trường hợp tập con dữ liệu này thuộc tập con kia. Nghĩa xác định dữ liệu trong một nhóm con của đối tượng có khác đáng kể so với toàn bộ đối tượng không? Theo cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thường sẽ được phát hiện. Vì những nhiệm vụ này, yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kết và chọn phương pháp Khai phá dữ liệu khác nhau. 3.4.3. Những vấn đề khó khăn trong Khai phá dữ liệu. Như chúng ta đã biết Khai phá dữ liệu là một lĩnh vực liên ngành và được ứng dụng rất rộng rãi trên nhiều lĩnh vực. Tuy nhiên với đặc điểm là việc xử lý các CSDL lớn nên Khai phá dữ liệu cũng có những vấn đề khó khăn của riêng mình. ở đây chúng ta sẽ xem xét một số vấn đề sau: 3.4.3.1. Vấn đề về CSDL. Đầu vào của một hệ thống Khai phá dữ liệu thường là tập các dữ liệu thô sơ nhiều lúc không đầy đủ và bị nhiễu bởi nhiều nguyên nhân khác nhau. Ngoài ra trong thực tế dữ liệu lại luôn luôn biến động không ngừng và được bổ xung liên tục tạo thành một lượng dữ liệu khổng lồ chứa đựng cả những thông tin có ích và không có ích. Chính vì vậy trong bất kỳ một hệ Khai phá dữ liệu nào việc đầu tiên cần làm là phân tích và xem xét CSDL mà hệ thống sẽ khai phá. 3.4.3.1.1. CSDL lớn. Việc sử dụng công cụ phân tích trực tuyến không khai thác được hết những thông tin của CSDL hiện thời, chính vì vậy những người xử lý dữ liệu không còn cách nào khác là lưu dữ liệu lại để phục vụ cho việc sử dụng sau này. Dữ liệu được lưu trữ chứa đựng cả thông tin hữu ích chưa được khai phá và cả những thông tin không có ích. Việc tích lũy này ngày càng lớn và cho đến nay các CSDL tới hàng triệu bản ghi có kích thước lên đến Tetabytes là chuyện bình thường. Tùy từng ứng dụng cụ thể, việc làm như thế nào để loại bỏ những dữ liệu thừa, những thông tin vô nghĩa lại có những cách thức khác nhau, vì vậy phương pháp xử lý dữ liệu hết sức đa dạng và phức tạp, không có một quy tắc chung nhất cho mọi ứng dụng. 3.4.3.1.2. Số chiều dữ liệu lớn. Tập dữ liệu thực chất là một tập các số đo từ môi trường hoặc quá trình. Trường hợp đơn giản nhất, chúng ta có tập hợp các đối tượng, mỗi đối tượng có một tập p số đo. Số đo chính là thuộc tính của các thực thể (đối tượng, bản ghi, ...). Cùng với yêu cầu của thông tin là đa dạng và đầy đủ mà dữ liệu cần lưu được thì số lượng các thuộc tính cũng cần phải nhiều lên. Mỗi một thuộc tính có thể được coi là một chiều trong không gian CSDL. Chính vì thể số chiều của bài toán trong hệ Khai phá dữ liệu cũng rất lớn. Một tập dữ liệu có số chiều lớn sẽ làm tăng không gian tìm kiếm của mô hình suy diễn. Hơn nữa nó sẽ làm tăng khả năng tìm thấy các mẫu giả trong các giải thuật của Khai phá dữ liệu. Biện pháp khắc phục vấn đề này là phải giảm số chiều của dữ liệu cần khai phá, và sử dụng các tri thức có sẵn để loại bỏ những biến không phù hợp. 3.4.3.1.3. Dữ liệu thay đổi liên tục. Đặc điểm cơ bản của hầu hết các CSDL là nội dung của chúng thay đổi liên tục. Đặc điểm này chính là việc dữ liệu có thể thay đổi theo thời gian và gây ra hệ quả là việc Khai phá dữ liệu bị ảnh hưởng tại thời điểm quan sát dữ liệu. Ví dụ trong CSDL thị trường chứng khoán, một số giá trị thuộc tính là hằng số, một số khác lại thay đổi liên tục theo thời gian như giá cổ phiếu, chỉ số Index, trong khi đó một số khác lại thay đổi tùy thuộc vào tình huống như số lượng cổ phiếu được giao dịch trong một phiên, ... Việc thay đổi dữ liệu nhanh chóng có thể làm mất giá trị của các mẫu trước đó, hơn nữa các biến trong CSDL của ứng dụng đã cho cũng bị thay đổi, bị xóa hoặc bị tăng lên theo thời gian. 3.4.3.1.4. Các thuộc tính dữ liệu không phù hợp. Một đặc điểm quan trọng khác của CSDL là tính không phù hợp của dữ liệu, nghĩa là mục dữ liệu trở thành không thích hợp với ý nghĩa hiện tại của việc khai phá. Một khía cạnh khác của tính không phù hợp của thuộc tính đó là giá trị của thuộc tính đó không phản ánh được ý nghĩa hiện tại mà chỉ thích hợp trong lịch sử của nó. 3.4.3.1.5. Dữ liệu bị thiếu không đầy đủ. Việc thiếu hụt không đầy đủ ở đây bao hàm cả sự không đầy đủ về giá trị và thuộc tính của dữ liệu. Sự có mặt hay không có mặt của giá trị các thuộc tính phù hợp ảnh hưởng rất lớn đến việc Khai phá dữ liệu. Việc quan sát không đầy đủ một CSDL có thể đưa đến các kết luận sai lầm. Việc quan sát dữ liệu phải được thực hiện trên toàn bộ các thuộc tính hữu ích có thể dùng các giải thuật về Khai phá dữ liệu để áp dụng giải quyết bài toán. Chính việc thiếu hụt dữ liệu có thể gây lên việc tìm ra các mẫu giả, dẫn đến kết quả là tri thức khám phá được có thể sai lệch với thực tế. 3.4.3.1.6. Dữ liệu bị nhiễu và không chắc chắn. Ngoài việc dữ liệu bị lỗi hay không đầy đủ thì bản thân dữ liệu cũng tiềm ẩn khả năng bị nhiễu, không chắc chắn. Đối với các thuộc tính đã phù hợp, thì giá trị của thuộc tính đó có thực tế phản ánh được quy luật trong dữ liệu hay không? Các giá trị của các thuộc tính khác nhau có thể là các số thực, số nguyên, có thể là chuỗi hoặc là tập các giá trị định danh. Các giá trị định danh này có thể được sắp xếp theo thứ tự từng phần, đầy đủ và thậm chí có thể có cấu trúc ngữ nghĩa. Một yếu tố khác của độ nhiễu chính là tính kế thừa hoặc độ chính xác mà dữ liệu cần có. Nói cách khác là độ nhiễu trên các phép đo và phân tích có ưu tiên. Mô hình thống kê mô tả tính ngẫu nhiên được tạo ra và được sử dụng để định nghĩa độ mong muốn và độ dung sai của dữ liệu. Thường thì các mô hình thống kê được áp dụng theo các cách đặc biệt để xác định một cách chủ quan các thuộc tính để đạt được các đánh giá thống kê của các giá trị thuộc tính. Đặc biệt đối với dữ liệu kiểu số, sự đúng đắn của dữ liệu là một yếu tố vô cùng quan trọng trong việc Khai phá. Ví dụ trong cách đo nhiệt độ cơ thể có thể cho phép chênh lệch đến 0,1 độ. Nhưng nếu phân tích theo xu hướng nhạy cảm nhiệt độ của cơ thể thì cần độ chính xác cao hơn nhiều. 3.4.3.1.7. Mối quan hệ phức tạp giữa các thuộc tính. Dữ liệu tồn tại trong nhiều dạng (forms) và không đặt trong một sự phân cấp đầy đủ (complete taxonomy). Thực vậy, rất khó xây dựng một phân cấp đầy đủ do một khía cạnh của dữ liệu trong tình huống này có thể lại không quan trọng trong tình huống khác. Dù vậy, có những sự phân biệt rõ ràng mà chúng ta nên để ý tới. Một là sự khác nhau giữa các số đo phân loại và định lượng. Các thuộc tính định lượng được đo trong một thang số và có thể nhận một giá trị bất kỳ (ví dụ bảng lương, giá cổ phiếu, ...). Ngược lại, các biến có giá trị thuộc tính phân loại (categorical variables) như là giới tính, trạng thái, loại cổ phiếu, trình độ học vấn, ... chỉ có thể nhận giá trị xác định, rời rạc. Các thuộc tính có giá trị phân loại có thể là sắp thứ tự được (có thứ tự tự nhiên, như là trình độ học vấn) hoặc là tên của các loại (đặt tên đơn giản cho các loại, như là marital status - tình trạng hôn nhân). Một kỹ thuận phân tích dữ liệu chỉ thích hợp cho một kiểu dữ liệu này mà có thể không thích hợp với kiểu dữ liệu khác (mặc dù nó dựa trên cùng mục đính phân tích). Ví dụ, ngay cả khi tình trạng hôn nhân được biểu diễn bằng số nguyên (1 ứng với chưa có gia đình, 2 - đã có gia đình, 3 - góa, ...), nó cũng sẽ không có nghĩa hoặc không thích hợp để tính giá trị trung bình thuộc tính này trên mẫu (sample). Tương tự, hồi qui tuyến tính đơn giản (dự đoán một biến định lượng như một hàm của các biến khác) thường thích hợp áp dụng cho biến định lượng, áp dụng nó cho dữ liệu có giá trị phân loại là không phù hợp; các kỹ thuật khác có mục

Các file đính kèm theo tài liệu này:

  • dochiep.doc
  • docTomtat.doc