Tại Sao Khai Thác Dữ Liệu?

• Sự tăng trưởng bùng nổ của dữ liệu, từ terabyte lên petabyte, thúc đẩy nhu cầu khai thác dữ liệu.
• Các công cụ thu thập dữ liệu tự động, hệ thống cơ sở dữ liệu, Web và xã hội số hóa giúp thu thập và lưu trữ dữ liệu dễ dàng hơn.
• Dữ liệu có giá trị tiềm ẩn cho cả mục đích thu thập ban đầu và các ứng dụng chưa được hình dung trước.
• Nhiều nguồn dữ liệu lớn, bao gồm:
  • Kinh doanh: Web, thương mại điện tử, giao dịch, chứng khoán,...
  • Khoa học: Viễn thám, tin sinh học, mô phỏng khoa học,...
  • Xã hội: Tin tức, máy ảnh kỹ thuật số, YouTube,...
• Máy tính ngày càng rẻ hơn và mạnh mẽ hơn, cho phép xử lý dữ liệu lớn.
• Khai thác dữ liệu là cần thiết vì kỹ thuật truyền thống không phù hợp cho dữ liệu thô.
• Mục đích của khai thác dữ liệu là giải quyết tình trạng "giàu dữ liệu nhưng nghèo thông tin".
• Cần các phương pháp phân tích dữ liệu để hiểu ý nghĩa của dữ liệu thu thập được.

Nguồn Gốc của Khai Thác Dữ Liệu

• Khai thác dữ liệu kết hợp các khái niệm từ học máy/AI, nhận dạng mẫu, thống kê và hệ thống cơ sở dữ liệu.
• Các kỹ thuật truyền thống có thể không phù hợp với dữ liệu quy mô lớn, chiều cao, không đồng nhất, phức tạp và phân tán.
• Khai thác dữ liệu là một thành phần quan trọng của lĩnh vực khoa học dữ liệu và khám phá dựa trên dữ liệu đang nổi lên.

Khai Thác Dữ Liệu và Các Lĩnh Vực Liên Quan

• Các lĩnh vực liên quan đến khai thác dữ liệu:
  • Học máy
  • Nhận dạng mẫu
  • Thống kê
  • Ứng dụng
  • Thuật toán
  • Công nghệ cơ sở dữ liệu
  • Tính toán hiệu năng cao
  • Trực quan hóa

Các Cơ Hội Lớn từ Khai Thác Dữ Liệu

• Cải thiện năng suất trong mọi lĩnh vực.
• Giải quyết hiệu quả hơn các vấn đề lớn của xã hội:
  • Chăm sóc sức khỏe
  • Biến đổi khí hậu
  • Năng lượng
  • Nạn đói

Khai Thác Dữ Liệu Là Gì?

• Khai thác dữ liệu là quá trình khám phá tri thức (Knowledge Discovery from Data - KDD) từ dữ liệu.
• Trích xuất các mẫu hoặc tri thức tiềm ẩn, không tầm thường, rõ ràng chưa biết và hữu ích từ lượng lớn dữ liệu.
• Các tên gọi khác:
  • Khám phá tri thức trong cơ sở dữ liệu (KDD)
  • Trích xuất tri thức
  • Phân tích dữ liệu/mẫu
  • Khảo cổ dữ liệu
  • Khai thác dữ liệu
  • Thu thập thông tin
  • Trí tuệ kinh doanh,...
• Không phải mọi thứ đều là khai thác dữ liệu:
  • Tìm kiếm và truy vấn đơn giản
  • Hệ chuyên gia suy diễn

Ứng Dụng Tiềm Năng của Khai Thác Dữ Liệu

• Phân tích dữ liệu và hỗ trợ quyết định.
• Phân tích và quản lý thị trường:
  • Tiếp thị mục tiêu
  • Quản lý quan hệ khách hàng (CRM)
  • Phân tích giỏ thị trường
  • Bán chéo, phân khúc thị trường.
• Phân tích và quản lý rủi ro:
  • Dự báo
  • Duy trì khách hàng
  • Cải thiện bảo lãnh phát hành
  • Kiểm soát chất lượng
  • Phân tích cạnh tranh.
