http://www.ictu.edu.vn
1

MỤC LỤC

DANH MỤC HÌNH VẼ..............................................................................................3
DANH MỤC BẢNG BIỂU..........................................................................................4
DANH MỤC TỪ VIẾT TẮT.......................................................................................5
LỜI MỞ ĐẦU..............................................................................................................6
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ.....................................8
LÝ THUYẾT TẬP THÔ..............................................................................................8
1. 1 Khai phá dữ liệu..................................................................................................................8
1.1.1 Khai phá tri thức..............................................................................................................................8
1.1.2 Khai phá dữ liệu............................................................................................................................10
1.1.2.1 Một số khía cạnh khai phá chủ yếu.......................................................................................11
1.1.2.2 Một số kỹ thuật Khai phá dữ liệu.........................................................................................12

1.2 Lý thuyết tập thô................................................................................................................16
1.2.1 Giới thiệu về tập thô......................................................................................................................16
1.2.2 Bảng quyết định.............................................................................................................................18

1.3 Kết luận chương 1...............................................................................................................20

CHƯƠNG 2. XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN ...................................22
THEO CÁCH TIẾP CẬN TẬP THÔ........................................................................22
2.1 Luật và quá trình khám phá Luật trong Bảng quyết định. ............................................22
2.1.1 Định nghĩa về luật và các đặc trưng..............................................................................................22
2.1.2. Khám phá luật bởi bảng phân bố tổng quát dựa trên tập thô và thuật toán tối ưu hoá các luật.. .23

2.2. Vấn đề rời rạc hoá dựa trên lý thuyết tập thô.................................................................24
2.2.1. Các định nghĩa..............................................................................................................................25


3.3 Phương pháp tra cứu thông tin áp dụng lý thuyết tập thô..............................................49
3.3.1 Xây dựng tập văn bản....................................................................................................................49
3.3.2 Gán trọng số cho thuật ngữ bởi dung sai xấp xỉ............................................................................49
3.3.3 Phân cụm văn bản..........................................................................................................................51
3.3.4 Biểu diễn đặc trưng các cụm.........................................................................................................52
3.3.5 Độ tương tự giữa văn bản và cụm.................................................................................................53

3.4 Kết luận chương 3...............................................................................................................53

CHƯƠNG 4. XÂY DỰNG HỆ THỐNG VÀ THỬ NGHIỆM.................................54
4.1 Môi trường và nền tảng phát triển....................................................................................54
4.2 Một số giao diện của hệ thống............................................................................................54
4.2.1 Xây dựng cơ sở dữ liệu.................................................................................................................54
4.2.2 Giao diện của hệ thống..................................................................................................................55
4.2.2.1 Phương pháp xây dựng kho dữ liệu......................................................................................55
4.2.2.2 Một số giao diện...................................................................................................................56

4.3 Kết luận chương 4...............................................................................................................57

KẾT LUẬN................................................................................................................58
TÀI LIỆU THAM KHẢO..........................................................................................59
PHỤ LỤC : DANH SÁCH CÁC TỪ DỪNG, TỪ TẦM THƯỜNG........................62

PHỤ LỤC TỪ DỪNG, TỪ TẦM
THƯỜNG..................................................64


http://www.ictu.edu.vn
3



http://www.ictu.edu.vn
5

DANH MỤC TỪ VIẾT TẮT

STT

Chữ viết tắt

Mô tả

1

KDD

Knowledge Data Development

2

CSDL

Cơ sở dữ liệu

3

SVM

Support Vector Machine

Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
phát triển trong nhiều lĩnh vực khác nhau như y tế, giáo dục, kinh tế...Đây cũng là
lĩnh vực liên quan đến nhiều ngành học như hệ cơ sở dữ liệu, trực quan hoá với
nhiều cách tiếp cận, sử dụng các kỹ thuật khác nhau như mạng nơron, lý thuyết tập
thô, biểu diễn tri thức...Nhằm mục đích tìm hiểu, nghiên cứu một phần nào đó của
việc sử dụng kỹ thuật khai phá tri thức, khai phá dữ liệu trong thực tiễn. Tôi mạnh
dạn chọn đề tài “Xây dựng tập thuộc tính rút gọn theo cách tiếp cận tập thô”, từ
đó sử dụng một thuật toán để tìm tập rút gọn phục vụ bài toán: Tra cứu thông tin.
2. Mục tiêu của đề tài
Mục tiêu của đề tài là nghiên cứu lý thuyết tập thô và tập rút gọn, từ đó áp
dụng trong Bài toán: Tra cứu thông tin trên Web.


