Chào mừng đến với BIS Đăng nhập | Đăng ký | Trợ giúp
trong Tìm kiếm

Thuật toán K láng giềng gần nhất

Bài cuối 10-26-2018 11:14 AM của nguyenvanhieu. 9 trả lời.
Trang 1 trong số 1 (10 nội dung)
Sắp xếp bài viết: Trước Tiếp theo
  • 11-13-2010 09:57 PM

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 10,000

    Thuật toán K láng giềng gần nhất

    Thuật toán K – Láng giềng gần nhất (K-Nearest Neighbors)

    Nguyễn Văn Chức – chuc.nv@due.edu.vn

    1. Giới thiệu thuật toán K-Nearest Neighbors

    K-Nearest Neighbors algorithm (K-NN) được sử dụng rất phổ biến trong lĩnh vực Data Mining. K-NN là phương pháp để phân lớp các đối tượng dựa vào khoảng cách gần nhất giữa đối tượng cần xếp lớp (Query point) và tất cả các đối tượng trong Training Data.

    Một đối tượng được phân lớp dựa vào K láng giềng của nó. K là số nguyên dương được xác định trước khi thực hiện thuật toán. Người ta thường dùng khoảng cách Euclidean để tính khoảng cách giữa các đối tượng.

    Thuật toán K-NN được mô tả như sau:

    1.    Xác định giá trị tham số K (số láng giềng gần nhất)

    2.    Tính khoảng cách giữa đối tượng cần phân lớp (Query Point) với tất cả các đối tượng trong training data (thường sử dụng khoảng các Euclidean)

    3.    Sắp xếp khoảng cách theo thứ tự tăng dần và xác định K láng giềng gần nhất với Query Point

    4.    Lấy tất cả các lớp của K láng giềng gần nhất đã xác định

    5.    Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho Query Point

    Để hiểu K-NN được dùng để phân lớp thế nào ta xem minh họa dưới đây.

    Trong hình dưới đây, training Data được mô tả bởi dấu (+) và dấu (-), đối tượng cần được xác định lớp cho nó (Query point) là hình tròn đỏ. Nhiệm vụ của chúng ta là ước lượng (hay dự đoán) lớp của Query point dựa vào việc lựa chọn số láng giềng gần nhất với nó. Nói cách khác chúng ta muốn biết liệu Query Point sẽ được phân vào lớp (+) hay lớp (-)

    Ta thấy rằng:

    1-Nearest neighbor : Kết quả là + (Query Point được xếp vào lớp dấu +)

    2-Nearest neighbors : không xác định lớp cho Query Point vì số láng giềng gần nhất với nó là 2 trong đó 1 là lớp + và 1 là lớp – (không có lớp nào có số đối tượng nhiều hơn lớp kia)

    5-Nearest neighbors : Kết quả là - (Query Point được xếp vào lớp dấu – vì trong 5 láng giềng gần nhất với nó thì có 3 đối tượng thuộc lớp - nhiều hơn lớp + chỉ có 2 đối tượng).

    2. Triển khai thuật toán K-NN với MS Excel

    Giả sử ta có dữ liệu như sau:

    Training Data gồm có 20 samples, mỗi đối tượng có 2 thuộc tính số (X1, X2) và thuộc tính Y là lớp của các đối tượng (ký hiệu + và -)

    Đối tượng cần dự đoán lớp (Query Point) có giá trị của 2 thuộc tính X1 và X2 lần lượt là 7 và 5

    Nhiệm vụ của chúng ta là sử dụng thuật toán K-NN để xác đinh lớp cho đối tượng (X1,X2) =(7,5) thuộc lớp + hay - dựa vào số láng giềng gần nhất của nó.

    Giải thích công thức trong Excel:

    Công thức tính khoảng cách (Euclidean) tại ô G2:

    =SQRT((C2-$C$22)^2+(D2-$D$22)^2)

    Xác định số láng giềng gần nhất (ô H23): K= 5

    Chọn ra  K láng giềng gần nhất của Query point (công thức tại ô H2)

    =IF(G2<=SMALL($G$2:$G$21,$H$23),E2,"")

    Dự đoán lớp của Query Point (ô H24). Trong ví dụ này lớp của Query point (7,5) được xác định là vì trong 5 láng giềng gần nhất với nó có 3 láng giềng thuộc lớp – (nhiều hơn số láng giềng thuộc lớp +)

    =IF(COUNTIF(H2:H21,"+")>COUNTIF(H2:H21,"-"),"+","-")

    Chú ý: Bạn có thể thay đổi dữ liệu về số láng giềng K ở ô H23 cũng như thay đổi training data hay Query Point để kiểm tra kết quả của thuật toán K-NN

    Trường hợp ứng dụng K-NN:

    Giả sử rằng  trong ứng dụng thực tế, thuộc tính X1: huyết áp, thuộc tính X2: nồng độ Cholesterol trong máu và Y thể hiện  tình trạng bệnh tim của bệnh nhân. Y có hai giá trị là + (có bệnh) và - (không có bệnh).

    Ta có dữ liệu về 20 người đã khám bệnh và kết quả như bảng sau (Training data, dữ liệu chỉ mang tính minh họa cho thuật toán K-NN)

    Bây giờ có một người bệnh đến khám bệnh (chưa biết có bị bệnh tim hay không), sau khi đo huyết áp và nồng độ Cholesterol có giá trị lần lượt là X1= 7 và X2= 5. Ta sử dụng thuật toán K-NN  để dự đoán (xếp lớp) bệnh nhân này có mắc bệnh tim hay không.  Trong ví dụ trên tham số k =5 có nghĩa là lấy 5 bệnh nhân có huyết áp và nồng độ Cholesterol gần  giống nhất với bệnh cần chuẩn đoán và ta thấy rằng trong 5 bệnh nhân gần nhất đó có 3 người không mắc bệnh tim (giá trị Y là -) và 2 người mắc bệnh tim (giá trị Y là +). Vì vậy theo K-NN ta xếp bệnh nhân cần chuẩn đoán bệnh vào lớp – (không bị bệnh tim)


     3. Triển khai thuật toán K-NN  với phần mềm Weka

    Phần này trình bày triển khai thuật toán K-NN với phần mềm WeKa

    Dữ liệu dùng để phân lớp trong ví dụ này là bộ dữ liệu về hoa Iris (xem mô tả về Iris dataset trong bài Building a Classification Model with Weka)

     

     


     Thuật toán K-NN có ưu điểm là đơn giản, dễ hiểu, dễ cài đặt. Tuy nhiên, kết quả bài toán phụ thuộc rất lớn vào việc chọn tham số K (số láng giềng gần nhất).

     

    Next Topic: Clustering Techniques. All comments please send to chucnv@ud.edu.vn

    • Điểm chủ đề: 95
  • 11-16-2010 10:03 AM trả lời

    Re: K-Nearest Neighbors Algorithm

    Cảm ơn anh Chức. Quả thực em đã đọc tài liệu về KNN nhưng hiểu không được sâu cho đến khi đọc bài viết của anh.
    Chúc anh luôn mạnh khỏe và viết nhiều bài về Data Mining nữa nhé. (hi hi)

     
    • Điểm chủ đề: 20
  • 06-06-2011 12:14 AM trả lời

    Re: K-Nearest Neighbors Algorithm

    em chào anh, 
    Nhờ các bài viết của Anh mà em hiểu hơn về Data mining,
    Anh có thể mô tả giúp em quy trinh thưc hiện được yêu cầu:
     Chuyển doccument sang vector và sử dụng thước đo cosine được không a?
    Từ khóa đại diện:
    • Điểm chủ đề: 35
  • 06-06-2011 10:42 AM trả lời

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 10,000

    Re: K-Nearest Neighbors Algorithm

    Chào em,
    Việc biểu diễn một document bằng một Term vector thực hiện theo qui trình sau:
    Loại bỏ các Stop word (sử dụng StopList)
    Chuyển các từ về dạng nguyên thể (Term Stems)
    Trích các term từ Document (Extracting Term) và tính tần suất (Term frequency)
    Đánh trọng số (weight) các term để loại đi các term không liên quan nhiều đến documents (thường sử dụng tf-idf) 
    Sử dụng một số công thức để đánh giá độ tương tự (Similar) giữa các Document dựa trên Term Vector
    Công thức Cosin dùng để xác định độ tương tự giữa 2 documents đó là góc giữa 2 documents đó như sau:
     

     
     Hình trên cho thấy document Q tương tự (similar) với document D2 hơn là với D1 vì góc giữa Q và D2 nhỏ hơn góc giữa Q và D1.
    Em có thể xem thêm qui trình chuyển một Document sang term Vector tại bài viết : 
    http://bis.net.vn/forums/t/469.aspx
    Chúc em thành công,
    • Điểm chủ đề: 50
  • 04-10-2013 08:57 PM trả lời

    • ngoclinh
    • 500 thành viên năng nổ nhất
    • Tham gia 04-10-2013
    • Điểm 20

    Re: Thuật toán K láng giềng gần nhất

    Em chào anh,
    Em thực sự rất mừng khi tìm được diễn đàn về BI và Data Mining này. Qua các bài viết của anh em đã có cái nhìn thực tế hơn về Data Mining.
    Em hiện đang tìm đề tài để làm tốt nghiệp cao học về Data Mining, rất mong anh tư vấn giúp em về lĩnh vực này để chọn đề tài. Thầy giáo HD em định hướng ứng dụng Data Mining trong phân tích hành vi đầu tư chứng khoán mà em chua biết cụ thể như thế nào, có thể sử dụng thuật toán nào trong Data Mining. 
    Mong anh tư vấn giúp em với, em cảm ơn anh nhiều.
     Chân thành cảm ơn anh trước.
     
    • Điểm chủ đề: 20
  • 01-15-2015 04:30 PM trả lời

    Re: Thuật toán K láng giềng gần nhất

    Anh ơi, anh cho em hỏi chút với ah,  K-NN là thuật toán thuộc học có giám sát đúng ko anh?
    • Điểm chủ đề: 35
  • 05-29-2018 11:32 PM trả lời

    • hoang
    • Không xếp hạng
    • Tham gia 05-29-2018
    • Điểm 20

    Re: K-Nearest Neighbors Algorithm

    em chào anh. KNN có được coi là một mạng nơ-ron nhân tạo không anh??? anh ơi theo như trên thì dựa vào thuật toán kNN mình hoàn toàn có thể so sánh, đối chiếu giữa hai văn bản giống như phần mềm ("text compare"). mà cũng có thể phát hiện đạo văn nếu ứng dụng kNN vào xử lý văn bản đúng không ạ. 
    và nếu hướng đi này khả quan thì anh cho em hỏi anh có code nguồn không (hoặc link chứa code nguồn) chỉ giùm em. em cảm ơn anh nhiều ạ!!! 
    • Điểm chủ đề: 20
  • 06-21-2018 03:56 PM trả lời

    Re: Thuật toán K láng giềng gần nhất

    Vậy thì để đánh giá mô hình phân loại co phù hợp với dữ liệu không thì làm sao vậy anh. Em có tìm hiểu một vài chỉ số đánh giá nhưng không hiểu. Ví dụ như chỉ số ARI, anh có thể giải thích giúp em được không ạ.
    • Điểm chủ đề: 20
  • 08-10-2018 04:12 PM trả lời

    Re: Thuật toán K láng giềng gần nhất

    Thuật toán học có giám sát là thuật toán mà với dữ liệu đầu vào cần phải biết được kết quả đầu ra (ví dụ bài toán gán nhãn thì với dữ liệu đầu vào để học thì đã được gán nhán). Như vậy ứng với khái niệm này thì Thuật toán K láng giềng gần nhất là thuật toán học có giám sát.
    https://trituenhantao.info
    http://tukyonline.com
    • Điểm chủ đề: 20
  • 10-26-2018 11:14 AM trả lời

    Re: K-Nearest Neighbors Algorithm

    Cảm ơn bài chia sẻ hữu ích của bạn.
    Founder at Blog tự học lập trình Nguyenvanhieu.vn
    • Điểm chủ đề: 20
Trang 1 trong số 1 (10 nội dung)
Powered by Community Server (Commercial Edition), by Telligent Systems