• Phát hiện gian lận
• Phát hiện các mẫu bất thường (ngoại lệ).
• Các ứng dụng khác:
  • Khai thác văn bản (nhóm tin, email, tài liệu) và khai thác Web.
  • Khai thác dữ liệu dòng (Stream data mining)
  • Tin sinh học và phân tích dữ liệu sinh học.

Quy Trình Khám Phá Tri Thức (KDD)

• Quy trình KDD bao gồm các bước sau:
  • Hiểu lĩnh vực ứng dụng (Learning the application domain).
  • Xác định tập dữ liệu mục tiêu (Identifying a target data set).
  • Xử lý dữ liệu (Data processing):
    • Làm sạch dữ liệu (Data cleaning): loại bỏ nhiễu và dữ liệu không nhất quán.
    • Tích hợp dữ liệu (Data integration): kết hợp nhiều nguồn dữ liệu.
    • Lựa chọn dữ liệu (Data selection): truy xuất dữ liệu liên quan từ cơ sở dữ liệu.
    • Biến đổi dữ liệu (Data transformation): chuyển đổi dữ liệu thành dạng phù hợp cho khai thác.
  • Khai thác dữ liệu (Data mining): áp dụng các phương pháp thông minh để trích xuất các mẫu dữ liệu.
  • Đánh giá mẫu (Pattern evaluation): xác định các mẫu thực sự thú vị.
  • Trình bày tri thức (Knowledge presentation): trình bày tri thức đã khai thác cho người dùng.
  • Sử dụng tri thức đã khám phá (Use of discovered knowledge).

Kiến Trúc Hệ Thống Khai Thác Dữ Liệu Điển Hình

• Giao diện người dùng (User Interface).
• Đánh giá mẫu (Pattern Evaluation).
• Công cụ khai thác dữ liệu (Data Mining Engine).
• Cơ sở tri thức (Knowledge Base).
• Cơ sở dữ liệu hoặc máy chủ kho dữ liệu (Database or Data Warehouse Server).
• Làm sạch dữ liệu, tích hợp và lựa chọn dữ liệu.
• Cơ sở dữ liệu (Database)
• Kho dữ liệu (Data Warehouse).
• Web
• Các kho thông tin khác (Other Info Repositories).

Khai Thác Dữ Liệu trong Trí Tuệ Kinh Doanh (Business Intelligence)

• Tiềm năng ngày càng tăng của việc hỗ trợ các quyết định kinh doanh (Increasing potential to support business decisions).
• Các bước từ dưới lên trên gồm (Bottom-up steps include): - Nguồn dữ liệu (Data Sources): Giấy, tệp, tài liệu Web, thí nghiệm khoa học, hệ thống cơ sở dữ liệu. - Tiền xử lý/Tích hợp dữ liệu, Kho dữ liệu (Data Preprocessing/Integration, Data Warehouses) - Khai thác Dữ liệu (Data Mining): Khám phá Thông tin - Thăm dò dữ liệu (Data Exploration): Tóm tắt thống kê, Truy vấn và Báo cáo - Trình bày dữ liệu (Data Presentation): kỹ thuật trực quan hóa. - Ra Quyết Định (Decision Making)
• Các nhà chuyên môn: - DBA - Chuyên viên phân tích dữ liệu (Data Analyst) - Chuyên viên phân tích nghiệp vụ (Business Analyst) - Người dùng cuối (End User)

Các Tác Vụ Khai Thác Dữ Liệu

• Các tác vụ khai thác dữ liệu được chia thành hai loại chính:
  • Tác vụ dự đoán (Prediction Tasks): Sử dụng các biến để dự đoán các giá trị chưa biết trong tương lai.
  • Tác vụ mô tả (Description Tasks): Tìm các mẫu có thể diễn giải được để mô tả dữ liệu.
