ThienThanCNTT
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Kỹ thuật phân lớp dữ liệu trong Data Mining

Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Kỹ thuật phân lớp dữ liệu trong Data Mining

Bài gửi by nth 27/04/10, 09:26 pm

Giới thiệu về phân lớp

Phân lớp dữ liệu là kĩ thuật dựa trên tập huấn luyện và những giá trị hay hay là nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới . Phân lớp cũng là tiên đoán loại lớp của nhãn . Bên cạnh kĩ thuật phân lớp có một hình thức tương tự là kĩ thuật tiên đoán , kĩ thuật tiên đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kĩ thuật tiên đoán mô hình những hàm đánh giá liên tục .
Kĩ thuật phân lớp được tiến hành bao gồm 2 bước : Xây dựng mô hình và sử dụng mô hình .
Xây dựng mô hình : là mô tả một tập những lớp được định nghĩa trước trong đó : mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được xát định bởi thuộc tính nhãn lớp , tập hợp của những bộ được sử dụng trong việc sử dụng mô hình được gọi là tập huấn luyện . Mô hình được biểu diễn là những luật phân lớp , cây quyết định và những công thức toán học .
Sử dụng mô hình : Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến . Trước khi sử dụng mô hình người ta thường phải đánh giá tính chính xát của mô hình trong đó : nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp của mô hình , độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình , tập kiểm tra là độc lập với tập huấn luyện .
Phân lớp là một hình thức học được giám sát tức là : tập dữ liệu huấn luyện ( quan sát , thẩm định ...) đi đôi với những nhãn chỉ định lớp quan sát , những dữ liệu mới được phân lớp dựa trên tập huấn luyện .
Ngược lại với hình thức học được giám sát là hình thức học không được giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không được biết đến
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty 2.Phân lớp bằng phương pháp qui nạp cây quyết định

Bài gửi by nth 27/04/10, 09:30 pm

Khái niệm cây quyết định :

Cây quyết định là một flow-chart giống cấu trúc cây , nút bên trong biểu thị một kiểm tra trên một thuộc tính , nhánh biểu diễn đầu ra của kiểm tra , nút lá biểu diễn nhãn lớp hoặc sự phân bố của lớp .

Việc tạo cây quyết định bao gồm 2 giai đoạn : Tạo cây và tỉa cây .

Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện là ở gốc sau đó phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính được chọn .
Việc tỉa cây là xát định và xóa những nhánh mà có phần tử hỗn loạn hoặc những phần tử nằm ngoài (những phần tử không thể phân vào một lớp nào đó) .

Việc sử dụng cây quyết định như sau : Kiểm tra những giá trị thuộc tính của mẫu đối với cây quyết định .

Thuật toán qui nạp cây quyết định :
Giải thuật cơ bản (giải thuật tham lam) được chia thành các bước như sau:

1. Cây được xây dựng đệ qui từ trên xuống dưới (top-down) và theo cách thức chia để trị (divide-conquer).

2. Ở thời điểm bắt đầu , tất cả những ví dụ huấn luyện ở gốc .

3. Thuộc tính được phân loại ( nếu là giá trị liên tục chúng được rời rạc hóa)

4. Những ví dụ huấn luyện được phân chia đệ qui dựa trên thuộc tính mà nó chọn lựa .

5. Kiểm tra những thuộc tính được chọn dựa trên nền tảng của heristic hoặc của một định lượng thống kê .


Điều kiện để dừng việc phân chia :

1.Tất cả những mẫu huấn luyện đối với một node cho trước thuộc về cùng một lớp.

2.Không còn thuộc tính còn lại nào để phân chia tiếp .

3.Không còn mẫu nào còn lại .

Độ lợi thông tin (Information Gain) trong cây quyết định :
Information gain là đại lượng được sử dụng để chọn lựa thuộc tính với information gain lớn nhất .Giả sử có hai lớp , P và N . Cho tập hợp của những ví dụ S chứa p phần tử của lớp P và n phần tử của lớp N . Khối lượng của thông tin , cần để quyết định nếu những mẫu tùy ý trong S thuộc về P hoặc N được định nghĩa như là :

I(p,n) = -[p/(p+n)]log 2 [p/(p+n)] – [n/(p+n)]log 2 [n/(p+n)]

