Xây dựng quy trình và thuật toán để phân loại tài liệu TBT
KHOA HỌC - ỨNG DỤNG
XÂY DỰNG QUY TRÌNH VÀ THUẬT TOÁN
ĐỂ PHÂN LOẠI TÀI LIỆU TBT
ThS. NGUYỄN MINH ĐẾ (*)
TÓM TẮT
Trong bài báo này trình bày bài toán Phân loại Tài liệu TBT, mà có hai công việc chính (quy
trình phân loại và thuật toán thực hiện), được xem như là một trong các thành phần cần thiết trong
quá trình phát một Hệ thông minh. Quy trình phân loại này trải qua các bước trong một tiến trình
xử lý thống nhất và có các đặc trưng giống như của một thuật toán. Bài báo đưa ra hai phương
pháp để phân loại tài liệu TBT, gồm có hai hướng chính: theo mô hình phân loại tài liệu TBT và
theo nội dung tài liệu TBT. Mô hình của phân loại tài liệu sẽ được xây dựng theo mô hình
Taxonomy phân cấp và trong việc phân cấp sẽ sử dụng các bảng/khung phân loại cho trước.
Phương pháp phân loại tài liệu TBT theo nội dung thì thực hiện theo một quy trình xử lý thống nhất
và có sử dụng hai kỹ thuật: mô hình N-Gram và tính trọng số TF-IDF.
Từ khóa: Chỉ số phân loại (CSPL), mô hình Taxonomy, phân loại tài liệu theo mô hình, phân
loại tài liệu theo nội dung, mô hình N-Gram, trọng số TF-IDF.
SUMMARY
In this paper, we present the problem of TBT Document Classification, which has two major
tasks (classification process and executive algorithm), which is considered as one of essential
components in developing a Smart System. This classification process has steps in a unified
process, and it has characteristics as an algorithm. This paper proposes two methods for TBT
Document Classification, these two methods consist of two main directions: according to the model
of TBT Document Classification; and according to the content of TBT documents. The model of
Document Classification will be constructed in hierarchical Taxonomy model, and this hierarchy
will be based on given classification tables/frames. The method of content-based TBT Document
Classification is performed in a unified treatment process, with two techniques: N-Gram model;
and TF-IDF weighting.
Key words: Categorical Indicator (CI); Taxonomy Model; Document Classification
according to the model; Document Classification according to the content; N-Gram model; TF-IDF
weight.
1. Mở đầu
Phân loại tài liệu TBT là một trong các công việc quan trọng để phục vụ và hỗ trợ cho mục tiêu
3 của đề tài “Nghiên cứu và xây dựng Hệ hỏi đáp thông minh cho thông tin về Hàng rào Kỹ thuật
trong Thương mại (TBT) của tỉnh Long An”. Mục tiêu 3 của đề tài là “Nghiên cứu và xây dự
ỏi đáp thông minh TBT Long An”, được chia ra làm các thành phần nhỏ hơn cần phải xây
dựng. Các thành phần này đều rời rạc và độc lập với nhau, nhưng có tồn tại sự liên kết cần thiết để
tạo thành một chỉnh thể của hệ thống. Sự liên kết này sẽ được tổ chức thành hệ thống có cấu trúc
tương tự như phân tán, nghĩa là cho phép có sự thiếu vắng một số thành phần bên trong nhưng hệ
thống vẫn hoạt động được.
Hệ thống để phân loại tài liệu có hai công việc cần phải xây dựng: Quy trình phân loại; Phương
pháp hỗ trợ việc phân loại. Quy trình phân loại tài liệu là công việc cần thiết đầu tiên để định hình
các bước phải thực hiện. Tiếp theo, phải xây dựng các hệ thố
ối ưu để chỉ dẫn nội
dung thực hiện và định hướng cho các chương trình máy tính thực thi. Quy trình phân loại tài liệu
thì cần phải xây dựng trước tiên. Sau đó, từ quy trình phân loại có được mới có thể xác định phương
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
64
KHOA HỌC - ỨNG DỤNG
pháp thực hiện cụ thể. Phương pháp thực hiện chia ra làm hai loại: thủ công và tin học hóa (chương
trình máy tính).
Chương trình máy tính cần có các thuật toán để xác định các hoạt động cần phải thực hiện theo
thứ tự trước sau.
thuật toán chi tiế
ẽ được xây dựng theo mô hình từ thuật toán tổng quát cho đến các
ất đa cấp bậc và lồng ghép lại, có sự liên kết lại với
nhau, và có đặc trưng riêng là các thành phần được thiết kế, xây dựng qua các phiên bản khác nhau.
Bài này trước tiên đề nghị một quy trình thống nhất để phân loại tài liệu TBT và có một tiến
trình xác định. Quy trình này có một số các đặc tính như đặc trưng của thuật toán: Tính xác định;
Tính hữu hạn; Tính kết quả; Tính phổ dụng; Tính hình thức.
Bài
cũng đưa ra phương pháp phân loại tài liệu TBT cũng như các thuật toán cần thiết để
thực hiện. Phương pháp phân loại này sẽ theo 2 hướng: Hướng theo mô hình phân loại tài liệu TBT;
Hướng theo nội dung của tài liệu TBT. Các thuật toán sẽ được chia ra làm hai nhóm tương ứng để
thực hiện cho từng phương pháp phân loại phù hợp.
Phần còn lại của bài
như sau: Phần 2, phần kế tiếp trình bày các thành phần của phân loại
tài liệu theo mô hình cây phân cấp Taxonomy; Phần 3, trình bày quy trình phân loại tài liệu TBT và
phương pháp thực hiện; Phần 4, trình bày các thuật toán để phục vụ cho các phương pháp thực hiện
của quy trình phân loại tài liệu TBT; Phần 5, trình bày kết quả và kết luận.
2. Các thành phần của Phân loại tài liệu theo mô hình phân cấp Taxonomy
Phân loại tài liệu có thể xem là việc dựa vào những dấu hiệu giống nhau và khác nhau để phân
chia, sắp xếp các tài liệu theo một trật tự nhất định.
Khung/bảng phân loại là cấu trúc có được do việc phân loại đã được thu gọn hoặc phản ánh vào
một giản đồ, bảng biểu (Scheme, Table) nhất định theo các nguyên tắc phân loại cho trước.
Một Taxonomy được mô tả với một gốc trên cùng là O, mỗi nút (gồm cả nút gốc O) là một thực
thể trong thế giới thực. Giữa các nút trong Taxonomy có quan hệ: Một mối quan hệ đặc biệt gọi là
is subclassificationof (nếu hướng liên kết từ nút con lên nút cha); is superclassification of nếu
hướng liên kết từ nút cha xuống nút con.
Quan hệ trên có thể chuyển thành hướng đối tượng tương ứng chặt chẽ hơn như sau: is subclass
of (lớp con); is superclass of (lớp cha).
Hình 1. Cây phân cấp lớp thú dạng phân cấp Taxonomy
Hình ảnh một cấu trúc phân cấp Taxonomy. Taxonomy trên gồm có nút gốc/lớp cha là O (lớp
thú), O có 3 lớp/nút con là: Bộ linh trưởng; Bộ ăn thịt; Bộ guốc chẵn. Lớp/Nút Bộ linh trưởng có 1
lớp/nút con Họ khỉ. Lớp/Nút Bộ ăn thịt có 1 lớp/nút con Họ mèo. Lớp/Nút Bộ guốc chẵn có 1
lớp/nút con Họ lạc đà.
Chỉ số của tài liệu
hiệu phản ánh đặc trưng riêng của một tài liệu, bao gồm một hoặc nhiề
hiệu thể hiện các nội dung khác nhau của một tài liệu. Chỉ số này được thiết lập theo tiêu chuẩn
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
65
KHOA HỌC - ỨNG DỤNG
CSPL cụ thể, mà trong bài này sẽ dựa vào chỉ số ICS hoặc HS
hiệu phân loại đầy đủ thường
được ghi ở một vị trí cụ thể, thông thường ở phía trên trang tên tài liệu và góc bên phải phía dưới
của phiếu mô tả cho tài liệu.
Sau khi phân loại tài liệu thì cần sắp xếp tài liệu một cách khoa học, các cách sắp xếp theo như
sau: Thời gian; Mẫu tự; Tính chất.
Danh mục tài liệu là bảng liệt kê một cách hệ thống tài liệu đã thu thập được. Nhờ vào danh
mục này mà thực hiện sắp xếp, quản lý và tra cứu tài liệu một cách nhanh chóng. Danh mục tài liệu
có tính chất sau: Cụ thể; Chính xác; Cập nhật thường xuyên.
Tài liệu phải được lưu trữ vào một vị trí nhất định để khi cần truy cập sẽ nhanh chóng,và cần
phải làm bảng liệt kê một cách hệ thống tài liệu. Nhờ vào danh mục này mà có thể sắp xếp, quản lý
và tra cứu tài liệu nhanh chóng.
Lưu trữ điện tử có thể được sử dụng không chỉ để lưu trữ tài liệu điện tử (thu được bằng cách
nhập dữ liệu hoặc quét tài liệu) mà còn để tạo ra thư viện các loại tập tin khác nhau: tập tin âm
thanh, tập tin, hình ảnh…
Phần trung tâm của hệ thống lưu trữ điện tử là kho lưu trữ điện tử. Kho lưu trữ điện tử là một hệ
thống lưu trữ có cấu trúc các tài liệu điện tử. Việc xây dựng kho lưu trữ điện tử là một cơ hội để làm
sạch các tài liệu và khả năng nhanh chóng tìm thấy các tài liệu cần thiết.
Biên mục tài liệu là một công việc quan trọng cần phải thực hiện khi nhận được một tài liệu cụ
thể. Biên mục tài liệu thực hiện việc thu thập các thông tin tổng quát quan trọng của một tài liệu:
nhan đề (tiêu đề), tác giả, nhà xuất bản/quốc gia, năm xuất bản, tóm tắt... Mỗi thông tin trên có thể
xem là một vùng thông tin của tài liệu.
Mỗi một tài liệu có các thông tin tổng quát đặc trưng riêng, nên tài liệu sẽ có các vùng thông tin
khác nhau, xét một tài liệu TBT sẽ có 8 vùng thông tin như sau:
i. Vùng nhan đề [tài liệu] và minh xác về trách nhiệm
ii. Vùng sản phẩm
iii. Vùng địa chỉ xuất bản
iv. Vùng thời gian
v. Vùng chi tiết vật chất tài liệu
vi. Vùng tài liệu kèm theo
vii. Vùng tóm tắt
viii. Vùng mã số/ký hiệu
Tài liệu TBT đều phải chuyển thành 2 dạng cơ bản: văn bản giấy và tài liệu điện tử (file dữ
liệu). đây chỉ trình bày mô hình lưu trữ của tài liệu điện tử (tập tin dữ liệu). Cấu trúc lưu trữ dạng
cây thư mục có phân cấp (cây Taxonomy), bao gồm các thư mục và các tập tin các tài liệu.
Một tài liệu TBT sẽ thu được 8 vùng thông tin chính như trên, nhưng trong đó có 6 thông tin
hữu dụng được sử dụng để phân loại tài liệu: Chuyên mục; Quốc gia/Khu vực; Cơ quan/tổ chức phi
chính phủ có thẩm quyền trách nhiệm; Khung phân loại Sản phẩm; Sản phẩm; Mã ký hiệu. Sáu
thông tin này sẽ được xem là 6 lớp để phân loại tài liệu TBT. Như vậy, cây thư mục lưu trữ sẽ có 6
lớp tương ứng, đây là Mô hình phân loại tài liệu:
i. Lớp cấp 0, Chuyên mục gồm có các thư mục tương ứng với các chuyên mục được phân chia từ
trước.
ii. Lớp cấp 1, Quốc gia/Khu vực gồm có các thư mục tương ứng với các Quốc gia/Khu vực. Mỗi
thư mục sẽ là một Quốc gia/Khu vực và sử dụng tên viết tắt có 3 ký tự.
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
66
KHOA HỌC - ỨNG DỤNG
iii. Lớp cấp 2, Cơ quan/Tổ chức gồm có các thư mục tương ứng với các Cơ quan /Tổ chức. Mỗi thư
mục sẽ là một Cơ quan /Tổ chức và sử dụng tên viết tắt chính thức của Cơ quan /Tổ chức đó.
iv. Lớp cấp 3, Khung phân loại gồm có các thư mục tương ứng với các Khung phân loại. Mỗi thư
mục sẽ là một Khung phân loại (chủ yếu khung/bảng HS và ICS).
v. Lớp cấp 4, Sản phẩm gồm có các thư mục tương ứng với các Sản phẩm. Mỗi thư mục sẽ là một
Sản phẩm và sử dụng ký hiệu đúng theo quy định của Khung phân loại cho trước ở trên.
vi. Lớp cấp 5, Mã/Số ký hiệu là chính tập tin của tài liệu TBT. Mỗi tập tin sẽ có tên chính là Mã/Số
ký hiệu đó.
3. Quy trình phân loại tài liệu TBT và phương pháp thực hiện
3.1
Tài liệu TBT đa số tồn tại ở dạng: văn bản giấy; dữ liệu điện tử (chủ yếu tập tin loại: văn bản
kiểu text; văn bản kiểu pdf…). Đối với 2 dạng tài liệu này thì về cơ bản đều sử dụng quy trình xử lý
giống nhau, do đó tất cả tài liệu TBT đều phải được chuyển sang dạng tập tin và thực hiện tiếp quy
trình phân loại.
Công tác biên mục và phân loại tài liệu là khâu quan trọng trong quy trình phân loại tài liệu
TBT. Tài liệu sau khi đã được thừa nhận để đưa vào phân loại thì đều phải trải qua quá trình xử lý
chuyên môn nghiệp vụ hoàn chỉnh thì mới được đưa vào phục vụ. Mỗi một tài liệu khi được bổ
sung vào thì phải được các nhân sự phụ trách công tác bổ sung lựa chọn các phương pháp phù hợp
cho nó.
Tài liệu khi bắt đầu nhập vào thì phải trải qua tất cả các khâu xử lý được quy định trước trong
công tác biên mục và phân loạ
này sẽ đề cập đến phương pháp xử lý thủ công và
phương pháp xử lý nghiệp vụ được tin học hóa (chương trình máy tính).
Khi tài liệu được bắt đầu đưa vào quy trình thì phải qua tác vụ đầu tiên của bộ phận nghiệp vụ là
đăng ký tổng quát, đăng ký cá biệt cho tài liệu, đóng dấu xác nhận vào và bắt đầu tiến hành công tác
biên mục, phân loại, lưu trữ.
Quy trình phải thực hiện qua từng bước, có tổng cộng 6 bước chính. Các bước thực hiện có sự
liên tục và không được bỏ bước thực hiện. Bước thực hiện trước phải thực hiện xong hoàn tất thì
mới chuyển qua bước kế tiếp. Từng bước đều có thể thực hiện thủ công và có sự hỗ trợ của phần
mềm máy tính.
3.2 Các bước thực hiện và mô tả chi tiết
Sáu bước để phân loại tài liệu TBT:
B1: Nhận tài liệu TBT và thực hiện việc kiểm tra về mặt số lượng, chất lượng của tài liệu.
B2: Đăng ký tài liệu trong Sổ đăng ký tổng quát/cá biệt.
B3: Xác định dạng tài liệu TBT.
• Nếu: Dạng tài liệu điện tử (tập tin) thì thực hiện B4.
• Nếu: Dạng tài liệu giấy thì
o Chuyển dạng tài liệu sang dạng tài liệu điện tử (tập tin).
o Thực hiện B4.
B4: Thực hiện thủ tục hành chính nếu có (sao chép, đóng dấu chủ quyền, lập báo cáo, …)
B5: Thực hiện tác vụ biên mục và phân loại tài liệu
Mô hình phân loại qua 6 lớp (theo CSPL) và theo nội dung của tài liệu.
• B5.1: Mô tả tài liệu
tả; Mẫu danh mục tài liệu;
• B5.2: Lập đề mục (lập danh mục tài liệu TBT đã có)
• B5.3: Phân loại (xác định CSPL)
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
67
KHOA HỌC - ỨNG DỤNG
B6: Lưu trữ tài liệu và sắp xếp theo tiêu chí thích hợp.
• B6.1: Tạo thư mục (theo cấu trúc CSPL, theo Mô hình lưu trữ tài liệu TBT)
• B6.2: Sao chép dữ liệu (theo cấu trúc của Mô hình lưu trữ tài liệu TBT)
• B6.3: Sắp xếp (theo các tiêu chí)
BKT: Kết thúc.
Mô tả chi tiết từng bước:
B1: Nhận tài liệu TBT và kiểm tra về mặt số lượng và chất lượng, thực hiện thủ công.
B2: Đăng ký tài liệu, đọ
đề của tài liệu để vào Sổ (SĐKTQ/SĐKCB là Bảng 1 và Bảng 2), có
thể dùng phần mềm máy tính để hỗ trợ.
• Vào SĐKTQ, mẫu sổ ở Bảng 1
Toàn bộ tài liệu nhập vào phải được ghi đầy vào Sổ ĐKTQ.
• Vào SĐKCB, mẫu sổ ở Bảng 2
Sổ ĐKCB là cung cấp thông tin cụ thể, chi tiết về từng tài liệu đã nhập vào. Tài liệu sau khi
được đăng ký tổng quát, sẽ được đăng ký từng chi tiết vào sổ đăng ký riêng.
B3: Xác định dạng Tài liệu TBT, thì việc chuyển dạng tài liệu sang dạng tài liệu điện tử (tập tin) sẽ
thực hiện thủ công (có sự hỗ trợ của phần mềm).
B4: Thực hiện thủ tục hành chính, thực hiện thủ công.
B5: Thực hiện tác vụ biên mục và phân loại, gồm có 3 bước
• B5.1: Mô tả tài liệu TBT theo Chuẩn biên mục mô tả tài liệu TBT, sẽ có 8 vùng và có thể sử
dụng phần mềm để thực hiện.
• B5.2: Lập danh mục tài liệu TBT, theo mẫu Bảng 3.
• B5.3: Phân loại. Xác định CSPL cho tài liệu TBT, thực hiện thủ công hoặc nhờ phần mềm hỗ
trợ qua từng bước của mô hình phân loại. Mô hình phân loại tài liệu TBT có 6 lớp nên sẽ có 6
khối mã/số. Như vậy, CSPL có 6 khối (Chuyên mục, Quốc gia, Cơ quan/Tổ chức, Khung
phân loại, Sản phẩm, Ký hiệu).
B6: Lưu trữ tài liệu và sắp xếp theo tiêu chí thích hợp, gồm có 3 bước
• B6.1: Tạo thư mục.
Theo mô hình phân loại tài liệu TBT thì thư mục sẽ có 6 cấp theo CSPL. Thực hiện tuần tự cho
CSPL từ trái sang phải, mỗi thư mục tương ứng với từng khối của CSPL, nếu thư mục chưa có thì
tạo ra, nếu có rồi thì truy xuất vào trong và lặp lại cho đến hết.
• Thư mục gốc chứa 1
• 1 chứa thư mục VNM
• VNM chứa MH
• MH chứa thư mục 1
• 1 có chứa thư mục 67.100.10
• Thư mục 67.100.10 có chứa
tập tin G/TBT/N/VNM/78.*, có
thể đổi dấu “/” thành dấu “-”
hoặc các dấu khác.
Hình 2: Cấu trúc thư mục lưu trữ tài liệu TBT
• B6.2: Sao chép dữ liệu. Có thể thực hiện thủ công hoặc nhờ sự hỗ trợ của phần mềm
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
68
KHOA HỌC - ỨNG DỤNG
• B6.3: Sắp xếp. Theo tiêu chí đã chọn, có thể thực hiện thủ công hoặc nhờ sự hỗ trợ của phần
mềm
BKT: Kết thúc.
4. Phương pháp phân loại tài liệu và các thuật toán
4.1 Phương pháp phân loại tài liệu TBT
• Phân loại theo như mô hình phân loại
Hướng tiếp cận này là: Xác định CSPL; Tìm vị trí thích hợp cho nội dung một tài liệu TBT.
Ngoài ra, việc phân loại tài liệu còn theo hướng khác là phân loại theo nội dung của tài liệu.
Sau khi phân loại thì CSPL của tài liệu TBT sẽ được thiết lập và sau đó thực hiện tiếp việc lưu
trữ tài liệu. Tuy nhiên việc thiết lập CSPL và việc lưu trữ tài liệu có thể thực hiện song song. Thuật
toán “Xây dựng CSPL và lưu tài liệu” ở dưới đây sẽ thực hiện hai công việc này đồng thời.
• Phân loại tài liệu theo nội dung tài liệu
Số lượng tài liệu TBT sẽ được gia tăng theo thời gian lưu trữ và toàn bộ đều là tài liệu ở dạng
văn bản. Đa số các phương pháp phân loại nội dung tài liệu đều theo một số hướng chung: Máy
học; Mô hình xác suất và thống kê; Giải thuật học tự động…
Bài toán phân loại tài liệu dựa vào chủ yếu ở tình huống phân loại dựa trên các CSDL có sẵn
các tài liệu TBT. Thuật toán phân loại thực hiện phân loại trên toàn bộ tập dữ liệu đã xử lý trước
thuộc CSDL tài liệu.
Quy trình chung cho phương pháp phân loại tài liệu theo nội dung:
• Sắp xếp tài liệu theo tiêu chí xác định trước;
• Xây dựng bộ dữ liệu để học;
• Tiến hành học trên bộ dữ liệu;
• Xử lý dữ liệu có được;
• Thu thập kết quả theo từng chủ đề;
• Rút ra các đặc trưng riêng biệt;
• Kết hợp các đặc trưng đã học với đặc trưng riêng biệt;
• Phân loại và đưa ra kết quả.
Để cung cấp một số các kỹ thuật xử lý cần thiết cho các bước trong quy trình phân loại thì có
các nội dung kỹ thuật sau:
o Quy trình xử lý tài liệu: nêu lên các bước cần thiết để phân loại tài liệu.
o Phương pháp tách từ: là một kỹ thuật sử dụng phương pháp n-gram để lấy các từ cần thiết.
o Phương pháp tính trọng số của từ: là kỹ thuật đếm từ trong văn bản.
o Cấu trúc biểu diễn tri thức RDF: là một cách để biểu diễn tri thức thu được.
4.2 Thuật toán phân loại tài liệu TBT
Phân loại tài liệu theo như mô hình phân loại
Do CSPL có cấu tạo từ 6 khối nên sẽ có 6 bước chính để xác định CSPL và tương ứng với việc
lưu trữ tài liệu.
Thuật toán Xay_Dung_CSPL_Luu thực hiện 2 công việc chính: tạo ra CSPL và lưu trữ tài
liệu đúng vị trí của nó. Dữ liệu đầu vào là một tài liệu TBT ở dạng văn bản đã xử lý theo tiêu chuẩn
cho trước. Kết thúc thuật toán thì tài liệu đã được định theo CSPL và đã lưu trữ đúng vị trí.
- Hàm Lay_ThuMuc (ThietBiLuu, ViTri) có 2 tham số vào: thiết bị để lưu trữ tài liệu TBT F
(ThietBiLuu); vị trí để lưu (ViTri). Hàm này sẽ trả kết quả ra là thư mục gốc dùng để chứa tài
liệu TBT F.
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
69
KHOA HỌC - ỨNG DỤNG
- Sáu hàm (Lay_So_Chuyen_Muc(), Lay_Quoc_Gia_Khu_Vuc(), Lay_Co_Quan_To_Chuc(),
Lay_Khung_Phan_Loai(), Lay_Ma_San_Pham(), Lay_Ky_Hieu()) đều có 1 tham số vào là
tập tin TBT F đã được xử lý và trả về tương ứng cho sáu chuỗi (mã số chuyên mục, mã số
quốc gia/khu vực, viết tắt cơ quan/tổ chức, k hiệu Khung phân loại, k hiệu Sản phẩm, k
hiệu tài liệu TBT).
Thuật toán Xay_Dung_CSPL_Luu
Function Xay_Dung_CSPL_Luu
Input: F (Tập tin TBT); Output: CSPL và TM
1. TM Lay_ThuMuc(ThietBiLuu, ViTri)
2. CSPL “”// CSPL rỗng
3. CSPL Lay_So_Chuyen_Muc(F)
4. Dua_Tai_Lieu_Vao(F, CSPL, TM)
5. CSPL
CSPL
+
“.”
+
+
+
Lay_Quoc_Gia_Khu_Vuc(F)
6. Dua_Tai_Lieu_Vao(F, CSPL, TM)
7. CSPL CSPL
Lay_Co_Quan_To_Chuc(F)
8. Dua_Tai_Lieu_Vao(F, CSPL, TM)
9. CSPL CSPL
+
“.”
+
“.”
Lay_Khung_Phan_Loai(F)
10. Dua_Tai_Lieu_Vao(F, CSPL, TM)
11. CSPL CSPL + “.” + Lay_Ma_San_Pham(F)
12. Dua_Tai_Lieu_Vao(F, CSPL, TM)
13. CSPL CSPL + “.” + Lay_Ky_Hieu(F)
14. Dua_Tai_Lieu_Vao(F, CSPL, TM)
15. Bkt. Kết thúc.
Thuật toán Dua_Tai_Lieu_Vao thực hiện công việc chính: đọc, phân tích CSPL, đưa tập tin ở
đầu vào đến đúng vị trí của nó dựa trên thư mục ở đầu vào.
Thuật toán Dua_Tai_Lieu_Vao
Input: F; CSPL; TM
1. VT Lay_Do_Dai(CSPL) //độ dài
2. TTM Lay_TenThuMuc(CSPL)
3. Nếu TTM != “” Thì
4. Chuyen_Tai_Lieu_Vao(F, TM)
5. Bkt. Kết thúc
6. Ngược lại Tao_ThuMuc(TM, TTM)
7. Bkt. Kết thúc.
Giải thích các hàm/thủ tục trong thuật toán ở dưới:
• Hàm Lay_Ky_Tu có 2 tham số vào là: Vị trí (VT); Chuỗi gốc (CSPL). Hàm này trả kết quả ra là
ký tự ở vị trí VT trong chuỗi gốc CSPL.
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
70
KHOA HỌC - ỨNG DỤNG
• Hàm Lay_Chuoi có 3 tham số vào là: Vị trí bắt đầu (VTD); Vị trí kết thúc (VTC); Chuỗi gốc
(CSPL). Hàm này trả kết quả ra là chuỗi ký tự mà có bắt đầu ở vị trí VT và lấy cho đến hết
trong chuỗi gốc CSPL.
• Hàm Lay_TenThuMuc(CSPL) để lấy ra tên thư mục, nếu TTM = “” thì thực hiện việc đưa/sao
chép tài liệu vào đúng chỗ với thủ tục Chuyen_Tai_Lieu_Vao(F, TM), nếu TTM != “” thì thực
hiện việc thủ tục Tao_ThuMuc(TM, TTM)
• Thủ tục Tao_ThuMuc(TM, TTM) để kiểm tra xem TM đã tồn tại TTM chưa, nếu chưa thì tạo
mới, nếu có thì bỏ qua.
Phân loại tài liệu theo nội dung tài liệu TBT
Các kỹ thuật để thực hiện đã được nghiên cứu ở các công trình.
Quy trình xử lý
Hình 3: Quy trình xử lý tài liệu
Trong đó:
–Ngữ liệu huấn luyện: kho ngữ liệu thu thập từ nhiều tài liệu khác nhau.
–Tiền xử lý: chuyển đổi tài liệu trong kho ngữ liệu thành một hình thức phù hợp để phân
loại/lớp.
–Vector
: mã
văn bản bởi một mô hình trọng số.
–Trích chọn đặc trưng: loại bỏ những từ (đặc trưng) không mang thông tin khỏi tài liệu nhằm
nâng cao hiệu suất phân loại và giảm độ phức tạp của thuật toán huấn luyện.
–Thuật toán huấn luyện: Thủ tục huấn luyện bộ phân lớp để tìm ra họ các tham số tối ưu.
–Đánh giá: bước đánh giá hiệu suất (chất lượng) của bộ phân lớp/loại.
Phương pháp tách từ
Phương pháp tách từ là sử dụng mô hình N-gram. N-gram là tần suất xuất hiện củ
(hoặc từ) liên tiếp nhau có trong dữ liệu.
tự
– Với n = 1 và tính trên k tự, có thông tin về tần suất xuất hiện nhiều nhất của các chữ cái.
– Với n = 2, có khái niệm bigram. Ví dụ: với các chữ cái tiếng Anh, ‘th’,’he’,’in’,’an’,’er’ là các
cặp k tự hay xuất hiện nhất. Ngoài ra, ta có thể biết thêm rằng sau k tự ‘q’ thì phần lớn đều là k
tự ‘u’.
– Với n = 3, có trigram. Nhưng vì n càng lớn thì số trường hợp càng lớn nên thường chỉ sử dụng
với n = 1 hoặc 2, hoặc đôi lúc là 3. Ví dụ, với các k tự tiếng Anh, tiếng Anh sử dụng 26 k tự, vậy
với n = 1 thì số trường hợp là 26, n = 2 thì số trường hợp là 262 = 676 trường hợp, n = 3 có 17576
trường hợp.
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
71
KHOA HỌC - ỨNG DỤNG
Hướng tiếp cận giải quyết ở đây là: chia văn bản ra làm nhiều chuỗi; mỗi chuỗi gồm n từ;
thường sử dụng n = 2. Ví dụ, khi áp dụng phương pháp này cho văn bản T = “dc gt de” thì sẽ thu
được từ 3 từ đơn (dc; gt; de) và 2 từ ghép (dc gt; gt de).
Vấn đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram:
i. Phân bố không đều:
Mô hình N-gram được xây dựng theo công thức “xác suất thô”, do đó có thể xuất hiện sự
phân bố không đều hoặc phân bố thưa trong tập văn bản huấn luyện và dẫn đến các ước lượng
không chính xác và kết quả thu được không tốt.
Có nhiều câu văn mà xác suất sẽ bằng 0, do cụm N-gram chưa tồn tại trong dữ liệu huấn
luyện. Để khắc phục tình trạng này thì sẽ sử dụng các phương pháp làm mịn.
ii. Kích thước bộ nhớ của mô hình ngôn ngữ:
Số lượng các cụm N-gram và kích thước của mô hình ngôn ngữ và sẽ tăng lên tùy theo kích
thước tập văn bản huấn luyện.
Phương pháp làm mịn: có một số loại khác nhau như (Chiết khấu-Discounting); Truy hồi
(Back-off); Nội suy (Interpolation)).
Trong bài
này sẽ không trình bày nội dung và so sánh các phương pháp làm mịn, mà chỉ
trình bày Thuật toán tách từ. Đối với từng tài liệu TBT cụ thể sẽ lựa chọn kỹ thuật làm mịn theo sự
chỉ dẫn riêng phù hợp với nó.
Thuật toán Tach_Tu_Ngram lấy độ dài của chuỗi là n, tạo danh sách lưu trữ kq, tiếp đó lần
lượt lấy ra các ký tự, số lượng ký tự lấy ra phụ thuộc vào tham số gram ở đầu vào, đưa chuỗi ký tự
lấy ra vào kq để lưu trữ.
Thuật toán Tach_Tu_Ngram
Function Tach_Tu_Ngram
Input: self; statement; gram
1. n len(statement)
2. kq[] // tạo mảng lưu kết quả
3. IF n >= gram THEN
For i in n do
kq = incre(kq[statement[i:i + gram])
4. Kết thúc.
Phương pháp tính trọng số của từ
Giải thuật:
Bước 1: Loại bỏ các từ tầm thường (stopword).
Bước 2: Đếm tần suất xuất hiện của các từ trong bước 1.
Bước 3: Tính trọng số của từ theo công thức trong khung ở dưới:
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
72
KHOA HỌC - ỨNG DỤNG
Weight =tf*idf
wi
tf =Ns(t)/∑w
idf =log(∑d/(d:t∈d))
Trongđó:
Ns:Số lần xuất hiện của từ trong tài liệu
∑w:Tổng số các từ trong tài liệu
∑d=tổng số tài liệu
D : t ∈d:số tài liệu có chứa từ
Cho một văn bản gồm có 1000 từ, trong đó từ “Sản Phẩm” xuất hiện 40 lần thì độ phổ biến
Tf (“Sản Phẩm”) = 40 / 1000 = 0.04
Giả sử có 2000 tài liệu đã được huấn luyện, trong đó có 400 tài liệu chứa từ “Sản Phẩm”.
Idf (“Sản Phẩm”) = log (2000 / 400) ≈ 0.699
Như vậy, với giá trị TF.IDF=tf*idf thì TF.IDF=0.04*0.699=0.028
5. Kết quả và thảo luận
Tài liệu TBT được thu thập sẽ tăng dần dần theo thời gian, được phân loại và lưu trữ theo
phương pháp xử lý trực tiếp và liên tục (khi nhận được bất kỳ tài liệu TBT nào thì lập tức thực hiện
việc xử lý và phân loại).
Tài liệu TBT có nội dung khác nhau do đó sẽ được phân chia vào các thể loại khác nhau. Bài
đề nghị một tài liệu TBT bất kỳ phải được phân loại vào một trong năm loại văn bản: Luật;
Thông báo; Quy chuẩn; Tiêu chuẩn; Tranh chấp. Số lượng tài liệu TBT đã thu thập được là 21706,
phân bố theo 5 loại: Luật (1347); Thông báo (10481); Quy chuẩn (146); Tiêu chuẩn (9692); Tranh
chấp (40).
Một tài liệu TBT sau khi thu thập được sẽ đi qua 6 bước như đã trình bày trong nội dung của
phần 3 ở trên. Trong 6 bước đã trình bày ở trên thì có các bước quan trọng cần tập trung là B5 và
B6. Hai bước bày có thể dùng thuật toán để thực hiện song song với nhau.
B5 và B6 có các tác vụ chủ yếu sau:
i. Xác định tài liệu thuộc một trong 5 loại (Luật; Thông báo; Quy chuẩn; Tiêu chuẩn; Tranh chấp),
phương pháp thực hiện thủ công (đọc nội dung trong tài liệu, xác định loại của văn bản và tùy thuộc
vào nhận biết chuyên môn của con người).
ii. Làm mẫu/phiếu biên mục tài liệu, các phiếu này đã được thiết kế sẵn theo mẫu Bảng 1 và Bảng
2. Công tác điền vào mẫu là nhập thủ công thông qua chương trình máy tính. Việc nhập các giá trị
vào tùy thuộc việc áp dụng thực tiễn, ở đây bài báo đề nghị một số nguyên tắc cần phải tuân thủ.
Các nguyên tắc như sau:
o Phải ghi đầy đủ nội dung vào các sổ.
o Ngày ghi bằng số Ả Rập, tháng ghi bằng số La Mã.
o Các số vào sổ phải liên tục, không được nhảy số, có thể quay lại giá trị ban đầu là 1 tùy theo
quy định khung thời gian (thường là 1 năm).
o Nếu tên tài liệu quá dài, có thể ghi tóm lược những chữ đầu và 3 chấm, hoặc ghi những chữ
đầu + 3 chấm + những chữ cuối.
iii. Một tài liệu TBT sẽ có 8 vùng: Nhan đề [tài liệu]; Sản phẩm; Địa chỉ xuất bản (Cơ quan/Tổ
chức xuất bản); Thời gian (xuất bản; góp ý; hiệu lực); Chi tiết vật chất tài liệu (dạng/loại, dung
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
73
KHOA HỌC - ỨNG DỤNG
lượng/kích thước); Tài liệu kèm theo (tên, dung lượng/kích thước); Tóm tắt; Mã/số Ký hiệu tiêu
chuẩn.
iv. Việc phân loại tài liệu sẽ theo 2 hướng: Hướng theo Mô hình phân loại tài liệu TBT; Hướng
theo Nội dung của tài liệu TBT. Hướng theo Mô hình phân loại sẽ áp dụng Thuật toán
Xay_Dung_CSPL_Luu. Thuật toán này có một công việc quan trọng là xác định CSPL. Xác định
CSPL thực hiện theo 2 cách tiếp cận: thủ công (đọc tài liệu và dò tìm trong bảng/khung phân loại);
phát triển thuật toán.
v. Thuật toán xác định CSPL có sử dụng các thuật toán hỗ trợ: Lay_So_Chuyen_Muc();
Lay_Quoc_Gia_Khu_Vuc();
Lay_Co_Quan_To_Chuc();
Lay_Khung_Phan_Loai();
Lay_Ma_San_Pham(); Lay_Ky_Hieu(). Sáu thuật toán này sẽ được xây dựng riêng qua các phiên
bản phát triển khác nhau.
vi. Tạo thư mục, trước tiên sẽ kiểm tra thư mục thích hợp nếu đã tồn tại thì bỏ qua, nếu chưa
tồn tại thì thực thi. Phương pháp thực hiện thủ công hoặc phát triển chương trình hỗ trợ.
vii. Sao chép dữ liệu và việc sắp xếp được thực hiện song song đồng thời với nhau, đều được
thực hiện c ng với 2 phương pháp thực hiện (thủ công hoặc phát triển chương trình hỗ trợ).
Nếu bỏ qua chi phí thực hiện ở các bước B1, B2, B3, B4 thì chi phí thực hiện chỉ còn có ở B5
và B6 là 6 bước nhỏ bên trong. Chi phí thời gian thực hiện thực tế sẽ phụ thuộc vào việc triển khai
lập trình cho các bước B5 và B6.
Cho CSDL TBT có số lượng tài liệu và các bước xử lý gia tăng như sau:
Bảng 4: Số lượng tài liệu TBT và số bước thực hiện tương ứng
Số lượng
Số bước
1000
2000
4000
8000
6000 12000 24000 48000
Số lượng 16000 32000 64000
128000
Số bước 96000 192000 384000 768000
Phụ lục bảng biểu
Bảng 1: Mẫu Sổ đăng ký tổng quát
Ngày STT
Nguồn
cung cấp
Tổng số
Tựa (tiêu
Chi
phí
Nguồn
Ghi
chú
Số
đề)
bản
1
2
3
4.1
4.2
5
6.1 6.2 6.3 6.4 6.5
7
Ngày
STT
Quốc gia và tựa
Xuất bản
Chi
phí
Số vào
SĐKTQ
Phụ
chú
Cơ quan /
Năm
Tổ chức
1
2
3
4.1
4.2
5
6
7
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
74
KHOA HỌC - ỨNG DỤNG
Bảng 3: Mẫu danh mục tài liệu TBT
STT
Ngày
Chuyên mục
Quốc gia Cơ quan / Sản phẩm
Tổ chức
Số vào
SĐKTQ
Ký
hiệu
1
2
3
4
5
6
7
8
Tài liệu tham khảo
[1]. Customs Cooperation Council (WCO) (1983), Công ước Quốc tế về Hệ thống hài hòa mô tả
và mã hàng hóa (Công ước HS), Brussels.
[2]. Cao Đức Tư (2011), Nghiên cứu mô hình ngôn ngữ N-gram và ứng dụng trong bài toán
thêm dấu cho tiếng Việt không dấu”, Đại học Công nghệ thông tin, Đại học Thái Nguyên.
Standardization, Switzerland..
[4].
(2017), Nghiên cứu và xây dựng Hệ hỏi đáp thông minh
cho thông tin về Hàng rào Kỹ thuật trong Thương mại (TBT) của tỉnh Long An”, Trường Đại học
Kinh tế Công nghiệp Long An.
[5]. Trần Cao Đệ, Phạm Nguyên Khang, Phân loại văn bản với máy học vector hỗ trợ và cây
quyết định, Trường đại học Cần Thơ.
[6].Trần Thị Thu Thảo, Vũ Thị Chinh, Xây dựng hệ thống phân loại tài liệu tiếng Việt, Khoa
Công nghệ Thông tin, Trường Đại học Lạc Hồng.
: 17/10/2017
: 27/10/2017
TẠP CHÍ KINH TẾ - CÔNG NGHIỆP
75
12 trang
12/05/2022
3400
Bạn đang xem tài liệu "Xây dựng quy trình và thuật toán để phân loại tài liệu TBT", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- xay_dung_quy_trinh_va_thuat_toan_de_phan_loai_tai_lieu_tbt.pdf