• Các tác vụ khai thác dữ liệu phổ biến:
  • Phân loại (Classification): Phân loại mục vào nhóm tương ứng (Predictive, phân tích dự đoán)
  • Phân cụm (Clustering): Nhóm các mục tương tự nhau (Descriptive, mô tả)
  • Khám phá luật kết hợp (Association Rule Discovery): Tìm mối quan hệ giữa các mục (Descriptive, mô tả)
  • Khám phá mẫu tuần tự (Sequential Pattern Discovery): Tìm các mẫu theo thời gian (Descriptive, mô tả)
  • Hồi quy (Regression): Dự đoán giá trị số (Predictive, phân tích dự đoán)
  • Phát hiện độ lệch (Deviation Detection): Xác định sự khác biệt so với kỳ vọng (Predictive, phân tích dự đoán)

Phân Loại

• Phân loại = khái quát hóa cấu trúc đã biết để áp dụng cho: - Dữ liệu mới. - Ví dụ: chương trình email muốn phân loại một email là "hợp pháp" hay là "spam".
• Học máy và thống kê: - Phân loại là: xác định đối tượng với một danh mục từ một tập hợp các danh mục đã biết. - Dựa trên cơ sở một tập huấn luyện.
• Trong học máy: - Được xem là một ví dụ học có giám sát: tập huấn luyện phải xác định đúng các quan sát. - Khai thác dữ liệu không giám sát: phân cụm.

Ví Dụ Bài Toán Phân Loại

• Cho một tập hợp các bản ghi (tập huấn luyện):
  • Mỗi bản ghi chứa một tập các attribute (thuộc tính), thuộc tính quan trọng nhất ở đây là class (lớp).
• Tìm kiếm một model (mô hình) của một thuộc tính class, có chức năng phụ thuộc vào giá trị của các thuộc tính còn lại.
• Mục tiêu:
  • Các bản ghi chưa từng thấy sẽ được gán class một cách chính xác nhất có thể.
  • Một test set được sử dụng để xác định chính xác các mô hình.
  • Dữ liệu được chia thành training/test sets , training để xây dựng model và test để xác thực.

Ví Dụ về Phân Loại

• Dự đoán độ tin cậy tín dụng.
• Các attribute bao gồm:
  • Level of education (Trình độ học vấn)

  • years at present address

• Kết hợp thành mô hình để dự đoán khả năng chi trả.

Các Ví Dụ về Nhiệm Vụ Phân Loại

• Phân loại giao dịch thẻ tín dụng là hợp pháp hay gian lận.
• Phân loại độ che phủ đất (khối nước, khu đô thị, rừng, v.v.) bằng dữ liệu vệ tinh.
• Phân loại tin tức theo tài chính, thời tiết, giải trí, thể thao, v.v.
• Xác định những kẻ xâm nhập trong không gian mạng.
• Dự đoán các tế bào khối u là lành tính hay ác tính.
• Phân loại cấu trúc thứ cấp của protein là alpha-helix, beta-sheet hoặc random coil.

Ứng Dụng Của Phân Loại

• Tiếp thị trực tiếp (Direct Marketing):
  • Mục Tiêu: Giảm chi phí gửi thư bằng cách nhắm mục tiêu đến một tập hợp những khách hàng có khả năng mua một sản phẩm điện thoại di động mới.
  • Cách Tiếp Cận:
    • Sử dụng dữ liệu cho một sản phẩm tương tự được giới thiệu trước đó.
    • Chúng ta biết những khách hàng nào quyết định mua và những khách hàng nào quyết định không mua. Quyết định {mua, không mua} này tạo thành thuộc tính lớp.
    • Thu thập nhiều thông tin khác nhau liên quan đến nhân khẩu học, lối sống và tương tác của công ty về tất cả những khách hàng đó.
• Phát hiện gian lận (Fraud Detection):
  • Mục Tiêu: Dự đoán các trường hợp gian lận trong các giao dịch thẻ tín dụng.
  • Cách Tiếp Cận:
    • Sử dụng các giao dịch thẻ tín dụng và thông tin về chủ tài khoản làm thuộc tính.
    • Gán nhãn các giao dịch trước đó là giao dịch gian lận hoặc giao dịch hợp lệ. Điều này tạo thành thuộc tính lớp.
    • Tìm hiểu một mô hình cho lớp giao dịch.