http://www.ictu.edu.vn
7

3. Đóng góp của đề tài
Đề tài đã nghiên cứu tập thô ở khía cạnh lý thuyết áp dụng trực tiếp vào bài
toán: Tra cứu thông tin, đề tài đã có các đóng góp cụ thể sau:
- Nghiên cứu phương pháp tra cứu thông tin áp dụng lý thuyết tập thô.
- Xây dựng tập dữ liệu phục vụ cho thử nghiệm.
- Xây dựng được hệ thống tra cứu thông tin trên web áp dụng lý thuyết tập thô.
4. Bố cục của luận văn
Luận văn được bố cục thành 4 chương chi tiết như sau:
- Chương 1: Tổng quan về khai phá dữ liệu và lý thuyết tập thô.
- Chương 2: Trình bày một số phương pháp xây dựng tập thuộc tính rút gọn.
- Chương 3: Phương pháp xây dựng hệ thống tra cứu thông tin áp dụng lý
thuyết tập thô
- Chương 4: Xây dựng hệ thống và thử nghiệm.


nhiệm vụ đề ra. Vì vậy, quá trình phát hiện tri thức là một hoạt động tương tác giữa
một người sử dụng hoặc một chuyên gia phân tích với các công cụ tin học. Các
ngôn ngữ thường dùng để biểu diễn tri thức trong quá trình phát hiện tri thức từ các
cơ sở dữ liệu là các khung, các cây và đồ thị, các luật, các công thức logic mệnh


http://www.ictu.edu.vn
9

đề…Tri thức được rút ra có thể được dùng cho các mục đích cung cấp các hiểu biết
sâu sắc và hữu ích về hành vi của các đối tượng (giải thích dữ liệu) hay dự đoán giá
trị của những đối tượng mới (dự báo).
Phương pháp này thường giúp con người tạo ra các quyết định hoặc giải quyết
hiện tượng quan sát được. Tri thức ở đây có thể được hiểu là một biểu thức trong
một ngôn ngữ nào đó diễn tả một hoặc nhiều mối quan hệ giữa các thuộc tính trong
các dữ liệu đó, hay tri thức chính là các thông tin tích hợp, bao gồm các sự kiện và
các mối quan hệ giữa chúng. Vậy tri thức được xem như là dữ liệu ở mức trừu
tượng hoá và tổng quát hoá cao, còn dữ liệu là thông tin về một nhóm đối tượng nào
đó, thông thường nó được coi như là một dãy các bit, hoặc các số, các ký hiệu mang
một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định.
Quá trình khai phá tri thức nhằm mục đích rút ra được tri thức mới sau một số
bước từ những cơ sở dữ liệu trong thực tế. Tiến trình của nó bao gồm các bước
chính như sau:

Hình 1.1: Mô hình mô tả quá trình khai phá tri thức
Bước 1: Xác định và định nghĩa vấn đề:
- Tìm hiểu lĩnh vực ứng dụng và nhiệm vụ đề ra, xác định các tri thức đã có và
các mục tiêu của người sử dụng.
- Tạo và chọn lựa cơ sở dữ liệu.


Tóm lại, Data Mining là việc tiến hành xử lý, khai phá từ trong kho dữ liệu
lớn, không hoàn chỉnh, nhiều nhiễu, mơ hồ, để trích rút ra những thông tin có giá
trị, có tri thức.


http://www.ictu.edu.vn
11

