Nghiên cứu phương pháp cho bài toán phân cụm và xây dựng hệ thống thử nghiệm

HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN LÂM TÚ NGHIÊN CỨU PHƢƠNG PHÁP CHO BÀI TOÁN PHÂN CỤM VÀ XÂY DỰNG HỆ THỐNG THỬ NGHIỆM Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2013 Luận văn đƣợc hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG Ngƣời hƣớng dẫn khoa học: PGS.TS Đoàn Văn Ban Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ đƣợc bảo vệ trƣớc Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bƣu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thƣ viện của Học viện Công nghệ Bƣu chính Viễn thông 1 LỜI MỞ ĐẦU Thông tin là một nguồn tri thức rồi rào và quan trọng đối với nhân loại, lƣợng dữ liệu con ngƣời ta thu thập đƣợc ngày càng lớn. Với sự phát triển của công nghệ điện toán và hệ thống lƣu trữ dữ liệu thì khối lƣợng tài nguyên số ngày càng trở nên đồ sộ và phức tạp. Trong một xã hội hiện đại, thông tin đóng một vai trò then chốt. Thông tin không những chỉ là một tri thức mà nó còn đóng những vai trò khác nhƣ điều hƣớng quá trình sản xuất. Ảnh hƣởng đến hoạt động xã hội hay thị trƣờng. Tác động đến thói quen ngƣời tiêu dùng. Việc phân cụm dữ liệu, để phân loại và quản lý nguồn dữ liệu một cách có hiệu quả là một trong những trọng tâm nghiên cứu trong khai phá dữ liệu và Khoa học máy tính. Mà ứng dụng của nó đã đƣợc hiện thực hóa nhiều trong thực tế, kinh doanh thông minh (BI-Bussiness Intellegent) là một ví dụ rõ nét nhất. Các công ty và doanh nghiệp luôn muốn phát triển khả năng kinh doanh của họ, muốn phục vụ khách hàng tốt, có thêm khách hàng và lợi nhuận nhiều hơn. Việc hoạch định chiến lƣợc kinh doanh dựa trên những thông tin hiện tại của công ty là một nhu cầu tất yếu. Từ đó xây dựng và phát triển các hệ thống BI trở nên rất cần thiết và dần gắn liền với các hoạt động của công ty. Phân cụm dữ liệu có khá nhiều phƣơng pháp. Mỗi phƣơng pháp đều có ƣu điểm, nhƣợc điểm và khả năng ứng dụng riêng của mình. Trong nội dung luận văn này, tác giả sẽ trình bày phƣơng pháp phân cụm phân cấp kết hợp với mạng nơ-ron để giải quyết một vấn đề cụ thể trong hệ thống BI. Luận văn đƣợc trình bày gồm 3 chƣơng với nội dung các chƣơng nhƣ sau: Chƣơng 1: Giới thiệu về khai phá dữ liệu, các khái niệm cơ bản trong khai phá dữ liệu. Đồng thời trong chƣơng này tác giả cũng đi sâu vào phân cụm dữ liệu và một số phƣơng pháp trong lĩnh vực này. Chƣơng 2: Trong chƣơng này luận văn tập trung vào việc tìm hiều kết hợp thuật toán trong phân cụm, áp dụng chúng vào một vấn đề cụ thể trong BI. Hai thuật toán đƣợc tìm hiểu sau trong chƣơng này là phân cụm phân cấp và thuật toán SOM. 2 Bài toán đƣợc đƣa ra để giải quyết là bài toán về phân loại khách hàng triển vọng và sản phẩm tiềm năng. Chƣơng 3: Chƣơng này sẽ đi vào việc cài đặt ứng dụng cụ thể dựa trên thuật toán và vấn đề đã đƣợc nêu ở chƣơng 2. Ứng dụng đƣợc phát triển là một ứng dụng đơn giản nhƣng bao quát đầy đủ thuật toán cũng nhƣ thỏa mãn bài toán đặt ra. 3 CHƢƠNG 1: KHAI PHÁ DỮ LIỆU VÀ CÁC PHƢƠNG PHÁP PHÂN CỤM DỮ LIỆU 1.1. Giới thiệu chung về khai phá dữ liệu Khai phá dữ liệu là một quá trình rút trích hay khai phá tri thức từ một lƣợng lớn dữ liệu. Ta nói rằng đây là một quá trình là bởi vì nó đƣợc thực hiện theo một quy trình với nhiều bƣớc rõ ràng, trong đó mỗi bƣớc có một vai trò nhất định. Việc khai phá dữ liệu là bắt nguồn từ một nhu cầu thực thế khi mà lƣợng dữ liệu con ngƣời ta sử dụng ngày càng nhiều. Lấy ví dụ nhƣ trong quá trình sản xuất, kinh doanh, dữ liệu về khách hàng, hợp đồng, số liệu kinh doanh, chứng từ, tài liệu, … lên đến hàng triệu file hay bản ghi. Việc quản lý và khai thác lƣợng lớn dữ liệu này là một điều sống còn với các doanh nghiệp. Quá trình khai phá dữ liệu đƣợc chia thành ba giai đoạn chính, đó là: - Giai đoạn tiền xử lý (pre-processing) - Giai đoạn khai phá, rút trích (data mining) - Giai đoạn hậu lý xong (post-processing) Hình 1.1.Quá trình khai phá dữ liệu Trong mỗi giai đoạn lại có thể đƣợc chia thành các nhiệm vụ nhỏ hơn.Thông thƣờng vì nhiều lý do mà những dữ liệu thô ban đầu chúng ta không thể sử dụng ngay cho quá trình khai phá đƣợc. Chúng cần đƣợc tinh lọc và xử lý trƣớc. Giai đoạn tiền xử lý bao gồm bốn bƣớc: - Bƣớc làm sạch dữ liệu (Cleaning): Loại bỏ những dữ liệu dƣ thừa hoặc không đồng nhất. 4 - Bƣớc tích hợp (Integration): dữ liệu có thể đƣợc lấy từ nhiều nguồn khác nhau, tại bƣớc này tất cả dứ liệu sẽ đƣợc kết hợp lại với nhau. - Bƣớc lựa chọn dữ liệu (Data Selection): trong bƣớc này những dữ liệu đƣợc coi là tốt nhất sẽ đƣợc lấy ra, chúng sẽ là dữ liệu đầu vào cho việc phân tích dữ liệu. - Bƣớc cuối cùng là bƣớc chuyển đổi (Transformation): trong bƣớc này dữ liệu sẽ đƣợc chuyển đổi hoặc hợp nhất vào một định dạng phù hợp với việc khai phá sau này. Một số kỹ thuật thƣờng đƣợc sử dụng ở bƣớc này là tổng quát hóa (summary) hay kết hợp (aggregation) . Giai đoạn khai phá dữ liệu là giai đoạn cơ bản và quan trọng nhất trong toàn bộ quá trình. Sau giai đoạn tiền xử lý, lƣợng dữ liệu sẽ đƣợc đƣa vào cho giai đoạn khai phá. Một số kỹ thuật đƣợc sử dụng trong giai đoạn này: khai phá luật kết hợp (association rule mining), khai phá mẫu tuần tự (sequential pattern mining), học giám sát (hay phân loại –classification) và học không giám sát (hay phân cụm - clustering ). Tuy vào đặc trƣng của từng bài toán mà kỹ thuật thích hợp nhất sẽ đƣợc sử dụng. Kết quả của giai đoạn này là đƣa ra, rút trích đƣợc các mẫu hay các tri thức. Giai đoạn cuối cùng là giai đoạn sau khi đã xử lý xong. Trong nhiều ứng dụng không phải tất cả các mẫu có đƣợc từ giai đoạn khai phá đều hữu dụng. Bạn hay tƣởng tƣợng rằng với một hệ thống lớn có sử dụng khai phá dữ liệu thì nó có thể có tới hàng nghìn hay hàng triệu các luật hay các mẫu. Các luật hay các mẫu này có đƣợc từ một giai đoạn xử lý phức tạp với lƣợng dữ liệu lớn. Chính vì thế không phải các luật, mẫu đƣợc sinh ra nào cũng thật sự tốt. Hơn thế, một mẫu đƣợc coi là tốt khi nó cần đảm bảo một số tính chất nhƣ: dễ hiểu và con ngƣời dễ tiếp cận, hoạt động tốt với những dữ liệu mới, mang tính cách tân và hữu dụng,nó cũng cần phù hợp với cá lý thuyết đƣợc đề ra. Đây chính là nhiệm vụ của bƣớc đánh giá (Evaluation) trong giai đoạn hậu xử lý dữ liệu. Ngoai ra trong giai đoạn này còn có bƣớc là trình bày lại tri thức (Knowledge Presentation). Bƣớc này sử dụng các kỹ 5 thuật về trình bày trực quan: có thể là đƣa ra các báo cáo, biểu đồ… nhằm giúp ngƣời dùng tiếp cận với các tri thức đã đƣợc rút trích [20]. 1.2. Các phương pháp phân cụm trong Khai phá dữ liệu Phân cụm dữ liệu là một quá trình nhằm sắp xếp các đối tượng vào các nhóm sao cho thành viên của mỗi nhóm có một đặc điểm riêng biệt nào đó. Cụm có thể được hiểu theo nghĩa là một tâp các đối tượng có đặc điểm giống nhau và khác biệt với đối tượng trong các nhóm khác. [3, 24] Phân cụm thƣờng đƣợc đề cập tới nhƣ là một kiểu “học không giám sát” (unsupervised learning). Tức là quá trình phân cụm dữ liệu không dựa trên nhãn cho trƣớc. Phƣơng pháp phân cụm đƣợc sử dụng để tìm ra cấu trúc của một tập hợp các dữ liệu không mang nhãn. Hai hay nhiều đối tƣợng cùng nằm trong một cụm nếu nhƣ một đối tƣợng trong chúng định ra đƣợc một khái niệm chung cho tất cả các đối tƣợng khác. Nói một cách khác thì các đối tƣợng đƣợc phân cụm dựa trên một khái niệm chung cho cả nhóm chứ không phải là từ một đặc điểm giống nhau riêng lẻ. 1.2.1. Phƣơng pháp phân hoạch (Partitioning Methods) Phƣơng pháp phân hoạch là phƣơng pháp phân chia n đối tƣợng cho trƣớc ra k nhóm khác nhau. Các nhóm tạo ra dựa vào sự phân hoạch các đối tƣợng. Một cách thức thƣờng đƣợc sử dụng nhất đó là dựa vào khoảng cách. Các đối tƣợng trong cùng một nhóm thì có các đặc điểm giống nhau hoặc gần giống nhau, trong khi đó các đối tƣợng ở các nhóm khác nhau thì có các đặc tính rất khác nhau. 1.2.2. Phƣơng pháp phân cấp (Hierarchical Methods) Đây là một phƣơng pháp nhằm phân chia các đối tƣợng thành các cụm dƣới dạng sơ đồ cấu trúc cây. Phƣơng pháp này bao gồm làm hai kỹ thuật chính: tích tụ (agglomerative) và phân chia (divisive). Tích tụ là cách phân cụm theo kiểu từ dƣới lên (buttom – up) còn phân chia là cách phân cụm theo kiểu từ trên xuống (top- down). 6 1.2.3. Phƣơng pháp dựa trên mật độ (Density-Based Methods) Để tìm ra các cụm có hình dạng phức tạp và ở nhiều kiểu khác nhau, ngƣời ta sử dụng phƣơng pháp phân cụm dựa trên mật độ [4, 20]. Phƣơng pháp nhằm phân định các vùng có mật độ đối tƣợng dầy đặc thành các nhóm và tách biệt khỏi những vùng có mật độ đối tƣợng ít. 1.2.4. Phƣơng pháp dựa trên lƣới (Grid-Based Methods) Cách tiếp cận phân cụm dựa trên lƣới sử dụng một cấu trúc lƣới đa phân giải. Lƣới cấu trúc này sẽ định lƣợng đối tƣợng trong không gian vào một lƣợng giới hạn các ô của lƣới. Tiếp đó nó thực hiện tất cả các thao tác phân cụm trên cấu trúc. Thuận lợi chính của tiếp cận này là thời gian xử lý nhanh chóng của nó độc lập với số các đối tƣợng dữ liệu và chỉ tuỳ thuộc vào số lƣợng các ô trong mỗi chiều của không gian [6, 7, 20]. 1.3. Kết luận chƣơng 7 CHƢƠNG 2: PHƢƠNG PHÁP PHÂN CỤM PHÂN CẤP VÀ PHƢƠNG PHÁP SOM 2.1. Phương pháp phân cụm phân cấp Phương pháp phân cụm phân cấp là một phương pháp phân cụm, trong đó các đối tượng dữ liệu được gom vào các cụm có cấu trúc dạng cây. Trong phƣơng pháp này các đối tƣợng sẽ đƣợc phân rã theo dạng cấu trúc phân cấp (có thứ bậc). Tuy theo cách thức phân rã mà ngƣời ta có thể sử dụng một trong hai kỹ thuật của phƣơng pháp này đó là: Phân rã theo hƣớng từ trên xuống (tiếp cận theo hƣớng phân chia) hoặc phân rã theo hƣớng từ dƣới lên (tiếp cận theo hƣớng tích tụ) [12]. 2.1.1. Những khái niệm chung trong phƣơng pháp Phân cụm phân cấp Cách tiếp cận dƣới lên: Ban đầu, chúng ta xem mỗi đối tƣợng là 1 nhóm (cụm) và nhóm 2 đối tƣợng gần nhất thành 1 cụm. Quá trình này lặp lại cho đến khi tất cả các đối tƣợng đƣợc nhóm vào 1 cụm cuối cùng. Cách tiếp cận trên xuống: Quá trình ngƣợc lại với tiếp cận dƣới lên, ban đầu chúng ta xem tất cả các đối tƣợng thuộc cùng 1 cụm, sau đó tiến hành phân thành 2 nhóm con (thƣờng dựa vào khoảng cách lớn nhất). Quá trình này đƣợc thực hiện cho đến khi mỗi nhóm chỉ còn 1 đối tƣợng. 2.1.2. Nội dung và đặc điểm của phƣơng pháp Phân cụm phân cấp Một thuật toán thƣờng đƣợc sử dụng trong phƣơng pháp phân cụm phân cấp nhƣ đó là: Thuật toán phân cụm phân cấp tích tụ (Agglomerative Hierarchical Clustering) [22] Kỹ thuật tính liên kết (linkage between objects): Bảng 2.1. Bảng so sánh các cách tính độ liên kết giữa các cụm Kỹ thuật Cách thức Độ phƣc tạp Đặc điểm Liên kết đơn Lấy khoảng cách 2 đối tƣợng gần ảnh hƣởng đến tập các đối tƣợng 8 nhau nhất 2( )N Liên kết hoàn toàn Lấy khoảng cách 2 đối tƣợng xa nhau nhất 2( log )N N Ảnh hƣởng đến các dữ liệu ngoại biên Liên kết trung bình nhóm Lấy khoảng cách trung bình giữa các đối tƣợng 2( log )N N Là lựa chọn tốt cho nhiều ứng dụng Liên kết tâm Lấy khoảng cách 2 tâm của cụm 2( log )N N Sự đảo ngƣợc có thể xảy ra 2.1.3. Ứng dụng của phƣơng pháp Phân cụm phân cấp Phƣơng pháp phân cụm theo thứ bậc đƣợc sử dụng khá nhiều trong thực tế. Một số kỹ thuật thƣờng thấy trong phƣơng pháp này đó là: [2. 20] - BIRCH - CURE - CHAMELEON Phƣơng pháp phân cụm phân cấp thƣờng đƣợc áp dụng cho các bài toán trong khai phá dữ liệu nhƣ: phân cụm các tài liệu theo cấu trúc cây; đƣợc áp dụng để phân cụm của các tập dữ liệu miêu tả về cấu trúc gen; Đƣợc áp dụng trong bài toán dự đoán tài chính, thị trƣờng chứng khoán. 2.2. Mạng nơ-ron và cách học không giám sát SOM 2.2.1. Giới thiệu về mạng Nơ-ron Mạng Nơ-ron (Artificial Neural Network- ANN) là một mô hình toán học được xây dựng dựa trên sự mô phỏng hệ thần kinh trong sinh học. Mô hình này bao gồm một số lượng lớn các nốt được gắn kết với nhau để xử lý thông tin. Các nốt này được gọi là đơn vị xử lý hay Nơ-ron. ANN giống như bộ não con người, được học bởi kinh nghiệm (thông qua huấn luyện), có khả năng lưu giữ những kinh nghiệm hiểu biết (tri thức) và sử dụng những tri thức đó trong việc dự đoán các dữ liệu chưa biết (unseen data) [13, 22]. 9 Hình 2.6. Mô hình của Nơ-ron trong mạng Nơ-ron Kiến trúc của mạng Nơ-ron: Nhìn chung một mạng Nơ-ron bao gồm ba lớp: Input layer, Hidden layer và Output layer. Trong đó, lớp Input layer có nhiệm vụ nhận dữ liệu đầu vào, lớp Hidden layer có nhiệm vụ nhận dữ liệu từ lớp trƣớc đó và chuyển dữ liệu này cho lớp xử lý tiếp theo, cuối cùng là lớp Output layer đƣa ra kết quả đầu ra của mạng. Nơ-ron hay còn đƣợc gọi là đơn vị xử lý (PE), hạt nhân, hay nốt là thành phần cơ bản của mạng Nơ-ron. Kiến trúc của ANN Mạng ANN bao gồm hai hình trạng chính: Mạng truyền thẳng và Mạng hồi quy. Trong mạng truyền thẳng dòng dữ liệu sẽ đi theo một hƣớng duy nhất. Mạng có thể có nhiều lớp nhƣng dữ liệu sẽ không đƣợc truyền phản hồi từ lớp này trở lại lớp kia. Điều đó có nghĩa là sẽ không xảy ra trƣờng hợp output của lớp này trở ngƣợc lại làm input của lớp trƣớc đó. Đối với mạng hồi quy, nó có chứa các liên kết hồi quy. Nghĩa là trong một số trƣờng hợp dòng dữ liệu sẽ đảo ngƣợc, quay trở lại với lớp trƣớc đó. Điều này sẽ làm tăng khả năng linh hoạt của mạng trong việc điều chỉnh chỉ số và các liên kết để hàm chuyển đổi có thể đạt đến giá trị mong muốn. Khi một mạng ANN đƣợc xây dựng và định dạng đƣợc cấu trúc cũng nhƣ hình trạng, đó là lúc nó sẵn sàng cho quá trình học. Giá trị trọng số của các đơn vị xử lý ban đầu sẽ đƣợc lựa trọn một cách ngẫu nhiên. Nhƣ thế quá trình học của ANN bắt đầu. ANN có hai phƣơng pháp học đó là: học có giám sát (Supervised 10 Learning) và học không giám sát (Un-Supervised Learning). Học giám sát nghĩa là các giá trị đầu vào và kết quả mong muốn đƣợc đƣa ra trƣớc. Điển hình cho kỹ thuật này là mạng Nơ-ron lan truyền ngƣợc (Backpropagation). Học không giám sát thì ta chỉ biết đƣợc giá trị đầu vào, còn giá trị mong muốn sẽ đƣợc thiết lập dần trong quá trình học. Mạng Nơ-ron điển hình đƣợc huấn luyện theo kiểu học không giám sát là mạng tự tổ chức SOM ( Self Organization Map). Không có kiểu học giám sát theo mô hình mạng tự tổ chức. Mạng Nơ-ron có 3 cách huấn luyện chính đó là huấn luyện theo khối, huấn luyện ngẫu nhiên và huấn luyện trực tuyến 2.2.2. Nội dung và đặc điểm của phƣơng pháp SOM SOM ( Seft Organization Map) là một mạng Nơ-ron nhân tạo, được huấn luyện bởi kỹ thuật không giám sát,trong đó số lượng Nơ-ron của SOM chính bằng số lượng cụm của dữ liệu huấn luyện. Các Nơ-ron trong SOM được biểu diễn bởi dãy, có thể là dãy một chiều hay dãy hai chiều. Cách biều diễn thường được sử dụng đó là biểu diễn theo hai chiều, khi đó SOM được coi như một mạng tự tổ chức hai chiều của các cụm. Dữ liệu đầu vào sẽ thuộc một cụm nhất định-tương ứng với một Nơ-ron, cụm có số chiều chính bằng số chiều của Nơ-ron này. Như vậy SOM có khả năng biểu diễn các dữ liệu đầu vào nhiều chiều trở thành ít chiều [19, 21]. Hình 2.7. Mạng tự tổ chức SOM Thuật toán: 11 Input: Tập các vector đầu vào, tập các Nơ-ron Output: Tập các cụm của dữ liệu đầu. Các cụm này tạo thành một SOM. Nội dung: Bước 1: Khởi tạo trọng số một cách ngẫu nhiên Bước 2: với mỗi vector đầu vào x, thực hiện bƣớc 3 đến 5 Bước 3: Đối với mỗi Nơ-ron thứ j, ta tính khoảng cách 2 1 ( ) ( - w ) (2.7) n i ji i D j x    Bước 4: Tìm khoảng cách D(j) nhỏ nhất, từ đó xác định đƣợc winning Nơ- ron Bước 5: cập nhật giá trị trọng số của tất cả các láng giềng j của winning Nơ- ron ij ij ijw w ( , )( w ) (2.8)ih i j x   Bước 6: giảm chỉ số học  và và bán kính láng riềng Bước 7: kiểm tra giá trị điều kiện dừng. kết thúc thuật toán nếu điều kiện dừng là đúng. 2.2.3. Ứng dụng của SOM trong thực tế Một số ứng dụng trong thực tế của SOM có thể kể ra: - Kohonen (1984) hệ thống nhận biết âm - Hệ thông nhận biết về ký tự 12 - Ứng dụng trong việc giải quyết bài toán ngƣời bán hàng. - Tổ chức và lƣu trữ tài liệu (Document Organization and Retrieval - SOM đƣợc sử dụng trong các ứng dụng về Gen và di truyền học. 2.3. Giới thiệu về BI và bài toán hỗ trợ kinh doanh 2.3.1. BI và chiến lƣợc khách hàng BI ( Business Intelligence) là tập hợp lý thuyết, phương pháp, quy trình, kiến trúc, và công nghệ với mục tiêu là chuyển hóa những dữ liệu thô thành những thông tin có nghĩa và hữu ích cho việc kinh doanh [27]. Các thành phần của BI: Hình 2.8. Các thành phần của hệ thống BI Thông thƣờng khi một doanh nghiệp chọn BI là khi mà họ nghĩ đến một hệ thống có khả năng dự báo hoặc hỗ trợ việc ra quyết định. Nhiệm vụ của BI chính là tạo ra những tri thức từ dữ liệu ban đầu của doanh nghiệp. Thông qua việc phân tích, đánh giá những tri thức ấy doanh nghiệp có thể dự báo trƣớc hoặc xác định những mục tiêu, quyết định của mình. BI có thể giúp cho doanh nghiệp thay đổi cách nhìn nhận về thực tế hoạt động của mình, cũng nhƣ đề ra những chiền lƣợc 13 kinh doanh phù hợp với thực tế đó. BI thay đổi tầm nhìn và thay đổi cách hoạt động trong tƣơng lai của doanh nghiệp. Cũng nhƣ theo định nghĩa của BI, thì nó có một vai trò quan trọng đó là chuyển hóa các dữ liệu thô thành những thong tin có nghĩa và hữu ích cho việc kinh doanh. Điều đó có nghĩa là BI đã giúp cho việc quản lý dữ liệu và tài nguyên của doanh nghiệp một cách tốt hơn và hơn thế nó tạo ra giá trị tri thức từ các nguồn dữ liệu đó. Mức độ chuyển hóa dữ liệu đƣợc đề cập đến đó là: Dữ liệu  Thông tin Tri thức. 2.3.2. Vai trò khai phá dữ liệu trong BI Khai phá dữ liệu đóng một vai trò rất quan trọng trong BI. Nó có nhiệm vụ biến đổi các dữ liệu thô, vô nghĩa thành những dữ liệu có tri thức nhằm giúp cho việc ra quyết định hay định hƣớng ra quyết định. 2.3.3. Bài toán phân loại khách hàng triển vọng và đánh giá những sản phẩm tiềm năng Khách hàng và sản phẩm là hai yếu tố quan trọng trong chiến lƣợc kinh doanh, nó gắn liền với sự thành công hay thất bại của doanh nghiệp. Hai yếu tố này cũng luôn đi đôi và có quan hệ qua lại với nhau.Nắm bắt đƣợc đâu là khách hàng, nhóm khách hàng phù hợp và triển vọng dựa trên các yếu tố hiện tại của công ty nhƣ dịch vụ, sản phẩm cùng với đặc điểm của khách hàng là điều mấu chốt. Từ việc phân vùng khách hàng mà ta biết đƣợc nên đầu tƣ và chú trọng đến mặt hàng nào để nâng cao sức hút với khách hàng và đẩy mạnh quá trình kinh doanh. Bài toán đƣợc đặt ra đó là: Cho trƣớc một số lƣợng khách hàng cùng với các đặc tính, hãy gom cụm những khách hàng này nhằm tìm ra nhóm khách hàng có những đặc điểm, thói quen giống nhau. Từ đó ta cũng biết đƣợc sản phẩm hay dịch vụ nào phù hợp với nhóm khách hàng ấy. Kết quả bài toán sẽ giúp cho doanh nghiệp biết đƣợc tính chất của từng nhóm khách hàng, khoanh vùng đƣợc khách hàng. Đồng thời cũng thấy đƣợc cần phải chú trọng vào mạng kinh doanh sản phẩm hay dịch vụ nào. 14 2.4. Kết hợp giữa phân cụm phân cấp và SOM để giải quyết bài toán hỗ trợ kinh doanh. 2.4.1. Sự kết hợp của phân cụm phân cấp với SOM, thuật toán HSOM SOM là một phƣơng pháp phân cụm đƣợc đánh giá là mạnh mẽ và linh hoạt. Trong đó trọng tâm của thuật toán rơi vào việc xây dựng mạng lƣới các Nơ-ron cùng với vector trọng số của mỗi Nơ-ron đó. Tính linh hoạt của phƣơng pháp gắn liền với quá trình cập nhật các lân cận của mỗi Nơ-ron chiến thắng. Mỗi Nơ-ron có thể đƣợc coi là một cụm. Nhƣ vậy, ta có thể thấy rằng việc xây dựng một mạng lƣới các Nơ-ron ban đầu cùng với các đặc tính của mỗi Nơ-ron là một bƣớc quan trọng của SOM. Việc sử dụng phƣơng pháp phân cụm phân cấp mà cụ thể là kỹ thuật tích tụ (tích tụ algorithm) là một hƣớng để tích hợp giữa hai phƣơng pháp. Quá trình xử lý của phƣơng pháp SOM có thể đƣợc minh họa bởi sơ đồ sau: Hình 2.9. Kết hợp phân cụm phân cấp và SOM Trong phạm vi luận văn này, việc kết hợp giữa hai phƣơng pháp SOM và Hierachical Clustering để tạo ra các bƣớc trong việc phân cụm dữ liệu đƣợc gọi là tắt là thuật toán HSOM. Nội dung của thuật toán HSOM nhƣ sau: Input: cho tập các vector đầu vào X ={x1, x2, …, xn} Output: Xác định cụm của mỗi vector đầu vào Bước 0: Xác định tham số đầu vào MxN (kích thƣớc Map của SOM); chỉ số học ban đầu 0 ; số lƣợng epoch (số lƣợng các lần huấn luyện). Bước 1: Xây dựng lƣới Nơ-ron. Sử dụng kỹ thuật Tích tụ để gom nhóm các Nơ-ron và tạo mạng tự tổ chức SOM. 15 Bước 1.1: Tập các vector đầu vào của các đối tƣợng xây dựng mạng tự tổ chức SOM. Bước 1.2: Tính toán khoảng cách giữa các đối tƣợng trong tập huấn luyện E. Thiết lập ma trận khoảng cách Bước 1.3: Coi mỗi đối tƣợng là một cụm. Lặp lại các bƣớc sau cho đến khi nào số lƣợng cụm chính bằng MxN - Tìm min(aij), xác định đƣợc hai đối tƣợng ei, ej. Gom nhóm hai đối tƣợng thành một nhóm - Cập nhật lại ma trận khoảng cách M với số lƣợng đối tƣợng giảm đi một. Bước 1.4: - Ta có đƣợc tập các cụm cùng với ma trận khoảng cách giữa các cụm. Mỗi một cụm là một Nơ-ron. - Đối với vector trọng số của mỗi Nơ-ron: Vector trọng số của mỗi Nơ-ron đƣợc tính toán lại theo công thức trung bình sau: 1 2w w ... ww (2.13)k k     - Thực hiện việc ánh xạ đến mạng tự tổ chức SOM nhƣ sau: + Tìm 2 vị trí còn trống có khoảng cách đến đến nhau là nhỏ nhất + Tìm min(aij), xác định đƣợc hai đối tƣợng ei, ej, đặt vào hai vị trí vừa tìm đƣợc. Gom nhóm hai đối tƣợng thành một nhóm +Cập nhật lại ma trận khoảng cách M với số lƣợng đối tƣợng giảm đi một. + Kết thúc quá trình ánh xạ nếu nhƣ lƣới SOM đƣợc lấp đầy - Xác định đƣợc bán kính láng giềng ban đầu của mạng tự tổ chức: 0 = max(aij)/2 Bước 2: với mỗi vector huấn luyện đầu vào x, thực hiện bƣớc 3 đến 5 Bước 3: Đối với mỗi Nơ-ron thứ j, ta tính khoảng cách 2 1 ( ) ( -w ) (2.14) n i ji i D j x    16 Bước 4: Tìm khoảng cách D(j) nhỏ nhất, từ đó xác định đƣợc Nơ-ron chiến thắng Bước 5: cập nhật giá trị trọng số của tất cả các láng giềng j của Nơ-ron chiến thắng ij ij ijw w ( , )( w ) (2.15)ih i j x   2 ( ,w ) 2( , ) exp (2.16)2 j innerdh i j         1 0/ log( ) (2.17)T epoch  Bước 6: giảm chỉ số học  và bán kính  0( ) exp (2.18)countn epochs   0 1 ( ) exp (2.19)countcount T         Bước 7: kiểm tra giá trị điều kiện dừng. kết thúc thuật toán nếu điều kiện dừng là đúng. 2.4.2. Thuật toán HSOM và bài toán hỗ trợ kinh doanh Thuật toán HSOM là một thuật toán phù hợp cho việc giải quyết bài toán phân loại khách hàng triển vọng và đánh giá những sản phẩm tiềm năng. Thực chất thì HSOM là một thuật toán phân cụm, kết quả cuối cùng đƣa ra là tập các cụm với những đặc tính riêng của chúng. Ngoài ra, HSOM có thể chấp nhận một lƣợng dữ liệu lớn đầu vào với cá thuộc tính cho trƣớc. Số lƣợng các cụm đầu ra có thể đƣợc xác định và không chế trƣớc. Hình 2.11. Mô hình bài toán hỗ trợ kinh doanh Thuật toán thực sự có ích khi số lƣợng dữ liệu khách hàng lớn và gây khó khăn cho ngƣời quản lý khi phân tích lƣợng dữ liệu phức tạp nhƣ vậy. Thuật toán 17 gom cụm và giảm thiểu số lƣợng dữ liệu đầu vào. Việc khách hàng thuộc vào cụm nào cũng thể hiện xu thế của khách hàng đó. Cùng với vector trọng số của mỗi cụm mà cho ta biết đƣợc yếu tố nào ảnh hƣởng đến nhóm khách hàng này nhiều nhất. Các thông tin tri thức trên sẽ đƣợc ngƣời quản lý nắm bắt và dựa vào đó mà đƣa ra những quyết định cho phù hợp với công ty. 2.4.3. Quá trình tìm kiếm BMU và cập nhật BMU vào HSOM Map Nơ-ron có vector trọng số gần giống với giá trị huấn luyện đầu vào nhất đƣợc gọi là BMU (Best matching unit). Hay có thể hiểu theo một cách khác, đây chính là Nơ-ron có khoảng cách nhỏ nhất tới giá trị huấn luyện. BMU đƣợc xác định ở bƣớc số 3 và 4 của thuật toán HSOM. Để có thể biết đƣợc đâu là Nơ-ron giống với giá trị huấn luyện nhất, chúng ta sử dụng cách tính khoảng cách bằng công thức Euclid: 2 1 ( ) ( -w ) n i ji i D j x    Sau đó ta xác định khoảng cách nhỏ nhất tƣơng ứng với Nơ-ron là BMU. BMU đƣợc xác định sau mỗi vòng lặp chứ không phải là cố định trong suốt quá trình chạy của thuật toán. BMU chỉ ra rằng, đâu là điểm trên mạng tự tổ chức giữ vai trò trung tâm trong vòng lặp đó. Đồng thời, nó cũng chỉ ra đƣợc những điểm láng giềng nhờ vào giá trị bán kính láng giềng. Tiếp sau đó, BMU sẽ đƣợc dịch chuyển và cập nhật giá trị sao cho càng tiến sát vector đâu vào hơn. Những giá trị láng giềng cũng theo đó mà đƣợc cập nhật và gom lại gần nhau hơn. Việc cập nhật này thông qua việc thay đổi giá trị trọng số của Nơ-ron cùng với vị trí của chúng trên mạng tự tổ chức. Việc cập nhật trọng số đƣợc tính theo công thức sau: ij ij ijw w ( , )( w )ih i j x   2.5. Kết luận chương 18 CHƢƠNG 3: XÂY DỰNG ỨNG DỤNG PHÂN CỤM DỮ LIỆU CHO BÀI TOÁN HỖ TRỢ KINH DOANH 3.1. Thu thập dữ liệu khách hàng từ hệ thống Taskhub Taskhub là một hệ thống phần mềm ERP dựa trên nền Web đƣợc phát triển bởi công ty Synergix Technologies (Singapore), nó có chức năng là hỗ trợ một cách hiểu quả với các hoạt động và quá trình kinh doanh của công ty. Taskhub đƣợc thiết kế trên nền Web nên có thể đƣợc truy cập ở mọi lúc và mọi nơi và nó cũng không phụ thuộc vào hệ điều hành hay nền tảng nào. Taskhub có đến hơn hai mƣơi module khác nhau, mỗi module hƣớng đến một phần trong hoạt động của doanh nghiệp nhƣ: MFG, AR, AP, SO, PJ… Trong đó SO (Sales Order) là module tƣơng tác với khách hàng và giúp khách hàng đƣa ra yêu cầu của mình. Đây cũng là module chứa dữ liệu khách hàng cùng với những đặc điểm và tƣơng tác của khách hàng đối với công ty. Trong luận văn, tác giả sẽ lấy một số dữ liệu khách hàng từ Module này của công ty, có sang lọc và tinh chỉnh để làm ví dụ cho hệ thống demo về HSOM. Bảng 3.1. Dữ liệu thử nghiệm cho ứng dụng 19 3.2. Xây dựng kiến trúc ứng dụng Hệ thống đƣợc xây dựng bao gồm 8 gói (package) nhƣ sơ đồ sau: Hình 3.1. Các gói (package) trong hệ thống 3.3. Thực hiện ứng dụng 3.3.1. Biểu đồ lớp và biểu đồ tuần tự Có 5 lớp chính đƣợc sử dụng trong ứng dụng, chúng sẽ đƣợc miêu tả theo sơ đồ lớp nhƣ sau: 20 Hình 3.2. Sơ đồ các lớp cơ bản trong ứng dụng Quá trình xử lý của ứng dụng có thể đƣợc mô hình hóa dƣới dạng sơ đồ tuần tự sau: Hình 3.3. Biểu đồ tuần tự quá trình xử lý của ứng dụng Quá trình tích hợp và xuất báo cáo đƣợc mô tả trong sơ đồ tuần tự sau: Hình Hình 3.4. Biểu đồ tuần tự quá trình truy xuất báo cáo 21 Dữ liệu đầu vào cho ứng dụng Dữ liệu đầu vào của ứng dụng có thể là dƣới dạng file hay trích xuất từ một cơ sở dữ liệu. Ứng dụng có thể chấp nhận các dữ liệu dạng vector đƣợc lƣu xuống file. File có phần đuôi mở rộng .som là file mặc định mà ứng dụng có thể đọc đƣợc. Trong phần cài đặt của luận văn, tác giả sử dụng hệ quản trị DB2 để quản lý dữ liệu. Cấu trúc của các bảng đƣợc sử dụng miêu tả bởi sơ đồ thực thể sau: Hình 3.5. Mô hình thực thể kết hợp Dữ liệu miêu tả mối quan hệ giữa khách hàng, đơn đặt hàng và sản phẩm trong các đơn đặt hàng đó. Ứng dụng có nhiệm vụ phải tìm ra những tri thức về khách hàng và sản phẩm thỏa mãn bài toán về phân loại khách hàng triển vọng và đánh giá các sản phẩm tiềm năng . 3.3.2. Biến đổi các giá trị trích xuất thành các vector trọng số Thuật toán SOM chỉ làm việc với những giá trị trọng số và vector. Chính vì thế cần có một bƣớc để biến dữ liệu thô thành dạng trọng số. Đây chính là nhiệm vụ của quá trình tiền xử lý dữ liệu trong ứng dụng. 22 Hình 3.6. Quá trình chuyển hóa dữ liệu thực qua dạng vector Kỹ thuật đƣợc xử dụng ở đây chính là sử dụng một bảng trung gian, nối kết các giá trị cụ thể với các trọng số. Tùy thuộc vào tình hình kinh doanh thực tế, cũng nhƣ những đặc điểm, hoạt động của công ty mà xác định đƣợc trọng số nào quan trọng. 3.4. Tìm hiểu công cụ IReport và xuất báo cáo kinh doanh từ ứng dụng JasperReport là một bộ công cụ mã nguồn mở trên nền java dùng chuyên cho các báo cáo(report) . JasperReport thƣờng đƣợc sử dụng cho các ứng dụng về BI hay các hệ thống quản trị doanh nghiệp. 3.5. Kết quả thu đƣợc và thực nghiệm Kết quả thu đƣợc: xây dựng đƣợc ứng dụng với các tính năng sau; thực thi đƣợc thuật toán đề ra. Luận văn đã xây dựng đƣợc một hệ thống thử nghiệm cho bài toán phân cụm đã đặt ra. Ứng dụng đã giải quyết đƣợc bài toán trong BI: “ nhằm xác định khách hàng triển vọng và đánh giá những sản phẩm tiềm năng”. Dựa trên những dữ liệu kinh doanh đầu vào của công ty, ứng dụng đã tách lọc, phân tích, khai phá, và gom nhóm dữ liệu. Cuối cùng, kết quả thu đƣợc là những báo cáo tích hợp những thông tin hỗ trợ cho việc ra quyết định và hoạch định chiến lƣợc. Giá trị thực Bộ biến đổi Giá trị trọng số 23 Hình 3.9. Hình ảnh về ứng dụng Hình 3.20. Báo cáo về nhóm khách hàng và sản phẩm Dƣới đây là một báo cáo khác nữa, nó cho thấy những mặt hàng(inventory Code) nào đƣợc mua nhiều nhất, có tiềm năng để kinh doanh. 3.6. Kết luận chƣơng 24 KẾT LUẬN Luận văn đã đi nghiên cứu và tìm hiểu về các phƣơng pháp phân cụm dữ liệu, mà trọng tâm là hai phƣơng pháp phân cụm phân cấp và SOM. Kết hợp tính chất phân cấp hội tụ của phân cụm phân cấp với SOM là một cách thức tiếp cận cho một số bài toán đƣợc đặt ra trong thực tế. Luận văn đã đƣa ra những cái nhìn khái quát nhất về một hƣớng phát triển trong lĩnh vực kinh doanh và quản lý, đó là BI ( Business Intellegence). Áp dụng công nghệ và khai phá dữ liệu vào BI là một điểm mấu chốt để phát triển lĩnh vực này. Luận văn đã đƣa ra một bài toán trong BI và giải quyết nó bằng các thuật toán khai phá dữ liệu. Tổng kết một số điểm mà luận văn đã đạt đƣợc nhƣ sau: - Trình bày về khai phá dữ liệu, các khái niệm cơ bản trong khai phá dữ liệu - Giới thiệu và tập trung vào hai phƣơng pháp phân cụm có thứ bậc và phân cụm theo SOM. - Xây dựng ứng dụng minh họa cho hai thuật toán. Từ đó áp dụng cho một bài toán cụ thể trong BI đó là bài toán: phân loại khách hàng triển vọng và sản phẩm có tiềm năng.