Lập lịch làm việc cho các tác vụ khai phá dữ liệu trong môi trường lưới dữ liệu

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008<br /> <br /> LẬP LNCH LÀM VIỆC CHO CÁC TÁC VỤ KHAI PHÁ DỮ LIỆU<br /> TRONG MÔI TRƯỜNG LƯỚI DỮ LIỆU<br /> Đoàn Văn Ban (Viện Công nghệ thông tin - Viện KH&CN Việt Nam)<br /> Vũ Đức Quảng (Trường ĐH Quảng Nam)<br /> <br /> 1. Giới thiệu<br /> Trong những năm gần đây, chúng ta đã chứng kiến sự bùng nỗ cả về số lượng lẫn kích<br /> thước của các kho dữ liệu điện tử. Điều này đem đến cho các nhà nghiên cứu cơ hội để phát<br /> triển hiệu quả các kỹ thuật khai phá để khám phá và trích rút tri thức từ khối lượng thông tin<br /> khổng lồ đó. Hơn nữa, do kích thước của dữ liệu lớn và thường được phân tán ngẫu nhiên. Nếu<br /> như chúng ta xem các thuật toán khai phá dữ liệu là thường xuyên được thực hiện, chúng ta có<br /> thể kết luận rằng lưới là nền tảng cơ sở cho việc kiển khai một dịch vụ hiệu năng cao cho quá<br /> trình khai phá trị thức phân tán (DKD-Distributed Knowledge Discovery).<br /> Môi trường lưới có thể cung cấp khả năng phân bố tài nguyên, khả năng xử lý cộng tác và<br /> khả năng phân tích khai phá dữ liệu với khối lượng lớn dữ liệu được đưa ra và được lưu trữ. Vì<br /> các ứng dụng DKD đòi hỏi dữ liệu đặt trưng, một trong những yêu cầu của môi trường lưới<br /> DKD là quản lý việc lưu trữ và việc truyền tải tài nguyên một cách hiệu quả.<br /> Trong báo cáo này, kiến trúc quản lý dữ liệu dựa trên các hệ thống lưu trữ và các dịch vụ<br /> quản lý siêu dữ liệu. Dịch vụ lưới dữ liệu được xây dựng bên trên các dịch vụ Globus cơ sở [8]<br /> và đơn giản hóa việc quản lý các tính toán truy cập các nguồn dữ liệu lớn và phân tán. Số các<br /> thành phần tính toán được xem xét với số lượng hữu hạn và các tính năng của chúng đã được<br /> biết. Lưới dữ liệu cung cấp bộ quản lý khối lượng công việc cần làm (WorkLoad manager) có<br /> nhiệm vụ định nghĩa các công việc với các yêu cầu liên quan và lập lịch làm việc cho chúng<br /> trong môi trường Lưới. Mô hình lưới dữ liệu trình bày ở trên đưa ra các yêu cầu đối với việc<br /> thực thi của một lưới DKD, ở đây, dữ liệu đòi hỏi có thể được lấy từ nhiều nguồn. Ngoài ra, các<br /> dịch vụ cơ sở của lưới dữ liệu có thể được sử dụng và được mở rộng để thực thi các dịch vụ lưới<br /> mức cao hơn liên quan đến quá trình khai phá tri thức từ các kho dữ liệu phân tán. Hạ tầng cơ sở<br /> lưới chuyên dụng như thế được gọi là lưới tri thức [8], kiến trúc này được thiết kế để phù hợp<br /> với các kỹ thuật lưới ở mức thấp hơn và với các kỹ thuật lưới dữ liệu. Kiến trúc lưới tri thức có<br /> thể được chia thành 2 lớp: Lớp K-Lưới trung tâm và Lớp K-Lưới mức cao.<br /> <br /> Hình 1. Kiến trúc lưới tri thức<br /> <br /> 22<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008<br /> <br /> Trên cơ sở kiến trúc Lưới tri thức, các dịch vụ trọng tâm của nó, ví dụ: Dịch vụ thư mục<br /> tri thức (KDS) và dịch vụ phân phối tài nguyên và quản lý thực thi (RAEM - Resource<br /> Allocation and Execution Management). KDS mở rộng dịch vụ kiểm soát và khai phá thông tin<br /> (MDS-Monitoring and Discovery Services) Globus[7] và có nhiệm vụ duy trì một mô tả của tất<br /> cả dữ liệu và các công cụ được sử dụng trong Lưới tri thức. Siêu dữ liệu được quản lý bởi KDS<br /> được trình bày trong các tài liệu XML, được lưu trữ trong kho siêu dữ liệu tri thức (KMRKnowledge Metadata Repository).<br /> Báo cáo này phân tích sâu một số vấn đề đã gặp trong thiết kế và thi hành một chiến lược<br /> lập lịch cho bộ định giá của kiến trúc lưới tri thức. Với cách giải quyết này, bộ lập lịch cần sử<br /> dụng một mô hình thực thi phức hợp để xem xét trạng thái hiện tại của lưới, xác định vị trí các<br /> nguồn dữ liệu và cách thức thực thi tác vụ. Thông tin về các chi phí thực thi là cần thiết đối với<br /> bộ định giá để có thể đánh giá khả năng của các hoạt động quản lý tập dữ liệu (ví dụ: việc di<br /> chuyển hay phân hoạch một tập dữ liệu) và để định cấu hình thời gian tải các công cụ DM nhằm<br /> đạt được hiệu suất mong muốn (ví dụ: bằng việc cho một phép phân tích có chi phí cao thực hiện<br /> song song). Tuy nhiên, chi phí thực thi của các công cụ DM không chỉ phụ thuộc vào kích thước<br /> dữ liệu mà còn phụ thuộc vào các tham số khai phá được xác định bởi người dùng.<br /> Xét ví dụ về khai phá luật kết hợp (ARM-Association Rule Mining): Độ phức tạp của<br /> ARM không chỉ phụ thuộc vào kích thước của dữ liệu đầu vào mà còn phụ thuộc vào ngưỡng hỗ<br /> trợ và ngưỡng tin cậy. Hơn nữa, sự tương quan của các mục (item) xuất hiện trong tập dữ liệu<br /> ảnh hưởng lớn đến số lượng và độ dài tối đa của các luật được tìm thấy bởi công cụ ARM. Bởi<br /> thế, thật khó để dự đoán việc cải tiến thực thi dựa vào chi phí vào/ra và kích thước dữ liệu đầu<br /> vào. Để giải quyết các vấn đề này, ta đưa vào trong dịch vụ KDS gồm cả thông tin động liên<br /> quan các thực thi khác nhau của các tác vụ DM trên các nguồn dữ liệu khác nhau. Thông tin này<br /> có thể được thêm vào giống như siêu dữ liệu bổ sung được kết hợp với tập dữ liệu. Vì thế, KDS<br /> được mở rộng không chỉ có siêu dữ liệu tĩnh được sử dụng để xem xét dữ liệu hay các công cụ<br /> được sử dụng trong lưới tri thức mà thông tin động còn được sử dụng để xác định làm thế nào<br /> để cấu hình và chạy các công cụ đó. Siêu dữ liệu động tập trung vào thông tin kiểm tra việc chạy<br /> các phần mềm khác nhau trước đây trên các tập dữ liệu xác định. Siêu dữ liệu động có thể được<br /> kết hợp với các tập dữ liệu để cho biết thông tin về các chi phí thực thi trước đây, thông tin này<br /> chỉ hữu dụng khi một tập dữ liệu chỉ định đã được phân tích ít nhất một lần, ví dụ, các yêu cầu<br /> ARM (bao gồm ngưỡng hỗ trợ và ngưỡng tin cậy) tương tự nhau được đưa ra để xem xét trên<br /> lưới tri thức. Tuy nhiên siêu dữ liệu này có thể không sẳn có, trong trường hợp một tập dữ liệu<br /> mới được đưa ra phân tích lần đầu dẫn đến thiếu vắng thông tin về các chi phí thực thi, dịch vụ<br /> lưới RAEM sẽ đưa ra các cách giải quyết lập lịch một cách mù quáng. Để giải quyết được vấn<br /> đề này, ta sử dụng phương pháp lấy mẫu như là một cách thức để thu được tri thức về các chi<br /> phí thực thi của các tác vụ DM. Phương pháp này có khả năng trích rút tri thức đúng đắn từ một<br /> mẫu của tập lớn dữ liệu [4]. Tuy nhiên, thực tế tri thức khai phá được không phụ thuộc tuyến<br /> tính vào kích thước mẫu, việc xác định bao nhiêu dữ liệu cần được sử dụng là không thể. Do đó<br /> chúng tôi đề xuất một hướng sử dụng khác của phương pháp lấy mẫu: khi mà không có tri thức<br /> sẳn có về chi phí của một phép phân tích được chỉ định, ta thực hiện phép phân tích này trên một<br /> mẫu nhỏ của tập dữ liệu để dự đoán chi phí thực thi thực tế của nó trên tập dữ liệu đầy đủ. Việc<br /> xác định đúng kích thước của mẫu là mấu chốt để trích rút tri thức chính xác, tuy nhiên, ta<br /> không thể áp dụng để đánh giá chi phí thực thi. Cùng với các chi phí thực thi, với phương pháp<br /> lấy mẫu ta có thể ước lượng được kích thước của các kết quả khai phá được, số lần vào/ra dữ<br /> liệu và dung lượng bộ nhớ chính yêu cầu. Các chi phí sẽ cung cấp các mô hình thực thi cụ thể<br /> 23<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008<br /> <br /> cho bộ lập lịch lưới tri thức để dự đoán chi phí truyền thông cần thiết, hiệu quả của việc phân bổ<br /> tài nguyên và ích lợi có thể nhận được từ việc thực thi song song.<br /> 2. Lập lịch phân tán trong môi trường lưới tri thức<br /> Một bộ định giá lưới hoạt động như sau:<br /> + Khai phá một số tài nguyên phù hợp với các yêu cầu tối thiểu cho việc thực thi.<br /> + Kiểm tra các giấy phép trong việc chọn một công việc để giải quyết trên các tài nguyên đó.<br /> + Chọn các nguồn tài nguyên phù hợp nhất với các yêu cầu thực thi ứng dụng và lập lịch<br /> làm việc.<br /> Các giải thuật lập lịch có thể được phân thành 2 dạng: Lập lịch làm việc động và lập lịch<br /> làm việc tĩnh. Dựa vào đặc điểm của các công việc khai phá dữ liệu, thường có tác động lẫn<br /> nhau, chiến lược lập lịch tốt nhất nên được sử dụng trong thiết kế bộ lập lịch lưới tri thức là<br /> chiến lược lập lịch làm việc động. Báo cáo này cũng đề cập đến việc đánh giá tính khả thi và lợi<br /> ích của việc sử dụng bộ lập lịch trực tuyến mức thấp (local scheduler) tập trung của một tổ chức<br /> AO (AO có một vài nhóm máy tính được kết nối tạo thành Lưới).<br /> 2.1. Các tính toán cần thiết cho việc lập lịch làm việc<br /> Gọi một tác vụ khai phá dữ liệu là ti được định nghĩa đầy đủ trong phạm vi phép phân<br /> tích DM yêu cầu, tập dữ liệu phân tích Di (có kích thước |Di|) và các tham số người dùng ui<br /> (được xác định trước). Tác vụ ti trích rút một mô hình tri thức từ tập dữ liệu Di. Đặt αi(Di) là dữ<br /> liệu được trích rút bởi ti, kích thước của nó là |αi(Di)|. Cuối cùng, mô hình tri trức được trích rút<br /> phải được chuyển đến một vị trí xác định trước.<br /> Trước khi nghiên cứu chi tiết giải thuật sắp xếp và môi trường lưới, ta giả sử rằng:<br /> - Một bộ lập lịch tập trung điều khiển việc sắp xếp các tác vụ DM trên nhiều máy tính<br /> khác nhau của Lưới AO trong môi trường lưới. AO gồm có một tập M = {m1, ...., m|M|} máy<br /> tính, pj là thừa số thực thi ứng với máy tính mj. Thừa số thực thi cho biết tốc độ của các máy tính<br /> trong lưới. Trong báo cáo này chúng tôi không xem xét tính đa nhiệm của nút và không đưa vào<br /> tham số truyền tải của máy tính ở bên ngoài có thể hưởng đến các thừa số thực thi.<br /> Ngoài ra, các máy tính được sắp xếp như một tập các nhóm CL = {cl1,...., cl|CL|}, mỗi<br /> nhóm clJ bao gồm một tập các máy tính rời nhau trong M máy có kết nối với nhau bởi một mạng<br /> có tốc độ truyền thông cao. Cụ thể, clJ = {m1J , m2J ,..., m|clJ J | } , mỗi clJ là có khả năng là một máy<br /> điều khiển việc thực thi song song một phân tích DM đã định. Các thừa số thực thi của một<br /> nhóm clJ là pJ, pJ bằng với thừa số thực thi của máy chạy chậm nhất trong nhóm.<br /> - Mã chương trình (tuần tự hay song song) thực thi công việc DM được xem là sẳn có ở<br /> mỗi nút của lưới. Vì thế, vấn đề sắp xếp chính là việc chọn lựa tác vụ nào nên được gán cho máy<br /> nào thực hiện là phù hợp nhất, liên quan đến thời gian truyền thông cần thiết cho việc di chuyển<br /> dữ liệu vào/ra và các thời điểm máy tính rỗi và các liên kết đang sẵn sàng.<br /> - Dựa trên nền tảng của phương pháp pháp lấy mẫu, có khả năng ước lượng ei là chi phí<br /> tính toán tuần tự để thực hiện tác vụ ti trên tập dữ liệu Di với các tham số người dùng ui. Đặt eij<br /> =pj * ei là thời gian thực thi thực tế của tác vụ ti trên máy mj; Khi một phép phân tích được thực<br /> hiện song song trên một nhóm clJ, nếu như việc cân bằng tải được giải quyết tốt, tác vụ ti có thể<br /> 24<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008<br /> <br /> được thực thi song song với tốc độ gần như hoàn hảo. Đặt eiJ là thời gian thực thi của tác vụ ti<br /> trên một nhóm clJ bằng max m J ∈cl (eit / | cl J |) + ovh = max m J ∈cl (( pt * ei ) / | cl J |) + ovh . Điều kiện<br /> t<br /> <br /> J<br /> <br /> t<br /> <br /> J<br /> <br /> ovh là mô hình tạp phí của việc thực thi song song và tính không đồng nhất của nhóm. Xét<br /> trường hợp, khi một nhóm là đồng nhất và ei là đủ lớn thì ovh là luôn luôn nhỏ.<br /> - Một tập dữ liệu Di có thể được tập trung hay được phân tán. Trong trường hợp các tập<br /> dữ liệu được phân bố không cố định. Vì thế, một tập dữ liệu chỉ được di chuyển khi điều đó có<br /> ích cho việc rút ngắn thời gian hoàn thành công việc. Chẳng hạn, một tập dữ liệu tập trung được<br /> lưu trữ tại vị trí h có thể được di chuyển sang vi trí j và chi phí di chuyển phụ thuộc vào dải<br /> thông mạng trung bình bhj giữa hai vị trí đó. Khi đó, Di có thể di chuyển với chi phí là |Di|/bhj<br /> Việc di chuyển dữ liệu giữa các vị trí được chuyển ra ngoài bởi bộ quản lý nhân bản của<br /> các dịch vụ lưới mức thấp. Các truy cập tới một tập dữ liệu trong tương lai có thể có được lợi<br /> thế do các bản sao khác nhau được phổ biến trong lưới. Vì thế, lúc tác vụ ti cần được sắp xếp, ta<br /> phải xem xét, đối với mỗi máy tính, ta phải lựa chọn bản sao tập dữ liệu nào có lợi nhất cần<br /> chuyển đi hay được truy cập.<br /> 2.2. Mô hình chi phí<br /> Giả sử rằng mỗi tập dữ liệu đầu vào được lưu trữ trên một máy tính đơn mh, khi mô hình<br /> tri thức được trích rút ra phải được di chuyển đến một máy tính mk. Dựa vào cách giải quyết<br /> được đưa ra bởi bộ lập lịch, các tập dữ liệu có thể được di chuyển đến các máy khác và vì thế<br /> được nhân bản hay có thể được phân hoạch cho các máy tính khác nhau của một nhóm máy để<br /> thực hiện song song. Vì vậy, bộ lập lịch phải đưa ra bảng báo cáo về một số bản sao (nhân bản<br /> hay phân tán) của một tập dữ liệu có thể tồn tại trên nhiều máy tính của lưới AO của nó.<br /> Thực thi tuần tự: Giả sử tập dữ liệu đầy đủ được lưu trữ trên một máy đơn mh ∈ M. Tác<br /> vụ ti được thực thi tuần tự bằng việc chạy một đoạn mã trên máy tính mj với thời gian thực hiện<br /> là eij. Ta cũng xem xét các truyền thông cần thiết để di chuyển Di từ máy mh đến máy mj và các<br /> truyền thông khác để di chuyển kết quả |αi(Di)| đến máy mk. Tổng số thời gian thực thi sẽ là:<br /> E ij =<br /> <br /> | Di |<br /> | α (D ) |<br /> + eij + i i<br /> bhj<br /> b jk<br /> <br /> Thực thi song song: Tác vụ ti được thực thi song song bởi việc chạy một đoạn mã trên một<br /> nhóm clJ với thời gian thực thi là eiJ. Ta cũng phải xem các truyền thông cần thiết để di chuyển Di từ<br /> máy mh đến clJ và để di chuyển kết quả |αi(Di)| đến máy mk. Tổng thời gian thực hiện sẽ là:<br /> EiJ =<br /> <br /> | Di | / | cl J |<br /> | α i ( Di ) | / | cl J |<br /> + eiJ + ∑<br /> bht<br /> btk<br /> mtJ ∈cl J<br /> mtJ ∈cl J<br /> <br /> ∑<br /> <br /> Các chi phí truyền thông liên quan là bằng 0 nếu tập dữ liệu này đã được phân tán và<br /> được định vị trên các máy tính của nhóm clJ.<br /> Xét giải thuật song song, chúng ta cùng phân phối các yêu cầu và lập lịch cho tất cả các máy<br /> tính của nhóm, ta giả sử rằng các tiến trình song song được kết hợp với nhau. Một mô hình thực thi<br /> khác nên được sử dụng nếu chúng ta sử dụng giải thuật DM phân bố bất đồng bộ hơn, trước tiên các<br /> tính toán phụ thuộc được thực thi trên các phân hoạch tập dữ liệu riêng biệt và rồi các kết qủa khác<br /> nhau của phép phân tích khai phá phân tán được tập hợp lại để thu được kết quả cuối cùng<br /> 25<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008<br /> <br /> Các thước đo thực thi: Eij và EiJ là thời gian thực thi tổng cộng mong muốn của tác vụ ti<br /> khi không có sự truyền tải hiện diện trong hệ thống. Khi mà sự truyền tải hiện hữu trong các<br /> máy tính và trong mạng, việc lập lịch sẽ trì hoàn thời điểm bắt đầu và thời gian hoàn thành một tác<br /> vụ. Trong phần sau chúng ta sẽ phân tích thời gian hoàn thành thực tế của một tác vụ trong trường<br /> hợp thực hiện tuần tự. Tương tự các phân tính cũng được làm trong trường hợp song song.<br /> Đặt Cij là thời gian thực mà tất cả sự truyền thông và tính toán tuần tự đòi hỏi để thực thi<br /> hoàn thành tác vụ ti. Để xác định Cij ta cần xác định thời điểm bắt đầu các truyền thông và thực<br /> hiện tính toán. Đặt shj là thời điểm bắt đầu truyền thông cần thiết để di chuyển dữ liệu đầu vào từ<br /> máy h đến máy j, đặt sj là thời gian bắt đầu việc thực thi tuần tự tác vụ ti trên máy j và đặt sjk là<br /> thời gian bắt đầu truyền thông cần thiết để di chuyển mô hình tri thức kết quả được trích rút ra<br /> từ máy j đến máy k. Từ các định nghĩa trên ta có:<br /> C ij = ( s hj +<br /> <br /> | Di |<br /> | α (D ) |<br /> ) + δ 1 + eij + δ 2 + i i = s hj + E hj + δ 1 + δ 2<br /> bhj<br /> b jk<br /> <br /> Trong đó: δ 1 = s j − ( s hj +<br /> <br /> | Di |<br /> ) ≥ 0 và δ 2 = s jk − ( s j + eij ) ≥ 0<br /> bhj<br /> <br /> Vì vậy, nếu Ai là thời gian đến của tác vụ ti và ti là tác vụ duy nhất trong quá trình thực<br /> hiện của hệ thống thì thời gian hoàn thành của tác vụ trên máy mj là Cij = Ai + Eij<br /> Giả sử rằng m j là máy được chọn bởi giải thuật lập lịch để thực thi tác vụ ti. Đặt Ci = C i j<br /> và C i = C i j . Đặt T là tập tất cả các tác vụ được lập lịch. Các đơn vị thời gian cho việc lập lịch<br /> hoàn thành được xác định là max t1∈T (C i ) và dùng để đo toàn bộ lượng dữ liệu đưa vào hệ thống.<br /> <br /> 3. Phương pháp dự đoán thực thi<br /> Trước khi nghiên cứu chiến lược sắp xếp công việc dựa vào mô hình chi phí, chúng tôi<br /> xét tính khả thi của phương pháp chọn mẫu trong việc dự đoán việc thực thi của tác vụ DM.<br /> Với phương pháp chọn mẫu, chúng ta có thể xác định vấn đề để rút ngắn thời gian hoàn<br /> thành của một tác vụ phức tạp, điều đó có lợi cho việc di chuyển dữ liệu và thực thi tác vụ đó trên<br /> một máy xác định ở xa với thời gian nhanh nhất, hay phân tán dữ liệu để thực thi tác vụ song song.<br /> Trong báo cáo này, chúng tôi không đề cập đến độ chính xác của tri thức được trích rút từ một tập<br /> dữ liệu được lấy mẫu, mà chỉ quan tâm đến độ chính xác của các dự đoán thực thi. Vì thế, chúng<br /> ta sẽ phân tích các yêu cầu bộ nhớ và thời gian thực thi của giải thuật DM được chỉ định như hàm<br /> kích thước mẫu khai thác được tức là khả năng thực hiện của giải thuật. Từ việc nghiên cứu tính<br /> khả thi, đối với mỗi giải thuật, các hàm đưa ra các tiêu chí đánh giá thu được từ phương pháp chọn<br /> mẫu, trả lại thời gian thực thi dự đoán, yêu cầu bộ nhớ cần thiết cho việc chạy các phương pháp<br /> khai phá tương tự khác trên tập dữ liệu đầy đủ.<br /> ⌢<br /> Giả sử một tác vụ cho trước ti được thực thi đầu tiên trên mẫu Di của Di trên máy mj, đặt<br /> ⌢<br /> ⌢ ⌢<br /> eij là thời gian thực thi tác vụ này và ei = eij / p j là thời gian thực thi chuNn hoá đối với mẫu<br /> này. Phương pháp chọn mẫu là có thể thực hiện được nếu hàm F() có dạng như sau:<br /> ⌢<br /> ⌢<br /> ei = F (ei , Di , Di ) . Trong trường hợp đơn giản hàm F là một hàm tuyến tính của mẫu với hệ số<br /> ⌢<br /> ⌢<br /> tỷ lệ s =| Di | / | Di | và ta có thể viết ei = ei + (1 − s ) β trong đó β là hệ số góc đường cong.<br /> <br /> 26<br /> <br />