Công ty TNHH cổ phần dịch vụ thương mại và truyền thông – Thế giới trẻ

ông ty thực hiện là tổ chức sự kiện, xây dựng hệ thống thông tin giải trí. Với đội ngũ nhân viên làm việc trẻ tuổi, nhiệt tình và tâm huyết đang đưa công ty ngày một phát triển Hiện tại M2u đã xây dựng một hệ thống giải trí bao gồm : Dj.m2u.vn: là một trang web nghe nhạc chuyên giới thiệu về dòng nhạc DJ (disk jocker) một dòng nhạc mới suất hiện ở Việt Nam Forum.m2u.vn: diễn đàn nơi thành viên có thể trao đổi chia sẽ thông tin. Trang chủ m2u.vn: Trong tương lai trang chủ m2u sẽ tích hợp ngoài 2 hệ thống trên sẽ có : trang breakdance – hệ thống video cho phép chia sẻ hình ảnh , thông tin tới mọi người. Kênh shopping cho phép buôn bán, trao đổi hàng trên mạng…. 1.3. CHỨC NĂNG VÀ NHIỆM VỤ Tổ chức các sự kiện, chương trình giải trí mang tính xã hội và giáo dục cao. Ví dụ : Các hoạt động từ thiện quyên góp ủng hộ nạn nhân chất độc gia cam, chương trình lễ hội nhạc trẻ … Phát triển quảng cáo nhằm quảng bá hình ảnh khách hàng tới mọi người. Xây dựng hệ thống chương trình giải trí dành cho đối tượng thanh niên thông qua việc xây dựng hệ thống liên hợp gồm nghe nhạc , xem phim, diễn đàn …. Hợp tác chuyển giao công nghệ với các công ty đối tác khác cùng thực hiện. 1.4. BỘ MÁY TỔ CHỨC Tuy công ty với số lượng thành viên hiện nay còn khiêm tốn nhưng bộ máy của tổ chức của công ty như sau: `Giám đốc Phòng quản lý nhân sự Phòng nội dung Phòng thiết kế và kỹ thuật 1.5. LÝ DO CHỌN ĐỀ TÀI Công nghệ thông tin hiện đã trở nên rất phổ biến trong thời điểm này. Có thể nói việc tin học hóa các công việc , các qui trình sản xuất đã tạo nên những đột biến lớn trong việc quản lý, sản xuất … Tuy nhiên, có một yếu tố mọi người thường bỏ qua khi xây dựng hệ thống thông tin đo là dữ liệu. Thông thường các hệ thống xây dựng sẽ chỉ chú trọng tới các thông tin hiện thời hoặc những thông tin ở thời điểm xung quanh khoảng thời gian xem xét. Ví dụ như thông tin từ 2-3 năm trở lại. Chính vì thế lượng thông tin lưu trữ qua một thời kỳ dài sẽ trở nên rất lãng phí. Do đó cần phải có một chiến lược, chiến thuật để khai thác dữ liệu, dựa trên các thông tin đó để đưa ra những qui luật áp dụng trong thực tế. Trong thời gian thực tập, tôi nhận thấy bên công ty có rất nhiều vấn đề cần quyết định thực hiện. Ví dụ như quyết định ký kết hợp đồng dự án, quyết định tăng thưởng lương nhân viên … Chính vì vậy tôi đã chọn đề tài này nhằm mục đích tìm hiểu sâu hơn về cây quyết định cũng như xây dựng chương trình giúp công ty có thể đưa ra những quyết định hợp lý mỗi khi thực hiện. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 2.1. SƠ LƯỢC VỀ KHAI PHÁ TRI THỨC 2.1.1. Tổng quan Ngày nay, khối lượng thông tin do con người khám phá và được lưu trữ ngày càng nhiều đặc biệt là trong những thập niên gần đây. Dữ liệu được tích lũy ngày càng nhiều và tốc độ phát triển của dữ liệu tích lũy ngày càng cao. Một số báo cáo cũng đã nhận định rằng lượng thông tin trên toàn cầu tăng khoảng gấp đôi sau hai năm, theo đó số lượng cũng như kích cỡ các cơ sở dữ liệu cũng tăng lên nhanh chóng. Trong rất nhiều ngành từ kinh tế, xã hội đến khoa học công nghệ, các nhà nghiên cứu, quản lý, ứng dụng và triển khai đang phải đối mặt với một thách thức to lớn là trong tay có một khối lượng tài nguyên thông tin khổng lồ nhưng trong nhiều trường hợp lại thấy thiếu tri thức. Lượng thông tin và dữ liệu khổng lồ này thực sự đã trở thành nguồn tài nguyên có giá trị bởi thông tin và dữ liệu là yếu tố then chốt trong quá trình xử lý, điều hành, nghiên cứu,… Việc khai thác những thông tin, tri thức tiềm ẩn mang tính dự đoán từ các cơ sở dữ liệu lớn, khổng lồ đã và đang ngày càng trở thành lĩnh vực thiết yếu trong cuộc sống con người Những năm năm mươi của thế kỷ trước, cha đẻ của ngành khoa học máy tính là A. Turing, J.von Neumann đã phân tích, so sánh, đánh giá và đưa ra nhiều nhận xét lạc quan về khả năng tư duy của máy tính trong tương lai. Những thành tựu bước đầu của máy tính để tự động hóa chứng minh các định lý trong logic toán, trong các trò chơi giải trí trí tuệ cao, phiên dịch,… ngay từ thập niên năm mươi tuy còn khá thô sơ nhưng cũng đủ để kích thích một chân trời mới cho nhiều ngành khoa học và công nghệ tri thức cho các thập niên tiếp theo. Và trong quá trình phát triển đó, con người có dịp tìm hiểu sâu hơn bản thân hoạt động nhận thức của mình, hệ thống tri thức mà mình tích lũy được, đưa ra các thuộc tính của tri thức và những đòi hỏi đối với tri thức trong hoạt động thực tiễn của con người trong một môi trường ngày càng nhiều biến động đồng thời cũng thúc đẩy việc nghiên cứu những phương pháp khoa học mới và giải pháp công nghệ để biểu diễn, thu thập và tìm kiếm tri thức, xử lý tri thức, quản trị tri thức nhằm đáp ứng các nhu cầu của con người trong quá trình vận động. Quá trình phát triển của khai phá tri thức có thể chia theo một số bước như sau: Tri thức chắc chắn và các phương pháp suy luận logic tất định. Tri thức không chắc chắn và việc tìm quy luật cho “cái” không chắc chắn Tri thức không chắc chắn trong môi trường biến động Chúng ta có thể tổng hợp khái niệm khai phá tri thức như sau: Khai phá tri thức (đôi khi còn gọi là khai phá dữ liệu hay khám phá tri thức), một cách chung nhất là một quá trình phân tích dữ liệu từ nhiều nguồn dữ liệu khác nhau và tổng hợp dữ liệu thành các tri thức. 2.1.2. Các quá trình khai phá tri thức Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình sau: Hình 1. Sơ đồ mô tả sơ bộ quá trình khai phá dữ liệu Trong đó, mỗi bước là mỗi quy trình nắm giữ một vai trò riêng và có các nhiệm vụ khác nhau cho mỗi bước, bao gồm: Quy trình 1. Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề (Problem Understanding and Data Understanding). Tại quy trình này, việc xác định vấn đề và xác định không gian dữ liệu để giải quyết vấn đề bao gồm chọn lựa các nguồn dữ liệu, phạm vị ứng dụng của không gian bài toán để từ đó hình thành nên quy mô của bài toán. Việc xác định vấn đề và không gian dữ liệu để giải quyết vấn đề là chiến lược quyết định thành công hay thất bại trong suốt quá trình khai phá dữ liệu. Quy trình 2. Chuẩn bị dữ liệu (Data preparation), bao gồm các quá trình làm sạch dữ liệu (data cleaning), tích hợp dữ liệu (data integration), chọn dữ liệu (data selection), biến đổi dữ liệu (data transformation). Làm sạch dữ liệu chính là việc trích lọc dữ liệu cần và loại bỏ các dữ liệu nằm ngoài phạm vi của bài toán nhằm khám phá tri thức theo một số tiêu chí nhất định. Tích hợp dữ liệu, chọn dữ liệu và biến đổi dữ liệu cho phép tác chuyển đổi, tính toán xử lý để các dữ liệu có khuôn dạng khác nhau về dạng dữ liệu phù hợp, rút gọn dữ liệu hoặc chỉnh sửa những dữ liệu sai lệch vì hầu hết các cơ sở dữ liệu lớn thường dư thừa hoặc sai lệch dữ liệu. Sau bước chuẩn bị, dữ liệu dùng cho khám phá tri thức đã được làm mịn phù hợp cho bước khai phá dữ liệu tiếp sau. Quy trình 3. Khai phá dữ liệu (Data Mining), quá trình này bắt đầu khi hệ thống dữ liệu đã được xây dựng và biến đổi. Tại đây, công việc phân tích và đưa ra các quyết định lựa chọn khai thác dữ liệu, áp dụng các kỹ thuật xây dựng, khai phá dữ liệu để trích chọn các mẫu, mô hình, các mối quan hệ ẩn trong dữ liệu để từ đó khai phá tri thức cần thiết. Các lớp mô hình phổ biến của các phương pháp khai phá dữ liệu là: Mô hình dự đoán bao gồm phân lớp (classification), hồi quy (regression) và phân cụm (clustering) Mô hình phụ thuộc, chẳng hạn như các mô hình đồ thị hoặc ước lượng mật độ Mô hình tóm lược như tìm ra các mối quan hệ giữa các trường, các mối liên kết Mô hình kiểm tra sự thay đổi để phát hiện độ lệch trong dữ liệu và tri thức Quy trình 4. Tổng hợp kết quả và đánh giá kết quả (Evaluation), Mục đích của giai đoạn này là hiểu tri thức đã tìm được từ việc khai phá dữ liệu đặc biệt là làm sáng tỏ và dự đoán chúng. Các kết quả khai phá sẽ được tổng hợp dưới nhiều dạng khác nhau nhằm mục đích hỗ trợ ra quyết định. Nghĩa là các thông tin hữu ích tìm được từ việc khai phá sẽ chuyển thành dữ liệu gần gũi với người sử dụng hơn. Kinh nghiệm của các nhà khoa học cho thấy rằng các mẫu hay các mô hình phát hiện từ việc khai phá dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay, mà quá trình khám phá tri thức cần phải lặp đi lặp lại nhiều lần có sự điều chỉnh, bước sau dựa vào kết quả của bước trước đó theo các tri thức khám phá được, lần sau hoàn chỉnh hơn lần trước. Các tri thức khám phá được sẽ được đánh giá theo những tiêu chí nhất định. Để có thế đánh giá các luật được áp dụng trong qui trình khám phá tri thức, người ta thường chia dữ liệu thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại quy trình này một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ước lượng các luật khả thi. Quy trình 5. Triển khai tri thức được khai phá (Deployment) Đây là giai đoạn áp dụng tri thức đã khám phá được vào sử dụng trong thực tế. Trong một số trường hợp, người ta sử dụng tri thức này mà không cần đưa vào một hệ thống máy tính. Hoặc là, các tri thức này có thể được đặt vào máy tính và được khai thác bởi các chương trình, chẳng hạn như đưa chúng vào làm tri thức cho các hệ chuyên gia, sau đó đưa các kết quả tìm được vào việc sử dụng thích hợp của người dùng, đây là mục đích cuối cùng của quá trình khám phá tri thức. Mặc dù được tóm tắt thành năm giai đoạn như trên, nhưng thực chất quá trình xây dựng và thực hiện việc khám phá tri thức không chỉ phải tuân theo các bước cố định mà các quá trình này còn có thể được lặp đi lặp lại ở một hoặc một số giai đoạn, lần sau sẽ hoàn thiện hơn lần trước và giai đoạn sau dựa vào kết quả của giai đoạn trước và cứ tiếp tục như thế sẽ làm cho quá trình khai phá và tìm kiếm dữ liệu càng ngày càng hoàn thiện hơn, trong sáng hơn. 1.2. KHAI PHÁ DỮ LIỆU Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình trích lọc các thông tin có giá trị ẩn trong lượng lớn dữ liệu được lưu trữ trong các CSDL hoặc các kho dữ liệu,… Khai phá dữ liệu cũng còn được coi là một quá trình tìm kiếm, khám phá ở nhiều góc độ để tìm ra các mối tương quan, các mối liên hệ dưới nhiều góc độ khác nhau nhằm tìm ra các mẫu hay các mô hình tồn tại bên trong cơ sở dữ liệu và đang bị dữ liệu (có khối lượng lớn) che khuất. Để trích rút các mẫu, mô hình tiềm ẩn có tính “tri thức” ta phải tìm và áp dụng các phương pháp, kỹ thuật khai phá sao cho phù hợp với tính chất, đặc trưng của dữ liệu và mục đích sử dụng. Tuy khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình khám phá tri thức từ dữ liệu nhưng nó lại là bước tiên quyết, quan trọng và ảnh hưởng đến toàn bộ quá trình. Việc khai phá dữ liệu nhằm các mục đích chính như sau: Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu hướng trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như: các tổ chức, doanh nghiệp, nhà nghiên cứu,…. đưa ra những quyết định kịp thời, được định hướng trên những tri thức được khám phá mang lại; Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá trình xử lý dữ liệu để tìm ra tri thức. 2.2.1. Chức năng của khai phá dữ liệu Các chức năng của khai phá dữ liệu có thể dựa trên các dạng của các mô hình từ cơ sở dữ liệu thông qua hai loại chính là loại khai phá dữ liệu dựa trên các công việc khai phá dữ liệu mô tả và khai phá dữ liệu dự báo: Khai phá dữ liệu mô tả sẽ mô tả các thuộc tính tổng quát của dữ liệu trong từng cơ sở dữ liệu dựa trên các phân tích và mô tả một tập các mẫu đã biết trong khả năng nhận thức của con người, giúp con người có thể hiểu rõ hơn về tri thức và dữ liệu của họ. Khai phá dữ liệu loại dự báo sẽ thực hiện việc suy luận trên dữ liệu để đưa ra các dự báo nhằm phân tích tập dữ liệu huấn luyện và tạo ra một mô hình cho phép dự đoán các mẫu, mô hình mới chưa biết Trong một số trường hợp các đối tượng có thể phân tích dữ liệu nhằm tìm ra mô hình một cách song song do không thể tìm ra được mô hình nào là phù hợp, chính vì vậy để có thể khai phá Trong vài trường hợp, người dùng có lẽ không có ý kiến về dạng mô hình trong dữ liệu của họ, những cái nào có thể thú vị, vì thế họ có lẽ thích tìm kiếm nhiều dạng mô hình khác nhau một cách song song. Vì vậy điều quan trọng là làm sao để có một hệ thống khai phá dữ liệu có thể khai phá được đa dạng mô hình chứa đựng được nhiều ứng dụng và mong đợi khác nhau của người dùng. Hơn nữa, các hệ thống khai phá dữ liệu nên có thể khám phá các mô hình ở nhiều mức độ trừu tượng khác nhau. Mặt khác, các hệ thống cơ sở dữ liệu cũng nên cho phép người sử dụng xác định rõ các gợi ý chỉ dẫn hoặc làm tập trung việc tìm kiếm các mô hình thú vị. Vì các mô hình có lẽ không nắm bắt được tất cả dữ liệu trong cơ sở dữ liệu, nên một tiêu chuẩn do độ chắc chắn và độ tin cậy thường được gắn kết với từng mẫu được khám phá 2.2.2. Các kỹ thuật khai phá dữ liệu Các kỹ thuật khai phá dữ liệu bao gồm các kỹ thuật chính 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ó. Các kỹ thuật này gồm có: phân cụm (clustering), tóm tắt (summerization), trực quan hóa (visualiztion), phân tích sự phát triển và độ lệch (Evolution and deviation analyst), phân tích luật kết hợp (association rules)... Dự đoán dữ liệu Kỹ thuật này 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. Các kỹ thuật này gồm có: phân lớp (classification), hồi quy (regression)... Phân cụm dữ liệu Mục tiêu chính của phương pháp phân cụ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 cụm sao cho các đối tượng thuộc cùng một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy. Không giống như phân lớp dữ liệu, phân cụ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 cụ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 cụ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 cụm thu được. Phân cụ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 cụ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. Phân lớp dữ liệu và hồi qui Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu 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ó thầy (supervised learning) khác với phân cụm dữ liệu là học không có thầy (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. Phương pháp hồi qui khác với phân lớp dữ liệu ở chỗ, hồi qui dùng để dự đoán về các giá trị liên tục còn phân lớp dữ liệu thì chỉ dùng để dự đoán về các giá trị rời rạc. Khai phá luật kết hợp 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. Các luật kết hợp là một dạng biểu diễn tri thức, hay chính xác là dạng mẫu của hình thành tri thức. Phương pháp nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập các luật kết hợp tìm được. Nhược điểm cơ bản của phương pháp này là sự gia tăng nhanh chóng khối lượng tính toán và các thông số. Tuy nhiên, với sự phát triển nhanh chóng và mạnh mẽ của phần cứng thì vấn đề này cũng được khắc phục. Khai phá dữ liệu sử dụng mạng Neural Mạng Neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng Neural có thể đưa ra ý nghĩa các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Một trong ưu điểm phải kể đến của mạng Neural là khả năng tạo ra các mô hình dự đoán do độ chính xác cao, có thể áp dụng cho nhiều các bài toán khác nhau, đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như: phân lớp, phân nhóm, mô hình hoá, dự báo… Mẫu chiết suất bằng mạng Neural được thể hiện bằng một trong những nút đầu của mạng. Mạng Neural sử dụng các hàm số chứ không sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Đặc điểm của mạng Neural là không cần gia công dữ liệu nhiều, trước khi bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên, để có thể sử dụng mạng Neural có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như: Mô hình mạng là gì? Mạng cần bao nhiêu nút? Số lớp ẩn sử dụng cho mạng là như thế nào? Khi nào thì việc học dừng? Ngoài ra còn có nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước khi đưa vào mạng Neural để mạng có thể hiểu được. Mạng Neural được đóng gói với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được họ đảm bảo các mô hình này làm việt tốt. Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. Khai phá dữ liệu sử dụng thuật giải di truyền Đây là phương pháp không chỉ thực hiện phát hiện tri thức mà còn phục vụ rất nhiều bài toán khác. Ví dụ bài toán tối ưu hoá hoặc lập lịch. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập dữ liệu ban đầu bằng ký tự nhị phân và gọi là những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến chúng ta biến đổi quần thể gene ban đầu và loại đi một số gene, làm cho số lượng gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho ta lời giải tối ưu toàn cục (khác với phương pháp mạng Neural). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể. Nói theo nghĩa rộng, giải thuật di truyền mô phỏng lại hệ thống tiến hoá trong tự nhiên, chính xác hơn là các giải thuật chỉ ra tập các cá thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ. Giải thuật di truyền là một giải thuật tối ưu hoá, được sử dụng rất rộng rãi trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng Neural. Sự kết hợp của nó với các giải thuật khai phá dữ liệu ở chỗ tối ưu hoá là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất. Khai phá dữ liệu sử dụng cây quyết định Phân lớp khai phá dữ liệu luật là một cách tiếp cận quan trọng trong qusa trình khai phá dữ liệu, mục tiêu nhằm tạo ra một tập luật tương đối nhỏ có đọ đúng đắn cao từ cơ sở dữ liệu lớn. Cây quyết định được cọi là phương pháp tiếp cận truyền thống cho phép phân lớp luật. Cây quyết định đưa ra cách tiếp cận heuristic nhằm tìm kiếm các thuộc tính tốt nhất và dẫn đến kết quả cao nhất. Tuy nhiên, cây quyết định có một số hạn chế khi triển khai lựa chọn thuộc tính khi xây dựng cây. Các hạn chế của cây quyết định là các trường hợp phân rã và tái tạo, vấn đề khi phân rã là khi cây quyết định cần phân chia dữ liệu nhiều lần để có thể nhận biết được toàn bộ dữ liệu mẫu. Vấn đề khi tái tạo là một cây con cần được xây dựng lại nhiều lần làm cho cây quyết định có độ sâu quá lớn và khó hiểu. Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên của các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của thuộc tính của đối tượng tới lá. Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân chia dữ liệu đã cho thành các lớp đã được định nghĩa. Trong thực tế, tập các cây quyết định có thể có đối với bài toán này rất lớn và rất khó có thể duyệt hết một cách tường tận. Có nhiều phương pháp xây dựng cây quyết định khi khai phá dữ liệu, đó là các phương pháp sử dụng các thuật toán CLS, ID3, C4.5,… và một phương pháp tương đối tiên tiến hiện nay và đang là tâm điểm được nghiên cứu là phương pháp xây dựng cây quyết định dựa trên phụ thuộc hàm. Tuy nhiên trong thực tập lần này, công việc chính của em sẽ nghiên cứu về giải thuật C4.5 mà thôi. 2.2.3. Các thách thức khi khai phá dữ liệu Mặc dù các phương pháp được ứng dụng trong khai phá dữ liệu rất phong phú và đa dạng cho việc giải quyết các bài toán thực tế hiện nay. Tuy nhiên vấn đề này gặp không ít khó khăn và thách thức lớn từ việc chuẩn bị cho đến việc khai phá cũng như việc trình bày và sử dụng tri thức đã được tìm thấy. Khó khăn về cơ sở dữ liệu Việc khai phá dữ liệu thường dựa trên một tập cơ sở dữ liệu lớn, các dữ liệu trong thực tế thường phức tạp, nhập nhằng, đa dạng, có tính chất thời gian, không đầy đủ hoặc nhiễu,… Ngoài ra, cơ sở dữ liệu có thể được lưu trữ phân tán, với số lượng thuộc tính và bản ghi quá đa dạng và phong phú dẫn đến độ phức tạp của bài toán quá lớn, không gian tìm kiếm rộng. Vấn đề dữ liệu phụ thuộc vào thời gian cũng gây không ít khó khăn khi khai phá, các dữ liệu này phụ thuộc vào thời gian và tính chất của dữ liệu thay đổi vào thời điểm quan sát hay khai phá nên tính đúng đắn hay tri thức khai phá được phụ thuộc vào thời điểm sử dụng. Có những dữ liệu chỉ đúng trong từng thời điểm nhất định nên chính điều này có thể gây nên các hiệu ứng phụ khi khai phá dữ liệu. Một số khó khăn nữa khi khai phá dữ liệu liên quan đến cơ sở dữ liệu là các thuộc tính không phù hợp, các bộ giá trị không đầy đủ gây nên nhầm lẫn hoặc ảnh hưởng tới quá trình khai phá. Đôi khi, các thuộc tính còn bị thiếu gây nên các giá trị của dữ liệu bị giảm. Vấn đề nhập nhằng, không chắc chắn của dữ liệu cũng cần được quan tâm, với những dữ liệu dạng này gây nên sự phát sinh lỗi hoặc tri thức không đúng. Mối quan hệ, liên quan giữa các thuộc tính cũng phải được xét đến, bộ thuộc tính hay giá trị có cấu trúc phân cấp, phân lớp hay có mối liên quan với nhau đôi khi cũng gây nên các lỗi trong cơ sở dữ liệu phục vụ khai phá. Một số vấn đề cần quan tâm Khi khai phá dữ liệu, các vấn đề cần quan tâm nảy sinh từ khi bắt đầu đến khi sử dụng lại tri thức được khai phá, tuy vậy có một số vấn đề mà chúng ta cần quan tâm khi khai phá dữ liệu, đó là: Sự quá khổ (overfitting): Điều này thường xuyên xảy ra đối với một hệ thống khai phá dữ liệu. Khi sử dụng thuật toán để đưa ra một mô hình kết quả rất có thể mô hình kết quả không phù hợp hoặc không có khả năng đáp ứng cho các tri thức dữ liệu dạng mới dẫn đến mô hình hoạt động không hiệu quả. Để có thể khắc phục được sự quá khổ này, người ta thường dùng các thuật toán kiểm tra chéo kết hợp với một số nguyên tắc cụ thể như thống kê, dự đoán, cắt tỉa,… Tính dễ hiểu của mô hình kết quả: Mô hình kết quả là đối tượng quan trọng nhất trong suốt quá trình khai phá dữ liệu, đây cũng là sản phẩm cuối cùng của quá trình khai phá. Mô hình kết quả thu được phải dễ hiểu cho người sử dụng như được thể hiện dưới dạng đồ họa, trực quan, có cấu trúc đơn giản, dễ biểu diễn bởi ngôn ngữ tự nhiên hay các kỹ thuật quen thuộc,… Sự tác động của người sử dụng tri thức vào các tri thức thu được: Vấn đề này là cốt yếu trong quá trình khai phá dữ liệu, đây là giai đoạn cuối cùng cũng như là mục đích cuối cùng của quá trình khai phá. Những tri thức này được sử đụng để phân tích, dự đoán sự phân bố xác suất dữ liệu trước đó hay phục vụ cho một công đoạn khai phá ra tri thức mới hoặc hỗ trợ cho người sử dụng ra quyết định ngay trong lĩnh vực đó. Hoặc chúng có thể được tổng hợp lại dưới dạng các báo cáo để hỗ trợ cho các quyết định khác nhau 2.2.4. Đánh giá, kết luận Khai phá dữ liệu là khâu cơ bản trong quá trình phát hiện tri thức từ dữ liệu. Để thực hiện nhiệm vụ này người ta thường sử dụng nhiều phương pháp khác nhau từ các phương pháp hồi quy, tương quan, kiểm định giả thuyết,… là các phương pháp quen thuộc của phân tích thống kê đến các phương pháp mới mô phỏng quá trình học đối với các bài toán phân loại và xếp nhóm trên các mạng nơ ron nhân tạo, mô phỏng quá trình tiến hóa sinh học để xây dựng các giải thuật “di truyền” giải bài toán bằng các phép lai ghép, chọn lọc, trao đổi chéo, đột biến “bắt chước” các phép biến đổi gen trong sinh học, xây dựng cây quyết định để rút ra các luật quyết định chính xác hoặc các tri thức chính xác về một lĩnh vực nào đó. Quá trình khai phá tri thức trên dữ liệu là một quá trình lâu dài và phức tạp nhằm nhận biết các mẫu hoặc mô hình ẩn chứa trong dữ liệu dựa trên các kỹ thuật thiết kế, tổng hợp, thăm dò, phân tích để phát hiện ra các mẫu dữ liệu thích hợp từ đó hợp thức hóa các kết quả tìm được bằng cách áp dụng các mẫu đã phát hiện cho tập con mới của dữ liệu. Ngày nay, trong hầu hết các lĩnh vực từ đời sống, kinh tế, xã hội, … đến khoa học kỹ thuật,… đều cần các công nghệ khai phá dữ liệu hiện đại, hiệu quả nhằm tìm ra các tri thức từ một khối lượng lớn thông tin, dữ liệu. Quá trình khai phá dữ liệu xuyên suốt qua nhiều giai đoạn từ xác định vấn đề, tiền xử lý (làm trong sáng dữ liệu, tổng hợp dữ liệu, chuyển đổi dữ liệu,…), khai phá dữ liệu, đánh giá mẫu được khai phá đến trình bày tri thức được khai phá. Trong các giai đoạn này thì giai đoạn tiền xử lý dữ liệu là giai đoạn tốn thời gian nhất và giai đoạn khai phá dữ liệu là giai đoạn quan trọng nhất. Nhiệm vụ của khai phá dữ liệu là tìm ra các mẫu cần được quan tâm phù hợp với yêu cầu của đối tượng cần khai phá từ một khối lượng khổng lồ dữ liệu. Các mẫu sau khi khai phá là tri thức nằm tiềm ẩn trong dữ liệu và có thể được khai phá từ nhiều mô hình cơ sở dữ liệu khác nhau như: cơ sở dữ liệu quan hệ, cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không gian,… hoặc từ các dạng lưu trữ thông tin khác như cơ sở dữ liệu đa phương tiện, cơ sở dữ liệu thời gian thực,…. Việc khai phá dữ liệu phù hợp và hiệu quả đối với các cơ sở dữ liệu lớn vẫn đang là nhu cầu và thách thức đối với các nhà khoa học 2.3. CÂY QUYẾT ĐỊNH 2.3.1. Khái niệm chung Phân lớp và dự đoán Trong một cơ sở dữ liệu lớn thường có nhiều thông tin hữu ích còn bị ẩn khuất, mà những thông tin này có thể được sự đụng để ra quyết định giao dịch hoặc là các tiên đoán thông minh đối với nhiều lĩnh vực. Đối với những dạng thông tin như thế thường thì các phương pháp phân tích, tổng hợp và thống kê truyền thống khó có thể phát hiện ra. Sự phân lớp và sự dự báo là hai dạng phân tích dữ liệu, chúng có thể được sử dụng để rút trích ra các mô hình mô tả các lớp dữ liệu quan trọng hoặc là để dự đoán các xu hướng dữ liệu tương lai. Trong khi sự phân lớp (classifcation) được dừng để dự đoán các nhãn rõ ràng, còn sự dự báo (prediction) được sử dụng để cho ra mô hình từ các hàm giá trị liên tục. Sự dự báo có thể được xem như sự xây dựng và sử dụng một mô hình để truy cập tới lớp mẫu không có nhãn, hoặc để truy cập các giá trị hoặc vùng giá trị của một thuộc tính, đây là các giá trị được mong đợi có mặt trong mẫu đã cho. Với cách nói này, thì sự phân lớp và sự hồi qui (classifcation and regression) là hai dạng cơ bản của các vấn đề dự đoán, trong khi sự phân lớp được sử dụng để dự đoán các giá trị được định danh hoặc các giá trị rời rạc, còn sự hồi qui thì được sử dụng để dự đoán các giá tri liên tục hoặc có thứ tự. Tuy nhiên, trong khai phá dữ liệu người ta thường chấp nhận: sự phân lớp dùng để dự đoán các nhãn lớp, còn sự dự đoán dùng để tiên đoán các giá trị liên tục (như việc sử dụng kỹ thuật hồi qui). Trong phần này và phần 3 sau đây, chúng ta sẽ nghiên cứu kỹ thuật phân lớp dữ liệu cơ bản đó là cơ sở dữ liệu quan hệ, các tính chất của cơ sở dữ liệu quan hệ, phụ thuộc hàm xấp xỉ và phân lớp bằng cây quyết định, một số phương pháp xây dựng cây quyết định và đây cũng chính là trọng tâm của báo cáo. Cây quyết định Cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Cây quyết định có cấu trúc hình cây và là một sự tượng trưng của một phương thức quyết định cho việc xác định lớp các sự kiện đã cho. Mỗi nút của cây chỉ ra một tên lớp hoặc một phép thử cụ thể, phép thử này chia không gian các dữ liệu tại nút đó thành các kết quả có thể đạt được của phép thử. Mỗi tập con được chia ra là không gian con của các dữ liệu được tương ứng với vấn đề con của sự phân lớp. Sự phân chia này thông qua một cây con tương ứng. Quá trình xây dựng cây quyết định có thể xem như là một chiến thuật chia để trị cho sự phân lớp đối tượng. Một cây quyết định có thể mô tả bằng các khái niệm nút và đường nối các nút trong cây. Mỗi nút của cây quyết định có thể là: Nút lá (leaft node) hay còn gọi là nút trả lời (answer node), nó biểu thị cho một lớp các trường hợp, nhãn của nó là tên của lớp. Nút không phải là lá (non-leaf node) hay còn gọi là nút trong (inner node), nút này xác định một phép thử thuộc tính (attribute test), nhãn của nút này có tên của thuộc tính và sẽ có một nhánh (hay đường đi) nối nút này đến cây con (sub-tree) ứng với mỗi kết quả có thể có của phép thử. Nhãn của nhánh này chính là giá trị của thuộc tính đó. Nút không phải lá nằm trên cùng là nút gốc (root node). Một cây quyết định sử dụng để phân lớp dữ liệu bằng cách bắt đầu đi từ nút gốc c._.