Giả sử rằng sử dụng thuộc tính A một tập hợp S được phân hoạch thành những tập hợp {S1,S2,..,Sv} . Nếu Si chứa những mẫu của P và ni mẫu của Ni entropy hoặc thông tin mong đợi cần để phân loại những đối tượng trong cây con Si là :

v
E(A) = Σ [(pi+ni)/(p+n)] I(pi,ni)
i=1

Thông tin nhận được ở nhánh A là : Gain(A) = I(p,n)-E(A)
Nội dung giải thuật học cây quyết định cơ bản ID3 :
ID3 là một giải thuật học cây quyết định được phát triển bởi Ross Quinlan (1983). Ý tưởng cơ bản của giải thuật ID3 là để xây dựng cây quyết định bằng việc sử dụng một cách tìm kiếm từ trên xuống trên những tập hợp cho trước để kiểm tra mỗi thuộc tính tại mỗi nút của cây . Để chọn ra thuộc tính mà hữu ích nhất cho sự phân loại trên những tập hợp cho trước , chúng ta sẽ đưa ra một hệ đo độ lợi thông tin.
Để tìm ra một cách tối ưu để phân loại một tập hợp thông tin , vấn đề đặt ra là chúng ta cần phải làm tối thiểu hóa ( Chẳng hạn, tối thiểu chiều cao của cây). Như vậy chúng ta cần một số chức năng mà có thể đánh giá trường hợp nào nào cho ra một sự phân chia cân bằng nhất . Hệ đo độ lợi thông tin sẽ là hàm như vậy.

ID3 ( Learning Sets S, Attributes Sets A, Attributesvalues V)
Return Decision Tree.
Begin
Đầu tiên nạp learning sets , tạo nút gốc cho cây quyết định 'rootNode', thêm learning set S vào trong nút gốc như là tập con của nó.
For rootNode, đầu tiên chúng ta tính
Entropy(rootNode.subset)
If Entropy(rootNode.subset)==0, then
rootNode.subset bao gồm records
tất cả với cùng giá trị cho cùng giá trị thuộc tính xát định, trả về một nút lá với decision attribute:attribute value;
If Entropy(rootNode.subset)!=0, then
tính độ lợi thông tin (information gain) cho mỗi thuộc tính trái (chưa được sử dụng để phân chia), tìm thuộc tính A với
Maximum(Gain(S,A)). Tạo những nút con của rootNode này và thêm vào rootNode trong cây quyết định.
For mỗi con của rootNode, áp dụng
ID3(S,A,V) một cách đệ qui cho đến khi đạt được
node mà có entropy=0 hay đạt được nút lá.
End ID3.
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Những thiếu sót của giải thuật ID3:

Bài gửi by nth 27/04/10, 09:31 pm

Trường hợp thiếu sót thứ nhất :

Một thiếu sót quan trọng của ID3 là không gian phân chia hợp lệ tại một node là cạn kiệt . Một sự phân chia là sự phân hoạch của mỗi trường hợp của không gian mà kết quả đạt được từ việc thử nghiệm tại một node quyết định ID3 và con cháu của nó cho phép sự kiểm tra tại tại một thuộc tính đơn và nhánh trong kết quả cho ra từ sự kiểm tra này.

Trường hợp thiếu sót thứ hai :

Một thiếu sót mà ID3 mắc phải là nó dựa vào rất nhiều vào số lượng của những tập hợp dữ liệu đưa vào. Quản lý sự tạp nhiễu của tập dữ liệu vào là vô cùng quan trọng khi chúng ta ứng dụng giải thuật học cây quyết định vào thế giới thực .Cho ví dụ , khi có sự lẫn tạp trong tập dữ liệu đưa vào hoặc khi số lượng ví dụ đưa vào là quá nhỏ để tạo ra một ví dụ điển hình của hàm mục tiêu đúng . ID3 có thể dẫn đến việc tạo quyết định sai.

Có rất nhiều những mở rộng từ giải thuật ID3 cơ bản đã phát triển để áp dụng những luật học cây quyết định vào thế giới thực , như là những post-pruning tree , quản lý những thuộc tính giá trị thực , liên quan đến việc thiếu những thuộc tính , sử dụng những tiêu chuẩn chọn lựa thuộc tính khác hơn thu thập thông tin .
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Mở rộng qui nạp cây quyết định cơ bản

