Wyniki wyszukiwania - Biblioteka Nauki

1

Using Non-Zero Dimensions for the Cosine and Tanimoto Similarity Search Among Real Valued Vectors

100%

Kryszkiewicz M.

Fundamenta Informaticae

|

2013

|

tom Vol. 127, nr 1-4

307--323

EN

The cosine and Tanimoto similarity measures are typically applied in the area of chemical informatics, bio-informatics, information retrieval, text and web mining as well as in very large databases for searching sufficiently similar vectors. In the case of large sparse high dimensional data sets such as text or Web data sets, one typically applies inverted indices for identification of candidates for sufficiently similar vectors to a given vector. In this article, we offer new theoretical results on how the knowledge about non-zero dimensions of real valued vectors can be used to reduce the number of candidates for vectors sufficiently cosine and Tanimoto similar to a given one. We illustrate and discuss the usefulness of our findings on a sample collection of documents represented by a set of a few thousand real valued vectors with more than ten thousand dimensions.

2

Concise representations of frequent patterns and association rules

100%

Kryszkiewicz M.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2002

|

tom z. 142

5-207

EN

The monograph is devoted to the concise representations of basic types of knowledge mined from large data sets; that is the representations of frequent patterns and association rules. The objective is a scientific contribution to the data mining and knowledge discovery area by offering new methods of reasoning about knowledge. The amount of knowledge discovered from large databases or data warehouses is often huge and beyond human capabilities to analyze it. It is indispensable to apply mechanisms and methods that allow presentation of all important knowledge in a brief way. In the monograph, we present our original solutions against those others available in the data mining literature. The comparative theoretical analysis of the concise representations of frequent patterns and association rules that we provide is not only in-depth, but also the only one offered thus far. Algorithms for transitioning among representations are offered. We prove, on a theoretical and experimental basis, that two out of three representations of frequent patterns that we have offered, are winners (namely, the disjunction-free generators representation and its generalized version). The two representations of frequent patterns outperform the third representation we have introduced (namely, the generators representation) and the closed itemsets representation even by two orders of magnitude both in the number of representations' elements and representations' extraction time. In the case of highly correlated data sets; the two representations are even by four orders of magnitude less numerous than the set of all frequent patterns derivable from the data. In addition, the representations of frequent patterns we have offered are lossless in that they allow on-demand derivation of all frequent patterns. On the other hand, the generators representation, although more numerous, is very useful for the efficient discovery of representations of association rules. Representative rules, we proposed, were the first sound and lossless representation of strong association rules. In recent years, a few other proposals of rules' representations have been offered. The rules' representations are thoroughly examined in the monograph whether they are lossless, sound and informative. Ways of correcting invalid representations are discussed. In the monograph, we propose a formal framework for deriving patterns and association rules not only from data sets, but also from a provided sample of knowledge. This "mining around knowledge" is unique in the literature. We show that one may derive certain knowledge from pieces of uncertain knowledge. This aspect is of high importance for avoiding insecure, unintended access to secret knowledge. Concise representation of known fraction of knowledge and/or the knowledge derived without accessing a data set is offered. Finally, we address the problem of reasoning about knowledge in the context of incompleteness. Pessimistic and optimistic bounds on uncertainty caused by occurrence of missing values in mined data sets are derived. A notion of a legitimate approach to incompleteness is defined in such a way that it guarantees deriving only such knowledge which is consistent with some possible complete instance of the originally incomplete data set. An example of a legitimate approach is provided. A number of examples of popular approaches to incompleteness have been overviewed and analyzed. We have proved that. although simple and popular, these approaches are not legitimate and should not be applied. Concise representations of association rules discovered from incomplete databases are proposed.

PL

