multibooks - tổng hợp it - pc part 22

giáo trình multibooks - tổng hợp it. bài giảng multimedia, cẩm nang microsoft office word 2007, ubuntu, kĩ nghệ đóng gói sotfs, python, the openbsd 4.0 crash course (2007), w7, wvista. bao gồm hệ thống các bài giảng, tips - sẽ hướng dẫn các bạn cụ thể, hiệu quả về các vấn đề trong chương trình mà cập nhật tới. Đây sẽ là 1 quyển sách cần thiết đối với các bạn mún theo môn học này.
Nội dung trích xuất từ tài liệu:
multibooks - tổng hợp it - pc part 22 Giả sử di và dj là hai tài liệu. Tính tương tự của hai tài liệu theo biểu diễn SVD TS* x D*T của bảng tần số được cho bởi giá trị tích vô hướng hai cột trong ma trận D*T kết hợp với hai tài liệu đó: Ở đây ma trận đơn sau khi rút gọn sẽ có kích thước (R x R). Chú ý rằng thay vì so sánh toàn bộ M khái niệm cho hai tài liệu này, ta chỉ so sánh R khái niệm, nó là số nhỏ hơn M rất nhiều (thông thường là 200). Tìm kiếm phù hợp p đầu tiên cho truy vấn Q Giả sử Q là truy vấn. Ta coi Q như tài liệu và tạo lập véctơ vecQ cho nó như trên đây. Tuy nhiên, có một điểm khác là: Chỉ R khái niệm quan trọng là được xem xét chứ không phải xem xét tất cả N. Khi được hỏi để tìm ra p khái niệm phù hợp nhất với Q, ta sẽ phải tìm p tài liệu da(1), ...,da(p) như sau: 1. Với mọi 1 £ i £ j £ p, tính tương tự giữa vecQ và da(i) lớn hơn hay bằng tính tương tự giữa vecQ và da(j) , và 2. không có tài liệu dz nào mà tính tương tự giữa dz và vecQ vượt quá tính tương tự của da(p) Điều này có thể thực hiện bằng sử dụng bất kỳ cấu trúc chỉ số hoá nào cho không gian R-d. Cấu trúc chỉ số hoá như vậy bao gồm cây R, cây k-d như đã nghiên cứu trước đây. Tuy nhiên, tổng quát thì cấu trúc chỉ số hóa như cây R và k-d không làm việc tốt với dữ liệu có số chiều ³ 20. Do vậy cần phải có kỹ thuật nào đó tốt hơn. Cây TV (TV-tree) được mô tả sau đây là cấu trúc chỉ số hoá phù hợp hơn cho loại dữ liệu nhiều chiều này. 4.4 Cây TV (TV-tree) Mục tiêu cơ bản của cây véctơ thu gọn (TV-Telescopic Vector Tree) là xâm nhập điểm dữ liệu trong không gian có số chiều rất lớn sao cho hiệu quả cao. Trên đây ta thấy, tài liệu d được xem như véctơ d có độ dài k, trong khi ma trận giá trị đơn, sau khi phân chia, có kích thước (k x k). Do vậy, mỗi tài liệu được xem như điểm trong không gian k chiều. Một CSDL tài liệu như mô tả trên đây được xem như tập hợp của các điểm như vậy và được chỉ số hoá phù hợp. Khi người sử dụng biểu diễn truy vấn Q, thực tế là họ xác định véctơ vec(Q) có độ dài k. Ta phải tìm p tài liệu trong CSDL mà nó phù hợp nhất với Q. Có nghĩa rằng ta phải tìm ra k láng giềng gần nhất với truy vấn Q có mặt trong CSDL tài liệu. Cây TV là cấu trúc dữ liệu mượn từ cây R. Cây TV cố gắng quyết định một cách mềm dẻo và động việc rẽ nhánh như thế nào, trên cơ sở dữ liệu đang xem xét. Ý tưởng là nếu nhiều véctơ phù hợp với một số thuộc tính (nếu nhiều tài liệu đều có các khái niệm chung), thì ta phải tổ chức chỉ số bằng rẽ nhánh đến các khái niệm đó (trường các véctơ) mà nó phân biệt giữa các véctơ/tài liệu này. Thí dụ, trong CSDL tài liệu chứa tập các báo cáo của Trường đại học Maryland, từ như database có thể xuất hiện trong hàng nghìn tài liệu. Để phân biệt tiếp theo giữa các bài báo có từ database, ta phải tổ chức chỉ số theo cách mà có thể rẽ nhánh theo sự hiện diện hay vắng mặt của vài từ khác mà nó có khả năng phân biệt hơn. 4.4.1 Tổ chức cây TV Trước khi định nghĩa cây TV để lưu trữ các điểm k chiều (k-d) thì ta phải chỉ ra hai tham số sau: 1. NumChild: số nút con cực đại mà 1 nút bất kỳ trong cây TV có thể có. 2. µ: là số lớn hơn 0 và nhỏ hơn hay bằng k, gọi nó là số chiều tích cực (number of active dimensions). Sử dụng ký pháp TV(k, NumChild, µ) để gọi cây TV, nó được sử dụng vào việc lưu trữ dữ liệu k-d, với NumChild là số nút con cực đại, µ số chiều tích cực. Như cây R, mỗi nút trong cây TV biểu diễn một vùng. Với mục đích sử dụng này, mỗi nút N trong cây TV chứa ba trường sau: 1. N.Center: Biểu diễn điểm trong không gian k-d. 2. N.Radius: Là số thực lớn hơn 0. 3. N.ActiveDims: Là danh sách của nhiều nhất µ chiều. Mỗi chiều là một số giữa 1 và k. Do vậy, N.ActiveDims là tập con của {1,...,k} của số µ hay nhỏ hơn. Giả sử x và y là những điểm trong không gian k-d, và ActiveDims là tập các chiều tích cực. Khoảng cách tích cực giữa x và y, được gọi là act_dist(x, y), cho bởi: Error! trong đó, xi, yi là giá trị của chiều thứ i của lần lượt x và y. Thí dụ, giả sử k=200, µ=5 và AvtiveDims={1,2,3,4,5} và giả sử rằng: x=(10,5,11,13,7, x6, x7,...,x200) y=(2,4,14,8,6,y6,y7,...,y200) Error! Sau đó khoảng cách tích cực giữa x và y được cho bởi: Chú ý rằng khoảng cách tích cực giữa hai véctơ bỏ qua mọi trường mà nó không tích cực. Cho trước nút N trong cây TV là nút biểu diễn vùng chứa mọi điểm x, trong đó khoảng cách tích cực giữa x và N.Center nhỏ hơn hay bằng N.Radius. Thí dụ, nếu chúng ta có nút N với tâm ở tại N.Center=(10, 5, 11, 13, 7, 0, 0, 0, 0,..., 0) và N.ActiveDims={1,2,3,4,5}, thì nút này biểu diễn vùng chứa mọi điểm x mà nó thỏa mãn: Error! Ta sử dụng ký pháp Region(N) để gọi vùng biểu diễn bởi nút N trong cây TV. Ngoài các trường Center, Radius, ActiveDims, nút N trong cây TV còn chứa trường Child của các con trỏ NumChild đến nút khác của cùng loại. Như trong trường hợp cây R, cây TV có các đặc tính sau: 1. Mọi dữ liệu được lưu trên các nút lá. 2. Mỗi nút trong cây TV (trừ gốc và các lá), trong đó ít nhất một nửa chúng phải có giá trị, do vậy, ít nhất nửa số con trỏ Child phải khác NIL. 3. Error! Nếu N là nút và N1,...,Nr là con của nó, thì 4.4.2 Chèn vào cây TV Hãy xem xét trường hợp có không gian 5-d (khi ta chỉ có 5 khái niệm rút ra từ tập hợp tài liệu), và ta muốn chèn vài véctơ vào cây TV với tên TV(5, 3, 2). Giả sử rằng toàn bộ không gian là siêu hình cầu (hyper-spher) có tâm tại (0,0,0,0,0) và bán kính 50. Khởi đầu cây TV là rỗng. 1. Giả sử véctơ thứ nhất sẽ chèn là (5,3,20,1,5). Nó được sử dụng để tạo ra nút gốc với các tính chất sau: Root.Center=(0,0,0,0,0). Root.Radius=50. Trong trường hợp này, gốc cũng là lá, có con trỏ đến thông tin phù hợp với điểm v1=(5,3,20,1,5). Giả sử Root.ActiveDims={2,3}. Error! Hình 4.5a chỉ ra tình huống này. 2. Error! Giả sử véctơ tiếp theo được chèn vào là v2=(0, 0, 18, 42, 4). Trong trường hợp này ta cũng tạo thêm lá mới như trên đây ...