Top Ad unit 728 × 90

Latest news

recent

Khoảng cách (Distance)

Nguồn từ: Internet

Trong một lần leo núi, khi tôi trên đường đi xuống thì gặp 2 bạn trẻ đang leo lên, các bạn hỏi tôi từ đây lên đỉnh còn bao xa, tôi trả lời 400m. Đôi trẻ nghe xong cười rất tươi, tôi thì cười nguy hiểm. Thật ra con số tôi đưa ra là tính theo đường chim bay còn tính theo đường chân đi thì chắc cũng hơn 4km trầy da tróc vảy. Trả lời như vậy cốt để các bạn có tinh thần tiến lên, cậu trai có cơ hội cõng em gái xinh xắn cơ hồ đã bắt đầu thấm mệt mà thôi. Đó cũng là một minh họa cho sự nhập nhằng trong khái niệm khoảng cách. Ngoài ra khoảng cách cũng không chỉ đơn giản là độ dài đường nối điểm này tới điểm kia, là cái sự bao xa như thông thường vẫn dùng, khoảng cách còn có khoảng cách giàu nghèo, khoảng cách học vấn ... nhìn chung từ khóa khoảng cách nên được hiểu rộng hơn như là sự khác biệt (difference), hay trong vài tình huống còn được xem là lỗi (error). Sự khác biệt ấy thể hiện cũng không giống nhau tùy theo đơn vị đo, không gian, cách thức đo, tính định lượng hay ước lượng thống kê. Với tôi khoảng cách có thể xem là khái niệm cốt lỏi của nhiều các chủ đề như tìm kiếm, phân loại, nhận dạng ... bởi xét đơn giản sự tìm kiếm, muốn tìm thì phải biết cách phân biệt cái mình cần tìm với vô vàn cái mình không cần xung quanh, không có cách nào khác là phải so sánh khác biệt, hay như nhận dạng, bạn muốn nói cái mặt đó là của ông A chứ không phải ông B thì bạn cũng chả có cách nào khác ngoài phải so sánh xem cái mặt ấy khác biệt với mặt ông A, ông B như thế nào. Dưới đây tôi sẽ lần lượt trình bày vài loại khoảng cách khác nhau, sau đó tôi sẽ chỉ cho các bạn hiểu người ta ứng dụng khái niệm khoảng cách này như thế nào.

- Khoảng cách Euclidean (Euclidean Distance): Khoảng cách giữa 2 điểm là chiều dài của đường thẳng nối chúng. Trong mặt phẳng, khoảng cách giữa 2 điểm (x1, y1)  và (x2, y2) được cho bởi định lý Pythagorean như sau:
Trong không gian ba chiều Euclidean, khoảng cách giữa hai điểm (x1, y1, z1) và (x2, y2, z2) là
Một cách tổng quát, khoảng cách giữa 2 điểm x, y trong không gian Euclidean R với n chiều được tính như sau:
Ví dụ:


- Khoảng cách Hamming (Hamming Distance): Là số thay thế nhỏ nhất các thành phần, phần tử thuộc đối tượng, hệ thống, dữ liệu A để có thể trở thành B. Khi đó nó gọi là khoảng cách Hamming giữa A và B. Cũng có thể hiểu khái niệm này như một dạng của phép đo lỗi (error) hay khác biệt (difference) giữa 2 trạng thái, 2 đối tượng khác nhau.

dễ dàng nhận thấy nếu A và B là hai chuỗi nhị phân thì Hamming Distance của chúng là số giá trị 1 trong kết quả của A XOR B.

Ví dụ:

A = "hello bioz"
B = "hallo bios"

d (A, B) = 2

- Khoảng cách Manhattan (Manhattan Distance = Rectilinear Distance = City Block Distance = Taxicab Geometry = Chebyshev Distance): Khoảng cách của hai điểm P1 và P2 trong một mặt phẳng bằng chiều dài của tất cả các đoạn nối p với q dọc theo mặt cắt trục đứng và trục ngang, theo một chiều tới.

Trong hình trên đường đỏ thể hiện khoảng cách Manhattan, đường xanh nước biển và vàng tương đương với khoảng cách Manhattan, đường xanh lá cây là đường thằng hay khoảng cách Euclidean.
Một cách tổng quát, khoảng cách Manhattan của 2 điểm p và q trong không gian vector n chiều với hệ tọa độ Cartesian xác định được tính như sau:
với

- Khoảng cách Cosine (hay Cosine Similarity):  từ công thức tính tích hai vector của Euclidean như sau:


chúng ta thấy nếu cho 2 vector A và B với n chiều ta sẽ có cos(θ), cosine tương tự (Cosine Similarity) hay khoảng cách theo góc của hai vector sẽ được tính bằng công thức:



Nếu kết quả là -1, hai vector hoàn toàn đối nghịch, 1 thì hai vector giống nhau, 0 tức là hai vector vuông góc, hay trực giao.

- Khoảng cách Minkowski (Minkowski Distance): là một trường hợp tổng quát của cả khoảng cách Euclidean và khoảng cách Chebyshev, cho bởi công thức:


trong đó r gọi là thành tố Minkowski (Minkowski Factor), khi r = 1 thì d tương đương với khoảng cách Euclidean, r = 2 thì d trở thành khoảng cách Chebyshev. Với x, y là các vector đặc trưng cùng có n chiều.

Khoảng cách Mahalanobis (Mahalanobis Distance):

còn nữa ...



Binh Nguyen - Bioz
Khoảng cách (Distance) Reviewed by Bioz Nguyen on 12:08:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.