Методы добычи данных при построении локальной метрики в системах вывода по прецедентам

В работе предложен метод принятия

В работе предложен метод принятия решений, основанный на совместном применении ранее не комбинировавшихся (по крайней мере, в отечественных разработках) методов извлечения знаний и вывода по прецедентам, где методы добычи данных используются для автоматического отбора из большой базы прецедентов.
На данный момент все существующие интегрированные системы подобного рода пытаются строить для себя модель данных как способ получения фонового знания. Например, системы, использующие байесовские сети – причинно-следственную модель, системы, использующие предварительную кластеризацию – понятийную модель.

Основная цель привлечения фонового знания в системах вывода по прецедентам – получение сведений для разумного выбора наиболее подходящих прецедентов и адаптации найденного решения. А это, в свою очередь, в большой степени зависит от выбранной меры близости. Наиболее часто используемым методом в выборе прецедентов является метод "ближайшего соседа". В произволе, который допускают системы при выборе меры близости в этом методе, и заключается их главный недостаток.
Предложенная в работе локальная контекстно-зависимая метрика имеет интерпретацию расстояния и позволяет ранжировать объекты, по отношению к исследуемому, целыми числами. При ее построении может быть использована как предварительная кластеризация базы прецедентов, так и разбиение базы на классы эквивалентности с привлечением экспертного знания.
Неполное описания объектов и попадание текущего случая в пересечение понятий (что часто встречается на практике) также не являются препятствием. Более того, сам факт такого пересечения используется в предлагаемой метрике.
При построении метрики используется предложенный авторами модифицированный метод кластерного анализа, ориентированный на распознавание объектов в ситуациях, когда объекты и кластеры имеют не полностью совпадающие наборы признаков. Эта метрика применима к широкому кругу приложений и не накладывает ограничений на типы используемых атрибутов.
В нашей стране такой подход еще не получил должного развития.
По сравнению с упомянутой ранее зарубежной разработкой (система M2), где используется предварительная кластеризация прецедентов, предлагаемый подход позволяет работать в условиях нефиксированного набора атрибутов, что часто встречается в различных приложениях в ситуациях, когда текущий случай попадает в смешение различных понятий из-за того, что он не полностью описан.
Что касается адаптации решения – предлагаемый метод позволяет сделать эту проблему более формализуемой. Хотя в общем случае проблема адаптации остается зависимой от предметной области, предложенный подход значительно упрощает эту задачу, так как учитывает фоновое знание.
Методы CBR уже применяются во множестве прикладных задач – в медицине, управлении проектами, для анализа и реорганизации среды, разработки товаров массового спроса с учетом предпочтений разных групп потребителей и т. д. Следует ожидать приложений методов CBR к задачам интеллектуального поиска информации, электронной коммерции (предложение товаров, создание виртуальных торговых агентств), планирования поведения в динамических средах, компоновки, конструирования, синтеза программ.

Методы добычи данных при построении локальной метрики в системах вывода по прецедентам

Библиография

Aamodt 94 Agnar Aamodt and Enric Plaza. "Case-based reasoning: Foundational issues, methodological variations, and system approaches". AI Communications, 7(1):39-59, 1994.

Acorn 92 Acorn T., Walden S. (1992). "SMART: Support management cultivated reasoning technology for Compaq customer service". In Proceedings of AAAI92. Cambridge, MA: AAAI Press/MIT Press.

Aha 93 Aha D. W., Salzberg S. L. "Learning to Catch: Applying Nearest Neighbor Algorithms to Dynamic Control Tasks". In P. Cheeseman & R. W. Oldford (Eds.) Selecting Models from Data: Artificial Intelligence and Statistics. - New York, NY: Springer-Verlag, 1993.

Aha 95 Aha D. W. "An Implementation and Experiment with the Nested Generalized Exemplars Algorithm". Technical Report AIC-95-003. - Washington, DC: Naval Research Laboratory, Navy Center for Applied Research in Artificial Intelligence, 1995

Aha 96 David W. Aha and Li Wu Chang. "Cooperative bayesian and case-based reasoning for solving multiagent planning tasks". Technical report, Navy Center for Applied Research in AI, Naval Research Laboratory, Washington, DC, USA, 1996.

Althof 95/1 Klaus-Dieter Althof, Eric Auriol, Ralph Barlette, and Michel Manago. A Review of Industrial Case-Based Reasoning Tools. AI Intelligence, 1995.