Khai phá dữ liệu là quá trình tìm kiếm, khám phá dưới nhiều góc độ khác nhau
nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ kiện, đối tượng bên trong cơ
sở dữ liệu, kết quả của việc khai phá là xác định các mẫu hay các mô hình tồn tại
bên trong nhưng chúng nằm ẩn ở các cơ sở dữ liệu. Về bản chất, nó là giai đoạn duy
nhất rút trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri thức tiềm
ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn
quan trọng nhất trong quá trình phát hiện ra tri thức từ cơ sở dữ liệu, các tri thức này
hỗ trợ trong việc ra quyết định, điều hành trong khoa học và kinh doanh, nó là quá
trình rất khó khăn, gặp phải nhiều vướng mắc như: quản lý các tệp dữ liệu, phải lặp
đi lặp lại toàn bộ quá trình.
1.1.2.1 Một số khía cạnh khai phá chủ yếu
* Phân tích kết hợp (Association Analysic)
Khai phá luật kết hợp do Rakesh Apwal và cộng sự cùng đưa ra. Giá trị giữa 2
biến hoặc từ hai biến trở lên tồn tại một tính quy luật được gọi là kết hợp. Luật kết
hợp dữ liệu là một vấn đề khá quan trọng trong kho dữ liệu, để nhằm phát hiện ra tri
thức. Phân tích kết hợp được phân thành kết hợp đơn giản, kết hợp time-series và
kết hợp nhân quả. Mục đích của phân tích kết hợp là tìm ra mạng kết hợp tiềm ẩn
trong kho dữ liệu.
* Phân lớp (Clustering)
Phân lớp là căn cứ vào tính chất của dữ liệu để phân thành từng lớp khác nhau.
Trong một lớp dữ liệu có nhiều đặc tính tương thích, phân lớp là căn cứ vào các đặc
trưng khái quát của dữ liệu để phân chúng thành từng lớp khác nhau, ví dụ như căn

* Mạng neural nhân tạo (Artificial Neural Networks)
Mạng neural là một trong những kỹ thuật được ứng dụng rất phổ biến hiện
nay, nó là cách tiếp cận tính toán mới liên quan đến việc phát triển các cấu trúc toán
học dựa trên nền tảng toán học vững vàng. Các phương pháp là kết quả của việc
nghiên cứu mô hình của hệ thống thần kinh con người. Mạng neural có thể đưa ra ý
nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể sử dụng để truy xuất
các mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ
thuật máy tính khác không thể phát hiện được.
Mạng neural mô tả kết cấu của bộ não người. Cơ sở của nó là mô hình MP và
phương pháp học Hebb. Nó có 3 mô hình mạng thần kinh chính:
(1). Mạng lan truyền tiến (mô hình học không giám sát).


http://www.ictu.edu.vn
13

(2). Mạng lan truyền ngược (giống mô hình mạng Hopfield).
(3). Mạng tự tổ chức như mô hình ART, Koholon (thường dùng trong trường
hợp phân cụm, phân lớp…)
Tư tưởng của phương pháp này được bắt đầu bằng việc cho một tập dữ liệu,
gọi là tập dữ liệu huấn luyện, mạng sẽ tự động điều chỉnh (học) qua từng lớp trong
mạng và cho ra kết quả, quá trình huấn luyện được lặp đi lặp lại nhiều lần. Sau khi
mạng học thành công thì nó được xem như là một chuyên gia trong lĩnh vực thông
tin.
Mạng neural là khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có
thể phát hiện ra các xu hướng phức tạp mà các kỹ thuật thông thường khác khó có
thể phát hiện ra được. Vì vậy, phương pháp này được ứng dụng rộng rãi và áp dụng
cho rất nhiều các loại bài toán khác nhau, đáp ứng được các nhiệm vụ đặt ra của
khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo các sự kiện phụ
thuộc vào thời gian…