• Đánh giá mức độ hài lòng của khách hàng (Customer Attrition/Churn):
  • Mục Tiêu: Dự đoán liệu một khách hàng có khả năng bị mất vào tay đối thủ cạnh tranh hay không.
  • Cách Tiếp Cận:
    • Sử dụng bản ghi chi tiết về các giao dịch với mỗi khách hàng trong quá khứ và hiện tại để tìm thuộc tính.
    • Gán nhãn khách hàng là trung thành hoặc không trung thành.
    • Tìm một mô hình cho lòng trung thành.

Thuật Toán Phân Loại

• Các thuật toán phân loại đa dạng:
  • Phân loại tuyến tính: Phân biệt tuyến tính Fisher, Hồi quy logistic, Phân loại Bayes ngây thơ (Naive Bayes classifier), Perceptron
  • Máy vectơ hỗ trợ: Máy vectơ hỗ trợ bình phương tối thiểu
  • Bộ phân loại bậc hai
  • Ước tính kernel: k-nearest neighbor
  • Tăng cường (meta-thuật toán)
  • Cây quyết định: Rừng ngẫu nhiên
  • Mạng nơ-ron
  • Học lượng tử hóa vectơ

Phát hiện Sai Lệch

• Xác định sai lệch đáng kể so với hành vi bình thường.
• Ứng dụng:
  • Phát hiện gian lận thẻ tín dụng
  • Phát hiện xâm nhập mạng
  • Xác định hành vi bất thường từ các mạng cảm biến để theo dõi và giám sát.
  • Phát hiện thay đổi trong độ che phủ rừng toàn cầu.

Luật Kết Hợp

• Học luật kết hợp: Nghiên cứu các mối quan hệ giữa các biến.
  • Mục tiêu: Tìm các chuỗi có xác suất cao cho tất cả cơ sở dữ liệu.
• Các luật kết hợp được sử dụng để xác định các quy tắc có thể được xác định trong cơ sở dữ liệu bằng cách sử dụng các thước đo như độ tin cậy (confidence).
• Ví dụ: siêu thị có thể thu thập dữ liệu về thói quen của khách hàng. Việc tạo luật kết hợp giúp việc xác định sản phẩm nào được mua nhiều thường xuyên hơn để phân bổ cho mục đích:
  • Tiếp thị
  • Phân tích
• Đôi khi được xem xét là "Phân tích giỏ hàng".

Các Bước Luật Kết Hợp

• Hạn chế các tham số đo lường khác nhau làm căn cứ để chỉ ra các quy tắc thú vị từ một tập các quy tắc khả thi, bao gồm:

  • Độ tin cậy (confidence)
  • Mức độ hỗ trợ (support) (dữ liệu được sử dụng để đáp ứng mức thông tin từ người dùng)

• Chèn tiêu chí hỗ trợ tối thiểu đồng thời

• Tạo và hình thành các quy tắc trong số các tập tiêu chí.

Định Nghĩa Khám Phá Luật Kết Hợp

• Cho một tập các ghi chú, mỗi tập chứa số mục từ một tập hợp đã cho:
  • Tạo ra các quy tắc bằng cách dự đoán sự xuất hiện của một mặt hàng để phản ánh sự xuất hiện của các quy tắc khác.
  • Milk -> Coke
  • Diaper, Milk -> Beer

Thuật Toán Luật Kết Hợp

• Theo dòng lịch sử nhiều thuật toán khác nhau đã được giới thiệu, bao gồm:

  • Thuật toán Apriori
  • Thuật toán Eclat (Chuyển đổi lớp tương đương)
  • Thuật toán tăng trưởng FP (FP: Mẫu thường xuyên), AprioriDP

• Các loại khai thác kết hợp khác:

  • Quy tắc kết hợp đa mối quan hệ
  • Quy tắc kết hợp dựa trên bối cảnh

Ứng Dụng Phân Tích Kết Hợp