Althof 95/2 Klaus-Dieter Althof, Eric Auriol, Ralph Traphöner, and Stefan Wess. "Inreca – a seamlessly integrated system based on inductive inference and case-based reasoning". In Agnar Aamodt and Manuela Veloso, editors, Case-Based Reasoning Research and Development, ICCBR-95, pages 371-380, 1995.

Althof 96 Althoff, K.D., Auriol, E., Barletta, R., and Manago, M. "A Review of Industrial Case-based Reasoning Tools". An AI Perspectives Report. Series Editor: Alex Goodall. 1996.

Anand 97/1 Sarabjot Anand, Bryan Scotney, Mee Tan, Sally McClean, David Bell, John Hughes, and Ian Magill. "Designing a kernel for data mining". IEEE Expert, 12(2):65-74, 1997.

Anand 97/2 S. S. Anand, W. Dubitzky, D. Patterson, A. Schuster, J. G. Hughes. "M2: A First Step Towards Automated Generation and Updating of Case-Knowledge from Databases", Internal Report, Faculty of Informatics, University of Ulster, 1997 (available from http://iserve1.infj.ulst.ac.uk:8080/m2.ps).

Anand 98 Anand S. S., Patterson D. W., Hughes J. G., Bell D. A. "Discovering Case Knowledge Using Data Mining". 2nd Pacific-Asia Conference in Knowledge Discovery in Databases (PAKDD-98), Australia, pp25-35, 1998.

Anand 99 Anand, S.S., Hughes, J.G., Bell, D.A. and Hamilton, P. "Utilising Censored Neighbours in Prognostication", Workshop on Prognostic Models in Medicine, Eds. Ameen Abu-Hanna and Peter Lucas, Aalborg, (AIMDM’99), Denmark, pp15-20, 1999.

Ashley 88 Ashley, K.D. and Rissland, E.L. (1988). "Waiting on Weighting: A Symbolic Least Committment Approach". In Proceedings of the Seventh National Conference on Artificial Intelligence, pp. 239-244.

Ashley 90 Ashley, Kevin D. (1990). "Modelling Legal Arguments: Reasoning with Cases and Hypotheticals", Cambridge, MIT Pre

Bareiss 88 Bareiss, E., Porter, B., and Wier, C. (1988). PROTOS: An Exemplar-based Learning Apprentice. International Journal of Man-Machine Studies, 29: 549-561.

Bareiss 91 Bareiss, R., ed. 1991. Proceedings of the DARPA Case-Based Reasoning Workshop. San Francisco, Calif.: Morgan Kaufmann.

Blanzieri 00 Enrico Blanzieri, Luigi Portinale (Eds.): Advances in Case-Based Reasoning, 5th European Workshop, EWCBR 2000, Trento, Italy, September 6-9, 2000, Proceedings. Lecture Notes in Computer Science 1898 Springer 2000, ISBN 3-540-67933-2 Contents BibTeX - EWCBR 2000 Home Page

Brand 98/1 Brand E., Gerritsen R. "Decision Trees". DBMS. - 1998. - № 7.

Brand 98/2 Brand E., Gerritsen R. "Naive-Bayes and Nearest Neighbor". DBMS. - 1998. - № 7.

Breese 95 John S. Breese and David Heckerman. "Decision-theoretic case-based reasoning".

In Proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, pages 56-63, 1995.

Breiman 84 Breiman L., Friedman J. H., Olshen R. A., & Stone, C. J. (1984). "Classification and regression trees". Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software.

Bull 97 M. Bull, G. Kundt, and L. Gierl. "Discovering of health risks and case-based forecasting of epidemics in a health surveillance system". In Jan Komorowski and Jan Zytkow, editors, Principles of Data Mining and Knowledge Discovery. Proceedings, pages 68-77, 1997.

Bundy 97 Alan Bundy, editor. Artificial Intelligence Techniques. Springer Verlag, 1997.

Brand 98 Brand E., Gerritsen R. "Decision Trees", DBMS. - 1998. - № 7.

Buntine 92 W. Buntine. "A theory of classification rules". 1992

Craw 02 Susan Craw, Alun D. Preece (Eds.): Advances in Case-Based Reasoning, 6th European Conference, ECCBR 2002 Aberdeen, Scotland, UK, September 4-7, 2002, Proceedings. Lecture Notes in Computer Science 2416 Springer 2002, ISBN 3-540-44109-3 Contents BibTeX - ECCBR 2002 Home Page

Curet 96 O. Curet, J. Elliott, M. Jackson. "Designing knowledge discovery based systems in business, finance and accounting with a case-based approach: two case studies", IEEE Colloquium on Knowledge Discovery and Data Mining, 1996

Dingsøyr 98 Torgeir Dingsøyr "Integration of Data Mining and Case-Based Reasoning" http://www.idi.ntnu.no/~dingsoyr/diploma/

Fayyad 96 U. Fayyad, G. Piatetsky-Shapiro, P. Smyth. "From Data Mining to Knowledge Discovery: An Overview". In Advances in Knowledge Discovery and Data Mining (Eds. U.M.Fayyad, G.Piatetsky-Shapiro, P.Smyth), Cambridge, Mass: MIT Press, 1996, pp. 1-34.

Fuernkranz 96 Fuernkranz J. "Separate-and-Conquer Rule Learning". - Vienna: Austrian Research Institute for Artificial Intelligence, Technical Report OEFAI-TR-96-25, 1996.

Funk 04 Peter Funk, Pedro A.

González-Calero (Eds.): Advances in Case- Based Reasoning, 7th European Conference, ECCBR 2004, Madrid, Spain, August 30 - September 2, 2004, Proceedings. Lecture Notes in Computer Science 3155 Springer 2004, ISBN 3-540-22882-9 Contents BibTeX - ECCBR 2004 Home Page

Gruvaeus 72 Gruvaeus, G., & Wainer, H. "Two additions to hierarchical cluster analysis". The British Journal of Mathematical and Statistical Psychology, 25, 200-206, 1972.

Hammond 86 Hammond, K. "A model of case-based planning", in Proceedings of the Fifth National Conference on Artificial Intelligence, 65-95. Menlo Park, Calif.: American Associan for Artificial Intelligence. 1986.

Hammond 89 Hammond, K., ed. 1989. Proceedings of the DARPA Case-Based Reasoning Workshop. San Francisco, Calif.: Morgan Kaufmann.

Hartigan 75 Hartigan, J. A. "Clustering algorithms". New York: Wiley, 1975.

Hartigan 78 Hartigan, J. A. & Wong, M. A.. "Algorithm 136. A k-means clustering algorithm". Applied Statistics, 28, 100, 1978.

Haton 94 Jean Paul Haton, Mark T. Keane, Michel Manago (Eds.): Advances in Case-Based Reasoning, Second European Workshop, EWCBR-94, Chantilly, France, November 7-10, 1994, Selected Papers. Lecture Notes in Computer Science 984 Springer 1995, ISBN 3-540-60364-6

Heckerman 95 Heckerman D., Geiger D., Chickering D. "Learning Bayesian networks: The combination of knowledge and statistical data". Machine Learning. - 1995. - 20. - P. 197-243.

Heckerman 97 Heckerman D. "Bayesian Networks for Data Mining". Data Mining and Knowledge Discovery. - 1997. - № 1. - P. 79-119.

HTTP/1 http://is1.cemi.rssi.ru/ruswin/index.htm

HTTP/2 http://www.wizsoft.com

Johnson 67 Johnson, S. C. Hierarchical clustering schemes. Psychometrika, 32, 241-254, 1967.

Kitano 96 Hiroaki Kitano, Hideo Shimazu, and Akihiro Shibata. "Case-method: A methodology for building large-scale case-based systems". In Proceedings of the AAAI, pages 303-308, 1993.

Kolodner 83 Kolodner, J.L. "Maintaining Organization in a Dynamic Long-term memory". Cognitive Science, 7(4): 243-280, 1983.

Kolodner 88 Kolodner, J., ed. Proceedings of the DARPA Case- Based Reasoning Workshop. San Francisco, Calif.: Morgan Kaufmann. 1988.

Leake 96 David B. Leake. "Case-Based Reasoning - Experiences, Lessons and Future Directions". AAAI/MIT Press, 1996.

Murthy 97 S. Murthy. "Automatic construction of decision trees from data: A Multi-disciplinary survey", 1997.

Nguyen 93 Nguyen, T., Czerwinski, M., and Lee, D. (1993). "Compaq QUICKSOURCE: Providing the Consumer with the power of AI". AI Magazine, Fall 1993, pp. 50-60.

Parsaye 97 Parsaye K. "Rules are Much More than Decision Trees". The Journal of Data Warehousing. - 1997. - № 1.

Quinlan 87 Quinlan J. R. "Generating production rules from decision trees". In Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87). - Morgan Kaufmann, 1987. - P. 304-307.

