CHƯƠNG 1: TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ MẠNG XÃ HỘI 1. Khai phá dữ liệu 1. Khai phá dữ liệu là gì? Khai phá dữ liệu (datamining) đƣợc định nghĩa nhƣ là một quá trình chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu. Một ví dụ hay đƣợc sử dụng là việc khai thác vàng từ đá và cát, Dataming đƣợc ví nhƣ công việc "Đãi cát tìm vàng" trong một tập hợp lớn các dữ liệu cho trƣớc.
Thuật ngữ Datamining ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lƣợng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng tự với từ Datamining nhƣ Knowledge Mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/patern analysis (phân tích dữ liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging (nạo vét dữ liệu),. Sau đây là một số định nghĩa mang tính mô tả của nhiều tác giả về khai phá dữ liệu: Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phƣơng pháp đƣợc dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chƣa biết bên trong dữ liệu”. Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó ta tìm kiếm các mẫu thông tin chƣa biết và bất ngờ trong CSDL lớn”.
Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tầm thƣờng nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu đƣợc”. Quá trình khai phá dữ liệu Khai phá dữ liệu là một bƣớc trong bảy bƣớc của quá trình KDD (Knowleadge Discovery in Database) và KDD đƣợc xem nhƣ 7 quá trình khác nhau theo thứ tự sau [1]: 1. Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu và các dữ liệu không cần thiết. TIEU LUAN MOI download : skknchat@gmail.
Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xử lý (data cleaning & preprocessing). Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không đầy đủ (incomplete data),. Chuyển đổi dữ liệu: Các dữ liệu đƣợc chuyển đổi sang các dạng phù hợp cho quá trình xử lý.
Khai phá dữ liệu (data mining): Là một trong các bƣớc quan trọng nhất, trong đó sử dụng những phƣơng pháp thông minh để chắt lọc ra những mẫu dữ liệu. Ƣớc lƣợng mẫu (knowledge evaluation): Quá trình đánh giá các kết quả tìm đƣợc thông qua các độ đo nào đó. Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho ngƣời dùng. Các chức năng chính của khai phá dữ liệu Data Mining đƣợc chia nhỏ thành một số hƣớng chính nhƣ sau [1]: • Mô tả khái niệm (concept description): 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. • Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính & thị trƣờng chứng khoán,.
• Phân loại và dự đoán (classification & prediction): xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ: phân loại vùng địa lý theo dữ liệu thời tiết. Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của “machine learning” nhƣ cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network),. Ngƣời ta còn gọi phân loại là học có giám sát (học có thầy).
TIEU LUAN MOI download : skknchat@gmail.com 5 • Phân cụm (clustering): xếp các đối tƣợng theo từng cụm (số lƣợng cũng nhƣ tên của cụm chƣa đƣợc biết trƣớc. Ngƣời ta còn gọi phân cụm là học không giám sát (học không thầy). • Khai phá chuỗi (sequential/temporal patterns): tƣơng tự nhƣ khai phá luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. 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 vì nó có tính dự báo cao.
Các kỹ thuật khai phá dữ liệu 1. Phân loại (phân loại - classification) 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 thuật toán phân loại 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 loại. Nhƣ thế quá trình phân loại 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 các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thoả 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” [3]. Ví dụ: Một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo là: họ tên, tuổi, giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ lãnh đạo của nhân viên. Hồi qui (regression) 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 loại, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải 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 hoá cũng đƣợc sử dụng, ví dụ: 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 bằng các thiết bị cảm biến từ xa; ƣớc lƣợng sác xuất ngƣời bệnh có thể chết bằng cách kiểm tra các triệu chứng; dự báo nhu cầu của ngƣời dùng đối với một sản phẩm, … [3]. TIEU LUAN MOI download : skknchat@gmail.
Phân cụm (clustering) Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể vừa thuộc nhóm này lại vừa thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm nhƣ phát hiện tập các khách hàng có phản ứng giống nhau trong CSDL tiếp thị; xác định các quang phổ từ các phƣơng pháp đo tia hồng ngoại, … Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm mật độ xác suất đa biến/các trƣờng trong CSDL [3].
Tổng hợp (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 tổng hợp 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”. Lƣu ý rằng luật dạng này có các khác biệt so với luật phân loại. 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]. Mô hình hoá 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. 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 đề là đú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 loại 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]. TIEU LUAN MOI download : skknchat@gmail. Phát hiện sự biến đổi và độ lệch (change and deviation dectection) Nhiệm vụ này tập trung 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 hay lệch theo nhóm.
Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ liệu, ở đây tính 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 đƣợ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 thƣờng ảnh hƣởng đến việc thiết kế và chọn phƣơng pháp khai phá dữ liệu khác nhau [3]. Mạng xã hội là gì? Mạng xã hội là việc thực hiện mở rộng một số lƣợng các mối quan hệ của doanh nghiệp hoặc các quan hệ xã hội bằng cách tạo ra các kết nối thông qua các cá nhân ngƣời dùng, thƣờng là thông qua các trang web mạng xã hội nhƣ Facebook, Twitter, LinkedIn và Google+[16].
Dựa trên sáu cấp độ của khái niệm ngăn cách (ý tƣởng rằng bất kỳ hai ngƣời trên hành tinh này có thể thực hiện liên lạc thông qua một chuỗi không quá năm ngƣời trung gian), mạng xã hội thiết lập các cộng đồng trực tuyến kết nối với nhau (đôi khi đƣợc gọi là đồ thị xã hội) giúp con ngƣời liên lạc đƣợc với những ngƣời họ biết – những ngƣời họ không thể gặp bằng phƣơng thức khác [16].