• Phân tích giỏ thị trường
  • Các quy tắc được sử dụng cho các mục tiêu: - Khuyến mãi - Quản lý vị trí sản phẩm.
• Chẩn đoán báo động viễn thông.
  • Dùng để tìm tổ hợp chuỗi báo động kích hoạt trong cùng thời gian.
• Tin học y tế:
  • Tìm sự tương thích tổ hợp triệu chứng và biểu hiện bệnh.

Ứng Dụng Khám Phá Luật Kết Hợp

• Quản lý kệ siêu thị:
  • Mục tiêu: Xác định vật phẩm thường xuyên được khách hàng gom mua.
  • Phương pháp: Sử dụng các thông tin thu được qua máy quét mã vạch tại điểm thu ngân.
  • Qui tắc cổ điển: Nếu khách hàng mua tã và sữa, người đó rất có thể sẽ mua bia: Tã → Bia, support = 20%, confidence = 85%.

Phân cụm

• Phân cụm là hoạt động khám phá các cấu trúc và nhóm trong cơ sở dữ liệu được xây dựng dựa trên sự tương đồng và khác biệt không dựa vào kinh nghiệm chủ quan bên ngoài.
• Phân tích cụm giúp tạo một tập hợp các đối tượng có cách thức tương đồng.
• Phân cụm thường được sử dụng để phân tích dữ liệu thống kê liên quan đến: - Học máy - Nhận dạng mẫu - Phân tích ảnh - Thu hồi thông tin và tin sinh học.

Kỹ Thuật Phân Cụm

• Mục tiêu:
  • Gộp từng nhóm đối tượng theo liên kết hoặc mối liên quan.
• Dựa theo khoảng cách Euclid để phân loại trong không gian 3-D.
  • Khoảng cách nội cụm được thu nhỏ
  • Khoảng cách giữa các cụm được tối đa hóa

Phân cụm (Tiếp)

• Algorithmic Categories liên quan đến khả năng liên kết giữa:
  • Phân cụm kết nối (phân cụm theo thứ bậc)
  • Phân cụm Centroid
• Dựa trên phân bổ
• Dựa trên mật độ
• Năng suất thuật toán đang được cải thiện.
• Các thuật toán phân cụm (Clustering algorithms).

Phương Pháp Phân Cụm

• Mục tiêu: - Tập hợp dữ liệu. - Xác định phạm trù.
• Phương pháp:
  • Dữ liệu trong một cụm có nhiều điểm tương đồng hơn.
  • Các thuộc tính khác biệt ít tương đồng hơn.
• Khoảng cách Euclid nếu thuộc tính là liên tục.
• Các phép đo khác theo từng trường hợp.

Ứng Dụng Phân Tích Cụm

• Khách hàng quen mặt:
  • Xây dựng hồ sơ mục tiêu.
• Nhóm các tài liệu liên quan để duyệt:
  • Gen nhóm có tính năng quen thuộc
  • Nhóm các cổ phiếu có biến động tương tự
• Tóm tắt:
  • Giảm kích thước cơ sở dữ liệu.

Ứng Dụng Phân Loại 1

• Phân đoạn thị trường:
  • Mục tiêu: Phân chia một thị trường thành các nhóm khách hàng riêng biệt, nơi bất kỳ nhóm con nào cũng có thể được chọn làm mục tiêu thị trường.
  • Phương pháp:
    • Thu thập nhiều thông tin khác nhau dựa trên yếu tố địa lý, lối sống và quan hệ giữa khách hàng.
    • Tìm kiếm cụm khách hàng tương đồng.
    • Đo lường chất lượng gom cụm bằng cách quan sát mô hình của khách hàng.

Ứng Dụng Phân Loại 2

• Đối chiếu các văn bản:
  • Mục tiêu: gom các văn bản có nhiều nét tương đồng
  • Phương pháp: lập danh sách các keyword diễn ra thường xuyên
  • Lợi ích: để tham khảo và truyền đạt thông tin.

Hồi Quy

