sosof_solo
New Member
Download Luận văn Nghiên cứu công nghệ khai phá dữ liệu văn bản, áp dụng cho các trang tin tức trên các thiết bị cầm tay (pdas & smartphones)
MỤC LỤC
TÓM TẮT . 5
CÁC THUẬT NGỮVÀ CÁC TỪVIẾT TẮT . 6
CHÚ GIẢI KÝ HIỆU VÀ MÔ HÌNH . 7
CÁC HÌNH MINH HỌA . 8
MỞ ĐẦU . 9
CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬTRÊN THIẾT
BỊCẦM TAY . 12
1.1. Báo điện tửvà công nghệInternet không dây. 12
1.1.1. Báo điện tử- một thành tựu của Internet . 12
1.1.2. Sựphát triển của các thiết bịcầm tay . 13
1.1.3. Công nghệkết nối internet không dây . 14
1.2. Bài toán xây dựng kênh tin tức điện tửtrên thiết bịcầm tay . 15
1.2.1. Mô tảbài toán . 15
1.2.2. Mô tảcác chức năng cơbản của hệthống . 16
1.3. Hướng tiếp cận giải quyết bài toán . 16
Chương II. THUẬT TOÁN RTDM VÀ ỨNG DỤNG TRONG TRÍCH XUẤT TIN . 18
2.1. Khái niệm “Chi phí chuyển đổi cây” . 18
2.2. Thuật toán RTDM . 22
2.3. Áp dụng RTDM trích xuất tin tức tự động. 29
2.3.1 Phân cụm trang . 31
2.3.2 Trích xuất mẫu chung . 32
2.3.3 Khớp dữliệu . 35
2.3.4 Gán nhãn dữliệu . 37
Chương III . PHÂN TÍCH THIẾT KẾHỆTHỐNG . 39
3.1.Giới thiệu. 39
3.2. Mô hình Use Case: . 40
3.2. Mô hình lớp . 45
3.4. Danh sách các thực thể. 47
3.5. Mô hình thực thểliên kết . 48
Chương IV. KẾT QUẢTHỰC NGHIỆM VÀ ĐÁNH GIÁ . 49
4.1. Giới thiệu chung vềhệthống . 49
4.2. Thực nghiệm và đánh giá kết quả. 49
KẾT LUẬN. 54
TÀI LIỆU THAM KHẢO . 55
PHỤLỤC. MÔ TẢCHI TIẾT CÁC THỰC THỂ.
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Theo Davi de Castro Reis và các đồng tác giả [28], cấu trúc của các trang Web
có thể được biểu diễn dưới dạng một cây (Ví dụ như Cây DOM), vì vậy chúng
ta sử dụng khái niệm chi phí chuyển đổi cây (Tree Edit Distance) để đánh giá
mức độ giống nhau giữa các trang. Một cách trực quan, khoảng cách giữa hai
cây TA và TB là "giá tối thiểu" phải trả cho một tập các thao tác để chuyển đổi
TA thành TB.
Mặc dù có thể áp dụng cho cây bất kỳ, nhưng để thuận tiện áp dụng nên trong
luận văn này, chúng tui tập trung chủ yếu vào cây có thứ tự, được gán nhãn, có
gốc cố định (labeled ordered rooted tree). Một cây có gốc (rooted tree) là cây
có đỉnh gốc là cố định. Cây có thứ tự có gốc (ordered rooted tree) là cây có gốc
cố định và thứ tự các con là cố định với mỗi đỉnh. Cây có thứ tự, được gán
nhãn, có gốc cố định là cây có mỗi đỉnh được gán nhãn l. Từ đây về sau, chúng
ta sẽ đơn giản sử dụng khái niệm "cây" để chỉ cây có thứ tự, được gán nhãn, có
gốc cố định, các trường hợp khác sẽ được chú thích cụ thể.
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 19
Để mô tả cấu trúc cây của các trang Web, ta giả sử rằng các trang Web này
được biểu diễn dưới dạng một cây "cây có thứ tự, được gán nhãn, có gốc cố
định". Các nhãn ở đây chính là các thẻ HTML như , , …
Hình 3. Ví dụ cây có thứ tự, được gán nhãn, có gốc cố định
Chi phí tính toán chi phí chuyển đổi cây thông qua việc sử dụng 3 thao tác
chính là Xoá đỉnh, Chèn đỉnh, Thay thế đỉnh. Chi phí cho từng thao tác này là
khác nhau tuỳ trường hợp. Giải pháp của bài toán chính là tìm tập hợp các thao
tác được thực hiện với chi phí là nhỏ nhất để chuyển đổi giữa hai cây.
Một bài toán tương đương chính là bài toán tìm ánh xạ chuyển đổi (dưới đây
gọi tắt là ánh xạ) giữa hai cây với chi phí nhỏ nhất.
Trong các phần trình bày dưới đây, kí hiệu Tx để chỉ một cây và kí hiệu Tx
để chỉ đỉnh thứ i của Tx. Kích thước của một cây chính là số đỉnh có trong cây
đó. Davi de Castro Reis và các đồng tác giả đã xem xét khái niệm ánh xạ
chuyển đổi cây như một khái niệm cơ bản trong phương pháp của họ [28].
Định nghĩa 1 [17, 18, 21, 25, 28]
Ánh xạ giữa cây T1 kích thước n1 và cây T2 kích thước n2 là một tập hợp M các
cặp có thứ tự (i, j) thoả mãn các điều kiện sau với mọi (i1, j1), (i2, j2) ∈ M:
• i1 = i2 khi và chỉ khi j1 = j2.
• T1[i1] ở bên trái của T1[i2] khi và chỉ khi T2[j1] ở bên trái T2[j2]
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 20
• T1[i1] là tổ tiên của T1[i2] khi và chỉ khi T2[j1] là tổ tiên của T2[j2]
Hình 1 - Ví dụ về ánh xạ giữa 2 cây
Điều kiện 1 xác định một đỉnh của một cây không xuất hiện quá 1 lần trong
ánh xạ, điều kiện thứ 2 bảo toàn thứ tự trái - phải giữa các nút, còn điều kiện
thứ 3 đảm bảo cấu trúc phân cấp giữa 2 cặp nút trong ánh xạ.
Nói một cách đơn giản, phép ánh xạ cho phép mô tả các bước hiệu chỉnh từ
cây này thành cây kia, không quan tâm đến thứ tự các thao tác được áp dụng.
Trong hình 3, những đường nét đứt giữa các đỉnh của cây T1 và các đỉnh của
cây T2 phải thay đổi nếu các đỉnh này khác nhau, các đỉnh còn lại không phải
thay đổi. Đỉnh không có đường nào nối tới trên cây T1 là đỉnh sẽ bị xoá, còn
đỉnh không có đường nào nối tới trên cây T2 là đỉnh phải được chèn vào.
Như đã đề cập ở trên, việc tìm chi phí chuyển đổi cây tương đương với việc
tìm chi phí nhỏ nhất cho ánh xạ giữa 2 cây. Gọi M là ánh xạ giữa hai cây T1 và
cây T2, gọi S là tập con các cặp (i,j) ∈ M với các nhãn riêng biệt, D là tập hợp
các nút trong T1 mà không xuất hiện trong bất cứ cặp (i,j) ∈ M, I là tập hợp các
nút trong T2 mà không xuất hiện trong bất cứ cặp (i,j) ∈ M. Khi đó chi phí cho
việc ánh xạ được cho bởi công thức:
c = Sp + Iq + Dr
Trong đó p, q, r tương ứng là chi phí cho thao tác thay thế, chèn và xóa một
nút. Ta có thể giả thiết các chi phí này là bằng nhau nhưng khi cài đặt vào ứng
dụng thực thì các chi phí này có thể khác nhau.
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 21
Bài toán tính toán chi phí chuyển đổi giữa hai cây là một bài toán khó, có một
số giải thuật, đưa vào một số các yếu tố cân bằng khác nhau, được đề xuất gần
đây, tuy nhiên tất cả đều có độ phức tạp tính toán trên cấp đa thức bậc hai. Hơn
nữa, người ta chứng minh rằng nếu hai cây không có thứ tự thì bài toán có độ
phức tạp là NP-đầy đủ.
Thuật toán đầu tiên về bài toán ánh xạ (được giới thiệu trong tài liệu [18]) với
độ phức tạp là O(n1n2h1h2) với n1 và n2 là kích thước của cây, h1 và h2 là độ cao
tương ứng. Đây là thuật toán tính toán động thực hiện việc tính toán đệ quy chi
phí chuyển đổi giữa các xâu biểu diễn tập hợp các đỉnh con của các đỉnh của
cây. J. T. L. Wang và các đồng tác giả [21] đã giới thiệu một thuật toán với độ
phức tạp O(d2n1n2min(h1,l1)min(h2,l2)) với d là chi phí chuyển đổi giữa các cây
con, h1 và h2 là chiều cao còn l1 và l2 là số các lá của mỗi cây.
Một trong các cách tiếp cận điển hình là tiếp cận dựa trên phép ánh xạ trên-
xuống, phép ánh xạ trên-xuống hạn chế các thao tác chèn và xoá ở các nút lá.
Hình 4 minh hoạ một ánh xạ trên-xuống như định nghĩa dưới đây.
Định nghĩa 2
Ánh xạ M giữa cây T1 và cây T2 được gọi là trên-xuống khi và chỉ khi với mọi cặp
(i1,i2) ∈ M, ta cũng có một cặp (cha(i1), cha(i2)) ∈ M với i1 và i2 tương ứng không
phải là nút gốc của T1 và T2.
Hình 2 – Ví dụ ánh xạ trên-xuống
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 22
Thuật toán đầu tiên giải quyết bài toán tính toán chi phí chuyển đổi cho ánh xạ
trên - xuống được Selkow giới thiệu trong [17].
Yang [25] giới thiệu một thuật toán quy hoạch động với độ phức tạp là O(n1n2)
trong đó n1, n2 là kích thước tương ứng của T1 và T2.
S. S. Chawathe [5] giới thiệu một thuật toán khác khá phổ biến giải quyết bài
toán ánh xạ trên-xuống cũng với độ phức tạp O(n1n2), tuy nhiên thuật toán này
không sử dụng phương pháp quy hoạch động mà được giải quyết bằng thuật
toán đơn hình.
Ánh xạ trên-xuống cũng đã áp dụng thành công trong một số ứng dụng liên
quan đến Web, ví dụ như ứng dụng phân loại tài liệu. Trong [16], Nierman và
Jagadish sử dụng thuật toán tính toán chi phí chuyển đổi cho ánh xạ trên xuống
để phân nhóm các tài liệu XML.
Trong bài toán "Trích xuất tin tức tự động", luận văn này chỉ quan tâm đến vấn
đề xác định sự tương đồng giữa cấu trúc của các trang Web. Thực sự là các
trang Web có cấu trúc hay là cấu trúc HTML hay là XML, như đã đề cập ở
trên, có thể biểu diễn dưới dạng cây có thứ tự được gán nhãn, có gốc cố định.
Thường mô hình DOM được vận dụng để mô tả cây.
Trong phần tiếp theo sẽ trình bày thuật toán mới xác định chi phí ánh xạ giữa
các cây biểu diễn cấu trúc của các trang Web cho lớp bài toán giới hạn đó là
ánh xạ trên...
Download miễn phí Luận văn Nghiên cứu công nghệ khai phá dữ liệu văn bản, áp dụng cho các trang tin tức trên các thiết bị cầm tay (pdas & smartphones)
MỤC LỤC
TÓM TẮT . 5
CÁC THUẬT NGỮVÀ CÁC TỪVIẾT TẮT . 6
CHÚ GIẢI KÝ HIỆU VÀ MÔ HÌNH . 7
CÁC HÌNH MINH HỌA . 8
MỞ ĐẦU . 9
CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬTRÊN THIẾT
BỊCẦM TAY . 12
1.1. Báo điện tửvà công nghệInternet không dây. 12
1.1.1. Báo điện tử- một thành tựu của Internet . 12
1.1.2. Sựphát triển của các thiết bịcầm tay . 13
1.1.3. Công nghệkết nối internet không dây . 14
1.2. Bài toán xây dựng kênh tin tức điện tửtrên thiết bịcầm tay . 15
1.2.1. Mô tảbài toán . 15
1.2.2. Mô tảcác chức năng cơbản của hệthống . 16
1.3. Hướng tiếp cận giải quyết bài toán . 16
Chương II. THUẬT TOÁN RTDM VÀ ỨNG DỤNG TRONG TRÍCH XUẤT TIN . 18
2.1. Khái niệm “Chi phí chuyển đổi cây” . 18
2.2. Thuật toán RTDM . 22
2.3. Áp dụng RTDM trích xuất tin tức tự động. 29
2.3.1 Phân cụm trang . 31
2.3.2 Trích xuất mẫu chung . 32
2.3.3 Khớp dữliệu . 35
2.3.4 Gán nhãn dữliệu . 37
Chương III . PHÂN TÍCH THIẾT KẾHỆTHỐNG . 39
3.1.Giới thiệu. 39
3.2. Mô hình Use Case: . 40
3.2. Mô hình lớp . 45
3.4. Danh sách các thực thể. 47
3.5. Mô hình thực thểliên kết . 48
Chương IV. KẾT QUẢTHỰC NGHIỆM VÀ ĐÁNH GIÁ . 49
4.1. Giới thiệu chung vềhệthống . 49
4.2. Thực nghiệm và đánh giá kết quả. 49
KẾT LUẬN. 54
TÀI LIỆU THAM KHẢO . 55
PHỤLỤC. MÔ TẢCHI TIẾT CÁC THỰC THỂ.
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
Theo Davi de Castro Reis và các đồng tác giả [28], cấu trúc của các trang Web
có thể được biểu diễn dưới dạng một cây (Ví dụ như Cây DOM), vì vậy chúng
ta sử dụng khái niệm chi phí chuyển đổi cây (Tree Edit Distance) để đánh giá
mức độ giống nhau giữa các trang. Một cách trực quan, khoảng cách giữa hai
cây TA và TB là "giá tối thiểu" phải trả cho một tập các thao tác để chuyển đổi
TA thành TB.
Mặc dù có thể áp dụng cho cây bất kỳ, nhưng để thuận tiện áp dụng nên trong
luận văn này, chúng tui tập trung chủ yếu vào cây có thứ tự, được gán nhãn, có
gốc cố định (labeled ordered rooted tree). Một cây có gốc (rooted tree) là cây
có đỉnh gốc là cố định. Cây có thứ tự có gốc (ordered rooted tree) là cây có gốc
cố định và thứ tự các con là cố định với mỗi đỉnh. Cây có thứ tự, được gán
nhãn, có gốc cố định là cây có mỗi đỉnh được gán nhãn l. Từ đây về sau, chúng
ta sẽ đơn giản sử dụng khái niệm "cây" để chỉ cây có thứ tự, được gán nhãn, có
gốc cố định, các trường hợp khác sẽ được chú thích cụ thể.
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 19
Để mô tả cấu trúc cây của các trang Web, ta giả sử rằng các trang Web này
được biểu diễn dưới dạng một cây "cây có thứ tự, được gán nhãn, có gốc cố
định". Các nhãn ở đây chính là các thẻ HTML như , , …
Hình 3. Ví dụ cây có thứ tự, được gán nhãn, có gốc cố định
Chi phí tính toán chi phí chuyển đổi cây thông qua việc sử dụng 3 thao tác
chính là Xoá đỉnh, Chèn đỉnh, Thay thế đỉnh. Chi phí cho từng thao tác này là
khác nhau tuỳ trường hợp. Giải pháp của bài toán chính là tìm tập hợp các thao
tác được thực hiện với chi phí là nhỏ nhất để chuyển đổi giữa hai cây.
Một bài toán tương đương chính là bài toán tìm ánh xạ chuyển đổi (dưới đây
gọi tắt là ánh xạ) giữa hai cây với chi phí nhỏ nhất.
Trong các phần trình bày dưới đây, kí hiệu Tx để chỉ một cây và kí hiệu Tx
để chỉ đỉnh thứ i của Tx. Kích thước của một cây chính là số đỉnh có trong cây
đó. Davi de Castro Reis và các đồng tác giả đã xem xét khái niệm ánh xạ
chuyển đổi cây như một khái niệm cơ bản trong phương pháp của họ [28].
Định nghĩa 1 [17, 18, 21, 25, 28]
Ánh xạ giữa cây T1 kích thước n1 và cây T2 kích thước n2 là một tập hợp M các
cặp có thứ tự (i, j) thoả mãn các điều kiện sau với mọi (i1, j1), (i2, j2) ∈ M:
• i1 = i2 khi và chỉ khi j1 = j2.
• T1[i1] ở bên trái của T1[i2] khi và chỉ khi T2[j1] ở bên trái T2[j2]
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 20
• T1[i1] là tổ tiên của T1[i2] khi và chỉ khi T2[j1] là tổ tiên của T2[j2]
Hình 1 - Ví dụ về ánh xạ giữa 2 cây
Điều kiện 1 xác định một đỉnh của một cây không xuất hiện quá 1 lần trong
ánh xạ, điều kiện thứ 2 bảo toàn thứ tự trái - phải giữa các nút, còn điều kiện
thứ 3 đảm bảo cấu trúc phân cấp giữa 2 cặp nút trong ánh xạ.
Nói một cách đơn giản, phép ánh xạ cho phép mô tả các bước hiệu chỉnh từ
cây này thành cây kia, không quan tâm đến thứ tự các thao tác được áp dụng.
Trong hình 3, những đường nét đứt giữa các đỉnh của cây T1 và các đỉnh của
cây T2 phải thay đổi nếu các đỉnh này khác nhau, các đỉnh còn lại không phải
thay đổi. Đỉnh không có đường nào nối tới trên cây T1 là đỉnh sẽ bị xoá, còn
đỉnh không có đường nào nối tới trên cây T2 là đỉnh phải được chèn vào.
Như đã đề cập ở trên, việc tìm chi phí chuyển đổi cây tương đương với việc
tìm chi phí nhỏ nhất cho ánh xạ giữa 2 cây. Gọi M là ánh xạ giữa hai cây T1 và
cây T2, gọi S là tập con các cặp (i,j) ∈ M với các nhãn riêng biệt, D là tập hợp
các nút trong T1 mà không xuất hiện trong bất cứ cặp (i,j) ∈ M, I là tập hợp các
nút trong T2 mà không xuất hiện trong bất cứ cặp (i,j) ∈ M. Khi đó chi phí cho
việc ánh xạ được cho bởi công thức:
c = Sp + Iq + Dr
Trong đó p, q, r tương ứng là chi phí cho thao tác thay thế, chèn và xóa một
nút. Ta có thể giả thiết các chi phí này là bằng nhau nhưng khi cài đặt vào ứng
dụng thực thì các chi phí này có thể khác nhau.
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 21
Bài toán tính toán chi phí chuyển đổi giữa hai cây là một bài toán khó, có một
số giải thuật, đưa vào một số các yếu tố cân bằng khác nhau, được đề xuất gần
đây, tuy nhiên tất cả đều có độ phức tạp tính toán trên cấp đa thức bậc hai. Hơn
nữa, người ta chứng minh rằng nếu hai cây không có thứ tự thì bài toán có độ
phức tạp là NP-đầy đủ.
Thuật toán đầu tiên về bài toán ánh xạ (được giới thiệu trong tài liệu [18]) với
độ phức tạp là O(n1n2h1h2) với n1 và n2 là kích thước của cây, h1 và h2 là độ cao
tương ứng. Đây là thuật toán tính toán động thực hiện việc tính toán đệ quy chi
phí chuyển đổi giữa các xâu biểu diễn tập hợp các đỉnh con của các đỉnh của
cây. J. T. L. Wang và các đồng tác giả [21] đã giới thiệu một thuật toán với độ
phức tạp O(d2n1n2min(h1,l1)min(h2,l2)) với d là chi phí chuyển đổi giữa các cây
con, h1 và h2 là chiều cao còn l1 và l2 là số các lá của mỗi cây.
Một trong các cách tiếp cận điển hình là tiếp cận dựa trên phép ánh xạ trên-
xuống, phép ánh xạ trên-xuống hạn chế các thao tác chèn và xoá ở các nút lá.
Hình 4 minh hoạ một ánh xạ trên-xuống như định nghĩa dưới đây.
Định nghĩa 2
Ánh xạ M giữa cây T1 và cây T2 được gọi là trên-xuống khi và chỉ khi với mọi cặp
(i1,i2) ∈ M, ta cũng có một cặp (cha(i1), cha(i2)) ∈ M với i1 và i2 tương ứng không
phải là nút gốc của T1 và T2.
Hình 2 – Ví dụ ánh xạ trên-xuống
Kênh tin tức điện tử cho các thiết bị cầm tay
Vũ Ngọc Anh – K9T3 Trang 22
Thuật toán đầu tiên giải quyết bài toán tính toán chi phí chuyển đổi cho ánh xạ
trên - xuống được Selkow giới thiệu trong [17].
Yang [25] giới thiệu một thuật toán quy hoạch động với độ phức tạp là O(n1n2)
trong đó n1, n2 là kích thước tương ứng của T1 và T2.
S. S. Chawathe [5] giới thiệu một thuật toán khác khá phổ biến giải quyết bài
toán ánh xạ trên-xuống cũng với độ phức tạp O(n1n2), tuy nhiên thuật toán này
không sử dụng phương pháp quy hoạch động mà được giải quyết bằng thuật
toán đơn hình.
Ánh xạ trên-xuống cũng đã áp dụng thành công trong một số ứng dụng liên
quan đến Web, ví dụ như ứng dụng phân loại tài liệu. Trong [16], Nierman và
Jagadish sử dụng thuật toán tính toán chi phí chuyển đổi cho ánh xạ trên xuống
để phân nhóm các tài liệu XML.
Trong bài toán "Trích xuất tin tức tự động", luận văn này chỉ quan tâm đến vấn
đề xác định sự tương đồng giữa cấu trúc của các trang Web. Thực sự là các
trang Web có cấu trúc hay là cấu trúc HTML hay là XML, như đã đề cập ở
trên, có thể biểu diễn dưới dạng cây có thứ tự được gán nhãn, có gốc cố định.
Thường mô hình DOM được vận dụng để mô tả cây.
Trong phần tiếp theo sẽ trình bày thuật toán mới xác định chi phí ánh xạ giữa
các cây biểu diễn cấu trúc của các trang Web cho lớp bài toán giới hạn đó là
ánh xạ trên...