Bài gửi by nth 27/04/10, 09:33 pm

Việc mở rộng qui nạp cây quyết định được áp dụng cho những thuộc tính giá trị liên tục : Định nghĩa một cách uyển chuyển những thuộc tính giá trị bị rời rạc mà sự phân chia giá trị thuộc tính thành một tập rời rạc của những khoảng .

Mở rộng qui nạp cây quyết định cũng được áp dụng cho những giá trị thuộc tính thiếu sót bằng cách : Gán những giá trị thiếu sót bằng giá trị thông thường nhất của thuộc tính hoặc gán khả năng có thể với mỗi giá trị có thể .

Việc mở rộng qui nạp cây quyết định cũng được áp dụng cho xây dựng thuộc tính : Tạo những thuộc tính dựa trên những cái đã tồn tại mà chúng thể hiện thưa thớt . Điều này sẽ giúp thu giảm việc phân mảnh , sự lặp lại và việc tạo bản sao .
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Thu giảm cây quyết định và những tập luật suy dẫn :

Bài gửi by nth 27/04/10, 09:37 pm

Việc xây dựng cây quyết định nhờ vào training set bởi vì cách chúng xây dựng liên quan nghiêm ngặt đến hầu hết các record trong tập huấn luyện .Trong thực tế , để làm như vậy nó có thể là điều hoàn toàn phức tạp. Với những đường đi dài và không đều .

Việc thu giảm cây quyết định được thực hiện bằng việc thay thế những cây con thành những nút lá.Sự thay thế này sẽ được thực hiện tại nơi mà luật quyết định được thiết lập nếu tần suất lỗi gây ra trong cây con là lớn hơn trong một nút lá.Cho ví dụ với cây đơn giản như sau:

Color -> red -> Success

->blue -> Failure

chứa 2 records thứ nhất là training red success và thứ hai là trainning blue failures và sau đó trong Test Set chúng ta tìm thấy 3 red failures và một blue success , chúng ta có thể xem xét việc thay thế cây con này bằng việc thay thế bằng một node đơn Failure . Sau việc thay thế này chúng ta sẽ còn lại 2 lỗi thay vì 5 lỗi .

Winston chỉ ra rằng làm thế nào để sử dụng Fisher's exact test để xát định nếu thuộc tính phân loại là thực sự phụ thuộc vào một thuộc tính không xát định. Nếu điều này không sãy ra thì thuộc tính không xát định không cần phải xuất hiện trong đường đi hiện tại của cây quyết định.

Quinlan và Breiman đề nghị những heuristic phức tạp hơn cho việc thu giảm cây quyết định .Một điều dễ dàng làm là có thể dẫn ra một luật từ một cây quyết định : viết ra một luật từ mỗi đường trong cây quyết định đi từ gốc đến lá.Vế trái của luật được xây dựng dễ dàng từ nhãn của những nút và nhãn của những cung.

Những luật rút ra có thể được rút gọn như sau:

Gọi LHS là LHS của luật Cho LHS’ nhận được bằng cách thu giảm một số điều kiện của LHS. Chúng ta có thể chắc chắn thay thế LHS bằng LHS’ trong luật này nếu tập con của training set thỏa mãn LHS và LHS’ là tương đương.
Một luật có thể được thu giảm bằng cách sử dụng metacondition ví dụ như “ không có luật khác có thể áp dụng ”.

P/S: Thông cảm nha, bài mình viết bằng tay nên còn nhìu sai sót, mọi người đọc góp ý nhé.
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Tránh việc quá khít (overfitting) trong việc phân lớp

Bài gửi by nth 27/04/10, 09:41 pm

Cây được tạo ra có thể quá khít với dữ liệu huấn luyện . Việc quá khít có thể sãy ra trong những trường hợp sau đây :

Quá nhiều những nhánh , một số có thể phản ánh sự dị thường vì những phần tử hỗn loạn (noise) hoặc những phần tử nằm ngoài phân lớp (outlier) .
Kết quả nhận được thiếu chính xát đối với những mẫu chưa thấy.

Có hai cách tiếp cận để tránh quá khít dữ liệu .

