CHƯƠNG 1 GIỚI THIỆU ĐỀ TÀI 1. Phát biểu vấn đề Với sự phát triển của truyền thông vô tuyến (wireless communications) và điện toán di động (mobile computing), việc khám phá tri thức về hành vi di chuyển của các nhóm đối tượng di động khác nhau trong mạng không dây trở nên hết sức cần thiết trong việc dự báo sự di chuyển của nút di động. Đó là vì, những người dùng di động thuộc về một nhóm thường có cùng hành vi di chuyển. Ví dụ, nhóm sinh viên thường di chuyển đến trường học, nhà sách, câu lạc bộ, công viên…nhóm nhân viên hành chánh thường di chuyển đến cơ quan, nhà hàng, quán cà phê… Do đó, chúng ta có thể dự báo vị trí kế tiếp của một đối tượng di động dựa trên hành vi di chuyển của các thành viên trong nhóm mà nó thuộc về.
Xét tổng thể vấn đề, đây là một hệ thống lớn, đòi hỏi công sức của nhiều người. Để xây dựng hệ thống, trước hết chúng ta cần định nghĩa một độ đo thích hợp để đo độ tương tự giữa các mẫu di chuyển trong mạng không dây. Dựa trên độ đo này, chúng ta xây dựng hệ thống gom cụm mẫu theo một phương pháp gom cụm thích hợp. Mục tiêu của đề tài là nhằm giải quyết hai vấn đề chính.
Đó là, chúng tôi đề xuất một giải pháp gom cụm mẫu di chuyển trong mạng không dây dựa trên độ đo tương tự mẫu và xây dựng hệ thống gom cụm hoàn chỉnh. Đối tượng nghiên cứu của đề tài là mô hình và giải thuật. Các công trình liên quan Các phương pháp gom cụm Các phương pháp phân chia: Cho trước một cơ sở dữ liệu với n đối tượng hay các bộ dữ liệu, một phương pháp phân chia được xây dựng để chia dữ liệu thành k phần, mỗi phần đại diện cho một cụm, k≤n. Đó là phân loại dữ liệu vào trong k nhóm, chúng thoả các yêu cầu sau: (1)Mỗi nhóm phải chứa ít nhất một đối tượng, (2)Mỗi đối tượng phải thuộc về chính xác một nhóm.
Nguyễn Huy Cường - Vũ Duy Khánh Trang 7 GVHD: ThS. Dương Thị Thùy Vân Phương pháp phân nhóm theo thứ bậc (Hierarchical Clustering Techniques): o Phương pháp phân nhóm theo thứ bậc làm việc bằng cách nhóm các đối tượng dữ liệu vào trong một cây các cụm. Các phương pháp phân cụm phân cấp có thể được phân loại xa hơn trong phân cụm phân cấp tích đống và phân ly, tuỳ thuộc vào sự phân ly phân cấp được thiết lập theo cách bottom-up hay top-down. o Các nghiên cứu gần đây thường đề cập tới sự tích hợp của tích đống phân cấp với các phương pháp lặp lại việc định vị.
Phân cụm phân cấp tích đống (Agglomerative Aapproach) và phân ly (Divisive Approach): o Phân cụm phân cấp tích đống: bắt đầu bằng cách đặt mỗi đối tượng vào một cụm và sau đó hoà nhập các cụm nguyên tử này lại với nhau dựa trên giá trị hàm mục tiêu, nên các cụm càng ngày càng lớn hơn cho tới khi tất cả các đối tượng nằm trong một cụm đơn hay cho tới khi thoả điều kiện dừng cho trước. Ví dụ về công trình phân cấp tích: phương pháp AGNES (Agglomerative Nesting) (Kaufman và Rousseeuw 1990). Phương pháp này sử dụng phương pháp kết nối đơn, tại đó mỗi cụm được đại diện bởi tất cả các điểm dữ liệu trong cụm, và độ tương tự giữa hai cụm được đo bởi độ tương tự của cặp điểm dữ liệu gần nhất thuộc về các cụm khác nhau. o Phân cụm phân cấp phân ly: Bắt đầu với tất cả các đối tượng trong một cụm, chia nhỏ cụm cho tới khi mỗi một đối tượng hình thành nên một cụm hay cho tới khi thoả một điều kiện dừng cho trước, ví dụ như số lượng các cụm được yêu cầu cần phải có hay khoảng cách giữa hai cụm gần nhất phải thoả một ngưỡng cho trước.
Các phương pháp phân ly nhìn chung không nhiều và hiếm khi được áp dụng bởi khó đưa ra một quyết định đúng của việc phân chia ở một mức cao. Ví dụ về công trình phân ly như DIANA (Divisia Analysis). Nguyễn Huy Cường - Vũ Duy Khánh Trang 8 GVHD: ThS. Dương Thị Thùy Vân Các phương pháp dựa trên mật độ (density)Các phương pháp phân cụm n à y được phát triển dựa trên khái niệm mật độ.
Ý tưởng chung đó là tiếp tục phát triển cụm cho trước với điều kiện là mật độ (số các đối tượng hay các điểm dữ liệu) trong "lân cận" vượt quá ngưỡng, tức là đối với mỗi điểm dữ liệu trong phạm vi một cụm cho trước thì lân cận trong vòng bán kính đã cho chứa ít nhất một số lượng điểm tối thiểu. Các công trình điển hình A Comparison of Ducoment Clustering Techniques công trình của Michael Steinbach, George Karypis, Vipin Kumar.Công trình nghiên cứu về K-means cơ bản và phương pháp K-means phân đôi (bisecting), từ đó tác giả đưa ra quyết định rằng phương pháp K-means phân đôi thì tốt hơn hoặc tốt bằng phương pháp gom cụm thứ bậc (hierarchical clustering). A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining. Mục tiêu của công trình này là phát triển và thực hiện thuật toán gom cụm k-model (mở rộng từ thuật toán k-means), không những loại bỏ được các hạn chế của thuật toán k-means mà còn giữ lại được những ưu điểm của nó.
A hierarchical clustering algorithm for categorical sequence data. Mục đích của công trình nghiên cứu là đề xuất giải pháp gom cụm dữ liệu chuỗi tuần tự. Nhóm tác giả đã định nghĩa một độ đo để đo độ tương tự giữa các đối tượng và phát triển một giải thuật gom cụm phân cấp. A sequence-element-based hierarchical clustering algorithm for categorical sequence data.
Công trìnhđề xuất một phương pháp mới, hiệu quả để gom nhóm dựa trên mật độ mạng và định nghĩa các độ đo tương tự mới. Mục tiêu và phạm vi Trong phạm vi đề tài, chúng tôi tập trung tìm hiểu các giải thuật gom cụm mẫu dựa trên độ đo tương tự mẫu cái mà được tính toán dựa trên không gian và thời gian của mẫu di chuyển, từ đó chúng tôi đề xuất một giải pháp gom cụm mẫu thích hợp trong mạng không dây dựa trên đặc điểm không gian và Nguyễn Huy Cường - Vũ Duy Khánh Trang 9 GVHD: ThS. Dương Thị Thùy Vân thời gian của mẫu di chuyển. Sau đó, chúng tôi tiến hành xây dựng hệ thống gom cụm theo giải pháp đã đề xuất.
Kết quả nghiên cứu của công trình này có thể được ứng dụng trong các hệ thống cung cấp dịch vụ dựa vào vị trí (Locaion based services – LBS) như hệ thống dự báo sự di chuyển của thiết bị di động trong mạng không dây hay hệ thống hỗ trợ đăng ký trước tài nguyên mạng (resource reservation). Nguyễn Huy Cường - Vũ Duy Khánh Trang 10 GVHD: ThS. Dương Thị Thùy Vân Chương 2: CƠ SỞ LÝ THUYẾT VÀ CÔNG NGHỆ 2.1 Tổng quan về gom cụm Tiến hành tách nhóm các đối tượng thành các lớp đối tượng giống nhau được gọi là gom cụm. Trong một cụm dữ liệu các phần tử có độ tương tự giống nhau và khác nhau so với các phần tử của cụm khác.
Phân chia cụm là một phương pháp rất quan trọng, nó là cách để phân biệt giữa các đối tượng Ví dụ : Động vật, Thực vật. -Trong động vật : có nhiều nhóm động vật, động vật ăn thịt, động vật ăn cỏ. Ngày nay các phương pháp gom cụm đã được ứng dụng rộng rãi trong nhiều ứng dụng, nhiều lĩnh vực : khoa học máy tính, kinh tế, sinh học, vật lý, hóa học. Trong kinh tế người ta sử dụng để phân tích thị trường từ đó có các phương pháp kinh doanh hợp lý, sinh học phân loại theo sinh vật, theo các tế bào, phân loại theo kiến trúc gen để có thể tìm ra các phương pháp khám chữa bệnh cũng như tìm ra các loại thuốc trị liệu hiệu quả với một số bệnh nguy hiểm mà con người ngay nay hay mắc phải: ung thư, viêm gan…Trong vật lý người ta có thể dùng các phương pháp gom cụm ứng dụng với các phần cứng : camera trắng, cảm biến ánh sáng, cảm biến âm thanh để áp dụng vào các hệ thống phân tích giao thông, các hệ thống thu phí, phân làn giao thông hiệu quả.Trong phạm vi đề tài này chúng tôi chỉ nghiên cứu các phương pháp gom cụm trong lĩnh vực khoa học máy tính, có rất nhiều các ứng dụng đã áp dụng phương pháp gom cụm phân tích dữ liệu, xử lý ảnh, dự báo trứng khoán, phân tích dữ liệu web để khai thác thông tin và đặc biệt trong lĩnh vực di động.
Hiện nay ở nước ngoài thì việc ứng dụng gom cụm vào các thiết bị di động không phải là mới nhưng trong phạm vi đề tài này chúng tôi đề xuất một phương pháp gom cụm với độ tương tự dựa trên không gian và thời gian của mẫu di chuyển Nguyễn Huy Cường - Vũ Duy Khánh Trang 11 GVHD: ThS. Dương Thị Thùy Vân để từ đó để dự báo hướng di chuyển tiếp theo của thiết bị. Tiếp theo dữ liệu của gom cụm sẽ là dữ liệu cho các giải thuật khác phân loại, mô tả. Chính vì hiệu quả mà nó mang lại khá thực tế cùng với đây là một lĩnh vực khá mới mẻ, có một lượng các bài báo trong nhiều nghiên cứu trong hầu hết các lĩnh vực : thống kê, máy học, kinh tế, khoa học máy tính, cơ sở dữ liệu thời gian thực, cơ sở dữ liệu không gian, sinh vật học, kinh doanh.
Các cơ sở dữ liệu thu thập đều hiệu quả, nghiên cứu sau mang lại hiệu quả cao hơn nghiên cứu trước, chính vì thế việc phân tích dữ liệu trên phương pháp gom cụm đã trở thành một đề tài được nhiều các nhà khoa học nghiên cứu trong nghiên cứu khai phá dữ liệu (Data mining). Theo các đề tài về nghiên cứu phân cụm được công bố các phương pháp gom cụm tập trung dựa trên “khoảng cách” các đối tượng. Từ đó có rất nhiều các phương pháp các thuật toán gom cụm được các nhà khoa học xây dựng : K- means, Hierarchical, k-medoids và một số các phương pháp khác cũng được xây dựng trong các phần mềm hệ thống phân tích thống kê : SAS, S-Plus và SPSS. Trong học máy, phép phân tích cụm thường dựa trên học không giám sát.
Không giống như phân loại, phân cụm không dựa trên các lớp đã định nghĩa trước và các mẫu dữ liệu huấn luyện đã gắn nhãn lớp. Bởi lý do này nên nó có dạng là học bằng sự quan sát, hơn là học bằng các mẫu. Trong phân cụm khái niệm, một nhóm đối tượng hình thành nên một lớp chỉ khi nào nó được mô tả bởi một khái niệm.