Quinlan 93 Quinlan J. R. "C4.5: Programs for Machine Learning". Morgan Kaufmann Publishers, San Mateo, CA, 1993.

Rodriguez 97 Andres F. Rodriguez, Sunil Vadera, and L. Enrique Sucar. "A probabilistic model for case-based reasoning". In I Smith and B Faltings, editors, Case-Based Reasoning Research and Development, ICCBR-97. Proceedings, pages 623-632, 1997.

Schank 82 Schank, R. (Ed.) (1982). "Dynamic Memory: A Theory of Learning in Computers and People". New York: Cambridge University Press.

Simpson 85 Simpson, R.L. (1985). "A computer model of case-based reasoning in problem solving: An investigation in the domain of dispute mediation". Ph.D. thesis, School of Information and Computer Science, Georgia Institute of Technology.

Smith 96 Ian F. C. Smith, Boi Faltings (Eds.): Advances in Case-Based Reasoning, Third European Workshop, EWCBR-96, Lausanne, Switzerland, November 14-16, 1996, Proceedings. Lecture Notes in Computer Science 1168 Springer 1996, ISBN 3-540-61955-0

Smyth 95 B. Smyth, M. T. Keane. "Remembering to Forget: A Competence- Preserving Case Deletion Policy for Case-Based Reasoning Systems", in Proc. of IJCAI-95, pp 337 - 382, 1995.

