- Trang Chủ
- Cơ sở dữ liệu
- Phân mảnh dữ liệu trong thiết kế cơ sở dữ liệu phân tán dựa vào kỹ thuật phân cụm hướng tri thức
Xem mẫu
- Lê Văn Sơn, Lương Văn Nghĩa
PHÂN MẢNH DỮ LIỆU TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN
DỰA VÀO KỸ THUẬT PHÂN CỤM HƯỚNG TRI THỨC
FRAGMENTATION IN DISTRIBUTED DATABASE DESIGN
BASED ON KNOWLEDGE-ORIENTED CLUSTERING TECHNIQUE
Lê Văn Sơn1 , Lương Văn Nghĩa2
1
Trường Đại học Sư phạm, Đại học Đà Nẵng; Email: levansupham2004@yahoo.com
2
Trường Đại học Phạm Văn Đồng; Email: nghia.itq@gmail.com
Tóm tắt – Bài toán tối ưu hóa cơ sở dữ liệu phân tán bao gồm các Abstract – The optimization problem of data fragmentation
bài toán: phân mảnh và định vị dữ liệu. Có nhiều phương pháp tiếp is requiring to several interrelated problems including: Data
cận khác nhau và nhiều thuật toán được đề xuất để giải quyết các fragmentation and Data allocation. Although we had many different
bài toán này. Tuy nhiên, độ phức tạp của thuật toán vẫn còn là một algorithms to approach solving problems, the complexity of
thách thức. Trong bài báo này, chúng tôi sử dụng kỹ thuật phân cụm algorithm is always a big challenge to solve. In this paper,
hướng tri thức cho cả hai bài toán phân mảnh ngang và phân mảnh we presented a knowledge-oriented clustering technique that is
dọc dữ liệu. Độ đo tương tự sử dụng trong hai thuật toán là các độ applying both of vertical fragmentation and horizontal fragmentation
đo được phát triển từ các độ đo cổ điển. Kết quả thử nghiệm trên problems. Similarity measures are used in both of algorithms which
các tập dữ liệu nhỏ hoàn toàn trùng khớp với kết quả phân mảnh were built in the traditional measures. The experimental result of
dựa vào các thuật toán cổ điển. Thời gian thực hiên phân mảnh dữ small data files and the fragmentation result based-on traditional
liệu cũng được giảm đáng kể (mặc dù độ phức tạp thuật toán trong algorithm are similar. The execution time of fragmented data is
trường hợp tổng quát vẫn chưa thay đổi). significantly reduced. (Although, the complexity of algorithm in the
general case is still un-changed).
Từ khóa – cơ sở dữ liệu phân tán; phân mảnh; định vị; độ đo tương Key words – distributed database; fragmentation; allocation;
tự, phân cụm; kỹ thuật phân cụm hướng tri thức. similarity measures; clustering; knowledge-oriented clustering
technique.
1. Đặt vấn đề điển và khai phá dữ liệu [2].
Trong môi trường phân tán, mỗi đơn vị dữ liệu (item) Nội dung chính của bài báo được tổ chức như sau: Các
được truy xuất tại các trạm (site) thường không phải là một khái niệm cơ sở được trình bày trong Mục 2. Mục 3, trình
quan hệ mà chỉ là một bộ phận của quan hệ. Vì vậy, để tối ưu bày thuật toán phân cụm hướng tri thức. Mục 4, 5 lần lượt
hóa quá trình thực hiện các truy vấn, các quan hệ của lược trình bày thuật toán phân mảnh dọc, phân mảnh ngang đề
đồ toàn cục (global scheme) được phân mảnh thành các đơn xuất. Mục 6 là phần kết luận.
vị dữ liệu. 2. Một số khái niệm cơ sở
Các loại phân mảnh dữ liệu bao gồm phân mảnh dọc,
phân mảnh ngang, phân mảnh hỗn hợp (mixed) và phân 2.1. Phân mảnh dọc
mảnh suy dẫn (derivate). Hai thuật toán cổ điển gắn liền với Phân mảnh dọc là phân rã tập thuộc tính của lược đồ
phân mảnh ngang và phân mảnh dọc lần lượt là thuật toán quan hệ R thành các lược đồ con R1 , R2 , .., Rm , sao cho
PHORIZONTAL và thuật toán BEA [5]. Nhiều tác giả đã đề các thuộc tính trong mỗi lược đồ con là thường được truy
xuất các thuật toán cải biên hai thuật toán này như Navathe vấn cùng nhau. Để thể hiện mức độ hay cùng được truy
và đồng sự (1984), Cornell và Yu (1987), Chakravarthy và vấn cùng nhau, Hoffer và Severance đưa ra khái niệm ái lực
đồng sự (1994), Bellatreche (2000), Schewe (2002),.. Tuy thuộc tính (attribute affinity) [13].
nhiên, độ phức tạp của các thuật toán này là khá lớn, phân Nếu Q = q1 , q2 , .., qm là tập các ứng dụng,
mảnh dọc là O(n2 ) với n là số lượng thuộc tính, phân mảnh R(A1 , A2 , .., An ) là một lược đồ quan hệ. Mối quan hệ giữa
ngang là O(2m ) với m là số bản ghi [5][8]. ứng dụng qi và thuộc tính Aj được xác định bởi giá trị sử
Trong thời gian gần đây, một số tác giả đã kết hợp giải dụng [2]:
bài toán phân mảnh và bài toán định vị bằng các thuật toán
1, Aj có tham gia qi
tối ưu [9][14] hay sử dụng các thuật toán heuristic [1][9], use (qi , Aj ) = (1)
0, Aj không có tham gia qi
thời gian thực hiện các thuật toán này giảm đáng kể so với
các thuật toán cổ điển mặc dù độ phức tạp của giải thuật Đặt Q(A, B) = q ∈ Q|use(q, A).use(q, B) = 1. Ái lực
trong trường hợp tổng quát vẫn chưa được cải thiện. Sử giữa 2 thuộc tính Ai , Aj :
dụng kỹ thuật luật kết hợp trong khai phá dữ liệu để phân !
mảnh dọc dữ liệu đã được đề cập [10], tuy vậy các kỹ thuật X X
Aff(Ai , Aj ) = refl (q) ∗ accl (q) (2)
khai phá dữ liệu khác cũng chưa được các tác giả quan tâm
q∈Q(Ai ,Aj ) ∀Sl
ứng dụng.
Trong bài báo này, chúng tôi đề xuất sử dụng thuật toán Trong đó, refl (q): số lần cặp thuộc tính (Ai , Aj ) được
phân cụm hướng tri thức cho 2 bài toán phân mảnh dọc và tham chiếu trong ứng dụng q tại trạm Sl; accl(q): tần số truy
phân mảnh ngang. Các độ đo tương đồng (similarity) được xuất ứng dụng q đến các thuộc tính (Ai , Aj ) tại trạm Sl .
phát triển dựa trên các độ đo đã có trong các thuật toán cổ Thuật toán BEA thực hiện gồm 2 giai đoạn chính:
59
- dù tính sinh ra 1 ma trận ái lực tụ thuộc tính CA (Cluster
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II
át Affintity matrix) có số đo ái lực chung AM (global
ợp (1). measure)
affinity Hoán vị hàng, cộtnhất
là lớn của ma
[5].trân ái lực thuộc tính sinh Một quan hệ tương đương (quan hệ 2 ngôi thỏa các tính
ra 1 ma trận ái lực tụ thuộc tính CA (Cluster Affintity matrix) chất phản xạ, đối xứng và bắc cầu) xác định trên U được gọi
đã (2).áiTìm điểm AM phân(global
hoạchaffinity
tập thuộc tính là
từ lớn
ma
có số đo lực chung measure) là một quan hệ không phân biệt trên U.
ệu trận tụ thuộc tính CA bằng phương pháp vét cạn, sao
nhất [5].
3. Thuật toán phân cụm hướng tri thức
cho (2).
[8]: Tìm điểm phân hoạch tập thuộc tính từ ma trận tụ
ng thuộc tính CA bằng phương pháp vét cạn, sao cho [8]: Thuật toán phân cụm hướng tri thức KO-Knowledge-
Z= CTQ *CBQ – COQ2 đạt cực đại, với:
Z = CTQ ∗ CBQ − COQ2 đạt cực đại, với: Oriented Clustering dựa vào lý thuyết tập thô đầu tiên
án
CTQ ref j (q j )acc j (qi ) được đề xuất bởi nhóm tác giả Shoji Hirano and Shusaku
ng qTQ Sj
X X
Tsumoto (2001) [12]. Đây là thuật toán phân cụm tự động
CTQ = refj (qj )accj (qi )
đã q∈TQ ∀Sj
xác định số cụm dựa vào bộ dữ liệu khảo sát. Ý tưởng chính
]. CBQ
CBQ =
X ref jX
(q j )acc j (q i )
refj (qj )accj (qi )
của thuật toán phân cụm này gồm 2 giai đoạn [3]:
1. Xây dựng 1 quan hệ tương đương ban đầu trên tập các
hư qBQ Sj
q∈BQ ∀Sj đối tượng cần phân cụm.
2.
ref
X X 2. Hiệu chỉnh các quan hệ tương đương bằng cách sử
c.
COQ COQ = refj (qj (j )acc
j (q j )acc q i ) j (qi )
dụng một ngưỡng Tk dựa trên độ không phân biệt.
qOQ Sj
q∈OQ ∀Sj
c, Quá trình lặp cập nhật lại Tk cho đến khi thu được
phân cụm tốt nhất.
A1 A2 .. Ai A i+1 .. An Thuật toán này được nhóm tác giả C.L Bean,
A1 C.Kambhampati hiệu chỉnh và thử nghiêm (2008) [4] (bài
báo của nhóm tác giả chỉ xây dựng lại quan hệ tương đương
.. TA ban đầu dựa vào ý tưởng đường “đẳng trọng” so với cách
ủa Ai xây dựng dựa trên gradient của nhóm tác giả Shoji Hiran,
m, Shusaku Tsumoto). Các kết quả thử nghiệm của 2 nhóm tác
Ai+1 giả trên nhằm minh họa cho thuật toán, chưa đưa ra các ứng
là
dụng trong thực tế.
độ BA
Sử dụng thuật toán này để phân mảnh dữ liệu, chúng tôi
và An đã đề xuất quan hệ tương đương ban đầu dựa trên khoảng
te Hình 1. 1:Ma
Hình Matrận
trận tụ thuộctính
tụ thuộc tính
CACA cách trung bình giữa các đối tượng.
Thuật toán phân cụm hướng tri thức chúng tôi sử dụng
Trong
Trong đó, đó,
g, cụ thể như sau:
AQ(q
AQ(qii)= {A
) ={A |use(qi,A
j| juse(q j)=1};
i, A TQ={qi | AQ(qi) TA}
j ) = 1}; Input: U= Tập các đối tượng cần phân cụm
hệ TQ = {qi |AQ(qi ) ⊆ TA};
BQ= i | AQ(qi) BA}; OQ=Q\ {TQBQ} (Mỗi đối tượng phải được mô tả các thông tin cần thiết
ởi BQ ={q{q |AQ(q ) ⊆ BA};
i i
để xây dựng độ tương tự).
Độ=phức
OQ Q{TQtạpcủa thuật toán tỉ lệ với n2
∪ BQ}.
Output: Các phân cụm (tương ứng với các phân mảnh
2.2. Độ
Phân mảnh
phức tạp của thuật toán tỉ lệ với n2 .
ngang dữ liệu)
2.2. Phân
Phânmảnh
mảnhngang
ngang là phân chia tập các bản ghi Method:
Bước 1: Xây dựng ma trận độ tương tự S=S(ti , tj ) giữa
thành các tập bản ghilà nhỏ
Phân mảnh ngang phânhơn. Phân
chia tập cácmảnh
bản ghingang dựa
thành các
Ái tập bản ghi nhỏ hơn. Phân mảnh ngang dựa vào các vị
điều tất cả các cặp đối tượng(ti , tj ).
vào các điều kiện truy vấn được thể hiện qua các từ
kiện truy vấn được thể hiện qua các vị từ đơn giản có dạng: Bước 2: Chỉ định một quan hệ không phân biệt ban đầu
đơn giản có dạng: Ri cho từng đối tượng. Tổng hợp để có được một phân cụm
2) P : Aj θ
ĐặtP:PA j ban đầu.
r = {p1 , p2 , .., pk } là tập các vị từ đơn giản được
trích raĐặt Bước 3: Xây dựng ma trận bất khả phân biệt Γ =
từ tập
Pr các
= {pứng
1, pdụng. k} là
Một
2, .., p hộitập cácđược
vị từ vị từ
xâyđơn giản
dựng từ
Aj) Pr có dạng: ν(ti , tj ) để đánh giá chất lượng phân cụm.
được trích ra từ tập các ứng dụng. Một hội vị từ được
p1 ∗ ∧p2 ∗ ∧.. ∧ pn ∗ (3) Bước 4: Sửa đổi phân cụm theo một quan hệ bất khả
xây dựng từ Pr có dạng: phân biệt mới Rimod cho từng đối tượng để đạt được một
ác Trong đó pi ∗là vị từ mang 1 trong giá trị là pi hay ¬pi
p1* p2* ..pn* (2.3) phân cụm sửa đổi.
ực Thuật toán PHORIZONTAL sử dụng các hội vị từ Bước 5: Lặp lại bước 3 và 4 cho đến khi thu được một
có thểTrong đó ptừi*Plàr , vị
xây dựng để từ
tìmmang 1 trong
các điều kiện giá
phântrịmảnh
là pi
phân cụm ổn định.
ngang dữ liệu [11]. Quan hệ r(R) sẽ được phân mảnh thành
Chi tiết của thuật toán có thể tham khảo [4][12]. Điểm
{r1 (R), r2 (R), .., rk (R)}, với ri (R) = σFi (r(R)), 1 ≤ i ≤ k;
cần lưu ý là chúng tôi đề xuất cách xây dựng quan hệ không
Fi là một vị từ hội sơ cấp (mj ).
phân biệt ban đầu khác với 2 nhóm tác giả Shoji Hirano,
2.3. Hệ thống thông tin và quan hệ không phân biệt Shusaku Tsumoto và C.L Bean, C.Kambhampati như sau:
Hệ thống thông tin là một cặp SI=(U, A), trong đó U là Quan hệ không phân biệt ứng với thuộc tính thứ i:
tập hữu hạn các đối tượng U={t1 , t2 , .., tn }, A là tập hữu Ri = {(ti , tj ) ∈ U × U : d(ti , tj ) ≤ Thi với j = 1, 2,
hạn khác rỗng các thuộc tính. . . . , n}
60
- Định nghĩa 1. Độ đo tham chiếu của giao tác qi {q1, q2, q3, q4}, và F = {f1, fLê Văn Sơn, Lương Văn Nghĩa
2, f3, f4} = {45, 5, 75, 3}.
với thuộcTrongtính đó
Aj d(t
ký i hiệu
, tj ) làM(q i, Ajcách
khoảng Mij2làđốitần
) haygiữa suấttham
tượng - TậpTừtần giảsuất
thiếtthựcta có cácứng
hiện vectorvới đặc trưng
tập các tham
giao tác
gia qphân
giao tác i cụm.
tham chiếu đến thuộc tính A j được xác định {q
chiếu: 1 , q2 , q3 , q4 }, và F = {f1 , f2 , f3 , f4 } = {45, 5, 75, 3}.
bởi giá trị:
Ngưỡng Thi được xác định như sau: Từ giả thiết ta có các vector đặc trưng tham chiếu:
q q q q 1 2 3 4
M(qi, Aj) = Mij= nuse(qi ,TẠP
Aj )* fi VA1= 45q1 0 q2 0 q3 0 q4
CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ ……………….
X VA12== 045 5 0 75 0 0 0
Với: fi làThtần
i =suất thực(1
− s(t
hiện củai , tjgiao tác −
)) /(n qi 1)
và
(4)
VA23== 450 5 5 0 75 3 0
j=1,j6=i
use(qi, Aj) xácĐịnh định nghĩa
bởi công 1. Độthứcđo(2.1).
tham chiếu của giao tác qi {qVA
1, q3
= 045 0 5 = {f
2, q3, q4}, và F75
4= 0 1,3f2,3f3, f4} = {45, 5, 75, 3}.
Với s(t , t ) là độ tương tự của 2M(q
đối tượng ti , tj .M
[2].là tần suất VA4 = 0 0 75 3
với thuộc
i j tính A ký hiệu
Định nghĩa 2. Vector đặc trưngi, tham
j Aj) haychiếu ijVA j Từ giả thiết ta có các vector đặc trưng tham
4. giao
của thuộc tính
Phân tác Aqji ứng
mảnh tham
dọc chiếu
với cơ đến
hệtham thuộc
sởchiếu
dữ tính
của
liệu các
phân Ajtán được
giao tácxác
dựa vàođịnh MaMa
trận độ tương
chiếu: tương
trận độ tự S4x4
tự = (s(A
S4x4 k , Akl ))
= (s(A ,A l)) k=1,4;l=1,4
k=1,4;l=1,4
bởi giá
thuật trị:
toán phân cụm
(q1, q2, ..,qm) được xác định như sau: hướng tri thức
A1 A2 A3 q1 qA2 4 q3 q4
Để chuyểnM(qiq, bàiAj) toán
= Mphân
ij = usemảnh
(qi ,dọc
A j )trọng
* f i hệ cơ sở dữ A1 1 0VA1=0.9918
45 00 0 0
1
liệu phân tán, các q … q
giả thiết2 bài toán được mchuyển đổi sang A2 1VA2=0.0073
0 50.9970
75 0
Với:
giả thiết bài fi là
toán tầncụm
phân suấtdựathực
vàohiện
các của
kháigiao
niệmtác
sau:qi và A3 VA3= 45 50.0026
1 0 3
VAj= M1j M2j … Mmj A4 01 75
use(q
4.1. ) xácvàđịnh
i, Ajtính
Thuộc bởiđặc
Vector công thức
trưng (2.1).
tham chiếu VA4= 0 3
Kết quả phân mảnh bằng thuật toán phân cụm
4.2. Độ
Địnhđo nghĩa
tương
Định 1.đồng của
nghĩa
Độ đo 2.2Vector
tham thuộc
chiếu tính
đặc trưngtáctham
của giao qi vớichiếu
thuộcVAj Kết quả phân mảnh bằng thuật toán phân cụm hướng tri
tính
hướng tri thức
thức thu được:thu được:
củaAjthuộc
Định
ký hiệu M(qi,
nghĩatính 3. A
Độ
Aj) hay tham
j ứng
đo với
Mij làchiếu
tương đồng
tần suất
của của
giao
cáctác
2 thuộc
qi tác
giao Ma trận độ tương tự S4x4= (s(Ak, Al)) k=1,4;l=1,4
tham chiếu đến thuộc tính Aj được xác định bởi giá trị Cụm Tập thuộc tính
tính A(q , ql 2có
k, 1A được xác
2 m)vector
, ..,q đặc định
trưngnhư sau:chiếu tương
tham Cụm ATập
1 thuộc
A2 A tính
3 A4
M(q , A ) = M = use(q , A ) ∗ fi 1 1 {A1, {A A3} }
ứng với bộ các
i j
giao tácij(qq1,1 q2, ..,q
i i A1 {A 1 ,A 0}1 , A30.9918 0
q:2
Với: fi là tần suất thực hiện của giao tác q…
m): qm 2 2 {A4 ,A }
i và use(qi , Aj ) A22 12 40.0073 0.9970
VAđịnh
xác k = (M , M2kthức
bởi1kcông , .., (1).
Mmk) Nhận xét: A3 1 0.0026
Nhận xét:
VA M M … M Kết
Kếtquả
quảphân
phân mảnh nàytrùng
trùngkhớp khớpvới với
VAl =
Định (M1l2.
nghĩa j=, .., M 1j
, MVector
2l đặc
ml )trưng 2j
tham chiếu VAj mj
của thuộc A 4 1 kết quả
mảnh này kết quả phân
tính Aj ứng với tham chiếu của các giao tác (q1 , q2 , .., qm ) phân
được xácđo định bởi độ đo cosin: mảnhmảnh
dọc dọc
theo Kết
theo
thuậtquả
toánphân
thuật toán
BEA. mảnh
BEA. bằng thuật toán phân cụm
Độ
4.2.xác
được định tương
như sau:đồng của 2 thuộc tính hướng tri thức thu được:
Định nghĩa 3. Độ m
đo tương đồng của 2 thuộc Phânmảnh
5. 5.Phân mảnhngang
ngang hệ cơsởsởdữ
hệ cơ dữliệuliệu phân
phân tántán
dựadựa
vào
tính VA Akk, *AVA l có
VA
q1
2 Mvector qM2 ik *...
M il m
Mđặc trưng
q
... Mtham chiếu tương cụm Cụm
vào thuật toán phân cụm hướng tri thức
thuật toán phân hướng Tập
tri thuộc
thức tính
jl=
s(Ak, Aứng
l) = 1j i 1 2j mj 1 {A1, A3}
với
VAkbộ* các VAl giao tác m (q1, q2, ..,q m m):: (4.1) Tươngtự như
Tương như phân mảnh
phân mảnh
2 dọc2trong
dọc
{A ,Atrong
hệ hệ
cơ cơ sở liệu
sở dữ dữ
4}
4.2. Độ đo tương đồng của M
VAk = (M1k, M2k, ..,ikMmk)
i
1
2 thuộc
2
*
i 1
tínhM 2
il
phân
liệu phân
thuật
tán,
Nhận
toán
việc chuyển
tán,xét: đổi giả thiết phân mảnh
việc chuyển đổi giả thiết phân mảnh
PHORIZONTAL dựa trên các khái
ngang
niệm
[2]
cơ
từ
sở
Định nghĩa 3. Độ đo tương đồng của 2 thuộc tính Ak , Al ngang [2] từ thuật toán PHORIZONTAL dựa trên các
có 2 vectorVA đặcl = (M1l, M2l, .., Mml)
trưng tham chiếu tương ứng với bộ các giao sau: Kết quả phân mảnh này trùng khớp với kết quả
4.3. Phân mảnh dọc): dựa vào thuật toán phân cụm khái niệm cơ sở sau:
tác (q1 , qđược xác định bởi độ đo cosin:
2 , .., qm phân mảnh
5.1. Vector hóa cácdọc bảntheo ghi thuật
của một toán quanBEA hệ[A9].
hướng tri thức 5.1. Vector hóa các bản ghi của một quan hệcác vị từ
VAk = (M1k , M2k , .., Mmk ) m Xét quan mảnh hệ r(R)={T ngang 1, T hệ 2 , cơ
.., Tsởl }, dữ tậpliệu phân tán dựa
Để minh họa 5. Phân
VAl = (Mphân mảnh dọc dựa vào
1l , M2l , .., Mml )
M ik *thuật
M il toán đơn giản rút trích từ các ứng dụng trên r(R) là
hệtoán r(R)={T1,cụm ..,Tl}, tập các vị từ
Pr = vào
{Pr1thuật Prmphân
VAk *VA Xét quan T2, hướng tri các
thức
phân cụms(Ahướng
k, Al) =
tri thức, sử ldụng lại igiả 1 thiết ví dụ bài , Pr2 , .., }. Vector hóa nhị phân bản ghi
được xác địnhVA bởi *độVAđo cosin: (4.1)đơn giản rút trích
Tương từ các
như ứngphân dụng mảnh trên r(R)
dọc là
trongPr={Pr 1,
hệ cơ sở dữ
toán phân mảnh dọc kdựa vào thuật toán
m
BEA được
m theo qui tắc:
l
m}. Vector hóa nhị phân các bản ghi theo qui
2 2
MP m * M il Pr2, ..,Prliệu phânPrtán, việc chuyển Prj đổi ... giả Prmthiết phân mảnh
ik
trình bày trong [2]: i 1 Miki ∗1Mil Pr ...
VAk ∗ VAl tắc: 1 2
ngang T1[2] Pra1từ11 thuật
Pr2a12 ..toán ...PrPHORIZONTAL dựa trên các
i=1
a1j.. Pr ... a1m
- Tậps(Acác k , Athuộc
l) = tính:
kVA Att = {A
k k ∗ kVAl k
= s
1, A m2, A3, A4}
s
m
(5)
j m
4.3. Phân mảnh dọc
- Tập các giao tác: Q = {q1, q2, q3i=1 dựa vào P
thuật
M
, q4}ik
2 ∗ toán M
P
phân
2
il
cụm khái niệm
... cơ
... sở
T1 a11 a12 .. a1j .. a1m ...sau: ... ... ... ...
i=1 T ai1 a ... aij ... aim
hướngMa tri trận
thứcsừ dụng: .. i .. i2 ..
5.1.TiVector
...
a
...hóa ...
a
các ..
bản
... ghi
a
... của
..
... một
a
... quan hệ
Để minh họa
4.3. Phân mảnh dọc phân
dựa
A1 A2 A3 A4
vào mảnh
thuật dọc
toán dựa
phân vào
cụm thuật
hướng toán T l
i1
a l1
i2
al2 ... ij
a lj ...im
alm
tri thức .. Xét quan .. hệ r(R)={T1, T .. 2, ..,Tl}, tập các vị từ
phân cụmqhướng 1 1 tri0 thức, 1 sử 0dụng lại giả thiết ví dụ bài Tl al1 a(l2 .. alj .. alm
Để minh
toán phânqhọa 2mảnh 0phândọc1mảnh dựa
1 dọcvào 0dựathuậtvào thuậttoántoánBEA được
phân đơn giản rút trích 1, từ khicácTi[Pr ứng j] =dụngtruetrên r(R) là Pr={Pr1,
∀aij =
cụm hướng
trình bàytriqtrong
3thức,0 [2]:
sử 1dụng 0lại giả1 thiết ví dụ bài toán phân Pr2, ..,Prm}. Vector 1, khi
0, khihóa Tinhị
Ti[Pr [Pr j=]
j ]phân falsecác bản ghi theo qui
true
[A8]
q4vào0thuật0 toán1BEA1được trình bày trong [2]: aij
mảnh dọc dựa tắc: 0, khi Ti [Pr j ] false
- -Tập Tập các thuộc
các thuộc tính:
tính Att = {A Att, A
1
= {A 1, A2, A3, A4}
2 , A3 , A4 }
5.2. Độ đo tương đồngPrcủa 1 2Prvector
2 .. nhị Prj phân .. Prm
- Tập tầnTập
- -Tập các các
suấtgiaothực giao
tác Q tác:
hiên= ứng
{qQ , với
=
q {q
, qtập
1,, qqcác
,
2} q 3giao
, q 4}tác: T a a .. a .. a1m
1 2 3 4 5.2. ĐộXétđo tươngxđồng
2 vector i và xjcủa
1 11
, được 2 vector
12
biểu diễn nhịbằng
1j
phân các biến nhị
Ma trận sử Ma dụng: trận sừ dụng: .. ..
phân. Giả sử các biến nhị phân có cùng trọng số. Ta có bảng
..
Ti ai1 ai2 .. aij .. aim
A1 A2 A3 A4 sự kiện như Bảng 1. Trong đó q là số các biến nhị phân bằng
.. .. ..
4 q1 1 0 1 0 1 đối với cả 2 vector xi và xj , s là số các biến nhị phân bằng
Tl al1 al2 .. alj .. alm
q2 0 1 1 0 0 đối với xi nhưng bằng 1 đối với xj , r là số các biến nhị
q3 0 1 0 1 phân bằng 1 đối với xi nhưng bằng 0 đối
1, khi [Prxj ]j ,
Tivới t là số các
true
q4 0 0 1 1 avới
biến nhị phân bằng 0 đối cả 2 vector x và x [2].
0, khi Ti [Pr j ] false
ij i j
- Tập tần suất thực hiên ứng với tập các giao tác: 61
- nhưng bằng 0 đối với xj, t là số các biến nhị phân bằng p1 p2
T1 1 0
0TẠP
đốiCHÍ
vớiKHOA
cả 2 HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II
vector xi và xj [2].
T2 0 1
Bảng
Bảng 1: Bảngsự
1. Bảng sựkiện chobiến
kiện cho biếnnhịnhị phân
phân Nhận xét: Kết quả phân T3 mảnh 1 này 0trùng khớp với kết
quả phân mảnh ngang theo T4 thuật 0toán PHORIZONTAL.
0
Đối tương j
1 0 Tổng 6. Kết luận T 5 0 1
1 q r q+r T6 1 0
Đối tượng i Trong bài báo này chúng T7 tôi1trình bày 0 giải pháp phân
0 s t s+t
mảnh dọc và ngang của hệ T8 cơ sở0 dữ liệu 1 phân tán dựa vào
Tổng q+s r+t p
thuật toán phân cụm hướng tri thức. Với giải pháp này chúng
Sự khác nhau của 2 vector xi và trên
Sự khác nhau của 2 vector xi và xj dựa
xj dựa trên các
các biến nhị đã đềKết
tôi 5.4. quả
xuất đượcphân
cách mảnh
chuyểnngang
đổi giả quanthiết các hệbài
Emp toántheo
biến nhị phân đối xứng (symmetric
phân đối xứng (symmetric binary dissimilarity) là: binary phânthật toán phân cụm hướng tri thức
mảnh cổ điển trở về giả thuyết cho bài toán phân cụm.
dissimilarity) là: Trong thuật toán phânCụm cụm hướng
Tập các bảntri thức,
ghi chúng tôi có
r+s
d(xi , xj ) = (6) đề xuất cách xây dựng1quan hệ T1, T3, T6, T7 ban đầu dựa
tương đương
r sq + r + s + t vào ngưỡng khoảng cách, đây làTđiểm khác biệt với 2 thuật
d ( xi , x j ) (5.1) 2 2, T5, T8
q r s t toán của 2 nhóm tác giả3 Shoji Hirano, T4 Shusaku Tsumoto và
Sự khác nhau của 2 vector xi và xj dựa trên các biến nhị
C.L Bean, C.Kambhampati đã đề xuất trước đó.
Sựđối
phân bất khác nhau
xứng của 2 vector
(asymmetric và xj dựa trên các
binaryxidissimilarity) Nhận xét:
Kết quả thử nghiệm trên các bộ dữ liệu trong [13] cho
biến nhị phân bất đối xứng r + s(asymmetric binary thấy kết quảKếttrùng
quả lắp
phân vớimảnh này
kết quả có trùng
được từ khớp với toán
2 thuật kết quả
d(xi , xj ) = (7)
dissimilarity) là: q+r+s phân mảnh
phân mảnh
cổ điển theo thuật toán và
là PHORIZONTAL
ngang thuật toán BEA.
PHORIZONTAL.
r s Ngoài dữ liệu thử nghiệm như đã trình bày, chúng tôi còn
Độdđo
( xitương xi và xj ,
, x j ) đồng (similarity) giữa 2 vector (5.2) Kết luận
thử6.nghiệm trên một số bộ dữ liệu khác, kết quả có được
được xác định bởi hệq r s
số Jaccard: cũng tương đồng với
Trong bài 2báo
thuật toán
này cổ điển
chúng tôinêu trên.
trình bày giải pháp
Độ đo tương
sim(xđồng (similarity)
i , xj ) = 1 − d(xi , xjgiữa
) 2 vector(8)xi Tuy các bộ cơ sở dữ liệu phân tán
phân mảnh dọc và ngang của hệ cơ sở dữ liệu thử nghiệm cònphân
nhỏ tán
và xj, được xác định bởi hệ số Jaccard: nhưng lại phù hợp với các thử nghiệm trên [2] cho các phân
dựa vào thuật toán phân cụm hướng tri thức. Với giải
5.3. Phân mảnh ngang dựa vào thuật toán phân cụm mảnh cổ điển, đồng thời so sánh được với kết quả trên thuật
sim
hướng i , x j ) 1 d ( xi , x j )
tri( xthức (5.3) toánpháp
phânnày
cụm hướngtôitriđã
chúng đề đã
thức xuấtđề được
xuất. Thờicách gian
chuyểntới, đổi
giả tôi
chúng thiết
sẽ các bài các
sưu tập toánbộphândữ liệumảnhđã đượccỗ điểncôngtrở
bố vềcó giả
Sử dụng lại giả thiết ví dụ bài toán phân mảnh ngang dựa
5.3.
vào Phân mảnh
thuật toán ngang dựa vào
PHORIZONTAL thuật
được trìnhtoán phân[2]:
bày trong cụm kíchthuyết cho bài toán phân cụm.
thước lớn hơn để có thử nghiệm so sánh tính khả dụng
hướng của giải pháp đề xuất với việc kết hợp các kỹ thuật phân
Giảtri
sử thức
có một quan hệ Emp cụm khácTrongdựa vàothuật
thuật toán
toán diphân
truyền,cụm tiếnhướng
hóa haytricácthức,
Sử dụng lại
ENO giả thiết
ENAME ví dụ bài toán phân mảnh
TITLE chúng
thuật tôi có đề
toán heuristic kếtxuất cách
hợp với các xây
côngdựngcụ toánquan hệ lý
học như tương
ngang dựa vào
T1 thuật
E1 toánJjoe
PHORIZONTAL
Elect-Eng được trình đương
thuyết ban tập
tập thô, đầumờdựa vàođểngưỡng
[3][4] đánh giákhoảng
và chỉ racách, đây là
các giải
T
bày trong [2]:
2 E 2 M.Smith Syst-Analyst pháp phânkhác
điểm mảnhbiệtdữ liệu
vớivới2 hiệu
thuậtnăng
toáncao. của 2 nhóm tác giả
T3 E3 A.Lee Mech-Eng
Giả sử
T4có một
E4 quan hệ EmpProgrammer
J.Smith Shoji Hirano, Shusaku Tsumoto và C.L Bean,
Tài liệu tham khảo
BảngT2.
5
DữE5liệu mẫu
B.Casey
để Syst-Analyst
phân đoạn ngang C.Kambhampati đã đề xuất trước đó.
T6 E6 L.Chu Elect-Eng [1] Adrian Runceanu, Towards Vertical Fragmention in Distributed
TENO
7 E7 ENAME
R.David TITLE
Mech-Eng Kết quả
Databases, thử nghiệm
International Joint trên các bộondữComputer,
Conferences liệu trong
T1 T8E1 E8 Jjoe
J.Jone Elect-Eng
Syst-Analyst [13] cho thấy
Information, andkết quảSciences,
Systems trùng lắp với kết quả
and Engineering có 2007)
(CISSE được từ
Conference; 01/2007.
T2
Xét
E2 M.Smith Syst-Analyst 2 thuật
[2] Lương Văntoán phân
Nghĩa mảnh
(2013), Phân cổđoạnđiển là PHORIZONTAL
dọc, ngang trong thiết kế cơ
T32 vị từE3đơn giản:A.Lee Mech-Eng
- Tp41 =(TITLE>“Programmer”)
E4 J.Smith và Programmer vàsở thuật toán BEA. Ngoài dữ liệu
và Công nghệ, Đại học Đà Nẵng, số 3(64).2013.
thử nghiệm như đã
dữ liệu phân tán dựa trên kỹ thuật phân cụm, Tạp chí Khoa học
- Tp52 =(TITLE
- Lê Văn Sơn, Lương Văn Nghĩa
[9] Marwa F. F. Areed, Ali I.El-Dosouky, Hesham A. Ali, A Heuristic 20-24, Volume 5– No.9.
Approach for Horizontal Fragmentation and Allocation in DOODB, [12] Shoji Hirano and Shusaku Tsumoto, A Knowledge-Oriented
infos2008.fci.cu.edu.eg/infos/DB-02-P009-016.pdf. Clustering Technique Based on Rough Sets, Computer Software and
[10] Narasimhaiah Gorla, Pang Wing Yan Betty, Vertical Applications Conference, 2001. COMPSAC 2001.
Fragmentation in Databases Using Data-Mining Technique, www. [13] Tamer O., Valduriez P.. (1999), Principles of Distributed Database
irmainternational.org/chapter/vertical-fragmentation-databases-us- Systems, Prentice Hall Englewood Cliffs, Second Edition, New
ingdata/40404/. Jersey 07362.
[11] Shahidul Islam Khan, A. S. M. Latiful Hoque (2010), A New [14] Yin-Fu Huang, Jyh-her Chen, Fragment Allocation in Distributed
Technique for Database Fragmentation in Distributed Systems, Database Design, Journal of Information Science and Engineering,
International Journal of Computer Applications (0975 – 8887), pp. 491-506(2001).
(BBT nhận bài: 21/12/2013, phản biện xong: 22/01/2014)
63
nguon tai.lieu . vn