bao gồm mạng neural, thuật giải di truyền, hệ thống tổ kiến,…Nó được coi như một
mô hình tiến hóa cấp cao, có khả năng kháng trừ các tác nhân khác và bảo trì sự ổn
định. Các khái niệm liên quan tới AIS:miễn dịch (Immunity), kháng thể (Antibody),
kháng nguyên (Antigen), Self and Non-Self, tế bào miễn dịch, tế bào B, tế bào T…
* Cây quyết định (Decision Trees)
Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân đối tượng dữ
liệu thành một số lớp nhất định, hoặc các giá trị của các đối tượng dữ liệu chưa
được biết sẽ được dự đoán, dự báo, là phương pháp dùng trong bài toán phân đoạn
dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính.
Trong khai phá dữ liệu, kỹ thuật này là một công cụ mạnh và hiệu quả trong việc
phân lớp và dự báo. Tri thức được rút ra trong kỹ thuật này thường được mô tả dưới
dạng tường minh, đơn giản, trực quan dễ hiểu đối với người sử dụng. Tuy nhiên, nó
đòi hỏi một không gian nhất định, để mô tả tri thức trong một phạm vi mà con
người có thể hiểu được.
Cây quyết định là sử dụng những thông tin lập luận để tìm kiếm những đặc
trưng trong lượng thông tin lớn để tạo thành các điểm. Trên thực tế, người ta thường
sử dụng và ảnh hưởng nhiều nhất bởi cây quyết định do Qiulan nghiên cứu và
phương pháp ID3.


http://www.ictu.edu.vn
15

Các nút của cây được gắn nhãn là tên các thuộc tính, các lá miêu tả các lớp
khác nhau. Các đối tượng được phân theo lớp các đường đi trên cây, qua các cạnh
tương ứng với giá trị thuộc tính của đối tượng lá.

Hình 1.2: Mô tả cây quyết định
Trong hình 1.2 là cây quyết định cho việc chơi bóng đá của một số câu lạc bộ,
cho biết các câu lạc bộ sẽ thi đấu hay không thi đấu. Mỗi nút lá đại diện một lớp mà

hợp. Rõ ràng có thể tồn tại một số đối tượng giống nhau ở một số thông tin nào đó,
và ta nói rằng chúng có quan hệ không phân biệt được. Đây chính là quan hệ mấu
chốt và chính là điểm xuất phát của lý thuyết tập thô: biên giới của tập thô là không
rõ ràng, chúng ta phải xấp xỉ nó bằng các tập hợp khác, nhằm mục đích cuối cùng là
trả lời được rằng một đối tượng nào đó thuộc tập hợp hay không. Lý thuyết tập thô
với cách tiếp cận như vậy đã được ứng dụng rất rộng rãi.
1.2 Lý thuyết tập thô
1.2.1 Giới thiệu về tập thô
Khai phá tri thức là phương pháp giúp con người trích dẫn tri thức từ lượng
lớn dữ liệu, phương pháp này thường giúp con người tạo ra quyết định hoặc giải
thích các hiện tượng quan sát được. Phương pháp khai phá tri thức và công cụ khai
phá dữ liệu đang ngày càng được quan tâm và sử dụng rộng rãi trong nhiều lĩnh
vực.
Phương pháp khai phá tri thức thường được bắt đầu bằng việc lấy mẫu, chọn
lọc thuộc tính và trừu tượng hóa, biến đổi và rút gọn kích thước, trích dẫn dữ liệu,
mô hình hóa hiện tượng vật lý, thường sử dụng các thuật toán từ những giả thiết về
dữ liệu cho trước.
Có rất nhiều kỹ thuật khai phá dữ liệu, mỗi kỹ thuật có những đặc điểm riêng
phù hợp với một lớp các bài toán, với các dạng dữ liệu và miền dữ liệu nhất định.
Một trong số những kỹ thuật đó là khai phá tri thức theo cách tiếp cận tập thô.


http://www.ictu.edu.vn
17

Định nghĩa tập thô:
Cho cơ sở tri thức K= (U, ℜ), X ⊆ U, R là một quan hệ tương đương trên U.
- X là có thể xác định trên R (R–definable): Nếu X là hợp của một số các phạm trù
sơ cấp trên R, được gọi là tập xác định, ngược lại X được gọi là tập thô (tập không
xác định trên R–Undefinable).

1.2.2 Bảng quyết định
Một tập dữ liệu được thể hiện dưới dạng bảng, trong đó mỗi dòng thể hiện một
trường hợp, một sự kiện hay đơn giản là một đối tượng. Mỗi cột của bảng thể hiện
một giá trị, một quan sát, một đặc điểm…gọi chung là một thuộc tính được “quy
định” cho từng đối tượng. Ngoài ra giá trị của thuộc tính cũng có thể được cung cấp
bởi chuyên gia hay người sử dụng. Một bảng như vậy gọi là một hệ thống thông tin
(Information system).
Như vậy, bảng quyết định là một hệ thống thông tin T có dạng T = (U , C , D) , với
C ∩ D = φ ; tập thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D ,
C được gọi là tập thuộc tính điều kiện, còn D gọi là tập thuộc tính quyết định.