Smyth 98 Barry Smyth, Padraig Cunningham (Eds.): Advances in Case-Based Reasoning, 4th European Workshop, EWCBR-98, Dublin, Ireland, September 1998, Proceedings. Lecture Notes in Computer Science 1488 Springer 1998, ISBN 3-540-64990-5 Contents BibTeX

Tirri 96 Henry Tirri, Perti Kontkanen, and Petri Myllymäksi. "A bayesian framework for case-based reasoning". In I Smith and B Faltings, editors, Advances in Case-Based Reasoning, EWCBR-96, pages 413-427, 1996.

UKCBR 04 http://www.bcs-sgai.org/ai2004/

UKCBR 05 http://www.bcs-sgai.org/ai2005/

Wang 99 Wang, H., Dubitzky, W., Dьntsch, I., Bell, D.A., "A Lattice Machine Approach to Automated Case Base Design: Marrying Lazy and Eager Learning". Proc. 17th Int. Joint Conference on Artificial Intelligence (IJCAI-99), Sweden, 1999.

Wess 93 Stefan Wess, Klaus-Dieter Althoff, Michael M. Richter (Eds.): Topics in Case-Based Reasoning, First European Workshop, EWCBR-93, Kaiserslautern, Germany, November 1-5, 1993, Selected Papers. Lecture Notes in Computer Science 837 Springer 1994, ISBN 3-540-58330-0

Wettschereck Wettschereck D., Aha D. W., Mohri T. "A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms". Artificial Intelligence Review. - 11. - pp. 273-314.

Айвазян 89 Айвазян С. А., Бухштабер В. М., Юнюков И. С., Мешалкин Л. Д. "Прикладная статистика: Классификация и снижение размерности". М.: Финансы и статистика, 1989.

Гупал 93 Гупал А. М., Пономарев А. А., Цветков А. М. "Об одном методе индуктивного вывода с подрезанием деревьев решений". Кибернетика и системный анализ. - 1993. - № 5. - С. 174-178.

Дюк 94 Дюк В. А. "Компьютерная психодиагностика".- СПб: "Братство", 1994.

Дюк 96 Дюк В. А. "Формирование знаний в системах искусственного интеллекта: геометрический подход".Вестник Академии Технического Творчества. - СПб, 1996, №2. - с.46-67.

Дюк 01 Дюк В. А., Самойленко А. П. "Data Mining: учебный курс" – СПб: "Питер", 2001. – 368 с.

Каменнова 95 М.С. Каменнова. "Корпоративные информационные системы: технологии и решения". Системы Управления Базами Данных № 3/1995 стр. 88-99.

Киселев 97 М. Киселев, Е. Соломатин. "Средства добычи знаний в бизнесе и финансах". - Открытые системы, № 4, 1997, с.41-44.

Уоссермен 92 Уоссермен. Ф. "Нейрокомпьютерная техника: Теория и практика". - М.: Мир, 1992. - 240 с.

Цветков 93 Цветков А. М. "Разработка алгоритмов индуктивного вывода с использованием деревьев решений". Кибернетика и системный анализ. - 1993. - № 1. - С. 174-178.