• Hồi quy được sử dụng để cho ra các giá trị thay vì gom nhóm.
• Nghiên cứu mở rộng trong thống kê và mạng thần kinh.
• Các ví dụ:
  • Ước tính doanh số cho sản phẩm mởi.
  • Hồi đáp các điều kiện như nhiệt độ, khoảng cách....
  • Các chỉ số Stock trong chuỗi thời gian.

Các Vấn Đề Chính trong Khai Thác Dữ Liệu

• Phương pháp và tương tác người dùng để khai thác:
  • Các loại kiến thức cần cho và từ khai thác.
  • Sử dụng và kích hoạt liên kết cơ sở dữ liệu.
  • Khai thác dữ liệu đa nhiệm.
• Tương tác đa nền tảng:
  • Hỗ trợ và cho phép thay đổi truy vấn một cách có kiểm soát
• Chú trọng đến kiến thức chuyên môn
  • Các qui trình phát hiện
  • Các mẫu trong kết quả
• Ngôn ngữ truy vấn dữ liệu và khai thác dữ liệu riêng.
  • Tạo ngôn ngữ truy vấn nâng cao tích hợp các ngôn ngữ DB/DW.
• Trình bày và trực quan
  • Sử dụng ngôn ngữ dễ hiểu, các biểu diễn.
• Quản lý độ nhiễu thông tin:
  • Dữ liệu có thể chưa đầy đủ.
• Dánh giá khuôn mẫu.
  • Kĩ thuật tiếp cận các khuôn mẫu đang được khám phá, bao gồm: - Xác nhận/phác thảo niềm tin - Đo các yếu tố chủ quan

Các Thách Thức về Hiệu Suất và Quy Mô

• Hiệu quả và khả năng mở rộng cần được bảo đảm
• Cần đáp ứng với:
  • khối lượng data lớn
  • thời gian chạy cần dự đoán trước và chấp nhận được
• Triển khai thuật toán từng phần song song.
  • Phân vùng data
  • Khối lượng data vừa đủ để sử dụng.
• Các loại hình cơ sở dữ liệu (CSDL):
  • CSDL phức tạp chứa nhiều vật phẩm, dữ liệu đa phương tiện, dữ liệu không gian.
• Khai thác web trở nên khó khăn hơn:
  • Các CSDL phức tạp là lĩnh vực phát triển nhanh.

Lịch Sử Tóm Tắt của Cộng Đồng Khai Thác Dữ Liệu

• Hội thảo IJCAI năm 1989 về Khám phá Tri thức trong Cơ sở Dữ liệu
  • Khám phá kiến thức trong CSDL

• 1991-1994 hội thảo khám phá kiến thước và dữ liệu trong cơ sở dữ liệu

• 1995-1998 các hội nghị quốc tế về khai thác dữ liệu
  • Journal of Data Mining and Knowledge Discovery
• Các tổ chức thảo luận:
  • ACM SIGKDD -PAKDD -PKDD -SIAM-Data Mining -IEEE ICDM -WSDM
• ACM Transactions on KDD

Các Hội Nghị và Tạp Chí về Khai Thác Dữ Liệu

• Các tạp chí tham khảo:
  • ACM SigKDD
  • ACM SIGMOD
  • IEEE ICDE
  • Các tạp chí liên quan khác
  • Các công trình hội nghị thường niên thường có.
• Tạp chí
  • Data Mining and Knowledge Discovery -IEEE Trans. Đang được sử dụng
  • KDD Explorations -ACM Trans.

Tóm lược

• Khai thác dữ liệu là khám phá các nhóm và kiến thức từ các dữ liệu.
• Quy trình KDD
  • Vệ sinh dữ liệu thích hợp
  • Xác định dữ liệu tương thích(dung lượng)
  • Quá trình gom data (khai thác thích hợp)
  • Đánh giá hiệu suất
  • Thể hiện và chuyển đạt
• Khai thác có thể chạy giữa các tập dữ liệu khác nhau.
• Các chức năng có thể kể đến là: mô tả ký tự, so sánh kết hợp....
• Vấn đề chính của công nghệ và ứng dụng Khai thác (data) (DM).