Báo cáo nghiên cứu khoa học: " ÁP DỤNG KỸ THUẬT PHÂN NHÓM VÀO PHÂN MẢNH NGANG LỚP TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

117
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo trình bày việc áp dụng kỹ thuật phân nhóm vào phân mảnh ngang lớp trong cơ sở dữ liệu hướng đối tượng khiến các phân mảnh hiện thời thích nghi với tập các ứng dụng người sử dụng mới; đồng thời đề xuất phương pháp phân nhóm gia tăng dựa trên phân cấp nhân có thể phân lớp lại tập các đối tượng khi thuộc tính các đối tượng tăng lên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: " ÁP DỤNG KỸ THUẬT PHÂN NHÓM VÀO PHÂN MẢNH NGANG LỚP TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG"

TẠP CHÍ KHOA HỌC, Đại học Huế, Số 50, 2009 ÁP DỤNG KỸ THUẬT PHÂN NHÓM VÀO PHÂN MẢNH NGANG LỚP TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG Nguyễn Thị Hương Giang Trường Đại học Sư phạm, Đại học Huế TÓM TẮT Bài báo trình bày việc áp dụng kỹ thuật phân nhóm vào phân mảnh ngang lớp trong cơ sở dữ liệu hướng đối tượng khiến các phân mảnh hiện thời thích nghi với tập các ứng dụng người sử dụng mới; đồng thời đề xuất phương pháp phân nhóm gia tăng dựa trên phân cấp nhân có thể phân lớp lại tập các đối tượng khi thuộc tính các đối tượng tăng lên. I. Giới thiệu Phân mảnh dữ liệu là một trong những hướng nghiên cứu mới trong cơ sở dữ liệu (CSDL), là kỹ thuật thiết kế cơ sở dữ liệu ở mức logic nhằm giảm bớt những truy xuất không cần thiết đến dữ liệu, cho phép thực hiện song song các câu truy vấn bằng cách chia nó ra thành một tập các câu truy vấn con tác động lên các mảnh nhằm nâng cao việc thực hiện các ứng dụng. Trong mô hình quan hệ, có các kiểu phân mảnh: phân mảnh ngang, phân mảnh dọc và phân mảnh hỗn hợp. Phân mảnh ngang là phân hoạch một quan hệ thành một tập các quan hệ con, mỗi quan hệ con này chứa một tập con các bộ (các hàng) của quan hệ ban đầu. Phân mảnh dọc là phân hoạch một quan hệ thành một tập các quan hệ con, trong đó mỗi quan hệ con được định nghĩa trên một tập con các thuộc tính của quan hệ ban đầu. Phân mảnh hỗn hợp phân hoạch một quan hệ thành các tập con các bộ con, trong đó các bộ con được xác định bởi phân mảnh dọc, còn các tập con được xác định bởi phân mảnh ngang. Trong những năm gần đây, do các ứng dụng ngày càng phức tạp, các mô hình CSDL trước đó cũng như mô hình quan hệ đã bộc lộ nhiều nhược điểm trong việc mô hình hóa và xử lý dữ liệu. Có nhiều mô hình CSDL ra đời và được phát triển nhằm khắc phục những hạn chế đó, một trong số chúng là mô hình CSDL hướng đối tượng. Có nhiều điểm tương đồng giữa phân mảnh ngang trong CSDL quan hệ và CSDL hướng đối tượng. Tuy nhiên, do mô hình CSDL hướng đối tượng có các đặc trưng riêng như: tính kế thừa, tính bao gói, phân cấp lớp,… nên chúng ta không thể áp dụng việc phân mảnh ngang từ mô hình quan hệ sang mô hình đối tượng. Do đó, phân mảnh dữ liệu trong CSDL hướng đối tượng vẫn đang được nhiều nhà nghiên cứu quan tâm. Vấn đề chúng tôi đưa ra trong bài báo này là áp dụng kỹ thuật phân nhóm vào phân mảnh ngang lớp trong CSDL hướng đối tượng. 27
Một hệ CSDL hướng đối tượng phân tán muốn tối ưu hóa việc thực hiện các ứng dụng cần phải có phân mảnh lớp và lược đồ phân phối các mảnh này tại các nơi phân tán để cực tiểu việc truyền dữ liệu. Một tiếp cận phân mảnh ngang sử dụng các phương thức gộp nhóm khai thác dữ liệu cho việc phân chia các thể hiện đối tượng thành các mảnh đã được trình bày trong [1], [2], [3], [4]. Nhưng các ứng dụng CSDL thực liên quan tới yếu tố thời gian, do đó, nó đòi hỏi sự phân mảnh để giải quyết tình trạng tại một thời điểm, có một số ứng dụng truy cập vào hệ thống và một số khác lại ra khỏi hệ thống. Trong trường hợp này, để có được phân mảnh phù hợp với tập các ứng dụng người sử dụng mới, chúng ta có thể áp dụng lược đồ phân mảnh ban đầu (ứng với CSDL ban đầu), nhưng cách làm này không hiệu quả. Vì vậy, cần có phương pháp phân mảnh mở rộng giải quyết trường hợp khi các ứng dụng người sử dụng mới đến hệ thống thì các phân mảnh hiện thời phải thích nghi theo. Mặt khác, nói chung, các phương pháp phân nhóm hiện thời bắt đầu với tập các đối tượng biết trước, cùng với tập các thuộc tính biết trước. Nhưng có nhiều ứng dụng có tập thuộc tính mô tả các đối tượng được mở rộng ra, được suy ra. Do đó, chúng tôi đề xuất phương pháp phân nhóm gia tăng dựa trên phân cấp nhân (Hieararchical Core Based Incremental Clustering - HCBIC), có thể phân lớp lại tập các đối tượng khi thuộc tính các đối tượng tăng lên. II. Mô hình vector toán học của CSDL hướng đối tượng Phân mảnh CSDL đối tượng có nghĩa là phân mảnh từng lớp của nó, giả sử gọi lớp đó là C. Một lớp C là một bộ được sắp xếp C=(K, A, M, I), với A là tập các thuộc tính đối tượng, M là tập các phương thức, K là định danh lớp và I là tập các thể hiện của lớp C. Trong phạm vi bài báo, chúng tôi chỉ giải quyết sự phân mảnh nguyên thủy [4]. Các lớp được tổ chức trong một phân cấp kế thừa, trong đó, lớp con là sự chuyên biệt hóa của lớp cha của nó. Bài toán chỉ giải quyết trường hợp thừa kế đơn, nhưng khi chuyển sang thừa kế bội cũng sẽ không ảnh hưởng tới thuật toán phân mảnh, miễn là các xung đột thừa kế được giải quyết bên trong mô hình dữ liệu. Liên kết giữa một đối tượng và một lớp được cụ thể hóa bởi một phép toán cụ thể. Một đối tượng O là một thể hiện của một lớp C nếu C là lớp được chuyên biệt hóa có liên kết (kết hợp) với O trong phân cấp kế thừa. Một đối tượng O là một thành viên của một lớp C nếu O là thể hiện của C hoặc là thể hiện của một trong các lớp con của C. Một CSDL hướng đối tượng là một tập các lớp từ một phân cấp kế thừa, với tất cả các thể hiện của nó. Root là lớp đặc biệt, là tổ tiên (lớp cha) của tất cả các lớp trong CSDL. Do đó, trong mô hình của chúng ta, đồ thị kế thừa là một cây. Các quan hệ khác giữa các lớp trong một CSDL là các mối quan hệ kết hợp và kết tập. Một điểm vào CSDL là một thể hiện siêu lớp (meta-class) trên biến cho trước trong hệ thống. Một điểm vào cho phép sự tìm kiếm từ nó tới tất cả các lớp và các thể hiện lớp của cây con của nó (bao gồm cả nó). Thường có nhiều điểm vào trong một CSDL hướng đối tượng. Cho trước một cây thừa kế phức H, một biểu thức đường dẫn P là C1.A1…An , n≥1 với C là một điểm vào trong H, A1 là một thuộc tính của lớp C1, Ai là một thuộc tính 28
của lớp Ci trong H, Ci là miền thuộc tính Ai-1 của lớp Ci-1 (1≤i≤n). Mục đích của phân mảnh và điều phối phân mảnh của hệ CSDL hướng đối tượng là tối ưu sự thực thi các truy vấn của người sử dụng. Một truy vấn hướng đối tượng là một bộ với cấu trúc như sau: q = (lớp mục tiêu, mệnh đề tính chất), trong đó “lớp mục tiêu” xác định lớp mà truy vấn trả về các thể hiện đối tượng của nó trên nó, “mệnh đề tính chất” là biểu thức logic trên các thuộc tính lớp trong hình thức nối chuNn. Biểu thức logic được xây dựng sử dụng các vị từ đơn giản: attribute Θ value với Θ ∈{ , ≥, ≤, ≠}. Gọi Q = {q1, …, qt} là tập các truy vấn mà phân mảnh thực hiện. PredQ(C) = {p1,.., pn} là tập các vị từ đơn giản. PredQ (C) = { p ∈ PredQ / p là điều kiện của một thuộc tính của lớp C}. Cho trước 2 lớp C và C”, với C” là lớp con của C, PredQ(C”) ⊇ PredQ(C). Do đó, tập các vị từ cho lớp C” gồm tất cả các vị từ được xác định trực tiếp trên các thuộc tính của C” và các vị từ được định nghĩa trên các thuộc tính của lớp cha C của nó và các thuộc tính được thừa kế từ C. Với mỗi một đối tượng Oi trong tập Inst(C ) - tập tất cả các thể hiện của lớp C, i = 1..m, m=|Inst(C)|, ta kết hợp một vector điều kiện ai = (ai1,…,ais), với PredQ(C) = {p1,…,ps}: 0, p j (Oi ) = false aij =   1, p j (Oi ) = true Các đối tượng sẽ được gộp nhóm với nhau trong các phân mảnh sao cho các đối tượng trong cùng một phân mảnh có độ tương tự cao, trong khi độ tương tự so với các đối tượng trong các nhóm khác thấp. Độ tương tự giữa các đối tượng được đo bằng các hàm khoảng cách, áp dụng cho các vector điều kiện mô tả các đối tượng. Chúng ta sử dụng khoảng cách Euclide để đo độ tương tự giữa các đối tượng: s 2 ∑(a − a jl ) với ai, aj là các vector điều kiện của Oi, Oj ∈Inst(C). d E (ai , a j ) = il l =1 2.1. Phân mảnh gia tăng sử dụng thuật toán CBIC (Core-Based Incremental Clustering) Trước tiên, khi đi từ CSDL trung tâm tới CSDL phân tán, ta áp dụng phương pháp phân mảnh khởi tạo. Trong [1], [2], [3], [4], cho trước một tập các truy vấn Qinit = {q1,…,qn}, mệnh đề phân mảnh ban đầu của tập đối tượng Inst(C) của lớp C đòi hỏi trước tiên các đối tượng trong Inst(C) phải được mô hình hóa như đã mô tả ở trên. Sau đó, áp dụng phương pháp phân nhóm k-means trên không gian vector mô tả Inst(C), và kết quả sẽ là các nhóm biểu diễn các phân mảnh cho lớp C. Phân mảnh hiện thời của CSDL hướng đối tượng phân tán được phát triển để tối ưu hóa sự thực thi của tập truy vấn ban đầu, Qinit. Khi các truy vấn mới vào hệ thống Qnew = Qinit ∪ {qp+1, …, qt}, phân mảnh đang tồn tại phải thích nghi theo. Chúng ta áp 29
dụng phương pháp gộp nhóm dựa trên k-means và Core Based Incremental Clustering (CBIC) – phương pháp gộp nhóm gia tăng dựa trên nhân ([5], [6]). Mở rộng của tập truy vấn Qinit thành Qnew có nghĩa là với một số các lớp trong CSDL, tập các vị từ có kết hợp với các lớp sẽ tăng lên. Do đó, các lớp này phải được phân mảnh lại để phù hợp với tập hợp truy vấn mới. Cho C là một lớp như vậy. Với mỗi PredQ-init(C) = {p1,…,pn} xác định PredQ-new(C) ∪ {pn+1,…,ps}. Do đó, vector điều kiện của mỗi một đối tượng Oi ∈ Inst(C) được mở rộng như sau:   a i' =  a i 1 , ..., a i n , a in + 1 , ..., a is   1u kiện ban4của đối tượng O  42 3  a điề  đầ u i i Phương pháp CBIC bắt đầu bằng việc phân chia Inst(C) thành các nhóm bằng cách áp dụng phương pháp k-means trong bước phân mảnh ban đầu. Cho {K1, p UK = Inst (C ) . K2,…,Kp} là các phân mảnh ban đầu của Inst(C), Ki ∩ Kj = ∅, i ≠j, l l =1 Phương pháp CBIC phân chia các đối tượng trong Inst(C): {K1’, K2’,….Kp’} sau khi mở rộng tập truy vấn. Nó bắt đầu từ ý tưởng khi bổ sung một số thành phần (các đặc tính, thuộc tính) vào các vector điều kiện và các thành phần này không mang lại nhiều thông tin trong hệ thống, thì việc sắp xếp thành các nhóm cũ tương tự với phương pháp mới. Thuật toán xác định sau đó các đối tượng bên trong mỗi một phân mảnh Ki có khả năng kết hợp lại với nhau trong cùng một nhóm. Chúng là những đối tượng, sau khi mở rộng thuộc tính, vẫn còn gần hơn với trọng tâm (trung bình nhóm) của nhóm Ki. Các đối tượng này tạo ra cái được gọi là nhân (core) của lớp Ki, gọi là Corei. Trọng tâm của Ki được tính là giá trị trung bình của tất cả các vector điều kiện được mở rộng của các đối tượng trong Ki. Các nhân của tất cả các phân mảnh Ki, i = 1..p, sẽ là nhóm khởi tạo mới cho các bước lặp phân chia tiếp theo bắt đầu. Tiếp đó, thuật toán CBIC tiếp tục theo cùng cách như thuật toán k-means thực hiện. Thuật toán CBIC, cho kết quả hiệu quả hơn là thực hiện k-means từ tập đối tượng có thuộc tính mở rộng. Ví dụ minh họa CSDL hướng đối tượng và tập truy vấn Xét cấu trúc phân lớp trong một CSDL của một trường đại học: Các truy vấn sau thực hiện trên các lớp của CSDL cho ở trên: q1: cho biết tất cả các sinh viên tốt nghiệp đã ghi tên vào khoa Component 30
Oriented Programming và khoa Intelligent Systems, q1= (Grad, Grad.Dept in (“Component Oriented Programming”, “Intelligent Systems”) ). q2: cho biết tất cả các sinh viên chưa tốt nghiệp đã ghi tên vào khoa Computer Science và có điểm trung bình từ 7 đến 10, q2 = (UnderGrad, UnderGrad.Dept like “CS%” and UnderGrad.Grade between 7 and 10). q3: cho biết tất cả các sinh viên chưa tốt nghiệp ghi tên vào khoa Computer Science và khoa Mathematics có tuổi lớn hơn 24, q3 = (UnderGrad, (UnderGrad.Dept like “Math%” or UnderGrad.Dept like “CS%”) and UnderGrad.Age >=24). q4: cho biết tất cả những nghiên cứu sinh đã viết ít nhất 2 bài báo, q4 = (Researcher, Researcher, count(Researcher. Doc) >=2. q5: cho biết tất cả các giảng viên làm việc trong khoa Component Oriented Programming hoặc khoa Intelligent Systems và có lương cao hơn 40.000, q5: (Prof, Prof. Dept in (“Component Oriented Programming“, “Intelligent Systems“) và Prof. Salary >=40.000 q6: cho biết tất cả các giảng viên có bài đăng trên ấn phNm IEEE hoặc ACM, q6 = (Prof, Prof.Doc.Pulisher in (“IEEE”, “ACM”) q7: cho biết tất cả các sinh viên thi trượt, q7 = (Student, Student.Grade 35.000) q9: cho biết tất cả các sinh viên đã tốt nghiệp có đăng ít nhất 1 bài báo, q9 = (Grad, Grad.count(Grad.Doc)>=1) q10: cho biết tất cả các đội ngũ nhân viên có lương cao hơn 12.000, q10 = (Staff, Staff.Salary > 12.000) q11: cho biết tất cả các nghiên cứu sinh viết số bài báo ít hơn số bài báo trung bình của các nghiên cứu sinh, q11 = (Researcher, Researcher.Count(Paper) < Avg( Researcher.Count(Paper) ) q12: cho biết tất cả các sinh viên đã tốt nghiệp lập gia đình, q12 = (Grad, Grad.MaritalStatuss=”married”) q13 : cho biết tất cả các sinh viên chưa tốt nghiệp ghi tên vào khoa Mathematics và khoa Computer Science, q13 = (Undergraduate, Undergraduate.Dept like “Math- CS%”) q14: cho biết tất cả những người có tuổi lớn hơn 30, q14 = (Person, Person, Person.Age > 30) q15 : cho biết tất cả các trợ giảng có tuổi lớn hơn 28, q15 = (Prof, Prof.Position = “assistant professor” and Prof.age > 28) 31
q16 : cho biết tất cả các sinh viên có quốc tịch Hungary hoặc Đức, q16 = (Student, Student.Nationality in (“ hungarian”, “ german”) Các truy vấn từ q1 đến q12 là những truy vấn ban đầu – có được từ phân mảnh ngang và lược đồ phân phối khởi tạo: Qinit = {q1, …., q12}. Các truy vấn từ q13 đến q16 là các truy vấn mới vào hệ thống, và phân mảnh đang tồn tại phải thích ứng để phù hợp và để tối ưu hóa tập ứng dụng mới: Qnew = Qinit ∪ {q13, …, q16}. III. Phương pháp phân nhóm gia tăng dựa trên phân cấp nhân (Hieararchical Core Based Incremental Clustering - HCBIC). Phân lớp là phương pháp phân biệt các nhóm bên trong một tập các đối tượng thực hiện trên tập các đặc tính hoặc thuộc tính có liên quan của đối tượng. Việc phân nhóm được thực hiện trên tập các đặc tính hoặc thuộc tính có liên quan của đối tượng. Các đối tượng bên trong một nhóm được xem là gần nhau hơn các đối tượng trong nhóm khác nhờ vào khái niệm độ tương tự. Độ tương tự giữa các đối tượng được đo bằng hàm khoảng cách hoặc bán khoảng cách trên các giá trị thuộc tính mô tả đối tượng. Phương pháp phân nhóm phân cấp biểu diễn lớp chính của kỹ thuật phân nhóm. Có 2 kiểu phân nhóm phân cấp. Cho trước một tập gồm n đối tượng và một số k, k≤n, phương pháp dưới lên (bottom-up) bắt đầu với n singleton (tập hợp chỉ có 1 thành phần), trộn chúng lại với nhau cho đến khi đạt được số lượng các nhóm k mong muốn. Tại mỗi bước, 2 nhóm tương tự nhau nhất được chọn để trộn. Còn phương pháp trên xuống (top- down) bắt đầu từ một nhóm chứa tất cả n đối tượng và chia nó cho đến khi đạt được số lượng các nhóm k mong muốn. Nói chung, các phương pháp này bắt đầu với tập các đối tượng biết trước, đo trên một tập các thuộc tính biết trước. Nhưng có nhiều ứng dụng có tập đối tượng là động, hoặc tập thuộc tính mô tả các đối tượng liên quan được mở rộng ra. Do đó, để có được phân lớp đối tượng trong các điều kiện này, thuật toán phân nhóm có thể phải thực hiện nhiều lần, bắt đầu từ tập các đối tượng ban đầu, và mỗi lần khi các đối tượng hoặc thuộc tính thay đổi lại thực hiện lại thuật toán. Rõ ràng điều này là kém hiệu quả. Vì vậy, chúng tôi trình bày trong bài báo này phương pháp phân nhóm gia tăng dựa trên phương pháp phân cấp nhân có thể phân lớp lại tập đối tượng khi tập thuộc tính tăng lên. Đầu tiên, chúng ta dùng thuật toán HCA (Hieararchical Clustering Algorithm) [7] để phân chia thành các nhóm, sau đó, khi thuộc tính thay đổi (được mở rộng) thì chúng ta áp dụng thuật toán HCBIC (Hieararchical Core Based Incremental Clustering). Điều này sẽ hiệu quả hơn khi thực hiện lại thuật toán HCA trên tập đối tượng có thuộc tính được mở rộng. 3.1 Định nghĩa Cho {O1, O2, …, On} là tập các đối tượng được phân lớp. Mỗi đối tượng được đo với tập m các thuộc tính khởi tạo và mô tả bởi m vector đa chiều Oi = (Oi1, …, Oim), Oik∈ ℜ, 1≤ i ≤ n, 1 ≤ k ≤ m. Thông thường, thuộc tính liên quan tới các đối tượng đều 32
được chuNn hóa để đảm bảo độ đo của chúng là bằng nhau [3]. Cho {K1, K2, …, Kp} là tập các nhóm có được khi áp dụng thuật toán HCA. Mỗi một nhóm là một tập các đối tượng. K j = {O1j , O 2j ,..., O nj j } , 1≤ j ≤ p. Tâm nhóm Kj biểu diễn giá trị trung bình của nhóm và được xác định bởi:  nj  nj  ∑ Ok 1 ∑ Okm  f j =  k =1  ,..., k =1  nj nj      Ta sử dụng hàm khoảng cách d cho các đối tượng phân biệt, cụ thể là dùng hàm khoảng cách Euclide: m ∑ (O − O jl ) 2 d( Oi, Oj) = dE(Oi, Oj) = il l =1 Việc đo các thuộc tính được thực hiện sau khi mở rộng s (s ≥ 1) thuộc tính mới, được ký hiệu là (m+1), (m+2),…, (m+s). Sau khi mở rộng, vector của đối tượng trở thành Oi’ = (Oi1, …, Oim, Oim+1, …Oim+s), 1≤ i ≤ n. Lấy điểm bắt đầu trong bước phân lớp trước bên trong nhóm và xét trong các điều kiện đó đối tượng mở rộng Oi j ' còn đúng khi đặt nó trong nhóm Kj’ của nó hay không. Để làm được điều đó, chúng ta biểu diễn các khoảng cách fj của Oi j ' tới các tâm cũ của nó và fj’ tới tâm các nhóm mới rồi so sánh với các khoảng cách tới các tâm fr và fr’ của một nhóm bất kỳ khác 1 ≤ r ≤ p, r≠j. Nếu các đối tượng trong nhóm j thỏa mãn các điều kiện và độ tương tự đủ lớn để được giữ cùng với nhau, chúng ta giữ chúng trong một nhóm. Các đối tượng còn lại trong nhóm j (những đối tượng này không thỏa mãn các điều kiện trên) sẽ được trích ra và được phân phối từng đối tượng một vào tập hợp một phần tử của nó. Tiến trình điều chỉnh nhóm này sẽ trả về kết quả là một số các nhóm k’, k ≤ k’ ≤ n. Để có lại được k nhóm đích, chúng ta tiếp tục trộn các nhóm theo cùng cách như thuật toán HCA. Nhưng khi chúng ta không bắt đầu lại từ tập hợp một phần tử, số các bước sẽ giảm đi đáng kể. Định lý: Nếu d E (Oi j , f j ) ≤ d E (Oi j , f r ), ∀j , r ,1 ≤ j , r ≤ p, r ≠ j (1) nj ∑O kl k =1 và Oil ≥ , ∀l ∈ {m+1, m+2, ..., m+s} (2) nj đúng với đối tượng Oij ' và nhóm K 'j của nó thì đối tượng Oij ' gần với tâm f j' của nó hơn các tâm f r' của nhóm khác, 1 ≤ j , r ≤ p, r ≠ j . 33
Chứng minh: 2 2  nj   nr   ∑Okl m+ s  ∑ kl   O m+ s d 2 (Oij ' , f j' ) − d 2 (Oij ' , f r' ) = d 2 (Oij , f j ) + ∑  k =1 − Oil  − d 2 (Oij , f r ) − ∑  k =1 − Oil  l =m+1   l = m+1   nj nr         Sử dụng bất đẳng thức (1), ta có : 2 2  nj   nr  m+ s  ∑ m + s  ∑ kl   Okl O d 2 (Oij ' , f j' ) − d 2 (Oij ' , f r' ) ≤ ∑  k =1 − Oil  − ∑  k =1 − Oil  l = m +1   l = m +1  nr  nj          nj   nj  nr nr m+ s  ∑ Okl ∑ Okl  ∑ Okl ∑ Okl  ⇔ d 2 (Oij ' , f j' ) − d 2 (Oij ' , f r' ) ≤ ∑  k =1  *  k =1 − 2* Oil  − k =1 + k =1 l = m +1    nj  nj nr nr       Nếu bất đẳng thức (2) đúng với mọi thuộc tính của Oij ' thì bất đẳng thức trên trở thành: 2  nj  nr m + s  ∑ kl ∑ Okl  O d (Oi , f j ) − d (Oi , f r ) ≤ − ∑  k =1  ⇔ d 2 (Oij ' , f j' ) − d 2 (Oij ' , f r' ) ≤ 0 2 j' ' 2 j' ' − k =1  nj  nr l = m +1     Vì tất cả các khoảng cách là các số không âm nên: d (O , f j' ) ≤ d (Oij ' , f r' ), ∀r ,1 ≤ r ≤ p, r ≠ j j' i Điều kiện (1) trong định lý đòi hỏi đối tượng Oi ∈ K j , ở bước cuối cùng của tiến trình phân nhóm đầu tiên (khởi tạo), là gần hơn với tâm nhóm của nó hơn tâm của nhóm bất kỳ nào khác. Tất cả các đối tượng Oi ∈ K j thỏa mãn bất đẳng thức (1) và có các mở rộng đối tượng thỏa mãn điều kiện (2), là có độ tương tự đủ lớn với các đối tượng khác cùng nhóm và không tương tự với các đối tượng trong các nhóm khác sau khi mở rộng tập thuộc tính . 3.2. Thuật toán HCBIC Chúng ta dùng các tính chất và định nghĩa ở phần trên để xác định trong mỗi nhóm, những đối tượng nào vẫn được giữ lại với nhau mà không di chuyển sang các nhóm khác. Các đối tượng này là kết quả của sự mở rộng tập thuộc tính, và chúng hình 34
thành nên cái gọi là nhân của nhóm. Định nghĩa: a, Đặt StrongCore j = {Oi j ' | Oi j ' ∈ K 'j , Oi j thỏa bất đẳng thức (1) và Oi j ' thỏa các bất đẳng thức (2)} là tập các đối tượng trong K 'j (trước khi mở rộng) gần với tâm nhóm của chúng hơn với tâm của bất kỳ nhóm nào khác và sau khi mở rộng, mỗi một thuộc tính mới l thỏa mãn bất đẳng thức (2), m + 1 ≤ l ≤ m + s . b, sat (Oi j ' ) là tập tất cả các thuộc tính mới l, m + 1 ≤ l ≤ m + s của đối tượng Oi j ' thỏa mãn bất đẳng thức (2). weakCore j = {Oi j ' | Oi j ' ∈ K 'j , Oi j t h ỏa bất đẳng thức (1) và nj ∑ | sat (O j' )| k j' k =1 | sat (Oi ) |≥ } nj Tập thuộc tính của các đối tượng trong K 'j thỏa mãn bất đẳng thức (1) trước khi mở rộng; và sau khi mở rộng thì ít nhất là trung bình cộng thuộc tính mới của các đối tượng trong K 'j thỏa mãn bất đẳng thức (2). c) Core j = StrongCore j nếu StrongCore j ≠ ∅ , nếu không thì Core j = weakCore j . OCore j = K 'j \ Core j là tập các đối tượng ngoài nhân trong nhóm K 'j . Với mỗi thuộc tính mới l, m + 1 ≤ l ≤ m + s và mỗi nhóm K 'j có ít nhất một đối tượng thỏa bất đẳng thức (2) tương ứng với thuộc tính l. Đó là đối tượng có giá trị thuộc tính l lớn nhất trong số các đối tượng trong K 'j chắc chắn thỏa quan hệ (giá trị lớn nhất trong một tập hợp lớn hơn hoặc bằng giá trị trung bình của tập hợp đó). Nhưng không đảm bảo trong nhóm K 'j có đối tượng thỏa quan hệ (2) cho tất cả các thuộc tính mới m+1,…, m+s. Nếu có các đối tượng như vậy thỏa bất đẳng thức (1) ( StrongCore j ≠ ∅ ) thì theo định lý trên, chúng gần với tâm nhóm f j' hơn với bất kỳ một tâm nhóm f r' nào khác, 1 ≤ r ≤ p, r ≠ j . Sau đó, Core j sẽ được lấy bằng với StrongCore j , và sẽ là tâm của nhóm j trong thuật toán gia tăng. Nhưng nếu StrongCore j = ∅ thì ta sẽ chọn là tâm nhóm j cho đối tượng ổn định (không thay đổi) nhất trong số các đối tượng trong K 'j . Các đối tượng này ( weakCore j ) có thể ít thay đổi nhất trong số các đối tượng trong StrongCore j . Tuy nhiên, điều này là không chắc chắn vì: các đối tượng trong tập “yếu hơn” weakCore j có thể lại thích hợp như các đối tượng trong StrongCore j , đó là do ta thấy điều kiện (2) trong định lý biểu diễn điều kiện đủ cho các đối tượng trong K 'j là 35
gần với f j' hơn với tâm nhóm f r' nào khác, nhưng không phải là điều kiện đủ. Các nhân của nhóm sẽ là các nhóm mới trong tiến trình phân nhóm gia tăng. Thuật toán phân nhóm gia tăng dựa trên phân cấp nhân và sẽ dừng khi đạt được số các nhóm mong muốn. Input: - X = {O1 ,..., On } : tập m các đối tượng được phân nhóm trước đó - Tập X'={O1 ,..., On } : tập m+s các đối tượng mở rộng được phân nhóm, Oi' có ' ' cùng m thành phần đầu tiên như Oi , - Khoảng cách dE giữa các đối tượng trong không gian đa chiều, - p: số lượng các nhóm mong muốn, - K={K1 ,..., K p } : tập các đối tượng được phân lớp trước đó trong X. Output: Phân lớp lại K'={K1' ,..., K p } cho các đối tượng trong X’. ' Thuật toán được mô tả như sau (theo ngôn ngữ “tựa” Pascal): Begin For tất cả các nhóm Kj ∈K do Tính Corej = (StrongCorej ≠ ∅) ? StrongCorej:=WeakCorej Tính Ocorej = Kj \ Corej EndFor C=∅ //tập hợp nhóm hiện thời For i=1 to p do If Corei ≠ ∅ C = C ∪ {Corej} EndIf For tất cả O ∈ Ocorej do C = C ∪ {O} //thêm một tập hợp một phần tử vào C EndFor EndFor While |C| > p do ( Cu* , Cv* ) := arg m in(Cu , Cv )d E (Cu , Cv ) Cnew = Cu* ∪ Cv* C = C \{Cu + , Cv+ ) ∪ {Cnew } EndWhile K ' =C End. 36
Khoảng cách giữa hai nhóm dE(Cu,Cv) được tính như sau: ∑ a ∈C ∑b ∈ Cv d E (ai , b j ) i u j d E (Cu , Cv ) = | Cu | × | Cv | Thuật toán bắt đầu bằng việc tính nhân các nhóm cũ. Các nhân sẽ là các nhóm khởi tạo mới trong các bước lặp tiếp theo. Sau đó, thuật toán được thực hiện như thuật toán HCA. 3.3 So sánh tính hiệu quả của thuật toán HCBIC và thuật toán HCA Chúng ta so sánh thuật toán HCBIC và HCA theo tiêu chí số lần lặp và độ “chặt” của các nhóm đạt được. Định nghĩa độ phân tán DISP (dispersion) trong tiến trình phân nhóm như sau: ∑ d (Oi , O j ) p ∑ Oi ,O j ∈K k ,i > j C|2 k | k =1 K DISP( K ) = p Với K={K1, …, Kp} là tập hợp nhóm có được sau khi áp dụng thuật toán phân nhóm. DISP biểu diễn khoảng cách trung bình giữa các đối tượng trong một nhóm. Khoảng cách này là nhỏ hơn và “chặt” hơn so với khoảng cách trong HCA [8]. IV. Kết luận Áp dụng kỹ thuật phân nhóm vào phân mảnh ngang lớp trong CSDL hướng đối tượng là phương pháp xử lý có hiệu quả trong các bài toán phân mảnh. Đây là một hướng nghiên cứu mới và có giá trị thực tiễn. Trong tương lai, chúng tôi sẽ ứng dụng và phân tích thuật toán trên các CSDL thực nghiệm cụ thể đồng thời nghiên cứu lý thuyết phân nhóm phân cấp sẽ được áp dụng cho các kỹ thuật phân nhóm khác như thế nào. TÀI LIỆU THAM KHẢO 10. Darabant, A.S., Campan, A., Semi-supervised learning techniques: kmeans clustering in OODB Fragmentation, IEEE International Conference on Computational Cybernetics ICCC 2004, Vienna University of Technology, Austria, August 30 - September 1 (2004), 333–338. 11. Darabant, A.S., Campan, A., Hierarchical AI Clustering for Horizontal Object Fragmentation, In Proc. of Int. Conf. of Computers and Communications, Oradea, May (2004), 117–122. 12. Darabant, A.S., Campan, A., AI Clustering Techniques: a New Approach to Object Oriented Database Fragmentation, in Proceedings of the 8th IEEE International Conference on Intelligent Engineering Systems, Cluj Napoca, (2004), 73–78. 37
13. Darabant, A.S., Campan, A., Cret, O., Hierarchical Clustering in Object Oriented Data Models with Complex Class Relationships, in Proceedings of the 8th IEEE International Conference on Intelligent Engineering Systems, Cluj Napoca, (2004), 307–312. 14. S¸erban, G., Campan, A., Core Based Incremental Clustering, Studia Universitatis “Babe¸s-Bolyai”, Informatica, XLXI(2), (2005), 89–96. 15. S¸erban, G., Campan, A., Incremental Clustering Using a Core-Based Approach, in Proc. of the 20th International Symposium on Computer and Information Sciences (ISCIS’05), Istanbul, Turkey, 2005. 16. S. Aeberhard, D. Coomans, and O. de Vel. The classification performance of rda. Tech. Rep. Dept. of Computer Science and Dept. of Mathematics and Statistics, James Cook University of North Queensland, (1992), 92-01. 17. Gabriela S¸erban and Alina Cˆampan. A New Core-Based Method For Hierarchical Incremental Clustering. Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2005 (SYNASC’05). 18. C. Manning and H. Schutze. Foundation of statistical natural language processing. MIT, 1999. 19. G. Serban and A. Campan. Core based incremental clustering. Studia Universitatis “Babes¸-Bolyai”, Informatica, L(1), (2005), 89–96. 20. Alina Campan, Adrian Sergiu Darabant, Gabriela Serban. Clustering techniques for adaptive horizontal fragmentation in object oriented databases. Proceedings of the International Conference on Theory and Application of Mathematics and Informatics ICTAMI 2005 - Alba Iulia, Romania. APPLYING CLUSTERING TECHNIQUES FOR HORIZONTAL FRAGMENTATION IN OBJECT ORIENTED DATABASES Nguyen Thi Huong Giang College of Pedagogy, Hue University SUMMARY In this paper, we introduce an incremental method to apply clustering techniques for horizontal fragmentation in object oriented databases which makes current fragments adapt with new applications; and propose a clustering method based on an hierarchical agglomerative approach, called Hierarchical Core Based Incremental Clustering (HCBIC), that is capable of the re-partition of the objects set, when the attribute sets increase. 38