Determining an estimate of an equivalence relation for moderate and large sized sets

• Autorzy: Klukowski L.

Identyfikatory

DOI

10.5277/ord170203

• Języki publikacji: EN

Abstrakty

EN

This paper presents two approaches to determining estimates of an equivalence relation on the basis of pairwise comparisons with random errors. Obtaining such an estimate requires the solution of a discrete programming problem which minimizes the sum of the differences between the form of the relation and the comparisons. The problem is NP hard and can be solved with the use of exact algorithms for sets of moderate size, i.e. about 50 elements. In the case of larger sets, i.e. at least 200 comparisons for each element, it is necessary to apply heuristic algorithms. The paper presents results (a statistical preprocessing), which enable us to determine the optimal or a near-optimal solution with acceptable computational cost. They include: the development of a statistical procedure producing comparisons with low probabilities of errors and a heuristic algorithm based on such comparisons. The proposed approach guarantees the applicability of such estimators for any size of set.

Słowa kluczowe

EN

estimation; equivalence relation; pairwise comparisons; random errors; nearest adjoining order

PL

oszacowanie; relacja równoważności; błędy losowe; najbliższe sąsiedztwo

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2017
• Tom: Vol. 27, No. 2
• Strony: 45--58
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Klukowski L.

• Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447 Warsaw, Poland

Bibliografia

• [1] CHOPRA R., RAO M.R., The partition problem, Math. Progr., 1993, 59, 87–115.
• [2] DAVID H.A., The Method of Paired Comparisons, 2nd Ed., Griffin, London 1988.
• [3] GORDON A.D., Classification, 2nd Ed., Chapman and Hall CRC, 1999.
• [4] HANSEN P., JAUMARD B., Cluster analysis and mathematical programming, Math. Progr., 1997, 79, 191–215.
• [5] HANSEN P., JAUMARD B., SANLAVILLE E., Partitioning Problems in Cluster Analysis. A Review of Mathematical Programming Approaches. Studies in Classification, Data Analysis and Knowledge Organization, Springer-Verlag, 1994.
• [6] HOEFFDING W., Probability inequalities for sums of bounded random variables, J. Am. Stat. As., 1963, 58, 13–30.
• [7] KLUKOWSKI L., Some probabilistic properties of the nearest adjoining order method and its extensions, Ann. Oper. Res., 1994, 51, 241–261.
• [8] KLUKOWSKI L., The nearest adjoining order method for pairwise comparisons in the form of difference of ranks, Ann. Oper. Res., 2000, 97, 357–378.
• [9] KLUKOWSKI L., Methods of estimation of relations of: equivalence, tolerance, and preference in a finite set, IBS PAN, Ser. Systems Research, Vol. 69, Warsaw 2011.
• [10] KLUKOWSKI L., Estimators of the relations of equivalence, tolerance and preference based on pairwise comparisons with random errors, Oper. Res. Dec., 2012, 22, 15–34.
• [11] RAO M.R., Cluster analysis and mathematical programming, J. Am. Stat. As., 1971, 66, 622–626.
• [12] SLATER P., Inconsistencies in a schedule of paired comparisons, Biometrika, 1961, 48, 303–312.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).