Đề tài Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA: CÔNG NGHỆ THÔNG TIN  BÁO CÁO THU HOẠCH PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC CÁC THỦ THUẬT (NGUYÊN TẮC) SÁNG TẠO ĐƯỢC ÁP DỤNG VÀO BÀI TOÁN KHÁM PHÁ DỮ LIỆU TRONG HỆ THỐNG THÔNG TIN DI ĐỘNG CỘNG TÁC Giảng viên: GS.TSKH. HOÀNG KIẾM Lớp : CAO HỌC – HTTT - K22 Học Viên: NGÔ THÙY HƯƠNG – 12 12 016 TP. Hồ Chí Minh, 25 tháng 11 năm 2012 Ngô Thùy Hương – 12 12 016 2 LỜI CẢM ƠN Sau quá trình tìm hiểu và thực hiện, bài thu hoạch “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác” (được viết dựa trên khóa luận tốt nghiệp đại học của em) trên cơ bản đã hoàn thành. Để đạt được kết quả như hôm nay em đã cố gắng rất nhiều và cũng được sự giúp đỡ, sự ủng hộ của gia đình, các thầy cô và bạn bè. Trước hết, chúng em xin chân thành cảm ơn Khoa Công Nghệ Thông Tin, trường Đại Học Khoa Học Tự Nhiên TpHCM đã tạo điều kiện thuận lợi cho em thực hiện tốt bài thu hoạch này. Em xin bày tỏ lòng biết ơn sâu sắc đến cô Nguyễn Trần Minh Thư đã tận tình hướng dẫn, chỉ bảo em trong suốt quá trình thực hiện luận văn. Con xin chân thành cảm ơn Ông Bà, Cha Mẹ đã chăm sóc, nuôi dạy chúng con thành người. Xin chân thành cám ơn thầy GS.TSKH Hoàng Kiếm đã tận tình giảng dạy và truyền lửa giúp em và các bạn trong lớp có thêm niềm đam mê và động lực để tiếp tục nghiên cứu khoa học. Em xin cảm ơn các các thầy cô, các anh chị và các bạn đã ủng hộ, giúp đỡ và động viên em trong thời gian học tập và nghiên cứu. Bài thu hoạch đã hoàn thành với một số kết quả nhất định, tuy nhiên vẫn không tránh khỏi sai sót. Kính mong sự đóng góp ý kiến của các thầy cô và các bạn. Sinh viên thực hiện Ngô Thùy Hương 12 - 2012 Ngô Thùy Hương – 12 12 016 3 MỤC LỤC LỜI MỞ ĐẦU ................................................................................................................. 7 TỔNG QUAN ............................................................................................ 8 CHƯƠNG 1: I. Giới thiệu chung .................................................................................................... 8 1.1. Giới thiệu ........................................................................................................ 8 1.2. Hướng tiếp cận ................................................................................................ 9 1.3. Nội dung đề tài ................................................................................................ 9 CƠ SỞ LÝ THUYẾT CHO CÁC NGHIÊN CỨU KHOA HỌC ............... 11 CHƯƠNG 2: I. VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT ...................... 11 1.1. Khái niệm...................................................................................................... 11 1.2. Phân loại ....................................................................................................... 11 1.3. Các tình huống vấn đề ................................................................................... 11 1.4. Các phương pháp phát hiện vấn đề khoa học ................................................. 12 1.5. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế .......... 12 II. 40 NGUYÊN TẮC SÁNG TẠO TRONG NGHIÊN CỨU KHOA HỌC ............. 14 2.1. Nguyên tắc phân nhỏ ..................................................................................... 14 2.2. Nguyên tắc “tách khỏi” ................................................................................. 14 2.3. Nguyên tắc phẩm chất cục bộ ........................................................................ 14 2.4. Nguyên tắc phản đối xứng ............................................................................. 15 2.5. Nguyên tắc kết hợp ....................................................................................... 15 2.6. Nguyên tắc vạn năng ..................................................................................... 15 2.7. Nguyên tắc “chứa trong” ............................................................................... 15 2.8. Nguyên tắc phản trọng lượng ........................................................................ 15 2.9. Nguyên tắc gây ứng suất sơ bộ ...................................................................... 15 2.10. Nguyên tắc thực hiện sơ bộ ........................................................................ 15 2.11. Nguyên tắc dự phòng ................................................................................. 16 2.12. Nguyên tắc đẳng thế................................................................................... 16 Ngô Thùy Hương – 12 12 016 4 2.13. Nguyên tắc đảo ngược ............................................................................... 16 2.14. Nguyên tắc cầu (tròn) hoá .......................................................................... 16 2.15. Nguyên tắc linh động ................................................................................. 16 2.16. Nguyên tắc giải “thiếu” hoặc “thừa” .......................................................... 16 2.17. Nguyên tắc chuyển sang chiều khác ........................................................... 16 2.18. Nguyên tắc sử dụng các dao động cơ học ................................................... 17 2.19. Nguyên tắc tác động theo chu kỳ................................................................ 17 2.20. Nguyên tắc liên tục tác động có ích ............................................................ 17 2.21. Nguyên tắc “vượt nhanh” ........................................................................... 17 2.22. Nguyên tắc biến hại thành lợi ..................................................................... 18 2.23. Nguyên tắc quan hệ phản hồi ..................................................................... 18 2.24. Nguyên tắc sử dụng trung gian ................................................................... 18 2.25. Nguyên tắc tự phục vụ ............................................................................... 18 2.26. Nguyên tắc sao chép (copy) ....................................................................... 18 2.27. Nguyên tắc “rẻ” thay cho “đắt” .................................................................. 18 2.28. Thay thế sơ đồ cơ học ................................................................................ 19 2.29. Sử dụng các kết cấu khí và lỏng ................................................................. 19 2.30. Sử dụng vỏ dẻo và màng mỏng .................................................................. 19 2.31. Sử dụng các vật liệu nhiều lỗ ..................................................................... 19 2.32. Nguyên tắc thay đổi màu sắc ...................................................................... 19 2.33. Nguyên tắc đồng nhất ................................................................................ 20 2.34. Nguyên tắc phân hủy hoặc tái sinh các phần .............................................. 20 2.35. Thay đổi các thông số hoá lý của đối tượng ............................................... 20 2.36. Sử dụng chuyển pha ................................................................................... 20 2.37. Sử dụng sự nở nhiệt ................................................................................... 20 2.38. Sử dụng các chất oxy hoá mạnh ................................................................. 20 2.39. Thay đổi độ trơ .......................................................................................... 21 2.40. Sử dụng các vật liệu hợp thành (composite) ............................................... 21 Ngô Thùy Hương – 12 12 016 5 PHÂN TÍCH CÁC KỸ THUẬT KHÁM PHÁ DỮ LIỆU & VIỆC ỨNG CHƯƠNG 3: DỤNG CÁC NGUYÊN LÝ SÁNG TẠO KHOA HỌC TRONG ĐÓ ............................ 22 I. GIỚI THIỆU........................................................................................................ 22 1.1. Giới thiệu ...................................................................................................... 22 1.2. Kỹ thuật khám phá dữ liệu trong kiến trúc COCA ......................................... 22 1.3. Kỹ thuật khám phá dữ liệu trong kiến trúc COOP ......................................... 24 1.4. Kỹ thuật khám phá dữ liệu trong mô hình cộng tác nhóm theo vùng CC (Cluster Cooperative Caching) ................................................................................ 25 1.5. Kỹ thuật khám phá dữ liệu trong cách tiệp cận khác cho cộng tác bộ nhớ PROACTIVE (Proactive Approach Caching) .......................................................... 28 II. PHÂN TÍCH CÁC NGUYÊN LÝ SÁNG TẠO KHOA HỌC ĐƯỢC ÁP DỤNG TRONG CÁC KỸ THUẬT KHÁM PHÁ DỮ LIỆU .................................................. 30 2.1. Nguyên lý phân nhỏ ...................................................................................... 30 2.2. Nguyên tắc kết hợp ....................................................................................... 31 2.3. Nguyên tắc vạn năng ..................................................................................... 31 2.4. Nguyên tắc thực hiện sơ bộ ........................................................................... 32 2.5. Nguyên tắc dự phòng .................................................................................... 32 2.6. Nguyên tắc linh động .................................................................................... 32 2.7. Nguyên tắc biến hại thành lợi ........................................................................ 32 ỨNG DỤNG CƠ SỞ LÝ THUYẾT NGHIÊN CỨU KHOA HỌC VÀO CHƯƠNG 4: CÔNG VIỆC NGHIÊN CỨU THỰC TIỄN CỦA BẢN THÂN..................................... 33 I. GIỚI THIỆU........................................................................................................ 33 1.1. Giới thiệu ...................................................................................................... 33 1.2. Kiến trúc MIXGROUP .................................................................................. 33 1.3. Nguyên lý tìm kiếm dữ liệu của MIXGROUP ............................................... 34 II. ÁP DỤNG CÁC NGUYÊN LÝ NGHIÊN CỨU KHOA HỌC TRONG QUÁ TRÌNH NGHIÊN CỨU .............................................................................................. 35 2.1. Nguyên lý phân nhỏ ...................................................................................... 35 2.2. Nguyên lý kết hợp ......................................................................................... 36 Ngô Thùy Hương – 12 12 016 6 2.3. Nguyên lý linh động ...................................................................................... 36 2.4. Nguyên lý hoạt động theo chu kỳ .................................................................. 38 2.5. Nguyên lý sử dụng trung gian ....................................................................... 39 III. ĐỀ XUẤT VÀ KẾT LUẬN ............................................................................. 41 3.1. Đề Xuất ......................................................................................................... 41 3.2. Kết luận......................................................................................................... 41 Ngô Thùy Hương – 12 12 016 7 LỜI MỞ ĐẦU Sự phát triển lịch sử xã hội loài người gắn liền với quá trình sáng tạo lâu dài và liên tục, từ việc chế tạo ra các công cụ thô sơ cho tới công cụ hiện đại hơn sử dụng nhiệt năng và tới sự phát minh ra điện đã đánh dấu một bước phát triển nhảy vọt trong sáng tạo, các máy tính khổng lồ cho tới các máy tính cá nhân nhỏ gọn lần lượt xuất hiện. Cùng với sự sáng tạo, con người ngày càng đạt được những thành tựu vượt bậc trong khoa học công nghệ làm thay đổi thế giới, thay đổi hoàn toàn cách thức làm việc và suy nghĩ của con người. Tuy nhiên, ngày nay do nhu cầu cải tiến sáng tạo trong công nghệ phục vụ cho cuộc sống ngày càng cao đòi hỏi phải có một môn khoa học chuyên nguyên cứu về phương pháp sáng tạo giúp cho việc sáng tạo được dễ dàng và có cơ sở lý thuyết rõ ràng hơn. Vì thế các phương pháp luận sáng tạo ra đời với mục đích trang bị cho người học hệ thống các phương pháp, các kỹ năng thực hành về suy nghĩ để giải quyết các vấn đề và ra quyết định một cách sáng tạo, về lâu dài, tiến tới điều khiển được tư duy. Và trong đó 40 nguyên tắc sáng tạo cơ bản được Alshuller G.S tổng hợp lại trở thành những nguyên tắc thủ thuật cơ bản thiết thực nhất. Trước hết, em xin gửi lời cảm ơn chân thành tới GS.TSKH. Hoàng Kiếm đã giảng dạy và hướng dẫn tận tình giúp em có cái nhìn tổng quan hơn trong sáng tạo và tầm quan trọng của sự sáng tạo nhất là trong khoa học nghiên cứu và ứng dụng sáng tạo trong thực tế. Để đúc kết lại kiến thức mà em thu nhận được em xin trình bày bài thu hoạch về: “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác ”. Bài thu hoạch được phân tích dựa trên khóa luận tốt nghiệp của em [13]. Ngô Thùy Hương – 12 12 016 8 TỔNG QUAN CHƯƠNG 1: I. Giới thiệu chung 1.1. Giới thiệu Ngày nay, cùng với sự phát triển nhanh chóng của công nghệ mạng không dây, các thiết bị di động hiện đại như laptop, PDA, điện thoại di động, ... ra đời và mang lại rất nhiều ứng dụng tiện ích cho con người trong việc trao đổi, cập nhật thông tin hiệu quả. Với những thiết bị di động con người có thể trao đổi thông tin ở bất cứ nơi đâu, bất cứ lúc nào mà không cần phụ thuộc vào các kiến trúc cơ sở hạ tầng. Tuy nhiên, việc giao tiếp thông tin giữa các thiết bị trong môi trường mạng di động vẫn còn một số hạn chế như: giới hạn về băng thông, quyền chia sẻ tài nguyên, dung lượng ít, khả năng kết nối yếu, ...Vì vậy, cần có kỹ thuật quản lý và lưu trữ dữ liệu phù hợp để giúp hệ thống hoạt động, trao đổi dữ liệu hiệu quả hơn. Kỹ thuật lưu trữ lại dữ liệu (caching method) là một trong những kỹ thuật quan trọng giúp các máy khách lưu trữ lại dữ liệu tại bộ nhớ cục bộ của nó để phục vụ cho các yêu cầu dữ liệu sau đó trong trường hợp không kết nối được tới máy chủ hoặc hạn chế việc truy cập quá nhiều đến máy chủ. Kỹ thuật lưu trữ lại dữ liệu quan tâm tới bốn vấn đề chính đó là: khám phá dữ liệu (Cache Discovery), thu nạp dữ liệu (Cache Admission), thay thế dữ liệu (Cache Replacement), nhất quán dữ liệu (Cache Consistency). Tuy nhiên, trong mục tiêu và giới hạn của bài thu hoạch em chỉ đề cập tới vấn đề đó là khám phá dữ liệu (Cache Discovery). Với các ứng dụng trong mạng không dây, thì kho lưu trữ cục bộ của các thiết bị di động rất hạn chế về mặt kích thước lưu trữ, do đó vấn đề đặt ra là phải tận dụng được không gian lưu trữ sao cho hiệu quả. Chính vì thế, chúng ta cần quan tâm tới việc khám phá và thu nạp mục dữ liệu như thế nào, để đảm bảo việc sử dụng tối ưu kho lưu trữ cục bộ. Các kỹ thuật khám phá dữ liệu sẽ đề cập tới việc làm sao có thể tối ưu hóa chi phí khi tìm kiếm một hạng mục dữ liệu trong hệ thống, giúp giảm thiểu số lần truy vấn tới máy Ngô Thùy Hương – 12 12 016 9 chủ (hay còn gọi là BS (Base Station), Server, Data Source), rút ngắn thời gian phản hồi truy vấn dữ liệu tại mỗi máy khách (hay còn gọi là Client, nút di động). Tuy nhiên, việc tìm kiếm mục dữ liệu yêu cầu, và việc thêm vào một hạng mục dữ liệu không phải lúc nào cũng thuận lợi vì quyết định sai có thể làm giảm tính sẵn sàng của dữ liệu. Chính vì thế mục tiêu của bài thu hoạch “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác” là tìm hiểu và phân tích những nguyên lý sáng tạo đã được áp dụng vào các kỹ thuật khám phá dữ liệu.Từ kết quả phân tích có thể giúp cho những nhà nghiên cứu liên quan có lựa chọn đúng đắn đến việc sử dụng kỹ thuật khám phá vào trong mỗi hệ thống đặc thù của mình. 1.2. Hướng tiếp cận Với mục tiêu đề tài đưa ra, hướng tiếp cận và giải quyết bài toán là sẽ tìm hiểu lần lượt các kỹ thuật khám phá dữ liệu trong môi trường hệ thống thông tin di động từ các công trình nghiên cứu trong và ngoài nước. Đồng thời sẽ tiến hành phân loại các trường hợp của kỹ thuật khám phá dữ liệu đã tìm hiểu. Sau đó đánh giá và so sánh các ưu khuyết điểm của các kỹ thuật phám phá dữ liệu. Và cuối cùng là đề xuất và thử nghiệm một số kỹ thuật khám phá dữ liệu để kiểm tra tính hiệu quả của từng giải pháp. 1.3. Nội dung đề tài Với mục tiêu, hướng tiếp cận, và cách giải quyết của bài thu hoạch “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác”. Nội dung bài thu hoạch được trình bày theo cấu trúc như sau:  Chương 1: Tổng quan Giới thiệu về bối cảnh, mục tiêu, hướng tiếp cận và nội dung của đề tài.  Chương 2: Cơ sở lý thuyết cho các nghiên cứu khoa học Ngô Thùy Hương – 12 12 016 10 Trong chương này, em sẽ trình bày về cơ sở lý thuyết cho các nghiên cứu khoa học và 40 nguyên lý sáng tạo trong khoa học.  Chương 3: Phân tích các kỹ thuật khám phá dữ liệu và việc áp dụng nguyên lý sáng tạo trong đó Trong chương này, em sẽ trình bày về kỹ thuật khám phá dữ liệu trong hệ thống thông tin di động cộng tác, đồng thời phân tích những nguyên lý sáng tạo được áp dụng trong từng kiến trúc.  Chương 4 : Ứng dụng cơ sở lý thuyết nghiên cứu khoa học vào công việc nghiên cứu thực tiễn của bản thân Trong chương này, em sẽ trình bày những nguyên lý sáng tạo mà em đã áp dụng vào đề tài của mình. Ngô Thùy Hương – 12 12 016 11 CƠ SỞ LÝ THUYẾT CHO CÁC CHƯƠNG 2: NGHIÊN CỨU KHOA HỌC I. VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT 1.1. Khái niệm Vấn đề khoa học (scientific problem) [19] cũng được gọi là vấn đề nghiên cứu (research problem) hoặc câu hỏi nghiên cứu là câu hỏi được đặt ra khi người nghiên cứu đứng trước mâu thuẫn giữa tính hạn chế của tri thức khoa học hiện có với yêu cầu phát triển tri thức đó ở trình độ cao hơn. 1.2. Phân loại Nghiên cứu khoa học luôn tồn tại hai vấn đề : - Vấn đề về bản chất sự vật đang tìm kiếm - Vấn đề về phương pháp nghiên cứu để làm sáng tỏ về lý thuyết và thực tiễn những vấn đề thuộc lớp thứ nhất. 1.3. Các tình huống vấn đề Có ba tình huống : Có vấn đề , không có vấn đề, giả vấn đề được cho trong hình dưới đây: Có vấn đề Có nghiên cứu Không có vấn đề Không có nghiên cứu Ngô Thùy Hương – 12 12 016 12 Hình 2.1: Sơ đồ phân loại 1.4. Các phương pháp phát hiện vấn đề khoa học Có sáu phương pháp: 1) Tìm những kẻ hở, phát hiện những vấn đề mới 2) Tìm những bất đồng 3) Nghĩ ngược lại quan niệm thông thường 4) Quan sát những vướng mắc trong thực tiễn 5) Lắng nghe lời kêu ca phàn nàn 6) Cảm hứng : những câu hỏi bất chợt xuất hiện khi quan sát sự kiện nào đó. 1.5. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế 1.5.1. Có 5 phương pháp:  Dựng Vepol đầy đủ  Chuyển sang Fepol  Phá vở Vepol  Xích Vepol  Liên trường 1.5.2. Có 40 thủ thuật:  Nguyên lý phân nhỏ.  Nguyên lý “tách khỏi”. Giả vấn đề Không có vấn đề Nảy sinh vấn đề khác Không có nghiên cứu Nghiên cứu theo một hướng khác Ngô Thùy Hương – 12 12 016 13  Nguyên lý phẩm chất cục bộ.  Nguyên lý (phản) bất đối xứng.  Nguyên lý kết hợp.  Nguyên lý vạn năng.  Nguyên lý “chứa trong”.  Nguyên lý phản trọng lượng.  Nguyên lý gây ứng suất (phản tác động) sơ bộ.  Nguyên lý thực hiện sơ bộ.  Nguyên lý dự phòng.  Nguyên lý đẳng thế.  Nguyên lý đảo ngược.  Nguyên lý cầu (tròn) hóa.  Nguyên lý linh động.  Nguyên lý giải (tác động) “thiếu” hoặc “thừa”.  Nguyên lý chuyển sang chiều khác.  Sử dụng các dao động cơ học.  Nguyên lý