Mở đầu - Chƣơng 1: Giới thiệu về khai thác dữ liệu, cơ sở dữ liệu kích thƣớc lớn. - Chƣơng 2: Khai phá tập phổ biến. - Chƣơng 3: Phƣơng pháp phân vùng, phân cấp trong khai phá tập phổ biến - Chƣơng 4: Kết luận và hƣớng phát triển trong tƣơng lai 4 CHƢƠNG 1 GIỚI THIỆU VỀ KHAI THÁC DỮ LIỆU, CƠ SỞ DỮ LIỆU KÍCH THƢỚC LỚN 1.1 Tổng Quan về khai thác dữ liệu 1.1 Mục tiêu của khai thác dữ liệu Với sự phát triển của phần mềm và phần cứng máy tính và số lƣợng khổng lồ và tăng tốc của dữ liệu. Từ khối dữ liệu rất lớn nhƣ vậy, cần phải có những công cụ tự động rút trích các thông tin và tri thức có ích, đó là khai thác dữ liệu (Data mining).
Khai thác dữ liệu là quá trình tìm kiếm các mẫu mới, những thông tin tiềm ẩn trong các khối dữ liệu khổng lồ, khai thác có thể dự đoán những xu hƣớng trong tƣơng lai, hay giúp cho các công ty kinh doanh ra các quyết định kịp thời, hay dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra quyết định (decision support systems - DSSs). Với các ƣu điểm trên, khai thác dữ liệu đƣợc ứng dụng rộng rãi trong các lĩnh vực nhƣ thƣơng mại, tài chính, y học, giáo dục và các lĩnh vực khác. Khai thác dữ liệu đƣợc định nghĩa, hay cách gọi khác của một thuật ngữ rất thông dụng là khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD): là việc trích ra các tri thức chƣa đƣợc nhận ra, tiềm ẩn trong các tập dữ liệu lớn một cách tự động [1] Một ví dụ tiêu biểu cho việc khai thác tập phổ biến [7] là phân tích giỏ hàng. Tiến trình này phân tích thói quen mua sắm của khách hàng bằng cách tìm ra sự kết hợp giữa các danh mục khác nhau từ trong giỏ hàng của họ.
Việc khám phá ra những sự kết hợp này giúp ích cho các nhà bán lẻ mở rộng phân phối sản phẩm bởi họ thấu hiểu đƣợc những lợi nhuận có đƣợc từ những danh mục đƣợc khách hàng mua thƣờng xuyên. Cho một ví dụ thực tiễn hơn, nếu khách hàng 5 mua sữa, khả năng họ mua bánh mì trên cùng một lần đi siêu thị là nhƣ thế nào? Những thông tin này sẽ giúp cho các nhà bán lẻ tăng doanh thu và giúp họ Lựa chọn kế hoạch tiếp thị và trƣng bày sản phẩm. Kết quả phân tích giỏ hàng có thể giúp bạn lên kế hoạch tiếp thị, chiến lƣợc quảng cáo, trƣng bày sản phẩm hay lập danh mục bán hàng giảm giá …Ví dụ, kết quả phân tích cho thấy nếu khách hàng mua một máy vi tính thì có thể mua kèm phần mềm diệt vi rút. Từ đó, bạn sẽ có kế hoạch trƣng bày sản phẩm hợp lý hơn (Thông tin về máy tính đƣợc hiển thị kèm theo phần mềm diệt vi rút đƣợc khuyến khích mua).
Từ phân tích giỏ hàng bạn cũng có thể tìm ra một số quy tắc hay luật kết hợp có ích. Ví dụ, thông tin khách hàng mua máy vi tính và cũng mua phần mềm diệt vi rút đã đƣa ra luật kết hợp nhƣ sau: Computer antivirus_software [support = 2%, confidence = 60%] Độ hỗ trợ (support) và độ tin cậy (confidence) của luật là hai độ đo đƣợc quan tâm nhất. Luật có support = 2%, nghĩa là số lần giao dịch mà máy vi tính và phần mềm diệt vi rút đƣợc mua cùng nhau chiếm 2% trong tổng số các giao dịch; confidence=60%, nghĩa là có 60% khách hàng mua máy vi tính thì cũng sẽ mua phân mềm diệt vi rút. Luật kết hợp đƣợc quan tâm nếu nó thỏa mãn cả hai ngƣỡng độ hỗ trợ nhỏ nhất (minimum support threshold) và độ tin cậy nhỏ nhất (minimum confidence threshold).2 Các bƣớc chính của quá trình khai thác dữ liệu [12] Hình 1.1: Quá trình khai thác tri thức - Gom dữ liệu (Gathering): Tập hợp dữ liệu là bƣớc đầu tiên trong quá trình khai phá dữ liệu.
Đây là bƣớc đƣợc khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. - Trích chọn dữ liệu (data selection): Ở giai đoạn này dữ liệu đƣợc lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó, ví dụ chọn tất cả những ngƣời có tuổi đời từ 25 – 35 và có trình độ đại học. - Tiền xử lý dữ liệu (data preprocessing): Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhƣng thực tế nó là một bƣớc rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thƣờng mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logic.
Vì vậy, dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này đƣợc xem nhƣ thông tin dƣ thừa, không có giá trị. Bởi vậy, đây là một 7 quá trình rất quan trọng vì dữ liệu này nếu không đƣợc “làm sạch - tiền xử lý - chuẩn bị trƣớc” thì sẽ gây nên những kết quả sai lệch nghiêm trọng - Biến đổi dữ liệu (data transformation): Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đƣa ra có thể sử dụng và điều khiển đƣợc bởi việc tổ chức lại nó.
Dữ liệu đã đƣợc chuyển đổi phù hợp với mục đích khai thác - Khai thác dữ liệu (data mining): Đây là bƣớc mang tính tƣ duy trong khai phá dữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thƣờng dùng là nguyên tắc phân loại, nguyên tắc kết hợp hoặc các mô hình dữ liệu tuần tự, … - Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu dữ liệu đƣợc chiết xuất ra bởi phần mềm khai phá dữ liệu.
Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ƣu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowledge). Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai đoạn 5 là giai đoạn đƣợc quan tâm nhiều nhất, đó là khai phá dữ liệu.3 Các dạng dữ liệu có thể khai thác đƣợc [12] - Cơ sở dữ liệu quan hệ (relational databases) - Cơ sở dữ liệu đa chiều (multidimention databases) - Cơ sở dữ liệu giao tác (transactional databases) - Cơ sở dữ liệu quan hệ - hƣớng đối tƣợng (object relation databases) - Dữ liệu không gian và dữ liệu chuỗi theo thời gian (spatial and time-series data) - Cơ sở dữ liệu đa phƣơng tiện (multimedia databases) 8 1.4 Hƣớng tiếp cận và các kỹ thuật trong khai thác dữ liệu [12] - Phân lớp và dự đoán (Classification & prediction): là quá trình xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ nhƣ: phân lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp loại cƣớc hoặc loại dịch vụ sử dụng dựa trên số máy bị gọi của cuộc gọi, phân lớp giờ cao điểm, thấp điểm dựa trên lƣu lƣợng giao thông hàng ngày, phân lớp vùng địa lý theo thời tiết… Đối với hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định (decision tree), mạng nơron nhân tạo (neural network), hay còn đƣợc gọi là học có giám sát – học có Thầy (supervised learning).
- Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng tƣơng đối đơn giản. Ví dụ: 85% sinh viên đăng ký học môn Kỹ thuật lập trình thì có tới 65% trong số họ đăng ký học môn Cơ sở dữ liệu, hay có 60% khách hàng gọi điện thoại liên tỉnh thì 85% họ gọi nội tỉnh… Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính,… - Khai thác mẫu tuần tự/ chuỗi thời gian (sequential/temporal patterns): Cũng tƣơng tự nhƣ khai phá dữ liệu bằng 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 biến cố Y. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán bởi chúng có tính dự báo cao.
- Phân cụm (clustering/segmentation): Sắp xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên, tức là số lƣợng và tên cụm chƣa đƣợc biết trƣớc. Các đối tƣợng đƣợc gom cụm sao cho mức độ tƣơng tự giữa các đối tƣợng trong cùng một cụm là lớn nhất, và mức độ tƣơng tự giữa các đối tƣợng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán này còn đƣợc gọi là học không giám sát - học không thầy (unsupervised learning) 9 - Mô tả khái niệm (concept description & summarization): Lớp bài toán này thiên về mô tả, tổng hợp và tóm tắt khái niệm (Ví dụ: tóm tắt văn bản). - Phân vùng phân cấp (the hierarchical partitioning approach): là khai thác tập phổ biến trong những cơ sở dữ liệu lớn, dựa trên một cấu trúc dữ liệu mới gọi là danh sách mẫu phổ biến.
Phƣơng pháp này phân vùng không gian tìm kiếm và không gian giải pháp và do đó chia cơ sở dữ liệu thành một tập các cơ sở dữ liệu con có kích thƣớc có thể quản lý đƣợc.5 Ph n loại các hệ thống khai thác dữ liệu[3] - Phân loại dựa trên kiểu dữ liệu đƣợc khai thác: CSDL quan hệ, CSDL giao tác, CSDL hƣớng đối tƣợng, … - Phân loại dựa trên dạng tri thức đƣợc khám phá: tóm tắt và mô tả, luật kết hợp, phân lớp, phân cụm,… - Phân loại dựa trên lĩnh vực đƣợc áp dụng: thƣơng mại, tài chính, y học… - Phân loại dựa trên kỹ thuật đƣợc áp dụng: phân tích trực tuyến, máy học 1.6 Ứng dụng của khai thác dữ liệu[3] - Tài chính và thị trƣờng chứng khoán. - Phân tích dữ liệu và hỗ trợ ra quyết định - Điều trị y học và chăm sóc y tế - Sản xuất và chế biến - Text mining & Web mining - Lĩnh vực khoa học - Mạng viễn thông - Bảo hiểm… 10 1.2 Cơ Sở Dữ Liệu Kích Thƣớc Lớn. Với sự tiến bộ của công nghệ thông tin và sự phổ biến của Internet thì dữ liệu đƣợc tạo ra và thu thập lại đã gia tăng đáng kể. Sự bùng nổ dữ liệu đã dẫn đến một nhu cầu cấp thiết cho các công nghệ và các công cụ có thể chuyển đổi dữ liệu thành thông tin và kiến thức bổ ích.