langtu_sitinh200699
New Member
Download miễn phí Đồ án Kết hợp các phương pháp phân cụm trong khai phá dữ liệu web
MỤC LỤC
LỜI CẢM ƠN.1
MỤC LỤC .2
DANH SÁCH HÌNH .4
DANH SÁCH BẢNG.6
DANH MỤC TỪ VIẾT TẮT .6
CHưƠNG 1: GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU WEB .8
1.1 Khai phá dữ liệu và khai phá tri thức.8
1.1.1 Khai phá dữ liệu .8
1.1.2 Quá trình khám phá tri thức .8
1.1.3 Khai phá dữ liệu và các lĩnh vực liên quan .9
1.1.4 Các kỹ thuật áp dụng trong khai phá dữ liệu.9
1.1.5 Những chức năng chính của khai phá dữ liệu .10
1.1.6 Ứng dụng của khai phá dữ liệu .11
1.2 Phương pháp phân cụm dữ liệu .12
1.2.1 Giới thiệu về kỹ thuật phân cụm .12
1.2.2 Ứng dụng của phân cụm dữ liệu .14
1.2.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu .14
1.2.4 Các kiểu dữ liệu và độ đo tương tự .15
1.3 Khai phá Web .19
1.3.1 Các kiểu dữ liệu Web .21
1.3.2 Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web.22
1.3.3 Một số vấn đề trong xử lý dữ liệu văn bản.22
1.4 Tiểu kết chương 1 .24
CHưƠNG 2: MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU .25
2.1 Thuật toán k-means.25
2.2 Thuật toán PAM.27
2.3 Thuật toán BIRCH.31
2.4 Thuật toán DBSCAN.33
2.5 Tiểu kết chương 2 .36
CHưƠNG 3: KHAI PHÁ DỮ LIỆU WEB.37
3.1 Khai phá nội dung Web .37
3.1.1 Khai phá kết quả tìm kiếm .38
3.1.2 Khai phá văn bản Web .38
3.2 Khai phá theo sử dụng Web.43
3.2.1 Các kỹ thuật được sử dụng trong khai phá theo sử dụng Web .44
3.2.2 Quá trình khai phá theo sử dụng Web.44
3.3 Khai phá cấu trúc Web .45
3.3.1 Tiêu chuẩn đánh giá độ tương tự.46
3.3.2 Khai phá và quản lý cộng đồng Web .47
3.4 Áp dụng thuật toán trong tìm kiếm và phân cụm tài liệu Web.48
3.4.1 Tìm hiểu kỹ thuật phân cụm tài liệu Web .48
3.4.2 Quá trình tìm kiếm và phân cụm tài liệu.49
3.5 Thực nghiệm .53
3.6 Tiểu kết chương 3 .59
Kết luận.60
Tài liệu tham khảo .61
Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.
Ketnooi -
You must be registered for see links
Ai cần tài liệu gì mà không tìm thấy ở Ketnooi, đă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 tài liệu:
nguyên
dƣơng.
Khoảng cách Euclidean: √∑
, (trƣờng hợp đặc biệt của
khoảng cách Minskowski trong trƣờng hợp q =2).
Khoảng cách Manhattan: ∑ | |
, (trƣờng hợp đặc biệt của
khoảng cách Minskowski trong trƣờng hợp q=1).
Khoảng cách cực đ i:
| |, đây là trƣờng hợp của
khoảng cách Minskowski trong trƣờng hợp .
Thuộc tính nhị phân:
Trƣớc hết ta có xây dựng bảng tham số sau:
y:1 y:0
x:1
y:1
Bảng 1-1: Bảng tham số thuộc tính nhị phân
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 18
Trong đó: . x,y là các đối tƣợng có thuộc tính đều là nhị
phân.
là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tƣợng x, y.
là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y.
là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y.
là tổng số các giá trị thuộc tính có giá trị là 0 trong x và y.
Các phép đo độ tƣơng tự đối với dữ liệu thuộc tính nhị phân đƣợc định
nghĩa nhƣ sau:
Hệ số đối sánh đ n giản:
, ở đây cả hai đối tƣợng x và y có vai
trò nhƣ nhau, nghĩa là chúng đối xứng và có cùng trọng số.
Hệ số Jacard:
, tham số này bỏ qua số các đối sánh giữa 0-0.
Công thức tính này đƣợc sử dụng trong trƣờng hợp mà trọng số của các thuộc tính có
giá trị 1 của đối tƣợng dữ liệu có giá trị cao hơn nhiều so với các thuộc tính có giá trị
0, nhƣ vậy các thuộc tính nhị phân ở đây là không đối xứng.
Thuộc tính định danh:
Độ đo phi tƣơng tự giữa hai đối tƣợng x và y đƣợc định nghĩa nhƣ sau:
, trong đó m là số thuộc tính đối sánh tƣơng ứng trùng nhau và p
là tổng số các thuộc tính.
Thuộc tính có thứ tự:
Phép đo độ phi tƣơng tự giữa các đối tƣợng dữ liệu với thuộc tính thứ tự đƣợc
thực hiện nhƣ sau, ở đây ta giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thƣớc
miền giá trị):
Các trạng thái Mi đƣợc sắp thứ tự nhƣ sau: [1Mi], ta có thể thay thế mỗi giá trị
của thuộc tính bằng giá trị cùng loại ri, với ri {1,,Mi}. Mỗi một thuộc tính thứ tự có
các miền giá trị khác nhau, vì vậy ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng
cách thực hiện phép biến đổi sau cho mỗi thuộc tính:
, với i=1,..,Mi.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 19
Sử dụng công thức tính độ phi tƣơng tự của thuộc tính khoảng đối với các giá trị
, đây cũng chính là độ phi tƣơng tự của thuộc tính có thứ tự.
Thuộc tính tỉ lệ:
Có nhiều cách khác nhau để tính độ tƣơng tự giữa các thuộc tính tỉ lệ. Một trong
những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính xi, thí dụ qi = log(xi),
lúc này qi đóng vai trò nhƣ thuộc tính khoảng. Phép biến đổi logarit này thích hợp
trong trƣờng hợp các giá trị của thuộc tính là số mũ.
Trong thực tế, khi tính độ đo tƣơng tự dữ liệu, ngƣời ta chỉ xem xét một phần các
thuộc tính đặc trƣng đối với các kiểu dữ liệu hay đánh trọng số cho cho tất cả các
thuộc tính dữ liệu. Trong một số trƣờng hợp, ngƣời ta loại bỏ đơn vị đo của các thuộc
tính dữ liệu bằng cách chuẩn hoá chúng hay gán trọng số cho mỗi thuộc tính giá trị
trung bình, độ lệch chuẩn. Các trọng số này có thể sử dụng trong các độ đo khoảng
cách trên, thí dụ với mỗi thuộc tính dữ liệu đã đƣợc gán trọng số tƣơng ứng wi
( ), độ tƣơng tự dữ liệu đƣợc xác định nhƣ sau:
√∑
.
Tóm lại, tuỳ từng trƣờng hợp dữ liệu cụ thể mà ngƣời ta sử dụng các mô hình
tính độ tƣơng tự khác nhau. Việc xác định độ tƣơng tự dữ liệu thích hợp, chính xác,
đảm bảo khách quan là rất quan trọng và giúp xây dựng thuật toán PCDL có hiệu quả
cao trong việc đảm bảo chất lƣợng cũng nhƣ chi phí tính toán của thuật toán.
1.3 Kh i phá dữ liệu Web
Khai phá dữ liệu Web là việc sử dụng các kỹ thuật KPDL để tự động hóa quá
trình phát hiện và trích chọn những thông tin hữu ích từ các tài liệu, các thông tin dịch
vụ, hồ sơ sử dụng và cấu trúc Website. Hay nói cách khác khai phá Web là việc thăm
dò những thông tin quan trọng và những mẫu dữ liệu tiềm năng từ nội dung Web, từ
thông tin truy cập Web, từ liên kết trang và từ nguồn tài nguyên thƣơng mại điện tử
bằng việc sử dụng các kỹ thuật KPDL, nó có thể giúp con ngƣời rút ra tri thức, cải tiến
việc thiết kế các Website và phát triển thƣơng mại điện tử tốt hơn [1].
uá tr nh hai phá
Tìm kiếm nguồn tài nguyên: Thực hiện tìm kiếm và lấy các tài liệu Web phục vụ
cho việc khai phá.
Lựa chọn và tiền xử lý dữ liệu: Lựa chọn và tiền xử lý tự động các loại thông tin
từ nguồn tài nguyên Web đã lấy về.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 20
Tổng hợp: Tự động khám phá các mẫu chung tại các Website riêng lẽ cũng nhƣ
nhiều Website với nhau.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 21
1.3.1 Các kiểu dữ liệu Web
Sơ đồ phân loại dữ liệu Web :
Các đối tượng của khai phá Web bao gồm[4] : Server logs, Web pages, Web
hyperlink structures, dữ liệu thị trƣờng trực tuyến và các thông tin khác.
Web logs(dữ liệu đăng nhập Web): Khi ngƣời dùng duyệt Web, dịch vụ sẽ phân
ra 3 loại dữ liệu đăng nhập: sever logs(dữ liệu đăng nhập trên server), error logs(dữ
liệu đăng nhập lỗi), và cookie logs(thông số của từng ngƣời dùng truy cập Wepsite).
Thông qua việc phân tích các tài liệu đăng nhập này ta có thể khám phá ra những
thông tin truy cập.
Web pages: Hầu hết các phƣơng pháp KPDL Web đƣợc sử dụng trong Web
pages là theo chuẩn HTML.
Web hyperlink structure: Các trang Web đƣợc liên kết với nhau bằng các siêu
liên kết, điều này rất quan trọng để khai phá thông tin. Do các siêu liên kết Web là
nguồn tài nguyên rất xác thực.
Dữ liệu thị trường trực tuyến: Nhƣ lƣu trữ thông tin thƣơng mại điện tử trong
các site thƣơng mại điện tử.
Các thông tin khác: Chủ yếu bao gồm các đăng ký ngƣời dùng, nó có thể giúp
cho việc khai phá tốt hơn.
Dữ liệu Web
Liên kết động
Dữ liệu cấu trúc Web
Dữ liệu sử dụng Web
Dữ liệu ngƣời dùng
Dữ liệu văn bản
Dữ liệu HTML
Dữ liệu động
Hình ảnh, video
Liên kết tĩnh
Dữ liệu XML
Văn bản tự do
Hình 1-3: Phân loại dữ liệu Web
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 22
1.3.2 Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web
1.3.2.1 Dữ liệu văn n
Văn bản là loại tài liệu phổ biến, đƣợc sử dụng trong mọi hoạt động của con
ngƣời, đặc biệt trong môi trƣờng truyền truyền thông số và trên Internet. Do vậy, các
bài toán xử lý loại dữ liệu này đã đƣợc đặt ra từ rất sớm và hiện nay nó vẫn là vấn đề
rất đƣợc nhiều nhà nghiên cứu quan tâm, một trong những bài toán đó là tìm kiếm và
trích dẫn văn bản, biểu diễn và phân loại văn bản,.
S văn n có thể chia làm 2 loại chính [6]:
D ng không có cấu trúc: Đây là những tài liệu văn bản thông thƣờng mà ta dùng
hằng ngày, thƣờng xuất hiện trên các sách, báo, internet, đây là dạng dữ liệu của
ngôn ngữ tự nhiên của con ngƣời và nó không theo một khuôn mẫu định sẵn nào cả.
D ng nửa cấu trúc: Đây là những văn bản đƣợc tổ chức dƣới dạng cấu trúc lỏng,
nhƣng vẫn thể hiện nội dung chính của văn bản, nhƣ văn bản HTML, Email,..
1.3.3 Một số vấn đề trong xử lý dữ liệu văn bản
Trong việc sử lý các dữ liệu văn bản thì mỗi văn bản đƣợc biểu diễn bằng một
vector Boolean hay vector số. Những vector này đƣợc xét trong một không gian đa
chiều, trong đó mỗi chiều tƣơng ứng với một từ mục riêng biệt trong tập văn bản.
- ột s ưu hi iểu đi n văn n ng h ng gian v ctor:
- Không gian vector: là một tập hợp bao gồm các từ.
- Từ: là một chuỗi các ký tự (chữ cái và chữ số). Ngoại trừ các khoảng
trống (space, tab), ký tự xuống dòng, dấu câu (nhƣ dấu chấm, phẩy, chấm
phẩy, dấu cảm,...). Mặt khác, để đơn giản trong quá trình xử lý, ngƣời ta
không phân biệt chữ hoa và chữ thƣờng (nếu chữ hoa thì chuyển về chữ
thƣờng).
- Gộp từ đồng nghĩ : Trong nhiều ngôn ngữ, nhiều từ có cùng từ gốc hay
là biến thể của từ gốc sang một từ khác. Việc sử dụng từ gốc làm giảm
đáng kể số lƣợng các từ trong văn bản (giảm số chiều của không gian),
nhƣng việc cắt bỏ các từ lại rất khó trong việc hiểu văn bản.
- Lo i bỏ từ: Trong phƣơng pháp biểu diễn dữ liệu văn bản bằng không
gian vector, thì chiều của một vector sẽ rất lớn bởi số chiều của nó đƣợc
xác định bằng số lƣợng các từ khác nhau trong tập hợp từ. Vì vậy, vấn đề
dặt ra là làm sao để giảm số chiều của vector mà vẫn đảm bảo việc xử lý
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 23
văn bản đúng và chính xác. Để giải quyết vấn đề này ngƣời ta đƣa ra một
số phƣơng pháp là: loại bỏ từ dừng và áp dụng định luật Zipf
1.3.3.1 Loại bỏ từ dừng
Trong ngôn ngữ văn bản hằng ngày có nhiều từ chỉ dùng để biểu diễn cấu trúc
câu chứ không biểu đạt nội dung của nó. Nhƣ các giới từ, từ nối,... những từ nhƣ vậy
xuất hiện nhiều trong các văn bản mà không liên quan gì tới chủ đề hay nội dung của
văn bản, những từ nhƣ vậy đƣợc gọi là những từ dừng. vậy nên, ta có thể loại bỏ từ
dừng để giảm số chiều của vector trong biểu diễn văn bản.
Sau đây là ví dụ về tần số xuất hiện cao của một số từ (tiếng Anh) trong ...
dƣơng.
Khoảng cách Euclidean: √∑
, (trƣờng hợp đặc biệt của
khoảng cách Minskowski trong trƣờng hợp q =2).
Khoảng cách Manhattan: ∑ | |
, (trƣờng hợp đặc biệt của
khoảng cách Minskowski trong trƣờng hợp q=1).
Khoảng cách cực đ i:
| |, đây là trƣờng hợp của
khoảng cách Minskowski trong trƣờng hợp .
Thuộc tính nhị phân:
Trƣớc hết ta có xây dựng bảng tham số sau:
y:1 y:0
x:1
y:1
Bảng 1-1: Bảng tham số thuộc tính nhị phân
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 18
Trong đó: . x,y là các đối tƣợng có thuộc tính đều là nhị
phân.
là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tƣợng x, y.
là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y.
là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y.
là tổng số các giá trị thuộc tính có giá trị là 0 trong x và y.
Các phép đo độ tƣơng tự đối với dữ liệu thuộc tính nhị phân đƣợc định
nghĩa nhƣ sau:
Hệ số đối sánh đ n giản:
, ở đây cả hai đối tƣợng x và y có vai
trò nhƣ nhau, nghĩa là chúng đối xứng và có cùng trọng số.
Hệ số Jacard:
, tham số này bỏ qua số các đối sánh giữa 0-0.
Công thức tính này đƣợc sử dụng trong trƣờng hợp mà trọng số của các thuộc tính có
giá trị 1 của đối tƣợng dữ liệu có giá trị cao hơn nhiều so với các thuộc tính có giá trị
0, nhƣ vậy các thuộc tính nhị phân ở đây là không đối xứng.
Thuộc tính định danh:
Độ đo phi tƣơng tự giữa hai đối tƣợng x và y đƣợc định nghĩa nhƣ sau:
, trong đó m là số thuộc tính đối sánh tƣơng ứng trùng nhau và p
là tổng số các thuộc tính.
Thuộc tính có thứ tự:
Phép đo độ phi tƣơng tự giữa các đối tƣợng dữ liệu với thuộc tính thứ tự đƣợc
thực hiện nhƣ sau, ở đây ta giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thƣớc
miền giá trị):
Các trạng thái Mi đƣợc sắp thứ tự nhƣ sau: [1Mi], ta có thể thay thế mỗi giá trị
của thuộc tính bằng giá trị cùng loại ri, với ri {1,,Mi}. Mỗi một thuộc tính thứ tự có
các miền giá trị khác nhau, vì vậy ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng
cách thực hiện phép biến đổi sau cho mỗi thuộc tính:
, với i=1,..,Mi.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 19
Sử dụng công thức tính độ phi tƣơng tự của thuộc tính khoảng đối với các giá trị
, đây cũng chính là độ phi tƣơng tự của thuộc tính có thứ tự.
Thuộc tính tỉ lệ:
Có nhiều cách khác nhau để tính độ tƣơng tự giữa các thuộc tính tỉ lệ. Một trong
những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính xi, thí dụ qi = log(xi),
lúc này qi đóng vai trò nhƣ thuộc tính khoảng. Phép biến đổi logarit này thích hợp
trong trƣờng hợp các giá trị của thuộc tính là số mũ.
Trong thực tế, khi tính độ đo tƣơng tự dữ liệu, ngƣời ta chỉ xem xét một phần các
thuộc tính đặc trƣng đối với các kiểu dữ liệu hay đánh trọng số cho cho tất cả các
thuộc tính dữ liệu. Trong một số trƣờng hợp, ngƣời ta loại bỏ đơn vị đo của các thuộc
tính dữ liệu bằng cách chuẩn hoá chúng hay gán trọng số cho mỗi thuộc tính giá trị
trung bình, độ lệch chuẩn. Các trọng số này có thể sử dụng trong các độ đo khoảng
cách trên, thí dụ với mỗi thuộc tính dữ liệu đã đƣợc gán trọng số tƣơng ứng wi
( ), độ tƣơng tự dữ liệu đƣợc xác định nhƣ sau:
√∑
.
Tóm lại, tuỳ từng trƣờng hợp dữ liệu cụ thể mà ngƣời ta sử dụng các mô hình
tính độ tƣơng tự khác nhau. Việc xác định độ tƣơng tự dữ liệu thích hợp, chính xác,
đảm bảo khách quan là rất quan trọng và giúp xây dựng thuật toán PCDL có hiệu quả
cao trong việc đảm bảo chất lƣợng cũng nhƣ chi phí tính toán của thuật toán.
1.3 Kh i phá dữ liệu Web
Khai phá dữ liệu Web là việc sử dụng các kỹ thuật KPDL để tự động hóa quá
trình phát hiện và trích chọn những thông tin hữu ích từ các tài liệu, các thông tin dịch
vụ, hồ sơ sử dụng và cấu trúc Website. Hay nói cách khác khai phá Web là việc thăm
dò những thông tin quan trọng và những mẫu dữ liệu tiềm năng từ nội dung Web, từ
thông tin truy cập Web, từ liên kết trang và từ nguồn tài nguyên thƣơng mại điện tử
bằng việc sử dụng các kỹ thuật KPDL, nó có thể giúp con ngƣời rút ra tri thức, cải tiến
việc thiết kế các Website và phát triển thƣơng mại điện tử tốt hơn [1].
uá tr nh hai phá
Tìm kiếm nguồn tài nguyên: Thực hiện tìm kiếm và lấy các tài liệu Web phục vụ
cho việc khai phá.
Lựa chọn và tiền xử lý dữ liệu: Lựa chọn và tiền xử lý tự động các loại thông tin
từ nguồn tài nguyên Web đã lấy về.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 20
Tổng hợp: Tự động khám phá các mẫu chung tại các Website riêng lẽ cũng nhƣ
nhiều Website với nhau.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 21
1.3.1 Các kiểu dữ liệu Web
Sơ đồ phân loại dữ liệu Web :
Các đối tượng của khai phá Web bao gồm[4] : Server logs, Web pages, Web
hyperlink structures, dữ liệu thị trƣờng trực tuyến và các thông tin khác.
Web logs(dữ liệu đăng nhập Web): Khi ngƣời dùng duyệt Web, dịch vụ sẽ phân
ra 3 loại dữ liệu đăng nhập: sever logs(dữ liệu đăng nhập trên server), error logs(dữ
liệu đăng nhập lỗi), và cookie logs(thông số của từng ngƣời dùng truy cập Wepsite).
Thông qua việc phân tích các tài liệu đăng nhập này ta có thể khám phá ra những
thông tin truy cập.
Web pages: Hầu hết các phƣơng pháp KPDL Web đƣợc sử dụng trong Web
pages là theo chuẩn HTML.
Web hyperlink structure: Các trang Web đƣợc liên kết với nhau bằng các siêu
liên kết, điều này rất quan trọng để khai phá thông tin. Do các siêu liên kết Web là
nguồn tài nguyên rất xác thực.
Dữ liệu thị trường trực tuyến: Nhƣ lƣu trữ thông tin thƣơng mại điện tử trong
các site thƣơng mại điện tử.
Các thông tin khác: Chủ yếu bao gồm các đăng ký ngƣời dùng, nó có thể giúp
cho việc khai phá tốt hơn.
Dữ liệu Web
Liên kết động
Dữ liệu cấu trúc Web
Dữ liệu sử dụng Web
Dữ liệu ngƣời dùng
Dữ liệu văn bản
Dữ liệu HTML
Dữ liệu động
Hình ảnh, video
Liên kết tĩnh
Dữ liệu XML
Văn bản tự do
Hình 1-3: Phân loại dữ liệu Web
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 22
1.3.2 Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web
1.3.2.1 Dữ liệu văn n
Văn bản là loại tài liệu phổ biến, đƣợc sử dụng trong mọi hoạt động của con
ngƣời, đặc biệt trong môi trƣờng truyền truyền thông số và trên Internet. Do vậy, các
bài toán xử lý loại dữ liệu này đã đƣợc đặt ra từ rất sớm và hiện nay nó vẫn là vấn đề
rất đƣợc nhiều nhà nghiên cứu quan tâm, một trong những bài toán đó là tìm kiếm và
trích dẫn văn bản, biểu diễn và phân loại văn bản,.
S văn n có thể chia làm 2 loại chính [6]:
D ng không có cấu trúc: Đây là những tài liệu văn bản thông thƣờng mà ta dùng
hằng ngày, thƣờng xuất hiện trên các sách, báo, internet, đây là dạng dữ liệu của
ngôn ngữ tự nhiên của con ngƣời và nó không theo một khuôn mẫu định sẵn nào cả.
D ng nửa cấu trúc: Đây là những văn bản đƣợc tổ chức dƣới dạng cấu trúc lỏng,
nhƣng vẫn thể hiện nội dung chính của văn bản, nhƣ văn bản HTML, Email,..
1.3.3 Một số vấn đề trong xử lý dữ liệu văn bản
Trong việc sử lý các dữ liệu văn bản thì mỗi văn bản đƣợc biểu diễn bằng một
vector Boolean hay vector số. Những vector này đƣợc xét trong một không gian đa
chiều, trong đó mỗi chiều tƣơng ứng với một từ mục riêng biệt trong tập văn bản.
- ột s ưu hi iểu đi n văn n ng h ng gian v ctor:
- Không gian vector: là một tập hợp bao gồm các từ.
- Từ: là một chuỗi các ký tự (chữ cái và chữ số). Ngoại trừ các khoảng
trống (space, tab), ký tự xuống dòng, dấu câu (nhƣ dấu chấm, phẩy, chấm
phẩy, dấu cảm,...). Mặt khác, để đơn giản trong quá trình xử lý, ngƣời ta
không phân biệt chữ hoa và chữ thƣờng (nếu chữ hoa thì chuyển về chữ
thƣờng).
- Gộp từ đồng nghĩ : Trong nhiều ngôn ngữ, nhiều từ có cùng từ gốc hay
là biến thể của từ gốc sang một từ khác. Việc sử dụng từ gốc làm giảm
đáng kể số lƣợng các từ trong văn bản (giảm số chiều của không gian),
nhƣng việc cắt bỏ các từ lại rất khó trong việc hiểu văn bản.
- Lo i bỏ từ: Trong phƣơng pháp biểu diễn dữ liệu văn bản bằng không
gian vector, thì chiều của một vector sẽ rất lớn bởi số chiều của nó đƣợc
xác định bằng số lƣợng các từ khác nhau trong tập hợp từ. Vì vậy, vấn đề
dặt ra là làm sao để giảm số chiều của vector mà vẫn đảm bảo việc xử lý
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 23
văn bản đúng và chính xác. Để giải quyết vấn đề này ngƣời ta đƣa ra một
số phƣơng pháp là: loại bỏ từ dừng và áp dụng định luật Zipf
1.3.3.1 Loại bỏ từ dừng
Trong ngôn ngữ văn bản hằng ngày có nhiều từ chỉ dùng để biểu diễn cấu trúc
câu chứ không biểu đạt nội dung của nó. Nhƣ các giới từ, từ nối,... những từ nhƣ vậy
xuất hiện nhiều trong các văn bản mà không liên quan gì tới chủ đề hay nội dung của
văn bản, những từ nhƣ vậy đƣợc gọi là những từ dừng. vậy nên, ta có thể loại bỏ từ
dừng để giảm số chiều của vector trong biểu diễn văn bản.
Sau đây là ví dụ về tần số xuất hiện cao của một số từ (tiếng Anh) trong ...