Phân cụm đa quan hệ là gì?

Phân cụm đa quan hệ là quá trình phân vùng các đối tượng dữ liệu thành một tập hợp các cụm dựa trên sự tương đồng của chúng, sử dụng thông tin trong nhiều quan hệ. Trong phần này, giới thiệu CrossClus (Phân cụm liên quan chéo với hướng dẫn người dùng), một thuật toán cho phân cụm đa quan hệ khám phá cách tận dụng hướng dẫn của người dùng trong phân cụm và truyền播 ID tuple để tránh các phép join vật lý.

Một thách thức chính trong phân cụm đa quan hệ là có quá nhiều thuộc tính trong các quan hệ khác nhau, và thường chỉ một phần nhỏ liên quan đến một nhiệm vụ phân cụm cụ thể.

Xét cơ sở dữ liệu khoa khoa học máy tính. Để phân cụm sinh viên, các thuộc tính bao phủ nhiều khía cạnh thông tin khác nhau, như các khóa học sinh viên tham gia, các bài báo của sinh viên, cố vấn và nhóm nghiên cứu của sinh viên, v.v.

Người dùng thường quan tâm đến phân cụm sinh viên bằng một khía cạnh thông tin nhất định (ví dụ: phân cụm sinh viên theo lĩnh vực nghiên cứu). Người dùng thường nắm vững yêu cầu ứng dụng và ngữ nghĩa dữ liệu của họ. Do đó, sự quản lý của người dùng trong cấu trúc của một truy vấn đơn giản có thể được sử dụng để cải thiện hiệu quả và chất lượng của phân cụm đa quan hệ chiều cao.

CrossClus chấp nhận các truy vấn của người dùng chứa một quan hệ mục tiêu và một hoặc nhiều thuộc tính liên quan, cùng xác định mục tiêu phân cụm của người dùng. CrossClus định nghĩa các thuộc tính đa quan hệ. Một thuộc tính đa quan hệ A' được định nghĩa bởi một đường dẫn join R_t ⋈ R₁ … ⋈ R_k một thuộc tính R_k.A của R_k, và có thể một toán tử tổng hợp (ví dụ: trung bình, đếm, max).

A' được biểu diễn chính thức bởi [A'.join path, A'.attr, A'.aggr], trong đó A'.aggr là tùy chọn. Một thuộc tính đa quan hệ A' là đặc trưng phân loại hoặc số, tùy thuộc vào việc R_k.A là phân loại hay số. Nếu A' là đặc trưng phân loại, thì đối với một tuple mục tiêu t, t.A' biểu diễn phân phối giá trị giữa các tuple trong R_k có thể join với t.

Trong quá trình phân cụm đa quan hệ, CrossClus cần tìm kiếm các thuộc tính liên quan qua nhiều quan hệ. CrossClus phải giải quyết hai thách thức chính trong quá trình tìm kiếm. Thứ nhất, quan hệ mục tiêu R_t thường có thể join với mỗi quan hệ phi mục tiêu R qua nhiều đường dẫn join khác nhau, và mỗi thuộc tính trong R có thể được sử dụng làm thuộc tính đa quan hệ.

Không thể thực hiện bất kỳ loại tìm kiếm toàn diện nào trong không gian tìm kiếm khổng lồ này. Thứ hai, trong số lượng lớn thuộc tính, một số liên quan đến truy vấn người dùng (ví dụ: cố vấn của sinh viên liên quan đến lĩnh vực nghiên cứu của cô ấy), trong khi nhiều thuộc tính khác không liên quan (ví dụ: thông tin cá nhân của bạn học cùng lớp của sinh viên).