Và U là tập hữu hạn các đối tượng ( U ≠ φ ) được gọi là tập vũ trụ.
Trong nhiều ứng dụng thực tế, tập vũ trụ được phân chia thành các tập đối
tượng con bởi một tập các thuộc tính phân biệt được gọi là tập thuộc tính quyết
định. Hay nói cách khác, tập vũ trụ đã được phân lớp bởi thuộc tính quyết định. Hệ
thống thông tin chứa sự phân lớp này gọi là bảng quyết định.
Định nghĩa bảng quyết định:
Một cách tổng quát, bảng quyết định là một hệ thống thông tin bất kỳ có dạng:
T = (U , C , { d } ) , với d ∈ T là thuộc tính quyết định.

Các thuộc tính thuộc C được gọi là thuộc tính điều kiện.
Giả sử có T = (U , C , { d } ) và Vd = {v1 , v2 ,..., vr ( d ) } .
Thuộc tính quyết định d xác định một phân hoạch của tập tổng thể U , tại đó
X k = { x ∈ U : d ( x ) = vk } , với 1 ≤ k ≤ r ( d ) .

Tập X i được gọi là lớp quyết định thứ i của T . Và viết X d (U ) có nghĩa là có
lớp quyết định { x ∈ U : d ( x ) = d ( u )} với ∀u ∈ U .
Tổng quát hóa định nghĩa ở trên bằng dạng T = (U , C , D) , trong đó tập
D = { d1 , d 2 ,..., d k } là tập các thuộc tính quyết định và C ∩ D = φ .


Và R2 = {Đau đầu, Thân nhiệt} (thể hiện ở Bảng 1.3)
Như vậy, tập lõi là Core = {Thân nhiệt} và {Thân nhiệt} là thuộc tính cần thiết
duy nhất. Các thuộc tính {Đau đầu}, {Đau cơ} đều không cần thiết, nghĩa là từ
Bảng này nếu ta loại bỏ hai thuộc tính này thì vẫn chuẩn đoán được đúng bệnh.
Tức là:

POS {Đau cơ,Thân nhiệt}({Cảm cúm})= POS C({Cảm cúm}),
POS {Đau đầu,Thân nhiệt}({Cảm cúm})= POS C({Cảm cúm}).


http://www.ictu.edu.vn
20

Đối tượng
U
u1
u2
u3

Thuộc tính
Đau cơ
Thân nhiệt
Có
Bình thường
Có
Cao
Có
Rất cao
Có
Bình thường

Đau cơ
Có

Thuộc tính
Thân nhiệt
Bình thường

u2
u3 u6

Có
Có

Cao
Rất cao

Có
Có

u5

Không

Cao

Không

,

,


Cảm cúm
Không
Có
Có
Không
Không
Có

Bảng 1.3 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R2)
1.3 Kết luận chương 1
Nội dung của chương 1 tập trung giới thiệu và tìm hiểu về khía cạnh phát
hiện tri thức (KDD-Knowledge Data Development) nói chung và một trong các
bước quan trọng của tiến trình này đó là khai phá dữ liệu (DM-Data Mining). Đồng
thời đề cập tới một kỹ thuật nhằm khai phá dữ liệu, đó là kỹ thuật sử dụng lý thuyết
tập thô.
Kỹ thuật phát hiện tri thức và khai phá dữ liệu nhằm phát hiện những tri thức
tiềm ẩn, không biết trước, và có ích trong cơ sở dữ liệu. Đây là quá trình tự động rút


http://www.ictu.edu.vn
21