Tỉa trước : Dừng sự xây dựng của cây sớm – không chia một node nếu điều này tạo kết quả ở dưới một ngưỡng theo một hệ đánh giá tốt . Một khó khăn trong việc tỉa trước là điều này sẽ tạo ra sự khó khăn trong việc tạo ra một ngưỡng thích hợp .
Tỉa sau : Loại những nhánh từ một cây “ lớn đầy đủ “ - tạo một thứ tự của những cây bị tỉa tăng dần lên trong đó ta sử dụng một tập dữ liệu khác nhau từ dữ liệu huấn luyện để xát định cái nào là “cây được tỉa tốt nhất “ (best pruned tree).

Tiếp cận xát định kích cỡ cây cuối cùng :

Thông thường người ta phân chia tập huấn luyện thành tập dữ liệu huấn luyện (2/3) và dữ liệu thử (1/3) , người ta sử dụng sự đánh giá chéo .
Cũng có một cách khác là sử dụng tất cả dữ liệu để huấn luyện , nhưng áp dụng kiểm tra thống kê để định lượng khi nào mở rộng hoặc tỉa bớt một nút có thể cải thiện toàn bộ sự phân phối .

Một cách thứ ba là sử dụng nguyên tắc mô tả chiều dài tối thiểu : trong đó người ta dừng sự phát triển của cây khi sự mã hóa được tối thiểu .
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Sự phân lớp cây quyết định trong cơ sở dữ liệu lớn

Bài gửi by nth 27/04/10, 09:42 pm

Sự phân lớp là một vấn đề cổ điển được nguyên cứu một cách mở rộng bởi những nhà thống kê và những nhà nguyên cứu máy học .Hướng phát triển hiện nay là của việc phân lớp là phân lớp những tập dữ liệu với hàng tỉ những mẫu thử và hàng trăm thuộc tính với tốc độ vừa phải.

Qui nạp cây quyết định được đánh giá cao trong khai phá dữ liệu lớn vì những nguyên nhân sau :
 Tốc độ học tương đối nhanh hơn so với những phương pháp phân loại khác .
 Có thể hoán chuyển được thành những luật phân lớp đơn giản và dễ hiểu .
 Có thể sử dụng truy vấn SQL để truy xuất cơ sở dữ liệu .
 Sự chính xát phân lớp có thể so sánh được với những phương pháp khác .
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Một số lưu ý khi tạo cây quyết định trong Microsoft SQL Server 2008

Bài gửi by nth 27/04/10, 10:08 pm

Dùng Microsoft Analysis services trong SQl 2008 nhé.

Mình chỉ ghi giải thích một vài thứ còn chưa rõ thôi.
Còn input database thì tự làm nha.

Mining Mode Wizard : sản phẩm của Microsoft đi đôi với những tác vụ trong một giới hạn và có thể tiên đoán một số bước . Mining mode wizard sẽ dẫn dắt chúng ta từng bước để tạo một mô hình .

1. Chọn nguồn (Select source).
2. Chọn case table hoặc những bảng cho mô hình khai phá dữ liệu .
3. Chọn kĩ thuật khai phá dữ liệu (giải thuật) .
4. Hiệu chỉnh những kết nối của những bảng được chọn như là nguồn trong những bước trước .
5. Chọn cột Case Key .
6. Chọn Input và cột tiên đoán .
7. Kết thúc .

Select Source :
Ta phải chọn việc tạo mô hình khai phá dữ liệu mà chứa những trường hợp đặt ở bảng quan hệ hoặc OLAP cubes .
Select case tables :
Kết nối được sử dụng với mô hình quan hệ được tạo ra và hiển thị trong màn Select Case Table . Ở đây cũng cung cấp một tùy chọn của việc tạo ra một kết nối mới bằng việc kích lên một Data Source mới .

Chọn một kỹ thuật khai phá dữ liệu :
Mining Model Wizard cung cấp hai giải thuật khai phá dữ liệu , hoặc "kĩ thuật" như chúng ta gọi trong wizard mà chúng ta chọn từ đó . Với mục đích đó , chúng ta chọn Microsoft Decision Tree trong màn hình Select Data Mining Techniques .