Problematyka, której poświęcona jest monografia, wywodzi się z nurtu badań związanych z odkrywaniem wiedzy z dużych zasobów informacyjnych - dziedziny bardzo intensywnie rozwijanej w ostatnim dziesięcioleciu. Dotychczasowe kierunki badań dotyczyły przede wszystkim opracowywania nowych metod eksploracji danych. Odniesiono niekwestionowane sukcesy w tym zakresie. Nowe algorytmy okazały się efektywne i skalowalne. Eksploracja olbrzymich zasobów danych stała się możliwa. Ujawnił się jednak kolejny problem, jakim jest olbrzymia liczba uzyskiwanych wyników, spośród których tylko mała część ma znaczenie dla potencjalnego użytkownika, podczas gdy ogrom pozostałej części uniemożliwia efektywną analizę odkrytej wiedzy i jej zastosowanie. W celu rozwiązania tego problemu, niezbędne stało się prowadzenie prac nad jakością, użytecznością i reprezentatywnością odkrywanej wiedzy. Jednym z kierunków badań, których celem jest ograniczenie liczby uzyskiwanych wyników do wiedzy uprzednio nieznanej, znaczącej i przydatnej, jest opracowywanie miar statystycznych określających jakość odkrywanej wiedzy. Inny kierunek badań, poświęcony ograniczaniu odkrywanej wiedzy do żądanej, podejmuje zagadnienia opracowywania wygodnych szablonów i/lub języków specyfikacji wiedzy oraz efektywnej implementacji zapytań wyrażanych z ich wykorzystaniem. Pierwsze podejście wywodzi się ze sztucznej inteligencji; natomiast drugie ma swój rodowód w technologii systemów baz danych. W ostatnich kilku latach pojawiło się jeszcze jedno podejście do problemu ograniczania liczby uzyskiwanych wyników, które adresuje zagadnienia bezpośredniego wyznaczania bezstratnych i możliwie najzwięźlejszych reprezentacji wiedzy ukrytej w danych oraz zagadnienia wyprowadzania wiedzy z otrzymanych reprezentacji. Na tym podejściu do odkrywania wiedzy koncentruje się autorka. Monografia poświęcona jest problematyce odkrywania bezstratnych reprezentacji wiedzy w postaci wzorców częstych i reguł asocjacyjnych zarówno z kompletnych, jak i niepełnych zasobów danych oraz mechanizmom wyprowadzania wiedzy z reprezentacji i/lub danej wiedzy częściowej. W pracy podjęto 4 zasadnicze zagadnienia: 1. Zwięzłe reprezentacje wzorców częstych. 2. Zwięzłe reprezentacje reguł asocjacyjnych. 3. Wnioskowanie z fragmentów wiedzy bez dostępu do danych. 4. Uprawnione podejścia do odkrywania wiedzy z danych niepełnych. Celem pracy było wniesienie wkładu naukowego w dziedzinę eksploracji danych i odkrywania wiedzy poprzez przedstawienie autorskich bezstratnych modeli reprezentacji wiedzy i metod wnioskowania o wiedzy na tle innych rozwiązań. Monografia zawiera pierwszą wnikliwą analizę teoretyczną wszystkich modeli reprezentacji wzorców częstych i reguł asocjacyjnych. Trzy spośród przedstawionych modeli reprezentacji wzorców częstych są autorskie, a mianowicie: reprezentacja generatorowa, reprezentacja oparta na generatorach wolnych od dysjunkcji oraz uogólniona reprezentacja oparta na generatorach wolnych od dysjunkcji. Reguły reprezentatywne są autorską propozycją modelu reprezentacji reguł asocjacyjnych. Zaproponowano algorytmy do wyszukiwania wszystkich autorskich reprezentacji zbiorów częstych i reguł asocjacyjnych. Zaoferowano także komplet algorytmów do przekształcania autorskich reprezentacji wzorców częstych w pozostałe bezstratne reprezentacje wzorców częstych bez odwoływania się do bazy danych. Z przeprowadzonej analizy porównawczej wynika, że najzwięźlej- szą spośród reprezentacji wzorców częstych z tzw. granicami jest uogólniona reprezentacja oparta na generatorach wolnych od dysjunkcji. Wyprowadzone są szczegółowe zależności pomiędzy wszystkimi reprezentacjami wzorców częstych. Wyniki eksperymentalne stanowią nie tylko potwierdzenie uzyskanych wyników teoretycznych, ale w praktyce dowodzą, że uogólniona reprezentacja oparta na generatorach wolnych od dysjunkcji jest najzwięźlejszą ze wszystkich dotychczas zaproponowanych modeli reprezentacji zbiorów częstych. Dla silnie skorelowanych zbiorów danych zaobserwowano, że uogólniona reprezentacja oparta na generatorach wolnych od dysjunkcji jest nawet o 2 rzędy wielkości bardziej zwięzła niż reprezentacja generatorowa i reprezentacja oparta na zamkniętych zbiorach częstych oraz o 4 rzędy wielkości bardziej zwięzła niż zbiór wszystkich wzorców częstych. Eksperymenty dowodzą także, że czas generacji reprezentacji wzorców częstych korzystających z granic zależy liniowo od liczności reprezentacji. W rezultacie, uogólniona reprezentacja oparta na generatorach wolnych od dysjunkcji jest wyszukiwania z silnie skorelowanych zbiorów danych nawet około 10 do2 razy szybciej niż reprezentacja generatorowa i reprezentacja oparta na zbiorach częstych oraz 10 do4 razy szybciej niż wszystkie wzorce częste. Pomimo, że reprezentacja generatorowa jest liczniejsza niż dwie pozostałe autorskie reprezentacje wzorców częstych, to jednak jest bardzo użyteczna przy wyznaczaniu reprezentacji regułowych. Otóż, ciekawą cechą większości reprezentacji regułowych jest to, że są zbudowane wyłącznie z elementów reprezentacji generatorowej i/lub reprezentacji opartej na zamkniętych zbiorach częstych. Poza tym, wzorce występujące w reprezentacji generatorowej są powszechnie wykorzystywane do wyznaczania reprezentacji opartej na zamkniętych zbiorach częstych. A zatem, efektywne wyszukiwanie reprezentacji generatorowej jest istotnym zagadnieniem. W monografii zaproponowano dwuetapowy proces odkrywania tej reprezentacji: zasugerowano, aby najpierw ekstrahować z zasobów danych (uogólnioną) reprezentację opartą na generatorach wolnych od dysjunkcji, a następnie uzyskaną pośrednią reprezentację przekształcać w reprezentację generatorową. Przeprowadzone eksperymenty pokazują, że taki dwuetapowy proces wyszukiwania reprezentacji generatorowej jest wielokrotnie szybszy niż jej bezpośrednie wyznaczanie z zasobów danych. Reguły reprezentatywne są pierwszą bezstratną reprezentacją regułową, którą zaproponowano w dziedzinie eksploracji danych. W ostatnich latach zaproponowano także szereg innych reprezentacji regułowych. Zaproponowane reprezentacje regułowe są w większości bezstratne, to znaczy pozwalają wyprowadzić każdą silną regułę asocjacyjną. W pracy szczegółowo przebadano także często zaniedbywane, aczkolwiek bardzo ważne, zagadnienie związane z użytecznością reprezentacji regułowych. Mianowicie sprawdzono czy reprezentacje są poprawne (tzn. czy wyprowadzają tylko silne reguły) oraz czy są informacyjne (tzn. czy umożliwiają prawidłowe określenie wartości wsparcia i zaufania wyprowadzanych reguł). Dowiedziono, że szereg reprezentacji regułowych nie spełnia tych warunków. Dla tych przypadków zaproponowano metody korygujące. W pracy zaproponowano także efektywną metodykę wyprowadzania wzorców i reguł asocjacyjnych z fragmentów wiedzy bez dostępu do danych. Metodologia ta oparta jest na założeniu, że fragmentaryczna wiedza powinna być zamieniana na informację pierwotną, czyli na informację o wsparciach zbiorów, z których zbudowane są reguły. Następnie za pomocą zaoferowanych operatorów rozszerzania i kurczenia zbiorów o znanych wsparciach, konstruuje się nowe zbiory, których wsparcia można precyzyjnie wyznaczyć. W chwili gdy nie ma możliwości wyprowadzenia nowych zbiorów poprzez rozszerzanie lub kurczenie, dodaje się informacje o zbiorach ograniczonych przez oryginalne lub wyprowadzone dotychczas zbiory. Tym razem operacja może być obarczona błędem, dlatego autorka wprowadza sposób określania szacowania wsparcia pesymistycznego i optymistycznego. Rozszerzony zbiór wzorców może posłużyć do wyprowadzenia znacznie większego zbioru reguł niż początkowo dany. W monografii zaoferowano także zwięzłe reprezentacje dla danej części zbiorów (są to zaadaptowane wersje generatorów i zbiorów zamkniętych), jak i reguł (czyli reguły maksymalnie pokrywające jako adaptacja reguł reprezentatywnych). Zaproponowano także algorytm przechodzenia z reprezentacji danego fragmentu zbiorów do reprezentacji wszystkich reguł, które można z niego wyprowadzić. Ostatnim zagadnieniem poruszonym w pracy jest problem odkrywania reguł ze zbiorów danych, w których mogą występować atrybuty o nieznanych wartościach. Autorka wyprowadziła formuły określające pesymistyczne i optymistyczne wartości wsparcia i zaufania dla reguł wyznaczanych z niepełnych danych. Formuły ograniczające niepewność wykorzystano dalej do sformułowania postulatów, które powinny być spełnione przez każde uprawnione podejście do odkrywania reguł z niepełnych danych. Zaprezentowano przykładowe uprawnione probabilistyczne podejście do niepełności, jak również przedyskutowano kilka popularnych rozwiązań, które okazują się nie być uprawnione. Na koniec zaproponowano kilka typów reguł asocjacyjnych adresujących aspekty niepewności wynikającej z niepełności danych oraz zaproponowano odpowiadające im typy uogólnionych reguł reprezentatywnych oraz uogólnionych reguł o minimalnych poprzednikach i maksymalnych następnikach.

3

ACBC-Adequate Association and Decision Rules Versus Key Generators and Rough Sets Approximations

100%

Kryszkiewicz M.

Fundamenta Informaticae

|

2016

|

tom Vol. 148, nr 1/2

65--85

EN

In this paper, we propose an ACBC-evaluation formula, which delivers a flexible way of formulating different kinds of criteria for association and decision rules. We prove that rules with minimal antecedents that fulfill ACBC-evaluation formulae are key generators, which are patterns of a special type. We also show that a number of types of rough set approximations of decision classes can be expressed based on ACBC-evaluation formulae. We prove that decision rules preserving respective approximations of decision classes are rules that satisfy an ACBC-evaluation formula and that antecedents of such optimal decision rules are key generators, too. A number of properties related to particular measures of association rules and key generators are derived.