trích, tìm kiếm các “tri thức” bị che giấu trong một tập hợp “dữ liệu” rất lớn thông
qua các mẫu, mô hình trong khối dữ liệu. Quá trình khai phá tri thức thường được
áp dụng để giải quyết một loạt các yêu cầu nhằm phục vụ những mục đích nhất định
và mang tính chất hướng nhiệm vụ, không phải là phát hiện mọi tri thức mà phát
hiện những tri thức phục vụ tốt một nhiệm vụ đề ra. Và là quá trình tìm kiếm, khám
phá dưới nhiều góc độ khác nhau nhằm phát hiện các mối liên hệ, quan hệ giữa các
dữ kiện, đối tượng bên trong cơ sở dữ liệu, kết quả của việc khai phá là xác định các

Các đặc trưng của luật là độ mạnh và độ nhiễu của luật, được phát biểu:
Cho luật X → Y , độ mạnh của luật này ký hiệu là S ( X → Y ) được xác định
theo công thức:
s ( X ) (1 − r ( X → Y ) )

Với s( X ) là độ mạnh của X , s( X ) được xác định như sau:
* Trong trường hợp không sử dụng tri thức kinh nghiệm, s( X ) được tính như
sau:
S ( X ) = s( PGk ) = ∑ pbk ( PI l \ PGl ) =
l

N ins − rel ( PGk )
N PGk

Với N ins − rel ( PGk ) là số các đối tượng quan sát thỏa mãn trong lần thứ i .


http://www.ictu.edu.vn
23

* Trong trường hợp sử dụng tri thức kinh nghiệm, s( X ) được tính như sau:
S ( X ) = s( PGk ) = ∑ pbk ( PI l \ PGl ) =

∑ BKF ( PG

l

l

\ PGk )



http://www.ictu.edu.vn
24

Giả sử có bảng quyết định T = (U , C , { d } ) gồm n đối tượng và m thuộc tính, tỷ
lệ nhiễu r . Câu hỏi đặt ra là tìm tập tối ưu các luật có cùng độ mạnh?
Bước 1: Các đối tượng với các giá trị thuộc tính điều kiện giống nhau được coi
như một đối tượng gọi là đối tượng ghép.
Bước 2: Tính toán tỷ lệ nhiễu r cho mỗi đối tượng ghép.
Bước 3: Chọn một đối tượng u từ U và tạo một vector phân biệt được cho u .
Bước 4: Tìm tất cả các tập rút gọn cho đối tượng u sử dụng hàm phân biệt.
Bước 5: Tạo các luật từ tập rút gọn cho u , và xem lại độ mạnh của mỗi luật.
Bước 6: Chọn luật tốt nhất từ các luật từ Bước 5, sử dụng phương pháp đánh
giá kinh nghiệm khi lựa chọn luật.
Bước 7: U = U − { u} ;
Nếu U ≠ φ , thì quay lại bước 3, trường hợp khác thì tiếp đến bước 8.
Bước 8: Kết thúc nếu số các luật được chọn trong bước 6 cho mỗi trường hợp
là 1, trường hợp còn lại tìm một tập tối thiểu các luật mà chứa tất cả các trường hợp
trong bảng quyết định.
Độ phức tạp thời gian của thuật toán: O ( mn3 + mn 2 N ( GT ) )
với N ( GT ) là số lần sinh và nhỏ hơn O ( 2m −1 ) .
Thuật toán này là có thể không phù hợp cho cơ sở dữ liệu mà số các thuộc tính
là lớn.
Để giải quyết vấn đề này, một số các phương pháp đã được đưa ra:
- Tìm kiếm tập rút gọn (tập con) của các thuộc tính điều kiện trong quá trình
tiền xử lý.
- Tìm giải pháp gần tối ưu sử dụng phương pháp tìm kiếm kinh nghiệm hiệu
quả.
2.2. Vấn đề rời rạc hoá dựa trên lý thuyết tập thô

Trong đó: D = { d1 , d 2 ,..., d k } ; U = { x1 , x2 ,..., xn } , và d : U → {1,2,...r} .
Giả sử Va = [ la , ra ] ⊆ R với ∀a ∈ T
Tiến hành chia Va thành các khoảng con, và ký hiệu là Pa

{[

)[

) [

Pa = c0a , c1a , c1a , c2a ,..., cka , cka+1

với: k a là một số nguyên.
la = c0a < c1a < ... < cka < cka+1 ;

)}