Tạo và hiệu chỉnh những kết nối : Nếu ta chọn nhiều bảng trong các bước trước sau đó màn hình tạo và hiệu chỉnh những kết nối sẽ hiển thị tiếp theo . Màn hình này sẽ cho phép ta đồ họa hóa những bản kết nối bằng việc kéo những cột từ những bảng cha vào con của nó . Nếu bạn chọn chỉ một bảng đơn thì bước này bị bỏ qua .

Chọn khóa của cột : Bước kế tiếp là chọn ID như là Case Key column . Sự chọn lựa của ID có một ảnh hưởng quan trọng lên đầu ra của quyết định bởi vì Key là công cụ để xát định sự duy nhất của một record.

Chọn lựa một khóa là điều bắt buột , do đó nó rất quan trọng để tạo một khóa trong SQL Server database nếu một cái chưa tồn tại .

Chọn input và tiên đoán cột : Trên màn hình tiên đoán và chọn cột , lấy ít nhất một cột cho mô hình khai phá từ một cột cho phép trong danh sách trên cửa sổ bên trái . Mô hình Input column thể hiện dữ liệu thực sự mà đựơc sử dụng để huấn luyện mô hình khai phá dữ liệu . Nếu bạn chọn Microsoft Decision Trees trong Select Case Tables screen , và cũng chọn ít nhất một cột tiên đoán .

Available columns : Chọn cột từ tree view . Sử dụng button được cung cấp để chuyển những cột về cả cửa sổ Predictable Column hoặc cửa sổ Input Column để loại bỏ những cột từ sự chọn lựa . Ta không thể sử dụng ID Column ta đã chọn trong Select Key Column dialog box như là một Input column bởi vì nó là khóa .

Predictable columns : Xem những cột được chọn lựa có thể tiên đoán được . Cửa sổ này chỉ được hiển thị chỉ nếu bạn lựa chọn Microsoft Decision Tree trong Select Case Tables dialog box .

Input columns : Xem selected input columns .

Kết thúc :
Cuối cùng những thông số mô hình khai phá dữ liệu được định nghĩa , ta phải nhập tên của mô hình khai phá dữ liệu .

Trình soạn thảo mô hình khai phá quan hệ :
Tiện dụng như wizard là những ứng dụng , chúng không giới hạn sự uyển chuyển trong mỗi bước bởi vì để quản lý đơn giản , wizard phải sử dụng những giá trị mặc định và những quyết định tường minh để hoàn thành một tác vụ . Bằng việc sử dụng Relational Mining Model Editor , ta có thể bỏ qua wizard .

Trực quan mô hình :
Một trong những đặc điểm có giá trị nhất của cây quyết định là sự đơn giản của logic bên trong cấu trúc của nó .Data Mining Model Editor chứa hai tabs ở đáy màn hình , lược đồ tab , mà được sử dụng để thay đổi cấu trúc của mô hình và Content tab là nơi hiển thị dữ liệu được phân loại và được tổ chức thành cây.
Content tab là cách nhanh và tiện lợi để xem mô hình , những cấu trúc và thuộc tính .

Dependency Network Browser :
Dependency Network Browser là công cụ được sử dụng để xem những sự độc lập và những mối quan hệ giữa những đối tượng trong mô hình khai phá dữ liệu . Để hiển thị nó từ cửa sổ Analysis Manager Tree , kích chuột phải một mô hình khai phá dữ liệu và sau đó chọn Browser Dependency Network .

Trong Dependency Network Browser , một mô hình khai phá dữ liệu được thể hiện như là một mạng của những thuộc tính . Bên trong mô hình , chúng ta có thể xát định dữ liệu độc lập và tiên đoán trong những thuộc tính quan hệ . Sự phụ thuộc được thể hiện bởi những mũi tên . Hướng của sự tiên đoán được chỉ định bởi arrowhead và bởi color-coding của những notes .

Bên trong giải thuật cây quyết định :
Giống như tên của chúng , giải thuật cây quyết định là mô hình dạng cây . Không có giới hạn cho cấp độ và những đầu vào và những biến được gán vào giải thuật , cây càng lớn - càng rộng và càng sâu hơn .
nth
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 35
Đến từ : Thiên Đường

https://thuhuong.forumvi.net

Về Đầu Trang Go down

Kỹ thuật phân lớp dữ liệu trong Data Mining Empty Re: Kỹ thuật phân lớp dữ liệu trong Data Mining

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết